mersenneforum.org April 2020
 Register FAQ Search Today's Posts Mark Forums Read

 2020-06-03, 21:16 #45 uau   Jan 2017 2·37 Posts Here's the first version of the code I used for the challenge (original 10 days before the correction to 19): Code: #!/usr/bin/python3 import numpy as np import itertools import sys def calc(adj): step = np.identity(128) idx = np.arange(128) for i in range(8): if i == 0: rows = np.ones(128, dtype=bool) else: rows = (idx & (1 << (i-1))).astype(bool) for j in range(1, 8): if not adj[i, j]: continue cols = (idx & (1 << (j-1)) == 0) x = step[np.ix_(rows, cols)] * 0.1 step[np.ix_(rows, cols)] -= x step[np.ix_(rows, cols==False)] += x step = np.linalg.matrix_power(step, 10) return step[0, 127] def marksmall(toosmall, perms, i): for j in range(28): if not i & (1< #include #include int a[5040][28]; int seen[1<<28]; int main(void) { for (int i = 0; i < 5040; i++) for (int j = 0; j < 28; j++) { int k; scanf("%d", &k); a[i][j] = 1 << k; } for (int i = 1; i < (1<<28); i++) { if (seen[i]) continue; for (int j = 0; j < 5040; j++) { int s = 0; for (int k = 0; k < 28; k++) s += (1 << k) * (bool)(i & a[j][k]); seen[s] = i; } } int l = fwrite(seen, sizeof(int), 1<<28, stdout); assert(l == 1<<28); return 0; } All permutations of the vertex order are equivalent to some permutation of adjacency matrix bits. The Python program writes those permutations to file "/tmp/perms.txt"; the C program can then be used to process that to "/tmp/perms.data" (it uses stdin/stdout, so it's called like "./a.out /tmp/perms.data"). The data file can then be interpreted as a table of integers, mapping each adjacency matrix to the canonical one of its class (each matrix mapped to an integer by reading the bit values in the upper triangle in order). The Python program thus uses simple table lookup to get the canonical form of any adjacency matrix. With the original 10 days limit, the problem is solvable within a few seconds. Most adjacency matrices have a probability below the target 0.7, and turning off any bits lowers the probability. Thus the program searches through all possible matrices in descending order, and when a matrix gets a probability <= 0.7, then it knows that all matrices obtained by turning off a bit have an even lower probability. The search space is originally 228 (28=8*7/2 bits in the adjacency matrix for edges), but most are ruled out as either not canonical after permuting vertex order, or by the <= 0.7 logic (implemented by the marksmall() function). If you increase the number of days from 10 to 19, the smallness cutoff is no longer as effective, and it'll take minutes instead of seconds.

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 4 2020-09-23 08:59 ewmayer Soap Box 308 2020-09-14 23:50 what Puzzles 1 2020-04-24 05:46 what Puzzles 20 2020-03-04 07:55 what Puzzles 21 2020-02-02 14:11

All times are UTC. The time now is 20:55.

Sun Sep 27 20:55:31 UTC 2020 up 17 days, 18:06, 0 users, load averages: 1.12, 1.33, 1.50