#!/usr/bin/env python3 """exact75.py -- independent enumeration of the closed trails of length at most 20 (check of the first row of Table tab:tail). Hexagon accepts only scripts and data files of a few types as ancillary files, so the C program exact75.c is stored in this file verbatim, as the string C_SOURCE below. Its sha256 digest is 6a01e44d63085e4fdc0a6a8aea81376e9e9fa85f4b70069c71a83abe6052a94b This script writes exact75.c to a directory, compiles it with gcc -O2 -frounding-math -ffp-contract=off exact75.c -lm -o exact75 runs the program with the arguments given, and passes its standard output and standard error through unchanged. Written from the definition of the weighted trail sums, independently of tailmem5.c. For one pair type X and one first direction D0 it prints, for each even n <= N, the number of closed trails and several weighted sums; the last column (optimal_h, the per-trail optimal ordering) is the quantity that tailmem5.c computes in its lines "E n value". Usage: python3 exact75.py --print-source print exact75.c to standard output and exit python3 exact75.py --write-source DIR write DIR/exact75.c and exit python3 exact75.py [--workdir DIR] [--cc CC] [--compile-only] [--verbose] [--] X N cs ct a b hB hC D0 NOPT --workdir DIR build in DIR and keep exact75.c and the binary there (default: a temporary directory that is removed at the end) --cc CC the C compiler (default gcc; the flags above are always used) --compile-only compile and exit --verbose print the compiler command and the compiler's messages to standard error The compiler and floating-point environment must honor directed rounding. Keep -frounding-math and -ffp-contract=off when compiling with GCC. Example (the recorded run, see jobs.yaml): python3 exact75.py B 20 0.961 0.935 0.16666666666666667 0.36 1 1.25 1 20 > exact75_B_1.log """ import hashlib, os, shutil, subprocess, sys, tempfile NAME = 'exact75' CFLAGS = ['-O2', '-frounding-math', '-ffp-contract=off'] LIBS = ['-lm'] SHA256 = '6a01e44d63085e4fdc0a6a8aea81376e9e9fa85f4b70069c71a83abe6052a94b' C_SOURCE = r'''/* exact75.c -- independent exact enumeration of the pair-response kernel M_1 (write-up sec7, eq. e:kernel) for one row X in {B, C} and one first-direction class D0 (0 = E, 1 = N, 2 = W, 3 = S; -1 = all), written from the definition (not from any earlier program). Kernel trail: w = (v_0 = u, ..., v_n = v) in Z^2 \ {c}, bond-self-avoiding, v_i != v for i < n. Passage i (step out of v_i): revisit if v_i in {v_0..v_{i-1}} (weight 1/5), else first visit (FV) of type straight / turn w.r.t. the arrival direction (c -> u for i = 0). FV pairs: (f,g) coefficient a, (f,o), (g,o) coefficient b, f, g the neighbours other than the arrival site and o; a pair is dead if it contains c or a site left twice before passage i (= visited at two times < i). kappa_h = sum over live pairs of coef * (h_B if collinear else h_C). Term of (w, k): 3^{-n} (3/5)^{rev} kappa(sigma(k)) prod_{l <= k} x_{sigma(l)}. Outputs per even n: number of closed trails; mass = sum 3^{-n}(3/5)^rev prod_{all FV} x; forward-order kernel columns (K_B, K_C); straights-first h-weighted value; per-trail optimal-order h-weighted value (n <= NOPT). Arithmetic: double, rounding mode UPWARD throughout (all quantities nonnegative), so every printed number is an upper bound of the exact one (printf also rounds upward under glibc). Pruning: a prefix at L1 distance > N - n from v cannot close by length N. Usage: exact75 X N cs ct a b hB hC D0 NOPT [a_s b_s b'_s a_t b_t b'_t] (type-dependent coefficients: pair coefficients of the passage's own type; if exactly one of f, g is dead the surviving pair gets b') */ #include #include #include #include static void set_rounding(int mode) { if (fesetround(mode) != 0) { fprintf(stderr, "could not set floating-point rounding mode %d\n", mode); exit(EXIT_FAILURE); } } #define G 80 #define O 40 static const int DX[4] = {1, 0, -1, 0}, DY[4] = {0, 1, 0, -1}; static int N, NOPT, D0; static double xs, xt, A, Bc, hB, hC, w3, w5; static int TD = 0; static double TA[2], TB[2], TBP[2]; /* type-dependent coefficients [0] straight, [1] turn */ static int cx = O, cy = O, ux = O - 1, uy = O, vx, vy; static unsigned char hb[G][G], vb[G][G]; /* bond (x,y)-(x+1,y), (x,y)-(x,y+1) used */ static int vis[G][G]; /* number of visits so far (times < current time, plus current) */ static int px[64], py[64], pdir[64]; static long cnt[64]; static double mass[64], fwB[64], fwC[64], sf[64], opt[64]; static unsigned char *bond(int x, int y, int d) { if (d == 0) return &hb[x][y]; if (d == 2) return &hb[x - 1][y]; if (d == 1) return &vb[x][y]; return &vb[x][y - 1]; } static int iabs(int z) { return z < 0 ? -z : z; } /* coefficient-weighted response of a first-visit passage at (x,y) with arrival direction ain and out direction d, at time n (dead: c, or a site with >= 2 visits at times < n). Returns kB, kC (unweighted by h). */ static void response(int x, int y, int ain, int d, double *kB, double *kC) { int back = (ain + 2) & 3, fxs[2], fys[2], nf = 0; for (int e = 0; e < 4; e++) if (e != back && e != d) { fxs[nf] = x + DX[e]; fys[nf] = y + DY[e]; nf++; } int ox = x + DX[d], oy = y + DY[d]; int P[3][4] = {{fxs[0], fys[0], fxs[1], fys[1]}, {fxs[0], fys[0], ox, oy}, {fxs[1], fys[1], ox, oy}}; int deadf = (fxs[0] == cx && fys[0] == cy) || vis[fxs[0]][fys[0]] >= 2; int deadg = (fxs[1] == cx && fys[1] == cy) || vis[fxs[1]][fys[1]] >= 2; int ty = (d == ain) ? 0 : 1; *kB = 0; *kC = 0; for (int q = 0; q < 3; q++) { int dead = (q == 0) ? (deadf || deadg) : (q == 1 ? deadf : deadg); if (dead) continue; double co; if (!TD) co = (q == 0) ? A : Bc; else co = (q == 0) ? TA[ty] : ((deadf || deadg) ? TBP[ty] : TB[ty]); if (P[q][0] == P[q][2] || P[q][1] == P[q][3]) *kB += co; else *kC += co; } } typedef struct { double key, x, w; } item; static int cmpi(const void *a, const void *b) { double d = ((const item *)a)->key - ((const item *)b)->key; return d < 0 ? -1 : d > 0; } /* per-trail optimal order (ascending (x-1)/w, w = x kappa_h), recomputed from the stored path */ static double optimal_value(int n) { static int tv[G][G]; memset(tv, 0, sizeof tv); item it[64]; int ni = 0, nrev = 0; for (int i = 0; i < n; i++) { int x = px[i], y = py[i]; if (tv[x][y] > 0) { nrev++; tv[x][y]++; continue; } int ain = (i == 0) ? 2 : pdir[i - 1], d = pdir[i]; double xx = (d == ain) ? xs : xt; /* response with the visit counts at times < i */ int back = (ain + 2) & 3, fxs[2], fys[2], nf = 0; for (int e = 0; e < 4; e++) if (e != back && e != d) { fxs[nf] = x + DX[e]; fys[nf] = y + DY[e]; nf++; } int ox = x + DX[d], oy = y + DY[d]; int P[3][4] = {{fxs[0], fys[0], fxs[1], fys[1]}, {fxs[0], fys[0], ox, oy}, {fxs[1], fys[1], ox, oy}}; double kh = 0; int deadf = (fxs[0] == cx && fys[0] == cy) || tv[fxs[0]][fys[0]] >= 2; int deadg = (fxs[1] == cx && fys[1] == cy) || tv[fxs[1]][fys[1]] >= 2; int ty = (d == ain) ? 0 : 1; for (int q = 0; q < 3; q++) { int dead = (q == 0) ? (deadf || deadg) : (q == 1 ? deadf : deadg); if (dead) continue; double co; if (!TD) co = (q == 0) ? A : Bc; else co = (q == 0) ? TA[ty] : ((deadf || deadg) ? TBP[ty] : TB[ty]); kh += co * ((P[q][0] == P[q][2] || P[q][1] == P[q][3]) ? hB : hC); } tv[x][y]++; double w = xx * kh; it[ni].key = (w > 0) ? (xx - 1) / w : 1e300; it[ni].x = xx; it[ni].w = w; ni++; } qsort(it, ni, sizeof it[0], cmpi); double tot = 0, pre = 1; for (int k = 0; k < ni; k++) { tot += it[k].w * pre; pre *= it[k].x; } double base = 1; for (int i = 0; i < n - nrev; i++) base *= w3; for (int i = 0; i < nrev; i++) base *= w5; return tot * base; } /* state carried along the prefix: full (all FV exposed) mass; forward pre / post-B / post-C; straights-first phases A, B (pre), C, D (post, h-weighted) */ static void dfs(int x, int y, int n, double full, double fpre, double fpB, double fpC, double sA, double sB, double sC, double sD) { if (x == vx && y == vy) { cnt[n]++; mass[n] += full; fwB[n] += fpB; fwC[n] += fpC; sf[n] += sC + sD; if (n <= NOPT) opt[n] += optimal_value(n); return; } if (n == N) return; if (iabs(x - vx) + iabs(y - vy) > N - n) return; int revisit = vis[x][y] > 0; px[n] = x; py[n] = y; vis[x][y]++; for (int d = 0; d < 4; d++) { if (n == 0 && D0 >= 0 && d != D0) continue; int nx = x + DX[d], ny = y + DY[d]; if (nx == cx && ny == cy) continue; unsigned char *b = bond(x, y, d); if (*b) continue; double f2, p2, pB2, pC2, a2, b2, c2, d2; if (revisit) { f2 = full * w5; p2 = fpre * w5; pB2 = fpB * w5; pC2 = fpC * w5; a2 = sA * w5; b2 = sB * w5; c2 = sC * w5; d2 = sD * w5; } else { int ain = (n == 0) ? 2 : pdir[n - 1]; double kB, kC; vis[x][y]--; /* response uses visit counts at times < n (current site excluded) */ response(x, y, ain, d, &kB, &kC); vis[x][y]++; double kh = kB * hB + kC * hC; int straight = (d == ain); double xx = straight ? xs : xt, wx = xx * w3; f2 = full * wx; p2 = fpre * wx; pB2 = fpB * w3 + p2 * kB; pC2 = fpC * w3 + p2 * kC; if (straight) { a2 = sA * wx; b2 = sB * wx; c2 = sC * wx; d2 = sD * w3 + b2 * kh; } else { a2 = sA * wx; b2 = sB * w3; c2 = sC * w3 + a2 * kh; d2 = sD * w3; } } pdir[n] = d; *b = 1; dfs(nx, ny, n + 1, f2, p2, pB2, pC2, a2, b2, c2, d2); *b = 0; } vis[x][y]--; } int main(int argc, char **argv) { if (argc < 11) { fprintf(stderr, "usage: exact75 X N cs ct a b hB hC D0 NOPT\n"); return 1; } char X = argv[1][0]; N = atoi(argv[2]); double cs = atof(argv[3]), ct = atof(argv[4]); A = atof(argv[5]); Bc = atof(argv[6]); hB = atof(argv[7]); hC = atof(argv[8]); D0 = atoi(argv[9]); NOPT = atoi(argv[10]); if (N > 60) return 1; if (argc >= 17) { TD = 1; for (int q = 0; q < 2; q++) { TA[q] = atof(argv[11 + 3 * q]); TB[q] = atof(argv[12 + 3 * q]); TBP[q] = atof(argv[13 + 3 * q]); } } set_rounding(FE_UPWARD); /* the decimal arguments are taken as exact: cs, ct are lower bounds, so 1/cs rounded up is an upper bound provided atof(cs) <= cs; we lower cs by a relative 1e-15 to be safe, and raise a, b likewise */ volatile double one = 1.0, three = 3.0, five = 5.0, eps = 1e-15; cs = cs * (one - eps); ct = ct * (one - eps); A = A * (one + eps); Bc = Bc * (one + eps); for (int q = 0; q < 2; q++) { TA[q] *= one + eps; TB[q] *= one + eps; TBP[q] *= one + eps; } xs = one / cs; xt = one / ct; w3 = one / three; w5 = one / five; vx = (X == 'B') ? O + 1 : O; vy = (X == 'B') ? O : O + 1; dfs(ux, uy, 0, 1, 1, 0, 0, 1, 1, 0, 0); printf("# exact75 X=%c N=%d cs=%s ct=%s a=%s b=%s h=(%s,%s) D0=%d NOPT=%d\n", X, N, argv[3], argv[4], argv[5], argv[6], argv[7], argv[8], D0, NOPT); printf("# n count mass fwd_KB fwd_KC straightsfirst_h optimal_h\n"); for (int n = 1; n <= N; n++) if (cnt[n]) printf("%d %ld %.15e %.15e %.15e %.15e %.15e\n", n, cnt[n], mass[n], fwB[n], fwC[n], sf[n], n <= NOPT ? opt[n] : 0.0); return 0; } ''' def main(argv): workdir, cc, compile_only, verbose = None, 'gcc', False, False i = 0 while i < len(argv): a = argv[i] if a == '--print-source': sys.stdout.write(C_SOURCE) return 0 if a == '--write-source': os.makedirs(argv[i + 1], exist_ok=True) with open(os.path.join(argv[i + 1], NAME + '.c'), 'w') as f: f.write(C_SOURCE) return 0 if a == '--workdir': workdir = argv[i + 1]; i += 2; continue if a == '--cc': cc = argv[i + 1]; i += 2; continue if a == '--compile-only': compile_only = True; i += 1; continue if a == '--verbose': verbose = True; i += 1; continue if a == '--': i += 1 break args = argv[i:] if not compile_only and not args: sys.stderr.write(__doc__) return 1 tmp = workdir is None d = tempfile.mkdtemp(prefix=NAME + '-') if tmp else os.path.abspath(workdir) os.makedirs(d, exist_ok=True) try: with open(os.path.join(d, NAME + '.c'), 'w') as f: f.write(C_SOURCE) cmd = [cc] + CFLAGS + [NAME + '.c'] + LIBS + ['-o', NAME] r = subprocess.run(cmd, cwd=d, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, universal_newlines=True) if verbose or r.returncode != 0: sys.stderr.write('cd %s && %s\n%s' % (d, ' '.join(cmd), r.stdout)) if r.returncode != 0: sys.stderr.write('%s.py: compilation failed\n' % NAME) return 1 if compile_only: return 0 sys.stdout.flush() return subprocess.run([os.path.join(d, NAME)] + args).returncode finally: if tmp: shutil.rmtree(d, ignore_errors=True) if __name__ == '__main__': if hashlib.sha256(C_SOURCE.encode('ascii')).hexdigest() != SHA256: sys.exit('%s.py: the stored C source does not match its sha256 digest' % NAME) sys.exit(main(sys.argv[1:]))