# find-octo3g_no_golly.py
# Dave Greene port (no Golly) — pure Python
# Usage: update basepath and either rle_path or pat_coords, then run with Python 3.
#
# Notes:
# - This uses the same octohash algorithm as the original Golly script,
#   but implements pattern transforms, normalization, and canonicalization
#   in plain Python (lists/tuples/strings).
# - It reads the octohashes3g_*.txt files and prints/writes matches.

import hashlib
import os
import re
import sys

# ======= USER CONFIG =======
basepath = r"./octo3gdatabase"  # UPDATE THIS to your download location
# Either point rle_path to an RLE file containing the pattern to search, or
# set pat_coords to a list of (x,y) tuples representing live cells.
rle_path = r"./pat.txt"  # e.g. r"C:\patterns\mypattern.rle"
pat_coords = None  # e.g. [(0,0), (1,0), (2,0)]
# Save matched patterns as RLE files:
save_matches = False
output_dir = "./matches.txt"
# ===========================

octo3g_searchfiles = [
    "octohashes3g_0.txt","octohashes3g_1.txt","octohashes3g_2.txt","octohashes3g_3.txt","octohashes3g_4.txt",
    "octohashes3g_5.txt","octohashes3g_6.txt","octohashes3g_7.txt","octohashes3g_8.txt","octohashes3g_9.txt",
    "octohashes3g_10.txt","octohashes3g_11.txt","octohashes3g_12.txt","octohashes3g_13.txt","octohashes3g_14.txt",
    "octohashes3g_15.txt","octohashes3g_16.txt","octohashes3g_17.txt","octohashes3g_18.txt","octohashes3g_19.txt",
]

searchfiles = octo3g_searchfiles

NUMLINES = 464746

# Build chardict same mapping as original
chardict = {}
for i in range(37, 127):
    chardict[i - 37] = chr(i)
# patch special mappings
chardict[92 - 37] = "!"   # backslash -> "!"
chardict[39 - 37] = "#"   # apostrophe -> "#"
chardict[44 - 37] = "$"   # comma -> "$"

def get9char(inputstr: str) -> str:
    """Compute the 9-character base-90-style mapping used by octohash."""
    h = hashlib.sha1()
    # Use surrogatepass encoding to match the original behavior used when
    # hashing canonical strings that may contain surrogate-escaped bytes.
    h.update(inputstr.encode('utf-8', errors='surrogatepass'))
    # convert first seven bytes of SHA1 digest to an integer
    i = 0
    for b in h.digest()[:7]:
        i = i * 256 + b
    s = ""
    while len(s) < 9:
        d = i // 90
        r = i - d * 90
        s = chardict[r] + s
        i = (i - r) // 90
    return s

# Transform helpers ----------------------------------------------------------

def transform_cells(cells, a, b, c, d):
    """Apply linear transform to cells: x' = a*x + b*y, y' = c*x + d*y"""
    return [(a * x + b * y, c * x + d * y) for (x, y) in cells]

def translate_cells(cells, dx, dy):
    return [(x + dx, y + dy) for (x, y) in cells]

def normalize_cells(cells):
    """Shift cells so their min x and min y are 0 (equivalent to the shrink+transform translation in original)."""
    if not cells:
        return []
    xs = [x for x, y in cells]
    ys = [y for x, y in cells]
    minx = min(xs)
    miny = min(ys)
    return translate_cells(cells, -minx, -miny)

def cells_to_canonical_string(cells):
    """
    Produce a canonical string representation for a set of cells.
    The Golly script used str(g.transform(pat, deltax, deltay)) which is
    basically a Python list-like string of integers (x,y pairs). We'll
    produce a consistent representation using Python's str() of a
    flattened integer list [x1,y1,x2,y2,...].
    """
    # Note: this function is kept for compatibility but the new canonicalization
    # uses compute_canonical_str_from_cells (added below).
    if not cells:
        return "[]"
    sorted_cells = sorted(cells)
    return ",".join(f"{x}:{y}" for x, y in sorted_cells)

# RLE parsing (simple) -------------------------------------------------------

def parse_rle(path):
    """
    Minimal RLE parser that returns a list of live cell (x,y) coordinates.
    Handles only basic RLE (B3/S23 etc) — it ignores comments and header lines.
    """
    cells = []
    with open(path, "r") as f:
        header_parsed = False
        x = y = 0
        curx = 0
        cury = 0
        for line in f:
            line = line.strip()
            if not line or line.startswith("#"):
                continue
            if not header_parsed:
                # header like: x = 3, y = 3, rule = B3/S23
                if line.startswith("x"):
                    header_parsed = True
                    # reset positions
                    curx = 0
                    cury = 0
                    continue
            # parse RLE body
            i = 0
            count = ""
            while i < len(line):
                ch = line[i]
                if ch.isdigit():
                    count += ch
                elif ch in ("b", ".", "B"):  # dead cells
                    n = int(count) if count else 1
                    curx += n
                    count = ""
                elif ch in ("o", "O", "A", "C"):  # live cells
                    n = int(count) if count else 1
                    for k in range(n):
                        cells.append((curx, cury))
                        curx += 1
                    count = ""
                elif ch == "$":  # end of line, go to next row
                    n = int(count) if count else 1
                    cury += n
                    curx = 0
                    count = ""
                elif ch == "!":  # end of pattern
                    break
                # ignore whitespace
                i += 1
    return cells

