Mercurial > repo

comparison interps/fukyorbrane/fukyorbrane.c @ 996:859f9b4339e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<Gregor> tar xf egobot.tar.xz
author HackBot
date Sun, 09 Dec 2012 19:30:08 +0000
parents
children
comparison
equal deleted inserted replaced
995:6883f5911eb7 996:859f9b4339e6
1 /*
2 * Copyright (c) 2005, 2009 Gregor Richards
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 * SOFTWARE.
21 */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <unistd.h>
27
28 #ifndef MAX_PROG_LEN
29 #define MAX_PROG_LEN 32256
30 #endif
31
32 /* program data */
33 int *progs[2];
34 /* a command is "spent" if it's a fork that's already forked
35 * perhaps later commits will be spendable too */
36 unsigned char *progSpent[2];
37 /* uncommitted program data */
38 int *progMods[2];
39 /* lengths of each program */
40 int proglens[2];
41 /* owner of each process */
42 unsigned char *procs;
43 /* defected processes */
44 unsigned char *procdef;
45 /* program pointer for each proc */
46 int *procpptrs;
47 /* data pointer for each proc */
48 int *procdptrs;
49 /* process count */
50 int procc;
51
52 /* verbose? */
53 unsigned char verbose = 0;
54 /* output turn numbers? */
55 unsigned char outt = 0;
56
57 #define CMD_NOP 0
58 #define CMD_INC 1
59 #define CMD_LFT 2
60 #define CMD_RHT 3
61 #define CMD_INP 4
62 #define CMD_OUT 5
63 #define CMD_COM 6 /* commit */
64 #define CMD_UNC 7 /* uncommit */
65 #define CMD_L1O 8 /* L1 = loop1 = [] = value at pointer != 0 */
66 #define CMD_L1C 9
67 #define CMD_L2O 10 /* L2 = loop2 = {} = enemy program pointer is NOT at data pointer */
68 #define CMD_L2C 11
69 #define CMD_L3O 12 /* L3 = loop3 = :; = fork */
70 #define CMD_L3C 13
71 #define CMD_BOM 14
72 #define CMD_OKB 15 /* "OK" bomb - for killing your own process, doesn't declare enemy winner */
73 #define CMD_DEF 16 /* defect - edit your own program */
74 #define CMD_CNT 17
75
76 /* not actually commands, just here to tell us when we're in comments */
77 #define CMD_CIN 18
78 #define CMD_COT 19
79
80 int cmdToInt(char cmd);
81 char intToCmd(int cmd);
82 char intToCmd(int cmd);
83 int execcmd(int procnum, unsigned char procowner, int *pptr, int *dptr);
84
85 int main(int argc, char **argv)
86 {
87 FILE *fps[2];
88 int prog, inc, proc;
89 long turnn;
90
91 if (argc <= 2) {
92 fprintf(stderr, "\n\nCopyright (c) 2005, 2009 Gregor Richards\n\n"
93 "Permission is hereby granted, free of charge, to any person obtaining a copy of\n"
94 "this software and associated documentation files (the \"Software\"), to deal in\n"
95 "the Software without restriction, including without limitation the rights to\n"
96 "use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies\n"
97 "of the Software, and to permit persons to whom the Software is furnished to do\n"
98 "so, subject to the following conditions:\n\n"
99 "The above copyright notice and this permission notice shall be included in all\n"
100 "copies or substantial portions of the Software.\n\n"
101 "THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\n"
102 "IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS\n"
103 "FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR\n"
104 "COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER\n"
105 "IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\n"
106 "CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\n\n\n");
107
108 fprintf(stderr, "Use: %s <program 1> <program 2> [options]\n"
109 " Options:\n"
110 " v: verbose mode\n"
111 " t: output turn numbers\n", argv[0]);
112 return 1;
113 }
114
115 if (argv[3]) {
116 for (proc = 0; argv[3][proc]; proc++) {
117 switch (argv[3][proc]) {
118 case 'v':
119 verbose = 1;
120 break;
121
122 case 't':
123 outt = 1;
124 break;
125 }
126 }
127 }
128
129 progs[0] = (int *) malloc(MAX_PROG_LEN * sizeof(int));
130 progs[1] = (int *) malloc(MAX_PROG_LEN * sizeof(int));
131 progSpent[0] = (unsigned char *) malloc(MAX_PROG_LEN * sizeof(unsigned char));
132 progSpent[1] = (unsigned char *) malloc(MAX_PROG_LEN * sizeof(unsigned char));
133 progMods[0] = (int *) malloc(MAX_PROG_LEN * sizeof(int));
134 progMods[1] = (int *) malloc(MAX_PROG_LEN * sizeof(int));
135 procs = (unsigned char *) malloc(1024 * sizeof(unsigned char));
136 procdef = (unsigned char *) malloc(1024 * sizeof(unsigned char));
137 procpptrs = (int *) malloc(1024 * sizeof(int));
138 procdptrs = (int *) malloc(1024 * sizeof(int));
139
140 fps[0] = fopen(argv[1], "r");
141 if (!fps[0]) {
142 perror(argv[1]);
143 return 3;
144 }
145
146 fps[1] = fopen(argv[2], "r");
147 if (!fps[1]) {
148 perror(argv[2]);
149 return 3;
150 }
151
152 for (prog = 0; prog <= 1; prog++) {
153 int incomment = 0;
154 proglens[prog] = 0;
155
156 while (!feof(fps[prog])) {
157 inc = cmdToInt(getc(fps[prog]));
158 if (inc == CMD_CIN) {
159 incomment = 1;
160 inc = -1;
161 }
162 if (inc == CMD_COT) {
163 incomment = 0;
164 inc = -1;
165 }
166
167 if (inc != -1 && !incomment) {
168 progs[prog][proglens[prog]] = inc;
169 progMods[prog][proglens[prog]] = inc;
170 progSpent[prog][proglens[prog]] = 0;
171 proglens[prog]++;
172 }
173 }
174 }
175
176 /* the programs must be of equal length to be fair */
177 while (proglens[0] < proglens[1]) {
178 progs[0][proglens[0]] = CMD_NOP;
179 progMods[0][proglens[0]] = CMD_NOP;
180 progSpent[0][proglens[0]] = 0;
181 proglens[0]++;
182 }
183 while (proglens[1] < proglens[0]) {
184 progs[1][proglens[1]] = CMD_NOP;
185 progMods[1][proglens[1]] = CMD_NOP;
186 progSpent[1][proglens[1]] = 0;
187 proglens[1]++;
188 }
189
190 /* now bootstrap the processes ... */
191 procs[0] = 1;
192 procdef[0] = 0;
193 procpptrs[0] = 0;
194 procdptrs[0] = 0;
195 procs[1] = 2;
196 procdef[1] = 0;
197 procpptrs[1] = 0;
198 procdptrs[1] = 0;
199 procc = 2;
200
201 for (turnn = 0; turnn < 10000000; turnn++) {
202 int winner;
203 unsigned char alive[2];
204
205 /* output the board if we're verbose */
206 if (verbose) {
207 int vproc;
208 char *outline;
209 int outll;
210
211 outline = (char *) malloc(MAX_PROG_LEN * sizeof(char));
212
213 for (proc = 0; proc < 2; proc++) {
214
215 fprintf(stderr, "==============================\n");
216 fprintf(stderr, "%s\n\t", argv[proc + 1]);
217 for (inc = 0; inc < proglens[0]; inc++) {
218 fprintf(stderr, "%c", intToCmd(progs[proc][inc]));
219 }
220 fprintf(stderr, "\n");
221
222 for (vproc = 0; vproc < procc; vproc++) {
223 outll = 0;
224 memset(outline, ' ', 32256);
225
226 if (procs[vproc] == proc + 1) {
227 outline[procpptrs[vproc]] = 'p';
228 if (procpptrs[vproc] >= outll)
229 outll = procpptrs[vproc] + 1;
230
231 if (procdef[vproc]) {
232 if (outline[procdptrs[vproc]] == 'p') {
233 outline[procdptrs[vproc]] = 'b';
234 } else {
235 outline[procdptrs[vproc]] = 'd';
236 }
237 if (procdptrs[vproc] >= outll)
238 outll = procdptrs[vproc] + 1;
239 }
240 } else if (procs[vproc] != 0 && !procdef[vproc]) {
241 outline[procdptrs[vproc]] = 'd';
242 if (procdptrs[vproc] >= outll)
243 outll = procdptrs[vproc] + 1;
244 }
245
246 outline[outll] = '\0';
247 fprintf(stderr, "%d:\t%s\n", vproc, outline);
248 }
249 }
250
251 fprintf(stderr, "==============================\n\n");
252
253 free(outline);
254 } else if (outt) {
255 fprintf(stderr, "%ld \r", turnn);
256 }
257
258 for (proc = 0; proc < procc; proc++) {
259 if (procs[proc]) {
260 if ((winner = execcmd(proc, procs[proc], procpptrs + proc, procdptrs + proc))) {
261 if (outt) fprintf(stderr, "\n");
262 printf("%s wins!\n", argv[winner]);
263 return winner;
264 }
265 }
266 }
267
268 // see if anybody accidentally quit themselves
269 alive[0] = 0;
270 alive[1] = 0;
271 for (proc = 0; proc < procc; proc++) {
272 if (procs[proc]) {
273 alive[procs[proc]-1] = 1;
274 }
275 }
276 if (!alive[0]) {
277 if (outt) fprintf(stderr, "\n");
278 printf("%s wins!\n", argv[2]);
279 return 2;
280 }
281 if (!alive[1]) {
282 if (outt) fprintf(stderr, "\n");
283 printf("%s wins!\n", argv[1]);
284 return 1;
285 }
286 }
287
288 printf("It's a draw due to 10,000,000 clocks with no winner!\n");
289
290 return 0;
291 }
292
293 int cmdToInt(char cmd)
294 {
295 switch (cmd) {
296 case '%':
297 return CMD_NOP;
298 case '+':
299 return CMD_INC;
300 case '<':
301 return CMD_LFT;
302 case '>':
303 return CMD_RHT;
304 case ',':
305 return CMD_INP;
306 case '.':
307 return CMD_OUT;
308 case '!':
309 return CMD_COM;
310 case '?':
311 return CMD_UNC;
312 case '[':
313 return CMD_L1O;
314 case ']':
315 return CMD_L1C;
316 case '{':
317 return CMD_L2O;
318 case '}':
319 return CMD_L2C;
320 case ':':
321 return CMD_L3O;
322 case ';':
323 return CMD_L3C;
324 case '*':
325 return CMD_OKB;
326 case '@':
327 return CMD_DEF;
328
329 case '(':
330 return CMD_CIN;
331 case ')':
332 return CMD_COT;
333 }
334 return -1;
335 }
336
337 char intToCmd(int cmd)
338 {
339 switch (cmd) {
340 case CMD_NOP:
341 return '%';
342 case CMD_INC:
343 return '+';
344 case CMD_LFT:
345 return '<';
346 case CMD_RHT:
347 return '>';
348 case CMD_INP:
349 return ',';
350 case CMD_OUT:
351 return '.';
352 case CMD_COM:
353 return '!';
354 case CMD_UNC:
355 return '?';
356 case CMD_L1O:
357 return '[';
358 case CMD_L1C:
359 return ']';
360 case CMD_L2O:
361 return '{';
362 case CMD_L2C:
363 return '}';
364 case CMD_L3O:
365 return ':';
366 case CMD_L3C:
367 return ';';
368 case CMD_BOM:
369 return 'B';
370 case CMD_OKB:
371 return '*';
372 case CMD_DEF:
373 return '@';
374 }
375 return ' ';
376 }
377
378 int execcmd(int procnum, unsigned char procowner, int *pptr, int *dptr)
379 {
380 int i, fnd, origpptr;
381 int procedits;
382 int depth;
383
384 if (procdef[procnum]) {
385 procedits = procowner - 1;
386 } else {
387 procedits = !(procowner - 1);
388 }
389
390 switch (progs[procowner-1][*pptr]) {
391 case CMD_INC:
392 progMods[procedits][*dptr]++;
393 if (progMods[procedits][*dptr] >= CMD_CNT) progMods[procedits][*dptr] = 0;
394 break;
395
396 case CMD_LFT:
397 (*dptr)--;
398 if (*dptr < 0) *dptr = 0;
399 break;
400 case CMD_RHT:
401 (*dptr)++;
402 if (*dptr >= proglens[0]) *dptr -= proglens[0];
403 break;
404
405 case CMD_INP:
406 case CMD_OUT:
407 /* no implementation, but reserved! */
408 break;
409
410 case CMD_COM:
411 progs[procedits][*dptr] = progMods[procedits][*dptr];
412 // if you commit a defect, you defect!
413 if (progs[procedits][*dptr] == CMD_DEF) {
414 procdef[procnum] = !procdef[procnum];
415 *dptr = *pptr;
416 }
417 /* perhaps make commit only work once? */
418 break;
419
420 case CMD_UNC:
421 progMods[procedits][*dptr] = progs[procedits][*dptr];
422 break;
423
424 case CMD_L1O:
425 if (!progMods[procedits][*dptr]) {
426 /* find the counterpart */
427 depth = 0;
428 origpptr = *pptr;
429 (*pptr)++;
430 while (progs[procowner-1][*pptr] != CMD_L1C ||
431 depth != 0) {
432 if (progs[procowner-1][*pptr] == CMD_L1O) depth++;
433 if (progs[procowner-1][*pptr] == CMD_L1C) depth--;
434 (*pptr)++;
435
436 if (*pptr >= proglens[0]) {
437 /* our loop-end was evicerated! */
438 *pptr = origpptr;
439 break;
440 }
441 }
442 }
443 break;
444 case CMD_L1C:
445 /* find the counterpart */
446 depth = 0;
447 origpptr = *pptr;
448 (*pptr)--;
449 if (*pptr < 0) *pptr = 0;
450 while (progs[procowner-1][*pptr] != CMD_L1O ||
451 depth != 0) {
452 if (progs[procowner-1][*pptr] == CMD_L1O) depth++;
453 if (progs[procowner-1][*pptr] == CMD_L1C) depth--;
454 (*pptr)--;
455
456 if (*pptr < 0) {
457 /* our loop-end was evicerated! */
458 *pptr = origpptr + 1;
459 break;
460 }
461 }
462 (*pptr)--;
463 break;
464
465 case CMD_L2O:
466 /* loop through every proc */
467 fnd = 0;
468 for (i = 0; i < procc; i++) {
469 if (procs[i] && procs[i] != procowner) {
470 if (procpptrs[i] == *dptr) {
471 /* got em */
472 fnd = 1;
473 }
474 }
475 }
476 if (fnd) {
477 /* find the counterpart */
478 depth = 0;
479 origpptr = *pptr;
480 (*pptr)++;
481 while (progs[procowner-1][*pptr] != CMD_L2C ||
482 depth != 0) {
483 if (progs[procowner-1][*pptr] == CMD_L2O) depth++;
484 if (progs[procowner-1][*pptr] == CMD_L2C) depth--;
485 (*pptr)++;
486
487 if (*pptr >= proglens[0]) {
488 /* our loop-end was evicerated! */
489 *pptr = origpptr;
490 break;
491 }
492 }
493 }
494 break;
495 case CMD_L2C:
496 /* find the counterpart */
497 depth = 0;
498 origpptr = *pptr;
499 (*pptr)--;
500 if (*pptr < 0) *pptr = 0;
501 while (progs[procowner-1][*pptr] != CMD_L2O ||
502 depth != 0) {
503 if (progs[procowner-1][*pptr] == CMD_L2O) depth++;
504 if (progs[procowner-1][*pptr] == CMD_L2C) depth--;
505 (*pptr)--;
506
507 if (*pptr < 0) {
508 /* our loop-end was evicerated! */
509 *pptr = origpptr + 1;
510 break;
511 }
512 }
513 (*pptr)--;
514 break;
515
516 case CMD_L3O:
517 /* start a new proc! */
518 if (!progSpent[procnum][*pptr]) {
519 procs[procc] = procowner;
520 procpptrs[procc] = *pptr + 1;
521 procdptrs[procc] = *dptr;
522 procdef[procc] = procdef[procnum];
523
524 procc++;
525
526 progSpent[procnum][*pptr] = 1;
527 }
528
529 /* now this proc needs to skip to the end */
530 /* find the counterpart */
531 depth = 0;
532 origpptr = *pptr;
533 (*pptr)++;
534 while (progs[procowner-1][*pptr] != CMD_L3C ||
535 depth != 0) {
536 if (progs[procowner-1][*pptr] == CMD_L3O) depth++;
537 if (progs[procowner-1][*pptr] == CMD_L3C) depth--;
538 (*pptr)++;
539
540 if (*pptr >= proglens[0]) {
541 /* our loop-end was evicerated! */
542 *pptr = origpptr;
543 break;
544 }
545 }
546
547 break;
548 case CMD_L3C:
549 /* we must be in the child proc, skip to the beginning of this proc
550 (really, you shouldn't let a proc do this, you should bomb it */
551 /* find the counterpart */
552 depth = 0;
553 origpptr = *pptr;
554 (*pptr)--;
555 if (*pptr < 0) *pptr = 0;
556 while (progs[procowner-1][*pptr] != CMD_L3O ||
557 depth != 0) {
558 if (progs[procowner-1][*pptr] == CMD_L3O) depth++;
559 if (progs[procowner-1][*pptr] == CMD_L3C) depth--;
560 (*pptr)--;
561
562 if (*pptr < 0) {
563 /* our loop-end was evicerated! */
564 *pptr = origpptr + 1;
565 break;
566 }
567 }
568 break;
569
570 case CMD_BOM:
571 /* boom! */
572 return ((!(procowner-1)) + 1);
573
574 case CMD_OKB:
575 /* sorta boom! */
576 if (procnum < 2) {
577 procs[procnum] = 0;
578 } else {
579 /* only bomb if it's the last command of a thread */
580 if (progs[procowner-1][(*pptr)+1] == CMD_L3C) {
581 procs[procnum] = 0;
582 }
583 }
584 break;
585
586 case CMD_DEF:
587 /* defect - edit your own program */
588 procdef[procnum] = !procdef[procnum];
589 *dptr = *pptr;
590 break;
591 }
592
593 (*pptr)++;
594 if (*pptr >= proglens[0]) *pptr = 0;
595
596 return 0;
597 }