Christmas! 🎄

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.