Anonymous user
Railway circuit: Difference between revisions
→{{header|Python}}
m (→{{header|Phix}}: syntax coloured) |
|||
Line 1,373:
{1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1}}
</pre>
=={{header|Python}}==
<lang python>from itertools import count, islice
import numpy as np
from numpy import sin, cos, pi
def draw_all(sols):
import matplotlib.pyplot as plt
def draw_track(ax, s):
turn, xend, yend = 0, [0], [0]
for d in s:
x0, y0 = xend[-1], yend[-1]
a = turn*pi/6
cs, sn = cos(a), sin(a)
ang = a + d*pi/2
cx, cy = x0 + cos(ang), y0 + sin(ang)
da = np.linspace(ang, ang + d*pi/6, 5)
xs = cx - cos(da)
ys = cy - sin(da)
ax.plot(xs, ys, 'green' if d == -1 else 'orange')
xend.append(xs[-1])
yend.append(ys[-1])
turn += d
ax.plot(xend, yend, 'k.', markersize=1)
ax.set_aspect(1)
if (ls := len(sols)) > 1:
w, h = min((abs(w*2 - h*3) + abs(ls - w*h), w, h)
for w, h in ((w, (ls + w - 1)//w)
for w in range(1, ls + 1)))[1:]
fig, ax = plt.subplots(h, w)
for a in ax.ravel(): a.set_axis_off()
elif ls == 0:
return
else:
w = h = 1
fig, ax = plt.subplots(h, w)
ax = [[ax]]
for i, s in enumerate(sols):
draw_track(ax[i//w][i%w], s)
plt.show()
def match_up(this, that):
l_lo, l_hi = 0, 0
r_lo, r_hi = 0, 0
l_n = len(this)
r_n = len(that)
tol = 1e-3
while l_lo < l_n:
while l_hi < l_n and this[l_hi][0] - this[l_lo][0] <= tol:
l_hi += 1
while r_lo < r_n and that[r_lo][0] < this[l_lo][0] - tol:
r_lo += 1
r_hi = r_lo
while r_hi < r_n and that[r_hi][0] < this[l_lo][0] + tol:
r_hi += 1
for a in this[l_lo:l_hi]:
for b in that[r_lo:r_hi]:
if np.abs(a[1] + b[2]) < tol:
yield(a[-1] + b[-1])
r_lo = r_hi
l_lo = l_hi
def track_combo(left, right):
n = (left + right)//2
res = [[] for i in range(right + 1)]
alphas = np.exp(1j*np.pi/6*np.arange(12))
def half_track(m):
turns = tuple(1 - 2*(m>>i & 1) for i in range(n))
rcnt = np.cumsum(turns)%12
asum = np.sum(alphas[rcnt])
want = asum/alphas[rcnt[-1]]
return np.abs(asum), asum, want, turns
for i in range(1<<n):
b = i.bit_count()
if b <= right:
res[b].append(half_track(i))
for v in res: v.sort()
return res
def railway(n):
assert(n&1 == 0)
seen = {}
def record(s):
for q in [s, tuple(reversed(s))]:
for _ in range(len(q)):
seen[q] = True
q = q[1:] + q[:1]
for l in range(n//2, n + 1):
r = n - l
assert(l >= r)
if (l - r)%12 == 0:
res = track_combo(l, r)
for i, this in enumerate(res):
if 2*i < r: continue
that = res[r - i]
for s in match_up(this, that):
if s in seen: continue
yield s
record(s)
if l == r:
record(tuple(-a for a in s))
sols = []
for i, s in enumerate(railway(30)):
# should show 357 solutions for 30 tracks
print(i + 1, s)
sols.append(s)
# draw at most 40 solutions
draw_all(sols[:40])</lang>
=={{header|Racket}}==
| |||