advent3.c

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 20
#define MASK ((1L<<N) - 1)
static struct {
    short x, y, wire;
} table[1L<<N];

static size_t
find(int x, int y)
{
    unsigned long s = x*0x414caee9UL ^ y*0x6a899563UL;
    size_t i = s & MASK;
    for (;;) {
        if (!table[i].wire) {
            table[i].x = x;
            table[i].y = y;
            return i;
        }
        if (table[i].x == x && table[i].y == y) {
            return i;
        }
        i = (s = s*0x166c5445UL + 1)>>(32 - N) & MASK;
    }
}

int
main(void)
{
    int id = 1;
    int x = 0, y = 0;
    long max = LONG_MAX;

    char dir;
    int steps;
    while (scanf(" %c%d", &dir, &steps) == 2) {
        static const int tx[] = {+1, +0, +0, -1};
        static const int ty[] = {+0, +1, -1, +0};
        int dx = tx[(dir>>2&3) + (dir&1)];
        int dy = ty[(dir>>2&3) + (dir&1)];

        while (steps--) {
            size_t t = find(x += dx, y += dy);
            if (table[t].wire && table[t].wire != id) {
                long dist = labs(x) + labs(y);
                if (dist < max) {
                    max = dist;
                }
            }
            table[t].wire = id;
        }

        if (getchar() != ',') {
            id++;
            x = y = 0;
        }
    }

    printf("%ld\n", max);
    return 0;
}