diff options
Diffstat (limited to '2017')
| -rw-r--r-- | 2017/25.c | 151 | ||||
| -rw-r--r-- | 2017/25.in | 62 |
2 files changed, 213 insertions, 0 deletions
diff --git a/2017/25.c b/2017/25.c new file mode 100644 index 0000000..46680d4 --- /dev/null +++ b/2017/25.c @@ -0,0 +1,151 @@ +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> +#include <stdint.h> +#include <string.h> +#include <ctype.h> +#include <assert.h> + + +const char* next_word(void){ + static char buf[1024]; + int len=0; + char c=getchar(); + while(isspace(c))c=getchar(); + if(feof(stdin))return NULL; + if(!isalnum(c)){ + buf[0]=c; + buf[1]='\0'; + return buf; + } + while(isalnum(c)&&!feof(stdin)){ + buf[len++]=c; + c=getchar(); + } + if(!feof(stdin))ungetc(c,stdin); + buf[len]='\0'; + return buf; +} + +struct rule { + int state; + int direction; // right = 1, left = -1 + bool value; +}; + +struct rules { + struct rule table[8][2]; + int start; + int stopcount; +}; + + +#define EQ(s1_,s2_) (strcmp((s1_),(s2_))==0) +#define READ(dest_) assert((dest_)=next_word()) +#define READ_EOF(dest_) ((dest_)=next_word()) +#define READSTATE(dest_) ((dest_)=next_word()[0]-'A') +#define READINT(dest_) ((dest_)=strtol(next_word(),NULL,10)) +#define EXPECT(s_) assert(EQ(next_word(),(s_))) + +static struct rules parse(void){ + struct rules R; + int curstate=0,curval=0; + const char *word; + while(true){ + READ_EOF(word); + if(!word)break; + if(EQ(word,"Begin")){ + EXPECT("in"); EXPECT("state"); + READSTATE(R.start); + EXPECT("."); + } else if(EQ(word,"Perform")){ + EXPECT("a"); EXPECT("diagnostic"); EXPECT("checksum"); EXPECT("after"); + READINT(R.stopcount); + EXPECT("steps"); EXPECT("."); + } else if(EQ(word,"In")){ + EXPECT("state"); + READSTATE(curstate); + EXPECT(":"); + } else if(EQ(word,"If")){ + EXPECT("the"); EXPECT("current"); EXPECT("value"); EXPECT("is"); + READINT(curval); + EXPECT(":"); + } else if(EQ(word,"-")){ + READ(word); + if(EQ(word,"Write")){ + EXPECT("the"); EXPECT("value"); + READINT(R.table[curstate][curval].value); + EXPECT("."); + } else if(EQ(word,"Move")){ + EXPECT("one"); EXPECT("slot"); EXPECT("to"); EXPECT("the"); + READ(word); + if(EQ(word,"right"))R.table[curstate][curval].direction=1; + else if(EQ(word,"left"))R.table[curstate][curval].direction=-1; + else assert(false); + EXPECT("."); + } else if(EQ(word,"Continue")){ + EXPECT("with"); EXPECT("state"); + READSTATE(R.table[curstate][curval].state); + EXPECT("."); + } else { + assert(false); + } + } else { + assert(false); + } + } + return R; +} + +#undef EQ +#undef EXPECT + +static void printrules(const struct rules R){ + printf("start=%c\nstopcount=%d\n",R.start+'A',R.stopcount); + for(int i=0;i<8;i++){ + printf("%c: %d,%c,%c %d,%c,%c\n", + 'A'+i, + R.table[i][0].value,"<>"[R.table[i][0].direction],R.table[i][0].state+'A', + R.table[i][1].value,"<>"[R.table[i][1].direction],R.table[i][1].state+'A'); + } +} + +int main(void){ + freopen("25.in","r",stdin); + struct rules R=parse(); + // printrules(R); + + assert(sizeof(bool)==1); + + int tapesize=4096; + bool *tape=calloc(tapesize,1); + + int state=R.start,ptr=tapesize/2; + + for(int iter=0;iter<R.stopcount;iter++){ + if(ptr==-1){ + bool *newtape=calloc(2*tapesize,1); + memcpy(newtape+tapesize,tape,tapesize); + ptr+=tapesize; + free(tape); + tape=newtape; + tapesize*=2; + } else if(ptr==tapesize){ + bool *newtape=calloc(2*tapesize,1); + memcpy(newtape,tape,tapesize); + free(tape); + tape=newtape; + tapesize*=2; + } + struct rule *rule=&R.table[state][tape[ptr]]; + tape[ptr]=rule->value; + ptr+=rule->direction; + state=rule->state; + } + + int total=0; + for(int i=0;i<tapesize;i++)total+=tape[i]; + printf("%d\n",total); + + free(tape); +} diff --git a/2017/25.in b/2017/25.in new file mode 100644 index 0000000..e2e4d56 --- /dev/null +++ b/2017/25.in @@ -0,0 +1,62 @@ +Begin in state A. +Perform a diagnostic checksum after 12399302 steps. + +In state A: + If the current value is 0: + - Write the value 1. + - Move one slot to the right. + - Continue with state B. + If the current value is 1: + - Write the value 0. + - Move one slot to the right. + - Continue with state C. + +In state B: + If the current value is 0: + - Write the value 0. + - Move one slot to the left. + - Continue with state A. + If the current value is 1: + - Write the value 0. + - Move one slot to the right. + - Continue with state D. + +In state C: + If the current value is 0: + - Write the value 1. + - Move one slot to the right. + - Continue with state D. + If the current value is 1: + - Write the value 1. + - Move one slot to the right. + - Continue with state A. + +In state D: + If the current value is 0: + - Write the value 1. + - Move one slot to the left. + - Continue with state E. + If the current value is 1: + - Write the value 0. + - Move one slot to the left. + - Continue with state D. + +In state E: + If the current value is 0: + - Write the value 1. + - Move one slot to the right. + - Continue with state F. + If the current value is 1: + - Write the value 1. + - Move one slot to the left. + - Continue with state B. + +In state F: + If the current value is 0: + - Write the value 1. + - Move one slot to the right. + - Continue with state A. + If the current value is 1: + - Write the value 1. + - Move one slot to the right. + - Continue with state E. |