#include #include #include int main(int argc, const char *argv[]) { /* Slurp the whole map as a single string, work out how big it is, * and set up deltas for moving one step in each of the four directions */ #define MAXSIZE 65536 char map[MAXSIZE+1]; char *end = map + fread(map, 1, MAXSIZE, stdin); *end = '\0'; int row = 1 + strchr(map, '\n') - map; int dp[4]; dp[0] = 1; dp[1] = -row; dp[2] = -1; dp[3] = row; /* Find the guard's starting position and direction */ int start_dir; char *start_pos; (start_dir = 0, start_pos = strchr(map, '>')) || (start_dir = 1, start_pos = strchr(map, '^')) || (start_dir = 2, start_pos = strchr(map, '<')) || (start_dir = 3, start_pos = strchr(map, 'v')); /* Bitwise encodings for map cells, ASCII assumed * * 0000xxxx - map edge * 0010xxxx - free passage * 0100xxxx - permanent obstacle * 0110xxxx - proposed obstacle * xxxx1xxx - entered going south (dir = 3) * xxxxx1xx - entered going west (dir = 2) * xxxxxx1x - entered going north (dir = 1) * xxxxxxx1 - entered going east (dir = 0) * * If an obstacle gets entered from the same direction twice, * it's part of a loop. */ /* Bitwise encode map */ int dir; char *pos; for (pos = map; pos < end; ++pos) { if (*pos == '#') *pos = 0x40; else if (strchr(">^= end) break; if (*pos < 0x10) break; if (*pos & 0x40) { /* Obstacle? */ if (*pos & (1 << dir)) { /* Loop? */ ++loops; break; } else { *pos |= (1 << dir); /* Mark it */ pos -= dp[dir]; /* Retreat */ dir = (dir - 1) & 3; /* Turn right */ } } } /* Clean route and proposed obstacle */ *obs_pos = 0x20; for (pos = map; pos < end; ++pos) if (*pos & 0xf0) *pos &= 0xf0; } printf("%d\n", loops); return 0; }