From 94d0033ed89bb5bfb6500051296892fb7cea6c29 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 25 Dec 2023 17:56:34 +0100 Subject: Small cleanup --- 2023/08/8a.c | 10 +++------ 2023/08/8b.c | 70 +++++++++++++++++++----------------------------------------- 2 files changed, 25 insertions(+), 55 deletions(-) (limited to '2023/08') diff --git a/2023/08/8a.c b/2023/08/8a.c index 62f6fcd..f6d58b5 100644 --- a/2023/08/8a.c +++ b/2023/08/8a.c @@ -1,17 +1,13 @@ -#include -#include -#include #include -#include #include #define N 30000 - -bool isnum(char c) { return c >= '0' && c <= '9'; } -int index(char *c) { return c[0]-'A' + (c[1]-'A' + (c[2]-'A')*26)*26; } +#define ISNUM(c) (c >= '0' && c <= '9') int map[N][2]; +int index(char *c) { return c[0]-'A' + (c[1]-'A' + (c[2]-'A')*26)*26; } + int main() { char *buf, dir[N], line[N]; int n, i, s; diff --git a/2023/08/8b.c b/2023/08/8b.c index 713bada..f704a36 100644 --- a/2023/08/8b.c +++ b/2023/08/8b.c @@ -1,74 +1,50 @@ /* -I hate this stupid problem. If you read the description carefully (which is -what I did), you would think that the problem is much, much harder than it -actually is. In reality, the author made many assumptions about the possible -paths that made is super easy. Let's see a few: +I hate this stupid problem. There are a bunch of unwritten properties +of the paths that make the problem very simple: -- Different ghost's path do not end up in the same Z-node (this is not super - important for the solution). -- Each ghost has exactly one Z-node in its path (one could think about this - when reading the strange remark that "there are as many A-nodes as Z-nodes", - which does not look important at first). -- Each ghosts meets a Z-node exactly once before entering a loop (this is - a fundamental and incredibly strong assupmtion). +- Different ghosts' paths do not end up in the same Z-node. +- Each ghost has exactly one Z-node in its path. +- Each ghost meets a Z-node exactly once before entering a loop. - If a ghost encounters a Z-node after X steps, it will encounter it exactly - every X steps (like WTF I don't even have to solve a system of congruences? - what is this, a problem for babies?) + every X steps; preperiods just end up aligning nicely. -Fuck. - -This code does not even solve the problem by the way, it computes some data -about the path that each ghost takes. Then you can figure out the solution -with a pocket calculator, or by hand. +In practice, everything just works out so that the lcm of the periods +is the solution, which is very much not the case for a general input. +This code computes the periods of the paths of the different ghosts. Then +you can figure out the solution with a pocket calculator, or by hand. */ -#include -#include -#include + #include -#include #include #define N 1000 typedef struct { char last; int next[2]; } node_t; -typedef struct { int preplen, plen, nz, z[N], zid[N]; } source_t; + +int v[N*N]; int ind(char s[3], char m[][3], int n) { for (int j = 0; j < n; j++) if (s[0] == m[j][0] && s[1] == m[j][1] && s[2] == m[j][2]) return j; - return -1; } -int v[N*N]; -source_t worksource(int i, node_t *nodes, char *dir, int n, int k) { - source_t s; - int state; - -printf("Working source %d\n", i); - +int findperiod(int i, node_t *nodes, char *dir, int n, int k) { memset(v, 0, sizeof(int) * N*N); - for (int j = i, d = 0, l = 1; true; d = (d+1)%k) { + for (int j = i, d = 0, l = 1, state = -1; ; d = (d+1)%k) { j = nodes[j].next[dir[d] == 'R']; state = j*k+d; -if (nodes[j].last == 'Z') printf("Found Z %d at %d\n", j, l); - if (v[state]) { - s.preplen = v[state]-1; - s.plen = l - v[state]; -printf("Stopping at %d. Preperiod: %d, period: %d\n", l, s.preplen, s.plen); - return s; - } else v[state] = l++; + if (v[state]) return l - v[state]; + else v[state] = l++; } - - return s; + return -1; } int main() { node_t nodes[N]; - source_t src[N]; char *buf, dir[N], line[N], name[N][3], lstr[N][3], rstr[N][3]; - int k, i, n, m, s; + int k, n; k = strlen(fgets(dir, N, stdin)) - 1; fgets(line, N, stdin); @@ -81,16 +57,14 @@ int main() { memcpy(rstr[n], buf+1, 3); } - for (i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { nodes[i].next[0] = ind(lstr[i], name, n); nodes[i].next[1] = ind(rstr[i], name, n); } -printf("%d %d\n", n, k); - - for (i = 0, m = 0; i < n; i++) + for (int i = 0; i < n; i++) if (nodes[i].last == 'A') - src[m++] = worksource(i, nodes, dir, n, k); + printf("%d\n", findperiod(i, nodes, dir, n, k)); return 0; } -- cgit v1.3