/* Jonathan Frech, 2021-06-11, 2021-06-12 */
/* best compiled with: % cc -Wall -Wpedantic -Wextra -Werror -O3 */

#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define N ((int64_t) (2+3+2))

typedef enum { WOOD, HOLE, PIN } board_t;
typedef enum { RIGHT, UP, LEFT, DOWN } compass_t;
typedef uint64_t move_t;
typedef uint32_t color_t;

void initialize_board(board_t board[N*N]) {
    board_t w = WOOD, h = HOLE, p = PIN;
    memcpy(board, (board_t[N*N]) {
        w,w,p,p,p,w,w,
        w,w,p,p,p,w,w,
        p,p,p,p,p,p,p,
        p,p,p,h,p,p,p,
        p,p,p,p,p,p,p,
        w,w,p,p,p,w,w,
        w,w,p,p,p,w,w,
    }, (size_t) (N*N) * sizeof (board_t));
}
#define PIN_COUNT_GOAL ((size_t) 1)


/* querying hopefully high-quality randomness */
FILE *DEV_URANDOM = NULL;
uint64_t unif(uint64_t n) {
    if (n <= 0)
        return 0;

    if (!DEV_URANDOM)
        DEV_URANDOM = fopen("/dev/urandom", "rb");
    if (!DEV_URANDOM)
        return fprintf(stderr, "cannot open /dev/urandom\n"), 0;

    uint8_t log = 0;
    for (uint64_t m = n; m; m >>= 1)
        ++log;
    uint64_t mask = (1ULL << log) - 1;
    uint8_t bytes = log / 8 + !!(log % 8);

    for (;;) {
        uint64_t r = 0;
        for (uint8_t b = 0; b < bytes; ++b) {
            int c = fgetc(DEV_URANDOM);
            if (c == EOF) {
                fprintf(stderr, "cannot read /dev/urandom\n");
                break;
            }

            r <<= 8;
            r |= c & 0xff;
        }

        r &= mask;
        if (r > n)
            continue;

        return r;
    }
}

/* caching randomness */
#define CACHED_RANDOMNESS (true)
#define URANGE ((uint64_t) (N*N*4-1))
#define UBUFFER_SIZE ((size_t) (1ULL << 20))
uint64_t UBUFFER[UBUFFER_SIZE];
uint64_t *PUBUFFER = NULL;
uint64_t UNIF_URANGE() {
    if (PUBUFFER == NULL || PUBUFFER >= UBUFFER+UBUFFER_SIZE) {
        PUBUFFER = NULL;
        for (size_t j = 0; j < UBUFFER_SIZE; ++j)
            UBUFFER[j] = unif(URANGE);
        PUBUFFER = &UBUFFER[0];
    }

    return *PUBUFFER++;
}


board_t get(board_t board[N*N], int64_t x, int64_t y) {
    if (x < 0 || x >= N || y < 0 || y >= N)
        return WOOD;
    return board[x +N* y];
}

void set(board_t board[N*N], int64_t x, int64_t y, board_t v) {
    if (x < 0 || x >= N || y < 0 || y >= N)
        return;
    board[x +N* y] = v;
}

int64_t   dot_x(move_t move) { return (int64_t)   (move       % N); }
int64_t   dot_y(move_t move) { return (int64_t)   ((move/N  ) % N); }
compass_t dot_d(move_t move) { return (compass_t) ((move/N/N) % 4); }


bool valid_move(board_t board[N*N], move_t move) {
    if (get(board, dot_x(move), dot_y(move)) != PIN)
        return false;

    switch (dot_d(move)) {
#define R(DX, DY) \
    return get(board, dot_x(move)+  (DX), dot_y(move)+  (DY)) == PIN \
        && get(board, dot_x(move)+2*(DX), dot_y(move)+2*(DY)) == HOLE
    case RIGHT: R(+1, 0);
    case UP:    R(0, -1);
    case LEFT:  R(-1, 0);
    case DOWN:  R(0, +1);
#undef R
    }

    return false;
}

void apply_move(board_t board[N*N], move_t move) {
    if (!valid_move(board, move))
        return;

    switch (dot_d(move)) {
#define R(DX, DY) \
    set(board, dot_x(move)       , dot_y(move)       , HOLE); \
    set(board, dot_x(move)+  (DX), dot_y(move)+  (DY), HOLE); \
    set(board, dot_x(move)+2*(DX), dot_y(move)+2*(DY), PIN); break
    case RIGHT: R(+1, 0);
    case UP:    R(0, -1);
    case LEFT:  R(-1, 0);
    case DOWN:  R(0, +1);
#undef R
    }
}