# Octohash computation (no golly) -------------------------------------------

# orientations same as original (8)
ORIENTATIONS = [
    (1, 0, 0, 1),
    (0, -1, 1, 0),
    (-1, 0, 0, -1),
    (0, 1, -1, 0),
    (-1, 0, 0, 1),
    (1, 0, 0, -1),
    (0, 1, 1, 0),
    (0, -1, -1, 0),
]

def place_oriented_patterns(pat_cells):
    """
    Emulate the Golly code that places 8 oriented copies side-by-side with offsets ptr*2048,0.
    Return the list of composed cells for the whole placement (ptr increments per orientation).
    """
    composed = []
    ptr = 0
    spacing = 2048
    for a, b, c, d in ORIENTATIONS:
        # transform orientation
        trans = transform_cells(pat_cells, a, b, c, d)
        # place at offset (ptr*spacing, 0)
        off = (ptr * spacing, 0)
        trans_off = translate_cells(trans, off[0], off[1])
        composed.extend(trans_off)
        ptr += 1
    return composed

# New canonicalization & helper functions (match discovered variant) ---------
def _get9char_from_str(s: str) -> str:
    """Compute 9-char token from canonical string (explicit wrapper)."""
    h = hashlib.sha1()
    h.update(s.encode('utf-8', errors='surrogatepass'))
    i = 0
    for b in h.digest()[:7]:
        i = (i << 8) | b
    out = ""
    while len(out) < 9:
        d = i // 90
        r = i - d * 90
        out = chardict[r] + out
        i = (i - r) // 90
    return out

def _y_asc_x_asc_order(coords):
    """Return coords ordered by y ascending, then x ascending."""
    return sorted(coords, key=lambda p: (p[1], p[0]))

def compute_canonical_str_from_cells(pat_cells):
    """
    Compute canonical string for a pattern following the discovered variant:
      - build 8 oriented copies placed at ptr*2048 offsets
      - for each 2048x2048 selection:
          * collect cells relative to selection origin (x - rx0, y - ry0)
          * order by y asc, then x asc
          * translate by -firstpair (delta = first)
          * flatten to [x,y,x,y,...] and use Python's str(list)
      - return lexicographically smallest string across the 8 orientations
    """
    if not pat_cells:
        return "[]"

    # Compose 8 oriented copies side-by-side (reuse existing helper)
    composed = place_oriented_patterns(pat_cells)
    candidates = []
    for j in range(8):
        rx0 = 2048 * j - 1024
        ry0 = -1024
        rx1 = rx0 + 2048 - 1
        ry1 = ry0 + 2048 - 1
        region = []
        for (x, y) in composed:
            if rx0 <= x <= rx1 and ry0 <= y <= ry1:
                region.append((x - rx0, y - ry0))
        if not region:
            cand_flat = []
        else:
            ordered = _y_asc_x_asc_order(region)
            # delta = negative of the first pair
            deltax = -ordered[0][0]
            deltay = -ordered[0][1]
            transformed = [(int(x) + deltax, int(y) + deltay) for (x, y) in ordered]
            cand_flat = []
            for (x, y) in transformed:
                cand_flat.append(int(x))
                cand_flat.append(int(y))
        candidates.append(str(cand_flat))
    # choose lexicographically smallest canonical string
    return min(candidates)

def compute_octohash_from_cells(pat_cells):
    """Return the 9-char token (no leading space) for pat_cells using new canonicalization."""
    canstr = compute_canonical_str_from_cells(pat_cells)
    return _get9char_from_str(canstr)
# ---------------------------------------------------------------------------

def getoctohash(pat_cells):
    """
    Compute octohash string (leading space + 9-char token) for a pattern represented by list of (x,y).
    This wrapper preserves the original outward behavior (leading space).
    """
    token = compute_octohash_from_cells(pat_cells)
    return " " + token

# RLE writer for output matches (simple) ------------------------------------

def save_as_rle(cells, path, comment=None):
    """
    Very simple RLE writer: writes bounding-box and uses only 'o', 'b' encoding.
    """
    if not cells:
        with open(path, "w") as f:
            if comment:
                f.write("# " + comment + "\n")
            f.write("x = 0, y = 0\n!\n")
        return
    xs = [x for x, y in cells]
    ys = [y for x, y in cells]
    minx, miny = min(xs), min(ys)
    # translate to positive coords
    trans = translate_cells(cells, -minx, -miny)
    maxx = max(x for x, y in trans)
    maxy = max(y for x, y in trans)
    width = maxx + 1
    height = maxy + 1
    # build rows
    rows = []
    cellset = set(trans)
    for y in range(height):
        row = []
        run = 0
        for x in range(width):
            if (x, y) in cellset:
                if run > 0:
                    row.append(str(run))
                    row.append("b")
                    run = 0
                row.append("o")
            else:
                run += 1
        if run > 0:
            row.append(str(run))
            row.append("b")
        rows.append("".join(row))
    body = "$".join(rows) + "!"
    with open(path, "w") as f:
        if comment:
            f.write("# " + comment + "\n")
        f.write(f"x = {width}, y = {height}\n")
        f.write(body + "\n")

