#!/usr/bin/env python3 """A plain starting point: simulated annealing on the smallest triangle, in floating point. Usage: search.py N [SEED] [STEPS] > n.txt (a few seconds for the defaults) It finds valid configurations some way below the best known ones. What it prints is judged by ../verify.py, exactly. """ import itertools import math import random import sys def smallest(p): return min(abs((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2 for a, b, c in itertools.combinations(p, 3)) def anneal(n, seed=0, steps=100000): rng = random.Random(seed) p = [(rng.random(), rng.random()) for _ in range(n)] now = best = smallest(p) kept = p[:] for k in range(steps): heat = 1e-3 ** (1 + k / steps) # the temperature falls from 1e-3 to 1e-6 step = 0.2 * 0.005 ** (k / steps) # and the moves shrink from 0.2 to 0.001 i = rng.randrange(n) old = p[i] p[i] = tuple(min(1.0, max(0.0, c + rng.gauss(0, step))) for c in old) new = smallest(p) if new >= now or rng.random() < math.exp((new - now) / heat): now = new if new > best: best, kept = new, p[:] else: p[i] = old return best, kept if __name__ == "__main__": if len(sys.argv) < 2: sys.exit(__doc__.strip()) given = [int(a) for a in sys.argv[1:4]] n, seed, steps = given + [0, 100000][len(given) - 1:] best, kept = anneal(n, seed, steps) print(f"# n = {n}: smallest triangle about {best:.6f}, found by examples/search.py {n} {seed} {steps}") for x, y in kept: print(f"{x:.6f} {y:.6f}")