/*
 * bedrock_finder.c — locate a Minecraft chunk from a bedrock pattern.
 *
 * Uses the seed-independent bedrock generation algorithm of pre-1.18 Java
 * Edition (Overworld Y=4 / Nether floor / Nether roof top layer): the
 * 1-in-5 bedrock distribution depends only on chunk (x, z) — not on the
 * world seed — so a sufficiently distinctive pattern uniquely identifies
 * a chunk.
 *
 * Algorithm adapted from ChromeCrusher / DaPorkchop_'s bedrock.c.
 *
 * --- HOW TO FILL IN THE PATTERN ---
 *   Edit the PATTERN[] array below.  Each row is a C string of equal length.
 *   Characters:
 *       'X'  = bedrock present at that block
 *       '_'  = no bedrock (any other block)
 *       '?'  = unknown (wildcard — will match either)
 *   Width and height are inferred automatically.  Max width/height = 16
 *   (one chunk).  Smaller patterns work too but produce more false positives;
 *   ~8x8 of certain cells is usually enough to be unique.
 *
 *   Orientation:  rows go top-to-bottom = North-to-South in-game,
 *                 cols go left-to-right = West-to-East.
 *   If you don't know which direction is north, the search tries all
 *   4 rotations and their reflections (8 variants total).
 *
 * --- COMPILE & RUN ---
 *   gcc -O3 -o bedrock_finder bedrock_finder.c
 *   ./bedrock_finder              # default search radius (10000 chunks)
 *   ./bedrock_finder 50000        # custom radius in chunks
 *   ./bedrock_finder 50000 2      # custom radius + allow N mismatches
 */

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* ============================================================== */
/* ===================== EDIT YOUR PATTERN HERE ================= */
/* ============================================================== */
static const char *PATTERN[] = {
    "??_X_?X_",
    "__X___X_",
    "________",
    "X_______",
    "_X_X____",
    "_______X",
    "_X_X_X__",
    "X_X_____",
    "X_____X_",
    "X_______",
    "__X_____",
    "_X______",
    "________",
};
/* ============================================================== */

#define WILDCARD 2
#define BEDROCK  1
#define EMPTY    0
#define MAX_DIM  16

/* dihedral group: 4 rotations x 2 reflections */
#define NUM_VARIANTS 8
static int variants[NUM_VARIANTS][MAX_DIM * MAX_DIM];
static int var_rows[NUM_VARIANTS], var_cols[NUM_VARIANTS];

static int pat_rows, pat_cols;
static int base_pattern[MAX_DIM * MAX_DIM];

/* ---- pattern transforms ---- */
static void rotate90(const int *in, int in_r, int in_c,
                     int *out, int *out_r, int *out_c) {
    *out_r = in_c;
    *out_c = in_r;
    for (int i = 0; i < in_r; i++)
        for (int j = 0; j < in_c; j++)
            out[j * in_r + (in_r - 1 - i)] = in[i * in_c + j];
}
static void flip_h(const int *in, int rows, int cols, int *out) {
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            out[i * cols + (cols - 1 - j)] = in[i * cols + j];
}

/* ---- parse PATTERN[] into base_pattern[] ---- */
static int load_pattern(void) {
    pat_rows = sizeof(PATTERN) / sizeof(PATTERN[0]);
    if (pat_rows == 0 || pat_rows > MAX_DIM) {
        fprintf(stderr, "Pattern row count %d out of range [1, %d]\n", pat_rows, MAX_DIM);
        return -1;
    }
    pat_cols = (int) strlen(PATTERN[0]);
    if (pat_cols == 0 || pat_cols > MAX_DIM) {
        fprintf(stderr, "Pattern col count %d out of range [1, %d]\n", pat_cols, MAX_DIM);
        return -1;
    }
    for (int i = 0; i < pat_rows; i++) {
        if ((int) strlen(PATTERN[i]) != pat_cols) {
            fprintf(stderr, "Row %d width mismatch (got %zu, expected %d)\n",
                    i, strlen(PATTERN[i]), pat_cols);
            return -1;
        }
        for (int j = 0; j < pat_cols; j++) {
            char c = PATTERN[i][j];
            int v;
            if (c == 'X' || c == 'x')      v = BEDROCK;
            else if (c == '_' || c == '.') v = EMPTY;
            else if (c == '?')             v = WILDCARD;
            else {
                fprintf(stderr, "Bad char '%c' at (%d,%d)\n", c, i, j);
                return -1;
            }
            base_pattern[i * pat_cols + j] = v;
        }
    }
    return 0;
}