# Main search logic ---------------------------------------------------------

def main():
    # get pattern
    if rle_path:
        if not os.path.exists(rle_path):
            print(f"RLE file not found: {rle_path}", file=sys.stderr)
            return
        pat = parse_rle(rle_path)
    elif pat_coords:
        pat = list(pat_coords)
    else:
        print("No input pattern specified. Set rle_path or pat_coords in the script.", file=sys.stderr)
        return

    if not pat:
        print("Input pattern is empty — nothing to search for.", file=sys.stderr)
        return

    # compute octohash for the pattern
    print("Computing octohash for input pattern...")
    hv = getoctohash(pat)
    print("Octohash:", hv)

    # Prepare output storage
    matches = []
    if save_matches and not os.path.exists(output_dir):
        os.makedirs(output_dir)

    count = NUMLINES
    outptr = 0

    # Search files
    for fname in searchfiles:
        path = os.path.join(basepath, fname)
        if not os.path.exists(path):
            print(f"Warning: search file not found: {path}", file=sys.stderr)
            continue
        with open(path, "r", errors="replace") as f:
            for line in f:
                count -= 1
                if hv in line:
                    # line format: PATTERNSTRING <space> octohash ... (original uses first token as pattern)
                    parts = line.split()
                    if not parts:
                        continue
                    matchingpatstr = parts[0]
                    # original script used g.parse(matchingpat) to get cells from pattern string.
                    # The database pattern string looks like a string representation of a list of ints,
                    # e.g. "x y x y x y ..." or a Golly pattern string. We try to parse comma/space-separated ints.
                    parsed_cells = parse_pattern_string_to_cells(matchingpatstr)
                    matches.append((matchingpatstr, parsed_cells, fname))
                    outptr += 1
                # progress indicator roughly every 1000 lines
                if count % 10000 == 0:
                    print(f"Searching. Lines remaining: {count//10000}0K")

    # Output findings
    if outptr == 0:
        print(f"No matches found for {hv}")
    else:
        plural = "" if outptr == 1 else "s"
        all_matches = "!"
        print(f"Found {outptr} line{plural} matching {hv} in up to {NUMLINES} lines of the octo3obj database.")
        for idx, (patstr, cells, srcfile) in enumerate(matches, start=1):
            print(f"Match {idx}: {patstr}")
            if all_matches == "!":
                all_matches = patstr
            else:
                all_matches = all_matches[0:-1] + "20$" + patstr
        # Split rle body into lines of max 70 chars
        all_matches = re.sub(r'[\dabcdeo.$]{0,69}[abcdeo.$!]', r'\n\g<0>', all_matches, flags=re.IGNORECASE)
        if save_matches:
            # Write all_matches to output_dir
            with open(output_dir, "w") as f:
                f.write(all_matches)
            print(f"Wrote all matches to {output_dir}")
        else:
            print("All matches:")
            print(all_matches)

# Helper to parse the database pattern string into cells ---------------------

def parse_pattern_string_to_cells(s):
    """
    Attempt to parse the 'matchingpat' token from the database file into a list of (x,y) ints.
    The original DB token is often a string like:
      "[x y x y x y ...]" or something similar.
    This function attempts multiple simple heuristics:
      - strip surrounding [] or () and parse numbers
      - if the string is compact (no separators) we fall back to returning empty list
    """
    orig = s
    # remove wrapping quotes/brackets
    if s.startswith('"') and s.endswith('"'):
        s = s[1:-1]
    s = s.strip()
    if s.startswith("[") and s.endswith("]"):
        s = s[1:-1]
    # split on commas or spaces or colons
    import re
    parts = re.split(r"[,\s:]+", s.strip())
    nums = []
    for p in parts:
        if p == "":
            continue
        # some tokens include non-digit characters; try to strip non-numeric suffix/prefix
        m = re.match(r"(-?\d+)", p)
        if m:
            nums.append(int(m.group(1)))
        else:
            # can't parse this token; abort and return empty
            return []
    # expect even number for coordinate pairs
    if len(nums) % 2 != 0:
        # odd length — maybe the first element is a length or id, drop it if odd
        nums = nums[1:] if len(nums) > 1 else []
        if len(nums) % 2 != 0:
            return []
    cells = []
    for i in range(0, len(nums), 2):
        cells.append((nums[i], nums[i + 1]))
    return cells

if __name__ == "__main__":
    main()