Day 6: Guard Gallivant

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • C

    Got super stumped on part 2. I’d add an obstacle for every tile on the path of part 1 but I kept getting wrong results, even after fixing some edge cases. Spent too much time looking at terminal dumps and mp4 visualisations.

    Eventually I gave up and wrote a for(y) for(x) loop, trying an obstacle in every possible tile, and that gave the correct answer. Even that brute force took only 2.5 ish seconds on my 2015 PC! But having that solution allowed me to narrow it down again to a reasonably efficient version similar to what I had before. Still I don’t know where I went wrong the first time.

    Code
    #include "common.h"
    
    #define GZ 134
    
    struct world { char g[GZ][GZ]; int x,y, dir; };
    
    static const char carets[] = "^>v<";
    static const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
    
    static inline char *ahead(struct world *w) {
        return &w->g[w->y+dy[w->dir]][w->x+dx[w->dir]]; }
    static inline int visited(char t) { return t && strchr(carets, t); }
    static inline int traversible(char t) { return t=='.' || visited(t); }
    
    /* new tile, previously visited tile, in a loop, out of bounds */
    enum { ST_NEW, ST_SEEN, ST_LOOP, ST_END };
    
    static int
    step(struct world *w)
    {
    	char *cell;
    	int is_new;
    
    	assert(w->x >= 0); assert(w->x < GZ);
    	assert(w->y >= 0); assert(w->y < GZ);
    
    	cell = &w->g[w->y][w->x];
    
    	if (!traversible(*cell))	/* out of bounds? */
    		return ST_END;
    	while (*ahead(w) == '#')	/* turn if needed */
    		w->dir = (w->dir +1) %4;
    	if (*cell == carets[w->dir])	/* walked here same dir? */
    		return ST_LOOP;
    
    	is_new = *cell == '.';
    	*cell = carets[w->dir];
    	w->x += dx[w->dir];
    	w->y += dy[w->dir];
    
    	return is_new ? ST_NEW : ST_SEEN;
    }
    
    int
    main(int argc, char **argv)
    {
    	static struct world w0,w1,w2;
    	int p1=0,p2=0, x,y, r,i;
    
    	if (argc > 1)
    		DISCARD(freopen(argv[1], "r", stdin));
    
    	for (y=1; y