fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <ctime>
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <unistd.h>
  11. using namespace std;
  12. typedef pair<int, int> pii;
  13. typedef vector<pii> vi;
  14. typedef vector<vi> vii;
  15. typedef pair<double, int> P;
  16.  
  17. // func and term
  18. enum {IF_FOOD_AHEAD, PROG2, PROG3, RIGHT, LEFT, MOVE};
  19. // vector
  20. enum {U, R, D, L};
  21. // gen mode
  22. enum {FULL, GROW};
  23. // variants
  24. int n, e, cnt, foods[55][55], FOODS[55][55], ant[55][55], nx, ny, nz, tmp;
  25. string mp[55], MP[55];
  26. vii node;
  27. //int runcnt;
  28.  
  29. class Tree {
  30. public:
  31.   int antx, anty;
  32.   int Energy, food;
  33.   int vec;
  34.   //  int szs;
  35.   bool isans;
  36.   int adr, nid;
  37.   double badrate;
  38.   Tree(bool in, int id) {
  39. 	antx = anty = 0;
  40. 	Energy = e;
  41. 	food = 0;
  42. 	vec = R;
  43. 	isans = in;
  44. 	badrate = 0.0;
  45. 	adr = 0;
  46. 	nid=id;
  47. 	//	szs = node[nid].size();
  48.   }
  49.   void run() {
  50. 	//	runcnt++;
  51. 	//	printf("%d\n",runcnt);
  52. 	if (adr >= node[nid].size()) return;
  53. 	if (Energy == 0) return;
  54. 	switch (node[nid][adr].first) {
  55. 	case IF_FOOD_AHEAD:
  56. 	  if_Food_Ahead();
  57. 	  break;
  58. 	case PROG2:
  59. 	  Prog2();
  60. 	  break;
  61. 	case PROG3:
  62. 	  Prog3();
  63. 	  break;
  64. 	case RIGHT:
  65. 	case LEFT:
  66. 	  change_vec();
  67. 	  break;
  68. 	case MOVE:
  69. 	  move();
  70. 	  break;
  71. 	}
  72.   }
  73.   void if_Food_Ahead() {
  74. 	nx=antx;
  75. 	ny=anty;
  76. 	if (vec == U) ny--;
  77. 	else if (vec == R) nx++;
  78. 	else if (vec == D) ny++;
  79. 	else nx--;
  80. 	if (nx<0||nx>=n||ny<0||ny>=n||!foods[ny][nx]) {
  81. 	  adr++;
  82. 	  trav();
  83. 	  run();
  84. 	} else {
  85. 	  adr++;
  86. 	  if (node[nid][adr].first==MOVE) badrate+=0.5;
  87. 	  tmp = node[nid][adr].second;
  88. 	  run();
  89. 	  adr = tmp;
  90. 	}
  91.   }
  92.   void Prog2() {
  93. 	adr++;
  94. 	tmp = node[nid][adr].second;
  95. 	nx=node[nid][adr].first;
  96. 	run();
  97. 	ny=node[nid][adr].first;
  98. 	run();
  99. 	tmp = adr;
  100. 	//	printf("%d %d\n",nx,ny);
  101. 	if ((nx==RIGHT&&ny==LEFT) || (ny==RIGHT&&nx==LEFT)) badrate+=1.0;
  102.   }
  103.   void Prog3() {
  104. 	adr++;
  105. 	nx=node[nid][adr].first;
  106. 	run();
  107. 	ny=node[nid][adr].first;
  108. 	run();
  109. 	nz=node[nid][adr].first;
  110. 	run();
  111. 	if ((nx==RIGHT&&ny==LEFT)||(ny==RIGHT&&nx==LEFT)) badrate+=1.0;
  112. 	if ((ny==RIGHT&&nz==LEFT)||(nz==RIGHT&&ny==LEFT)) badrate+=1.0;
  113.   }
  114.   void change_vec() {
  115. 	Energy--;
  116. 	if (node[nid][adr].first == RIGHT) vec = (vec + 1) % 4;
  117. 	else vec = (vec + 3) % 4;
  118. 	adr++;
  119. 	if (isans) {
  120. 	  puts("");
  121. 	  for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
  122. 		  if (i == anty && j == antx) {
  123. 			if (vec == 0) printf("^");
  124. 			else if (vec == 1) printf(">");
  125. 			else if (vec == 2) printf("v");
  126. 			else printf("<");
  127. 		  } else {
  128. 			printf("%c",mp[i][j]);
  129. 		  }
  130. 		  if (j == n - 1) puts("");
  131. 		}
  132. 	  puts("");
  133. 	  usleep(1000*500);
  134. 	}
  135.   }
  136.   void move() {
  137. 	Energy--;
  138. 	nx = antx;
  139. 	ny = anty;
  140. 	if (vec == U) ny--;
  141. 	else if (vec == R) nx++;
  142. 	else if (vec == D) ny++;
  143. 	else nx--;
  144. 	if (nx<0||ny>=n||ny<0||ny>=n) badrate+=1.0;
  145. 	else {
  146. 	  antx=nx; anty=ny;
  147. 	  if (ant[anty][antx]) badrate += 0.5;
  148. 	  if (foods[anty][antx]) {
  149. 		food++;
  150. 		mp[anty][antx] = '.';
  151. 		foods[anty][antx] = 0;
  152. 	  }
  153. 	  ant[anty][antx] = 1;
  154. 	}
  155. 	adr++;
  156. 	if (isans) {
  157. 	  puts("");
  158. 	  for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
  159. 		  if (i == anty && j == antx) {
  160. 			if (vec == 0) printf("^");
  161. 			else if (vec == 1) printf(">");
  162. 			else if (vec == 2) printf("v");
  163. 			else printf("<");
  164. 		  } else {
  165. 			printf("%c",mp[i][j]);
  166. 		  }
  167. 		  if (j == n - 1) puts("");
  168. 		}
  169. 	  puts("");
  170. 	  usleep(1000*500);
  171. 	}
  172.   }
  173.   void trav() {
  174. 	if (adr >= node[nid].size()) return;
  175. 	switch (node[nid][adr].first) {
  176. 	case IF_FOOD_AHEAD:
  177. 	case PROG2:
  178. 	  adr++;
  179. 	  trav(); trav();
  180. 	  break;
  181. 	case PROG3:
  182. 	  adr++;
  183. 	  trav(); trav(); trav();
  184. 	  break;
  185. 	case RIGHT:
  186. 	case LEFT:
  187. 	case MOVE:
  188. 	  adr++;
  189. 	  break;
  190. 	}
  191.   }
  192. };
  193. ///////////////////////////////////////////////////////////////
  194. int pa;
  195. void printnode(int nid) {
  196.   if (node[nid][pa].first==IF_FOOD_AHEAD) {
  197. 	pa++;
  198. 	printf("f(");
  199. 	printnode(nid);
  200. 	printf(",");
  201. 	printnode(nid);
  202. 	printf(")");
  203.   } else if (node[nid][pa].first==PROG2) {
  204. 	pa++;
  205. 	printnode(nid);
  206. 	printnode(nid);
  207.   } else if (node[nid][pa].first==PROG3) {
  208. 	pa++;
  209. 	printnode(nid);
  210. 	printnode(nid);
  211. 	printnode(nid);
  212.   } else if (node[nid][pa].first==RIGHT) {
  213. 	pa++;
  214. 	printf("r");
  215.   } else if (node[nid][pa].first==LEFT) {
  216. 	pa++;
  217. 	printf("l");
  218.   } else {
  219. 	pa++;
  220. 	printf("m");
  221.   }
  222. }
  223. void mapinit() {
  224.   for (int i=0; i<n; i++) {
  225. 	mp[i] = MP[i];
  226. 	for (int j=0; j<n; j++) {
  227. 	  foods[i][j] = FOODS[i][j];
  228. 	  ant[i][j] = 0;
  229. 	}
  230.   }
  231.   ant[0][0] = 1;
  232. }
  233. int getsize(int nid) {
  234.   return node[nid].size();
  235. }
  236. double evalution(int nid) {
  237.   Tree tree(false, nid);
  238.   mapinit();
  239.   tree.run();
  240.   return (double)tree.food*100-tree.badrate-(double)getsize(nid)/100.0;
  241. }
  242. int calcfood(int nid) {
  243.   Tree tree(false, nid);
  244.   mapinit();
  245.   tree.run();
  246.   return tree.food;
  247. }
  248.  
  249. // generate random node
  250. int ga;
  251. void gen_rnd_node(int nid, int depth, int max_d, int method) {
  252.   double r = (double)(rand() % 10 + 1) / 10.0;
  253.   if (max_d == depth || (depth > 1 && method == GROW && r < 0.5)) {
  254. 	int rc = rand() % 3 + 3;
  255. 	node[nid].push_back(make_pair(rc,0));
  256. 	node[nid][node[nid].size()-1].second=node[nid].size();
  257.   } else {
  258. 	int rc = rand() % 3;
  259. 	node[nid].push_back(make_pair(rc,0));
  260. 	ga=node[nid].size()-1;
  261. 	gen_rnd_node(nid,depth+1,max_d,method);
  262. 	gen_rnd_node(nid,depth+1,max_d,method);
  263. 	if (rc==PROG3) gen_rnd_node(nid,depth+1,max_d,method);
  264. 	node[nid][ga].second=node[nid].size();
  265.   }
  266. }
  267.  
  268. class Func {
  269. public:
  270.   // crossover
  271.   int crosscnt, crossadr[2];
  272.   vector<bool> cr1, cr2;
  273.   int c1, c2, c3, c4;
  274.   void find_same(int nid1, int nid2) {
  275. 	if (crossadr[0]<getsize(nid1)||crossadr[1]<getsize(nid2)) return;
  276. 	crosscnt++;
  277. 	cr1[crossadr[0]] = cr2[crossadr[1]] = true;
  278. 	if (node[nid1][crossadr[0]].first<=PROG2&&
  279. 		node[nid2][crossadr[1]].first<=PROG2) {
  280. 	  crossadr[0]++; crossadr[1]++;
  281. 	  find_same(nid1,nid2);
  282. 	  find_same(nid1,nid2);
  283. 	} else if (node[nid1][crossadr[0]].first==PROG3&&
  284. 			   node[nid2][crossadr[1]].first==PROG3) {
  285. 	  crossadr[0]++; crossadr[1]++;
  286. 	  find_same(nid1,nid2);
  287. 	  find_same(nid1,nid2);
  288. 	  find_same(nid1,nid2);
  289. 	} else {
  290. 	  tmp = node[nid1][crossadr[0]].second;
  291. 	  crossadr[0] = tmp;
  292. 	  tmp = node[nid2][crossadr[1]].second;
  293. 	  crossadr[1] = tmp;
  294. 	}
  295.   }
  296.   void unite_pos(int nid1, int nid2, int r) {
  297. 	if (crosscnt==r) {
  298. 	  c1=crossadr[0];
  299. 	  c3=node[nid1][c1].second;
  300. 	  c2=crossadr[1];
  301. 	  c4=node[nid2][c2].second;
  302. 	  return;
  303. 	}
  304. 	crosscnt++;
  305. 	if (node[nid1][crossadr[0]].first<=PROG2&&
  306. 		node[nid2][crossadr[1]].first<=PROG2) {
  307. 	  crossadr[0]++; crossadr[1]++;
  308. 	  unite_pos(nid1,nid2,r);
  309. 	  unite_pos(nid1,nid2,r);
  310. 	} else if (node[nid1][crossadr[0]].first==PROG3&&
  311. 			   node[nid2][crossadr[1]].first==PROG3) {
  312. 	  crossadr[0]++; crossadr[1]++;
  313. 	  unite_pos(nid1,nid2,r);
  314. 	  unite_pos(nid1,nid2,r);
  315. 	  unite_pos(nid1,nid2,r);
  316. 	} else {
  317. 	  tmp = node[nid1][crossadr[0]].second;
  318. 	  crossadr[0]=tmp;
  319. 	  tmp=node[nid2][crossadr[1]].second;
  320. 	  crossadr[1]=tmp;
  321. 	}
  322.   }
  323.   void crossover(int nid1, int nid2, int cid1, int cid2) {
  324. 	crosscnt = 0;
  325. 	cr1.resize(node[nid1].size(), false);
  326. 	cr2.resize(node[nid2].size(), false);
  327. 	crossadr[0]=crossadr[1]=0;
  328. 	find_same(nid1, nid2);
  329. 	if (crosscnt > 1) {
  330. 	  // puts("find same");
  331. 	  crossadr[0] = crossadr[1] = 0;
  332. 	  int r = rand() % (crosscnt-1) + 1;
  333. 	  crosscnt = 0;
  334. 	  unite_pos(nid1, nid2, r);
  335. 	  copy(node[nid1].begin(), node[nid1].begin()+c1, back_inserter(node[cid1]));
  336. 	  copy(node[nid2].begin(), node[nid2].begin()+c2, back_inserter(node[cid2]));
  337. 	  copy(node[nid1].begin()+c1, node[nid1].begin()+c3, back_inserter(node[cid2]));
  338. 	  copy(node[nid2].begin()+c2, node[nid2].begin()+c4, back_inserter(node[cid1]));
  339. 	  copy(node[nid1].begin()+c3, node[nid1].end(), back_inserter(node[cid1]));
  340. 	  copy(node[nid2].begin()+c4, node[nid2].end(), back_inserter(node[cid2]));
  341. 	} else if (crosscnt == 1) {
  342. 	  // puts("find same");
  343. 	  crosscnt=0;
  344. 	  crossadr[0] = crossadr[1] = 0;
  345. 	  unite_pos(nid1, nid2, 1);
  346. 	  copy(node[nid1].begin(), node[nid1].begin()+c1, back_inserter(node[cid1]));
  347. 	  copy(node[nid2].begin(), node[nid2].begin()+c2, back_inserter(node[cid2]));
  348. 	  copy(node[nid1].begin()+c1, node[nid1].begin()+c3, back_inserter(node[cid2]));
  349. 	  copy(node[nid2].begin()+c2, node[nid2].begin()+c4, back_inserter(node[cid1]));
  350. 	  copy(node[nid1].begin()+c3, node[nid1].end(), back_inserter(node[cid1]));
  351. 	  copy(node[nid2].begin()+c4, node[nid2].end(), back_inserter(node[cid2]));;
  352. 	}
  353.   }
  354.  
  355.   // mutation
  356.   int mutcnt;
  357.   void mutrun(int togen, int fromgen, int depth, int r) {
  358. 	if (mutcnt == r) {
  359. 	  gen_rnd_node(togen, depth+1, 20, GROW);
  360. 	  tmp = node[fromgen][mutcnt].second;
  361. 	  mutcnt = tmp;
  362. 	}
  363. 	if (mutcnt >= getsize(fromgen)) return;
  364. 	node[togen].push_back(node[fromgen][mutcnt]);
  365. 	int flag = node[fromgen][mutcnt].first;
  366. 	mutcnt++;
  367. 	if (flag<=PROG3) {
  368. 	  mutrun(togen, fromgen, depth+1, r);
  369. 	  mutrun(togen, fromgen, depth+1, r);
  370. 	  if (flag==PROG3) mutrun(togen,fromgen,depth+1,r);
  371. 	} 
  372.   }
  373.   void mutation(int ngen, int rgen) {
  374. 	int sz = getsize(rgen);
  375. 	if (sz!=0) {
  376. 	  int r = rand() % sz;
  377. 	  while (r == 0) r = rand() % sz;
  378. 	  mutcnt = 0;
  379. 	  // printf("%d\n",sz);
  380. 	  mutrun(ngen, rgen, 0, r);
  381. 	}
  382.   }
  383. };
  384.  
  385. // generation
  386. static int SZ=100, GENE=1000, TSZ=2;
  387. vector<P> dn;
  388. Func func;
  389.  
  390. void initialisation() {
  391.   node.resize(SZ*2, vi(0));
  392.   for (int i=0; i<SZ; i++) {
  393. 	gen_rnd_node(i,0,5,FULL);
  394.   }
  395. }
  396. int tournament() {
  397.   set<int> st;
  398.   while (st.size() < TSZ) {
  399. 	int r = rand() % SZ;
  400. 	st.insert(r);
  401.   }
  402.   set<int>::iterator it;
  403.   vector<P> dnx;
  404.   for (it=st.begin(); it!=st.end(); it++) {
  405. 	dnx.push_back(P(evalution((*it)), (*it)));
  406.   }
  407.   sort(dnx.begin(), dnx.end());
  408.   return dnx[TSZ-1].second;
  409. }
  410. void run_cross(int ngen) {
  411.   int r1 = tournament();
  412.   int r2 = tournament();
  413.   if (ngen+1>=node.size()) node.push_back(vi(0));
  414.   if (ngen+2>=node.size()) node.push_back(vi(0));
  415.   func.crossover(r1,r2,ngen+1,ngen+2);
  416.   int e1 = evalution(ngen+1);
  417.   int e2 = evalution(ngen+2);
  418.   if (e1 > e2) {
  419. 	copy(node[ngen+1].begin(), node[ngen+1].end(), back_inserter(node[ngen]));
  420.   } else {
  421. 	copy(node[ngen+2].begin(), node[ngen+2].end(), back_inserter(node[ngen]));
  422.   }
  423.   node[ngen+1].clear();
  424.   node[ngen+2].clear();
  425. }
  426. void calc_gen() {
  427.   dn.clear();
  428.   for (int i=0; i<SZ; i++) {
  429. 	dn.push_back(P(evalution(i), i));
  430.   }
  431.   sort(dn.begin(), dn.end());
  432. }
  433.  
  434. int gp(int gennum) {
  435.   calc_gen();
  436.   if (gennum >= GENE) {
  437. 	return dn[SZ-1].second;
  438.   }
  439.   double r=(double)(rand()%1000+1)/1000.0;
  440.   int ngen = SZ;
  441.   while (ngen<SZ*2) {
  442. 	if (r<0.05) {
  443. 	  int rm= rand() % SZ;
  444. 	  // puts("mutation");
  445. 	  func.mutation(ngen, rm);
  446. 	} else if (r<0.1) {
  447. 	  // puts("tournament");
  448. 	  int t = tournament();
  449. 	  copy(node[t].begin(), node[t].end(), back_inserter(node[ngen]));
  450. 	} else {
  451. 	  // puts("crossover");
  452. 	  run_cross(ngen);
  453. 	}
  454. 	ngen++;
  455. 	r=(double)(rand()%1000+1)/1000.0;
  456.   }
  457.   // puts("hyouji");
  458.   usleep(1000*200);
  459.   for (int i=0; i<SZ; i++) {
  460. 	node[i].clear();
  461. 	copy(node[i+SZ].begin(), node[i+SZ].end(), back_inserter(node[i]));
  462. 	node[i+SZ].clear();
  463.   }
  464.  
  465.   for (int i=0; i<SZ/10; i++) {
  466.   	printf("generation %d: ", gennum + 1);
  467.   	for (int j=i*10; j<min(SZ,(i+1)*10); j++) {
  468.   	  printf("%d(%.3f) ", calcfood(j), evalution(j));
  469.   	}
  470.   	puts("");
  471.   }
  472.   return gp(gennum + 1);
  473. }
  474.  
  475. int main() {
  476.   srand((unsigned int)time(NULL));
  477.   scanf("%d%d",&n, &e);
  478.   for (int i=0; i<n; i++) cin>>MP[i];
  479.   for (int i=0; i<n; i++) {
  480. 	mp[i] = MP[i];
  481. 	for (int j=0; j<n; j++) {
  482. 	  if (MP[i][j] == '#') FOODS[i][j] = foods[i][j] = 1;
  483. 	}
  484.   }
  485.  
  486.   initialisation();
  487.  
  488.   //  runcnt=0;
  489.   for (int i=0; i<SZ/10; i++) {
  490. 	printf("generation %d: ", 0);
  491.   	for (int j=i*10; j<min(SZ,(i+1)*10); j++) {
  492.   	  printf("%d(%.3f) ", calcfood(j), evalution(j));
  493.   	}
  494.   	puts("");
  495.   }
  496.  
  497.   int ans = gp(0);
  498.   mapinit();
  499.   Tree tree(true, ans);
  500.   tree.run();
  501.  
  502.   printf("result: food=%d Energy=%d evalution=%.3f\n",tree.food,tree.Energy,evalution(ans));
  503.   printnode(ans);
  504.   puts("");
  505.   // test();
  506. }
  507.  
Runtime error #stdin #stdout 0.04s 11256KB
comments (?)
stdin
copy 
32 400
.###............................
...#............................
...#.....................###....
...#....................#....#..
...#....................#....#..
...####.#####........##.........
............#................#..
............#.......#...........
............#.......#...........
............#.......#........#..
....................#...........
............#...................
............#................#..
............#.......#...........
............#.......#.....###...
.................#.....#........
................................
............#...................
............#...#.......#.......
............#...#..........#....
............#...#...............
............#...#...............
............#.............#.....
............#..........#........
...##..#####....#...............
.#..............#...............
.#..............#...............
.#......#######.................
.#.....#........................
.......#........................
..####..........................
................................
stdout
copy 
Standard output is empty
https://ideone.com/7yt3F
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!