size_t count_pins(board_t board[N*N]) {
    size_t count = 0;
    for (int64_t y = 0; y < N; ++y)
        for (int64_t x = 0; x < N; ++x)
            count += get(board, x, y) == PIN;

    return count;
}


void print_board(FILE *f, board_t board[N*N]) {
    for (int64_t y = 0; y < N; ++y) {
        for (int64_t x = 0; x < N; ++x) {
            switch (get(board, x, y)) {
            case WOOD: fputc(' ', f); break;
            case HOLE: fputc('.', f); break;
            case PIN:  fputc('#', f); break;
            default:   fputc('?', f);
            }
            fputc(' ', f);
        }
        fputc('\n', f);
    }
    fputc('\n', f);
}

void print_move(FILE *f, move_t move) {
    fprintf(f, "x%" PRId64 "y%" PRId64, dot_x(move), dot_y(move));
    switch (dot_d(move)) {
    case RIGHT: fputc('R', f); break;
    case UP:    fputc('U', f); break;
    case LEFT:  fputc('L', f); break;
    case DOWN:  fputc('D', f); break;
    default:    fputc('?', f);
    }
}


void visualize(move_t *beg, move_t *end) {
    uint8_t log10n = 0;
    for (int64_t n = N; n; n /= 10)
        log10n++;
    size_t move_char_len = 1+log10n+1+log10n+1+1;
    size_t ext_len = 4;
    size_t n_moves = end-beg;

    char *fn = malloc((n_moves*move_char_len + ext_len) * sizeof *fn);
    if (!fn) {
        fprintf(stderr, "memory exhaustion\n"); return; }

    size_t cell_n = 2 * n_moves;
    color_t *img = calloc(N*N * cell_n*cell_n, sizeof *img);
    if (!img) {
        free(fn), fprintf(stderr, "memory exhaustion\n"); return; }

    for (size_t j = 0; j < n_moves; ++j) {
        move_t mov = beg[j];

        snprintf(fn+move_char_len*j, move_char_len+1, "x%dy%d%c-",
            (int) dot_x(mov), (int) dot_y(mov), "ruld"[dot_d(mov)]);

        int r = 64 + j*(255-64)/(n_moves-1);
        int b = 255 - r;
        int g = 255 - (r+b)/3;
        color_t c = (r<<16) | (g<<8) | b;

        size_t dx = dot_x(mov)*cell_n, dy = dot_y(mov)*cell_n;
        for (size_t i = j; i <= cell_n-j; ++i) {
#define C(DIRECTION) if (dot_d(mov) != DIRECTION)
            C(RIGHT) img[(dx + cell_n-j) +N*cell_n* (dy + i)]        = c;
            C(UP)    img[(dx + i)        +N*cell_n* (dy + j)]        = c;
            C(LEFT)  img[(dx + j)        +N*cell_n* (dy + i)]        = c;
            C(DOWN)  img[(dx + i)        +N*cell_n* (dy + cell_n-j)] = c;
#undef C
        }
    }
    snprintf(fn+move_char_len*n_moves-1, ext_len+1, ".ppm");

    fprintf(stderr, "saving file: %s\n", fn);
    FILE *f = fopen(fn, "wb");
    if (!f) {
        free(fn), free(img), fprintf(stderr, "failed to open file\n"); return; }

    fprintf(f, "P3 %zu %zu 255\n", (size_t) (N*cell_n), (size_t) (N*cell_n));
    for (size_t y = 0; y < N*cell_n; ++y)
        for (size_t x = 0; x < N*cell_n; ++x) {
            color_t c = img[x +N*cell_n* y];
            fprintf(f, "%d %d %d\n", (c>>16) & 0xff, (c>>8) & 0xff, c & 0xff);
        }

    free(fn), free(img);
}


int main() {
    board_t board[N*N];
    move_t moves[N*N*4], *pmoves;

    do {
        initialize_board(board);
        pmoves = &moves[0];

        for (;;) {
            move_t move0 = CACHED_RANDOMNESS ? UNIF_URANGE() : unif(N*N*4-1);
            for (
                move_t move = (move0+1) % (N*N*4);
                move != move0;
                move = (move+1) % (N*N*4)
            ) {
                if (valid_move(board, move)) {
                    apply_move(board, move);
                    *pmoves++ = move;
                    goto moved;
                }
            }
            break; moved: continue;
        }
    } while (count_pins(board) > PIN_COUNT_GOAL);

    fprintf(stderr, "final board:\n");
    print_board(stderr, board);

    visualize(moves, pmoves);

    if (DEV_URANDOM)
        fclose(DEV_URANDOM);
}