meetStructuresInMiddle.py

import itertools
import random
import time

A = 0x5deece66d
B = 11
LCG_MOD_POW = 48
M = 2**LCG_MOD_POW
BIG_MASK = M - 1

LUT_BITS = 24 # With enough ram you can push this higher.
assert LUT_BITS > 17
NUM_PORTALS = 6
LARGEST_REGION = 100

_RESULT_CARRY = pow(2, LCG_MOD_POW-17, 25)
_SMALL_MASK = (1 << LUT_BITS) - 1
_SCRAMBLER_UPPER = A >> LUT_BITS

class Random:
    def __init__(self, seed):
        self.seed = (seed ^ A) & BIG_MASK

    def _next(self):
        self.seed = (self.seed * A + B) & BIG_MASK
        return self.seed

    def next_int(self, n):
        return (self._next() >> 17) % n


def ruined_portal(seed_plus_structure_salt, region_salt):
    r = Random(seed_plus_structure_salt + region_salt)
    return r.next_int(25), r.next_int(25)


def build_LUT( measurements):
    LUT = {}
    checkpoint = time.time()
    start_time = checkpoint
    for lower_bits in range(1 << LUT_BITS):
        if lower_bits % 100000 == 0:
            print(lower_bits, time.time() - checkpoint, time.time() - start_time)
            checkpoint = time.time()
        # For each lower bit, we must compute at each location a "compatibility certificate" to compare with the
        # upper bits.
        # This means:
        # Recording if the lower bits would cause a carry at each location,
        # Recording the required offset mod 25 the upper bits must contribute to produce a valid seed
        # Recording for which upper bits and where we'd have sum overflow 2^48, affecting the value modulo 25
        carries, targets = get_lower_signature(lower_bits, measurements)
        if carries not in LUT:
            LUT[carries] = [None for _ in range(25)] #TODO this data structure is completely idiotic, and only done out of desperation that python lists might be less memory intense.
        node = LUT[carries]
        for t in targets[:-1]:
            if node[t] is None:
                node[t] = [None for _ in range(25)]
            node = node[t]
        if node[targets[-1]] is None:
            node[targets[-1]] = []
        node[targets[-1]] += [lower_bits]
    print(f"LUT building took {time.time() - start_time}")
    return LUT

def get_lower_signature(lower_bits, measurements):
    carries = []
    targets = []
    for region_salt, vals in measurements:
        rx, rz = vals
        # can cache region salt and related variables if need be
        region_salt_lower = region_salt & _SMALL_MASK
        # Though it seems exponential, only linearly many of these can occur.
        carries.append(1 if lower_bits + region_salt_lower > _SMALL_MASK else 0)
        s = ((lower_bits + region_salt_lower) ^ A) & _SMALL_MASK
        s1 = (A * s + B) & BIG_MASK
        s2 = (A * s1 + B) & BIG_MASK
        target1 = (rx - (s1 >> 17)) % 25 #actual rng call is (s1 >> 17) % 25 # A * (s1 + s2) + B = As1 + As2 + B
        target2 = (rz - (s2 >> 17)) % 25 # A(A * (s1 + s2) + B) = A^2 s1 + A^2 s2 + AB + B
        targets.append(target1)
        targets.append(target2)
    return tuple(carries), targets

def get_upper_signature(upper_bits, carry_pattern, upper_salts):
    signature = []
    for n in range(NUM_PORTALS):
        s = (((carry_pattern[n] + upper_salts[n] + upper_bits) ^ _SCRAMBLER_UPPER) << LUT_BITS) & BIG_MASK
        s1 = (A * s) & BIG_MASK #NO +B because lcgs are only affine linear, not linear, and the +B is already in the lower_bits
        s2 = (A * s1) & BIG_MASK
        signature.append((s1 >> 17) % 25)
        signature.append((s2 >> 17) % 25)
    return signature

def traverse_LUT(upper_signature, LUT, index):
    if index == len(upper_signature):
        return LUT
    result = []
    if LUT[upper_signature[index]] is not None:
        result += traverse_LUT(upper_signature, LUT[upper_signature[index]], index+1)
    if  LUT[(upper_signature[index] - _RESULT_CARRY) % 25] is not None:
        result += traverse_LUT(upper_signature, LUT[(upper_signature[index] - _RESULT_CARRY) % 25], index+1)
    return result

def get_compatible_seeds_with_given_upper_bits(upper, salts, LUT):
    lowers = []
    upper_salts = [salt >> LUT_BITS for salt in salts]

    for carry_pattern in LUT.keys():
        signature = get_upper_signature(upper, carry_pattern, upper_salts)
        lowers += traverse_LUT(signature, LUT[carry_pattern], 0)
    result = []
    for lower in lowers:
       # print(lower, len(lowers))
        result += [(upper << LUT_BITS) + lower]
    return result

def is_valid(seed, measurements):
    return all(ruined_portal(seed, salt) == target for salt, target in measurements)


def get_all_seeds(salts, coords_in_region):
    candidates = []
    measurements = [c for c in zip(salts, coords_in_region)]
    LUT = build_LUT(measurements)
    print("LUT MADE!")
    start_time = time.time()
    checkpoint = start_time
    result = []
    for upper in range(1 << (LCG_MOD_POW - LUT_BITS)):
        if upper % 100000 == 0:
            print(upper, time.time() - checkpoint, time.time() - start_time)
            checkpoint = time.time()
        if len(get_compatible_seeds_with_given_upper_bits(upper, salts, LUT)) > 0:
            print(get_compatible_seeds_with_given_upper_bits(upper, salts, LUT))
            result += get_compatible_seeds_with_given_upper_bits(upper, salts, LUT)
    print(result)
    result = [seed for seed in result if is_valid(seed, measurements)]
    print(result)
    print(f"Upper half finding took {time.time() - start_time}")
    return result

def main():
    seed = random.randint(0, 2 ** LCG_MOD_POW)
    print(seed)
    region_coords = [(random.randint(-LARGEST_REGION, LARGEST_REGION + 1), random.randint(-LARGEST_REGION, LARGEST_REGION + 1))
              for _ in range(NUM_PORTALS)]
    salts = [(x * 341873128712 + z * 132897987541) % M for x, z in region_coords]
    chunk_coords = [ruined_portal(seed, region_salt) for region_salt in salts]
    assert seed in get_all_seeds(salts, chunk_coords)


if __name__ == "__main__":
    main()