Mercurial > repo

comparison interps/bfjoust/egojoust.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 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <time.h>
5
6 #include "buffer.h"
7
8 #define MINTAPELEN 10
9 #define MAXTAPELEN 30
10 #define POLARITIES 4
11 #define RUNCOUNT (((MAXTAPELEN-MINTAPELEN) + 1) * POLARITIES)
12
13 /* parse a BFJoust program */
14 int parseFile(struct Buffer_char *progp)
15 {
16 int i, end, inner, iend, llen, ilen, rlen, times, rep, loc;
17 struct Buffer_char prog = *progp;
18 struct Buffer_char temp;
19
20 /* go through looking for things to expand */
21 for (i = 0; i < prog.bufused; i++) {
22 if (prog.buf[i] == '(') {
23 /* look for the match */
24 int depth = 1;
25 inner = iend = -1;
26 for (end = i + 1; end < prog.bufused && depth; end++) {
27 if (prog.buf[end] == '(') {
28 depth++;
29 } else if (prog.buf[end] == ')') {
30 depth--;
31 } else if (depth == 1 && prog.buf[end] == '{') {
32 inner = end;
33 } else if (depth == 1 && prog.buf[end] == '}') {
34 iend = end;
35 }
36 }
37
38 /* make sure it's sensible */
39 end--;
40 if (end + 2 >= prog.bufused) return 0;
41
42 /* expand it only if it includes [ or ], or is a '%' loop (which make interpretation basically impossible if unexpanded) */
43 llen = end - i;
44 if (strcspn(prog.buf + i, "[]") >= llen && prog.buf[end+1] == '*') {
45 continue;
46 }
47
48 /* check what comes next */
49 times = atoi(prog.buf + end + 2);
50 if (times < 0 || times > 10000) times = 10000;
51 if (prog.buf[end+1] == '*') {
52 llen = end - i - 1;
53
54 /* the simple case, just repeat n times */
55 INIT_BUFFER(temp);
56 temp.bufused = times * llen;
57 while (temp.bufsz < temp.bufused) {
58 EXPAND_BUFFER(temp);
59 }
60 for (rep = 0; rep < times; rep++) {
61 memcpy(temp.buf + rep * llen, prog.buf + i + 1, llen);
62 }
63
64 } else if (prog.buf[end+1] == '%') {
65 /* make sure there's a {} */
66 if (inner == -1 || iend == -1) return 0;
67
68 llen = inner - i - 1;
69 ilen = iend - inner - 1;
70 rlen = end - iend - 1;
71 if (llen < 0 || ilen < 0 || rlen < 0) return 0;
72
73 /* set up the buffer */
74 INIT_BUFFER(temp);
75 temp.bufused = times * llen + ilen + times * rlen;
76 while (temp.bufsz < temp.bufused) {
77 EXPAND_BUFFER(temp);
78 }
79
80 /* now the left */
81 loc = 0;
82 for (rep = 0; rep < times; rep++) {
83 memcpy(temp.buf + loc + rep * llen, prog.buf + i + 1, llen);
84 }
85 loc = times * llen;
86
87 /* the inner */
88 memcpy(temp.buf + loc, prog.buf + inner + 1, ilen);
89 loc += ilen;
90
91 /* and the right */
92 for (rep = 0; rep < times; rep++) {
93 memcpy(temp.buf + loc + rep * rlen, prog.buf + iend + 1, rlen);
94 }
95
96 } else {
97 return 0;
98
99 }
100
101 /* now copy it back into prog */
102 while (prog.bufsz < prog.bufused + temp.bufused + 1) {
103 EXPAND_BUFFER(prog);
104 }
105 memmove(prog.buf + i + temp.bufused, prog.buf + end + 1, prog.bufused - end - 1);
106 memcpy(prog.buf + i, temp.buf, temp.bufused);
107 prog.bufused = prog.bufused - end + i - 1 + temp.bufused;
108 WRITE_BUFFER(prog, "", 1); prog.bufused--;
109
110 FREE_BUFFER(temp);
111
112 i--;
113 }
114 }
115
116 memcpy(progp, &prog, sizeof(prog));
117 return 1;
118 }
119
120 /* returns true if this is a BF comment */
121 int isComment(char c)
122 {
123 return (c != '<' && c != '>' && c != '-' && c != '+' && c != '[' && c != ']' && c != '(' && c != ')' && c != '.');
124 }
125
126 /* run an execution step */
127 void runStep(struct Buffer_char prog, int *loops, int *pip,
128 char *tape, char *otape, int tapelen, int *tip,
129 int tapedir, int polarity,
130 struct Buffer_int *pstack, struct Buffer_int *pmax)
131 {
132 int pi = *pip;
133 int ti = *tip;
134 int reps = 0;
135
136 /* find a non-comment character */
137 rerun:
138 if (++reps > 16) return;
139 if (pi < 0) return;
140 for (; pi < prog.bufused && isComment(prog.buf[pi]); pi++);
141 *pip = pi;
142 if (pi >= prog.bufused) return;
143
144 /* run it */
145 switch (prog.buf[pi]) {
146 case '<':
147 ti -= tapedir;
148 break;
149
150 case '>':
151 ti += tapedir;
152 break;
153
154 case '-':
155 otape[ti] -= polarity;
156 break;
157
158 case '+':
159 otape[ti] += polarity;
160 break;
161
162 case '[':
163 if (tape[ti] == 0) {
164 /* first check the cache */
165 if (loops[pi] != -1) {
166 pi = loops[pi];
167 } else {
168 int depth = 1;
169 int opi = pi;
170 for (pi++; pi < prog.bufused && depth; pi++) {
171 switch (prog.buf[pi]) {
172 case '[':
173 depth++;
174 break;
175
176 case ']':
177 depth--;
178 break;
179 }
180 }
181 pi--;
182
183 loops[opi] = pi;
184 loops[pi] = opi;
185 }
186 }
187 break;
188
189 case ']':
190 if (tape[ti] != 0) {
191 /* check the cache */
192 if (loops[pi] != -1) {
193 pi = loops[pi];
194 } else {
195 int depth = 1;
196 for (pi--; pi >= 0 && depth; pi--) {
197 switch (prog.buf[pi]) {
198 case ']':
199 depth++;
200 break;
201
202 case '[':
203 depth--;
204 break;
205 }
206 }
207 pi++;
208 }
209 }
210 break;
211
212 case '(':
213 /* make sure this is cached */
214 if (loops[pi] == -1) {
215 int depth = 1;
216 int ipi;
217 for (ipi = pi + 1; ipi < prog.bufused && depth; ipi++) {
218 switch (prog.buf[ipi]) {
219 case '(':
220 depth++;
221 break;
222
223 case ')':
224 depth--;
225 break;
226 }
227 }
228 ipi--;
229
230 loops[pi] = ipi;
231 loops[ipi] = pi;
232 }
233
234 /* push the counter */
235 {
236 int count = atoi(prog.buf + loops[pi] + 2);
237 if (BUFFER_SPACE(*pstack) < 1) {
238 EXPAND_BUFFER(*pstack);
239 EXPAND_BUFFER(*pmax);
240 }
241 pstack->buf[pstack->bufused++] = 0;
242 pmax->buf[pmax->bufused++] = count;
243 }
244
245 /* then continue immediately */
246 pi++;
247 goto rerun;
248
249 case ')':
250 /* increment the counter */
251 if (pstack->bufused > 0) {
252 pstack->buf[pstack->bufused-1]++;
253 }
254
255 /* either reloop or don't */
256 if (pstack->buf[pstack->bufused-1] < pmax->buf[pstack->bufused-1]) {
257 pi = loops[pi];
258 } else {
259 pstack->bufused = pmax->bufused = pstack->bufused - 1;
260 }
261 pi++;
262 goto rerun;
263
264 case '.':
265 /* nop */
266 break;
267 }
268 pi++;
269
270 *pip = pi;
271 *tip = ti;
272 }
273
274 /* simple hashing function, same as is used in sdbm */
275 size_t simpleHash(size_t slen, unsigned char *str)
276 {
277 size_t hash = 0;
278
279 for (; slen > 0; slen--)
280 hash = (*str++) + (hash << 6) + (hash << 16) - hash;
281
282 return hash;
283 }
284
285 int main(int argc, char **argv)
286 {
287 struct Buffer_char lprog, rprog;
288 struct Buffer_int lloops, rloops;
289 struct Buffer_int lpstack, rpstack, lpmax, rpmax;
290 FILE *lfh, *rfh;
291 int lparse, rparse;
292 char *tape, *otape;
293 int lt, rt, tapelen;
294 int polarity, lpol, rpol;
295 int lpi, rpi;
296 int lwins, rwins;
297 int lloss, rloss;
298 int step;
299
300 if (argc < 3) {
301 fprintf(stderr, "Use: egojoust <left program> <right program>\n");
302 return 0;
303 }
304
305 /* read in the files */
306 INIT_BUFFER(lprog);
307 SF(lfh, fopen, NULL, (argv[1], "r"));
308 READ_FILE_BUFFER(lprog, lfh);
309 WRITE_BUFFER(lprog, "", 1); lprog.bufused--;
310
311 INIT_BUFFER(rprog);
312 SF(rfh, fopen, NULL, (argv[2], "r"));
313 READ_FILE_BUFFER(rprog, rfh);
314 WRITE_BUFFER(rprog, "", 1); rprog.bufused--;
315
316 /* parse them */
317 lparse = parseFile(&lprog);
318 rparse = parseFile(&rprog);
319 if (!lparse) {
320 if (!rparse) {
321 printf("Both warriors failed to parse. Tie!\n");
322 return 0;
323 } else {
324 printf("Left warrior failed to parse, right warrior wins!\n");
325 return RUNCOUNT;
326 }
327 } else if (!rparse) {
328 printf("Right warrior failed to parse, left warrior wins!\n");
329 return -RUNCOUNT;
330 }
331
332 /* allocate the tape */
333 SF(tape, malloc, NULL, (30));
334 SF(otape, malloc, NULL, (30));
335
336 /* prepare the caches */
337 INIT_BUFFER(lloops);
338 INIT_BUFFER(rloops);
339 while (lloops.bufsz < lprog.bufused) EXPAND_BUFFER(lloops);
340 memset(lloops.buf, -1, lprog.bufused * sizeof(int));
341 while (rloops.bufsz < rprog.bufused) EXPAND_BUFFER(rloops);
342 memset(rloops.buf, -1, rprog.bufused * sizeof(int));
343
344 INIT_BUFFER(lpstack);
345 INIT_BUFFER(rpstack);
346 INIT_BUFFER(lpmax);
347 INIT_BUFFER(rpmax);
348
349 /* run for each polarity, for each length from 10 to 30 */
350 lwins = 0;
351 rwins = 0;
352
353 printf("%s vs %s:\n", argv[1], argv[2]);
354
355 for (polarity = 0; polarity < POLARITIES; polarity++) {
356 /* set up the polarity */
357 if (polarity & 0x2) {
358 lpol = -1;
359 } else {
360 lpol = 1;
361 }
362
363 if (polarity & 0x1) {
364 rpol = -1;
365 } else {
366 rpol = 1;
367 }
368
369 for (tapelen = MINTAPELEN; tapelen <= MAXTAPELEN; tapelen++) {
370 /* make the tape */
371 memset(tape, 0, tapelen);
372 tape[0] = tape[tapelen-1] = (char) (unsigned char) 128;
373 lt = 0;
374 rt = tapelen - 1;
375 memcpy(otape, tape, tapelen);
376
377 /* then run */
378 lpi = rpi = lloss = rloss = 0;
379 for (step = 0; step < 100000 && lloss < 2 && rloss < 2; step++) {
380 /* run the left */
381 runStep(lprog, lloops.buf, &lpi, tape, otape, tapelen, &lt, 1, lpol, &lpstack, &lpmax);
382
383 /* and the right */
384 runStep(rprog, rloops.buf, &rpi, tape, otape, tapelen, &rt, -1, rpol, &rpstack, &rpmax);
385
386 /* commit the tape */
387 memcpy(tape, otape, tapelen);
388
389 /* check for loss conditions */
390 if (tape[0] == 0) {
391 lloss++;
392 } else {
393 lloss = 0;
394 }
395 if (lt < 0 || lt >= tapelen) {
396 fprintf(stderr, "Left ran off the tape (%d/%d)!\n", lt, tapelen);
397 lloss = 3;
398 }
399 if (tape[tapelen-1] == 0) {
400 rloss++;
401 } else {
402 rloss = 0;
403 }
404 if (rt < 0 || rt >= tapelen) {
405 fprintf(stderr, "Right ran off the tape (%d/%d)!\n", rt, tapelen);
406 rloss = 3;
407 }
408 }
409
410 /* now find the victor */
411 if (lloss > rloss) {
412 /*printf("%d/%d: %s wins!\n", polarity, tapelen, argv[2]);*/
413 printf(">");
414 rwins++;
415 } else if (rloss > lloss) {
416 /*printf("%d/%d: %s wins!\n", polarity, tapelen, argv[1]);*/
417 printf("<");
418 lwins++;
419 } else {
420 /*printf("%d/%d: Tie!\n", polarity, tapelen);*/
421 printf("X");
422 }
423 }
424
425 printf(" ");
426 }
427
428 printf("\n");
429
430 if (lwins > rwins) {
431 printf("%s wins\n\n", argv[1]);
432 } else if (rwins > lwins) {
433 printf("%s wins\n\n", argv[2]);
434 } else {
435 printf("Tie\n\n");
436 }
437 return rwins - lwins;
438 }