static void build_variants(void) {
    /* variants 0..3 = rotations of original */
    memcpy(variants[0], base_pattern, sizeof(int) * pat_rows * pat_cols);
    var_rows[0] = pat_rows;
    var_cols[0] = pat_cols;
    for (int r = 1; r < 4; r++) {
        rotate90(variants[r - 1], var_rows[r - 1], var_cols[r - 1],
                 variants[r], &var_rows[r], &var_cols[r]);
    }
    /* variants 4..7 = rotations of horizontally flipped original */
    int flipped[MAX_DIM * MAX_DIM];
    flip_h(base_pattern, pat_rows, pat_cols, flipped);
    memcpy(variants[4], flipped, sizeof(int) * pat_rows * pat_cols);
    var_rows[4] = pat_rows;
    var_cols[4] = pat_cols;
    for (int r = 5; r < 8; r++) {
        rotate90(variants[r - 1], var_rows[r - 1], var_cols[r - 1],
                 variants[r], &var_rows[r], &var_cols[r]);
    }
    /* deduplicate identical variants (e.g. symmetric patterns) */
    for (int i = 0; i < NUM_VARIANTS; i++) {
        for (int j = 0; j < i; j++) {
            if (var_rows[i] == var_rows[j] && var_cols[i] == var_cols[j] &&
                memcmp(variants[i], variants[j], sizeof(int) * var_rows[i] * var_cols[i]) == 0) {
                var_rows[i] = 0; /* mark as duplicate */
                break;
            }
        }
    }
}

/* ---- generate top-layer bedrock pattern for one chunk ---- */
static int chunk_buf[16 * 16];

static void gen_chunk(int64_t x, int64_t z) {
    int64_t seed = (x * 341873128712LL + z * 132897987541LL) ^ 0x5DEECE66DLL;
    for (int a = 0; a < 16; a++) {
        for (int b = 0; b < 16; b++) {
            seed = seed * 709490313259657689LL + 1748772144486964054LL;
            seed = seed & ((1LL << 48) - 1);
            chunk_buf[a * 16 + b] = (4 <= ((seed >> 17) % 5)) ? 1 : 0;
            seed = seed * 5985058416696778513LL + -8542997297661424380LL;
        }
    }
}

/* ---- try one variant at one (oy, ox) offset within current chunk ---- */
static int try_offset(const int *pat, int rows, int cols,
                      int oy, int ox, int max_mismatch) {
    int mism = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int pv = pat[i * cols + j];
            if (pv == WILDCARD) continue;
            if (pv != chunk_buf[(oy + i) * 16 + (ox + j)]) {
                if (++mism > max_mismatch) return -1;
            }
        }
    }
    return mism;
}

int main(int argc, char **argv) {
    int radius = (argc > 1) ? atoi(argv[1]) : 10000;
    int max_mismatch = (argc > 2) ? atoi(argv[2]) : 0;

    if (load_pattern() != 0) return 1;
    build_variants();

    fprintf(stderr, "Pattern: %d rows x %d cols\n", pat_rows, pat_cols);
    fprintf(stderr, "Search:  chunk x,z in [-%d, %d]\n", radius, radius);
    fprintf(stderr, "Allowed mismatches per match: %d\n\n", max_mismatch);

    clock_t t0 = clock();
    long total_found = 0;

    for (int64_t cz = -radius; cz <= radius; cz++) {
        for (int64_t cx = -radius; cx <= radius; cx++) {
            gen_chunk(cx, cz);
            for (int v = 0; v < NUM_VARIANTS; v++) {
                int prows = var_rows[v], pcols = var_cols[v];
                if (prows == 0) continue; /* deduped */
                for (int oy = 0; oy <= 16 - prows; oy++) {
                    for (int ox = 0; ox <= 16 - pcols; ox++) {
                        int m = try_offset(variants[v], prows, pcols, oy, ox, max_mismatch);
                        if (m >= 0) {
                            int64_t bx = cx * 16 + ox;
                            int64_t bz = cz * 16 + oy;
                            printf("MATCH chunk=(%lld, %lld)  variant=%d  "
                                   "offset=(row=%d, col=%d)  block_nw=(%lld, %lld)  mismatches=%d\n",
                                   (long long) cx, (long long) cz, v, oy, ox,
                                   (long long) bx, (long long) bz, m);
                            fflush(stdout);
                            total_found++;
                        }
                    }
                }
            }
        }
        if ((cz & 0xff) == 0) {
            double dt = (double) (clock() - t0) / CLOCKS_PER_SEC;
            fprintf(stderr, "  z=%lld   found=%ld   t=%.1fs\n",
                    (long long) cz, total_found, dt);
        }
    }

    double dt = (double) (clock() - t0) / CLOCKS_PER_SEC;
    fprintf(stderr, "\nDone. Total matches: %ld   (%.1fs)\n", total_found, dt);
    return total_found > 0 ? 0 : 2;
}