#!/usr/bin/env python3 """Sound randomised repair (min-conflicts with tabu) on the bar window, per-offset COUNT update (job #2105, route 90). State: residues res[k] for the first n primes; window [start, start+R); offset j covered iff some prime p has (start+j) == +-1 (mod p) under the residue convention of repair90c.py (class c covers offsets == c - v mod p ...), implemented by reusing repair90c's Cov.pos_of so the semantics are identical to the corrected engine. Each step: pick a random current hole, evaluate every covering move (all primes, both classes) by the exact count update, take the best non-tabu move (fewest resulting holes; ties random), tabu the prime for T steps; restart from the best state after `patience` non-improving steps. Reports the minimum hole count reached, with the state. Usage: minconf2105.py --start 17 --R 2489 --secs 600 --seed 1 """ import sys, os, json, time, random, argparse import numpy as np sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import importlib.util spec = importlib.util.spec_from_file_location('rc', os.path.join(os.path.dirname(os.path.abspath(__file__)), 'repair90c.py')) rc = importlib.util.module_from_spec(spec); spec.loader.exec_module(rc) def run(start, R, secs, seed, tabu_T=6, patience=400): st = json.load(open(os.path.join(os.path.dirname(os.path.abspath(__file__)), 'state-n25.json'))) res0 = st['residues'] if 'residues' in st else st cov = rc.Cov(res0, start, R) rng = random.Random(seed) cur = list(cov.res); cnt = cov.cnt0.copy() holes = int((cnt == 0).sum()); best = holes; best_state = list(cur) tabu = {}; t0 = time.time(); steps = 0; since_improve = 0; restarts = 0 hist = {} while time.time() - t0 < secs: steps += 1 hl = np.flatnonzero(cnt == 0) if hl.size == 0: best = 0; best_state = list(cur); break i = int(rng.choice(list(hl))) cands = [(k, v) for (k, v) in cov.candidates_for(i) if tabu.get(k, -1) < steps] if not cands: cands = cov.candidates_for(i) # exact evaluation of every candidate by count update scored = [] for (k, v) in cands: c = cnt.copy() c[cov.pos_of(k, cur[k])] -= 1; c[cov.pos_of(k, v)] += 1 scored.append((int((c == 0).sum()), rng.random(), k, v)) scored.sort() h, _, k, v = scored[0] cnt[cov.pos_of(k, cur[k])] -= 1; cnt[cov.pos_of(k, v)] += 1; cur[k] = v tabu[k] = steps + tabu_T holes = h; hist[holes] = hist.get(holes, 0) + 1 if holes < best: best = holes; best_state = list(cur); since_improve = 0 else: since_improve += 1 if since_improve > patience: cur = list(best_state); cov2 = rc.Cov(cur, start, R); cnt = cov2.cnt0.copy(); cov.pos = cov2.pos since_improve = 0; restarts += 1 # perturb: one random move k = rng.randrange(cov.n); v = rng.randrange(rc.PRIMES[k]); cnt[cov.pos_of(k, cur[k])] -= 1; cnt[cov.pos_of(k, v)] += 1; cur[k] = v # verify best state from scratch covb = rc.Cov(best_state, start, R) return dict(start=start, R=R, seed=seed, secs=round(time.time() - t0, 1), steps=steps, restarts=restarts, best_holes=best, best_holes_recomputed=covb.holes0, holes_at_start=cov.holes0, best_state=best_state, hole_histogram={str(k): v for k, v in sorted(hist.items())}) if __name__ == '__main__': ap = argparse.ArgumentParser(); ap.add_argument('--start', type=int, default=17); ap.add_argument('--R', type=int, default=2489) ap.add_argument('--secs', type=float, default=600); ap.add_argument('--seed', type=int, default=1) a = ap.parse_args() print(json.dumps(run(a.start, a.R, a.secs, a.seed)))