Anonymous user
Talk:Railway circuit: Difference between revisions
no edit summary
(additional solutions?) |
No edit summary |
||
Line 58:
[[File:Railway_circuits_additional.gif]]<br>
[[User:Fwend|Fwend]] ([[User talk:Fwend|talk]]) 22:28, 5 April 2016 (UTC)
==All solutions are wrong==
As it stands, there's no correct implementation on the task page. This is partly due to the wrong math provided by the original implementation in EchoLisp, but also because none of the other solutions are doing the duplicate detection correctly. For example, take the 35 solutions shown on this talk page plus 5 more given by the Go program for the 24 segment case, the true solution indices are:
<code>
1 2 3 4 5 6 7 8 [4] [5]
[6] 9 10 [10] 11 12 [7] [8] [12] 13
14 15 16 [13] [15] 17 [16] 18 19 20
[18] [19] 21 [21] 22 23 24 25 26 27
</code>
where numbers not in brackets are true unique solutions, while ones in brackets indicate which solution it is a duplicate of, like: the 9th row provided on top of this page (his #8) is a mirror image of the 4th row (his #3). And the EchoLisp code evidently missed the last five solutions given by Go because the "right turn count in the last 6" check is insufficient. I have derived the correct mathematics (I believe) for the legality check of tracks without straights, but it's too large to fit in the margin here--I mean, rosettacode seems broken in the equations department. Anyhow, here's the python code plotting the solutions:
<lang python>import matplotlib.pyplot as plt
import numpy as np
sstr='''1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1
1 1 1 1 1 1 -1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 -1 1
1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 1 -1 1 -1 -1 1 1
1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 -1 1
1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1
1 1 1 1 1 1 -1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 -1 1
1 1 1 1 1 1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1
1 1 1 1 1 1 -1 -1 1 -1 1 1 1 1 1 1 1 1 -1 -1 1 -1 1 1
1 1 1 1 1 1 -1 -1 1 -1 1 1 1 1 1 1 1 -1 1 1 -1 -1 1 1
1 1 1 1 1 1 -1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1
1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 1 -1 -1 -1 1 1 1
1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 -1 1
1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1
1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1
1 1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1
1 1 1 1 1 -1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 -1 1 1
1 1 1 1 1 -1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1
1 1 1 1 1 -1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1
1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 1 -1 -1 1 1 1 -1 1
1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1
1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1
1 1 1 1 -1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 -1 1
1 1 1 1 -1 1 1 1 -1 -1 1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1
1 1 1 1 -1 1 1 1 -1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1
1 1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1
1 1 1 1 -1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 -1 1
1 1 1 1 -1 -1 1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 -1 1
1 1 1 1 -1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 -1 1
1 1 1 -1 1 1 1 1 -1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 -1 1
1 1 1 -1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 1 -1 -1 1 1
1 1 1 -1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 -1 1
1 1 1 -1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 1 -1 1 1 -1 1
1 1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 -1 1
1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1
1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1
1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1
1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1
1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1
1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1'''
sols24 = [tuple(int(s) for s in l.split()) for l in sstr.split('\n')]
sin = lambda x: np.sin(x/180*np.pi)
cos = lambda x: np.cos(x/180*np.pi)
def plot_sol(ax, s):
m = 2*sin(15)
xe, ye = [0], [0]
angle = -15
for d in s:
norm_angle = angle + d*90
trav_angle = angle + d*15
new_angle = angle + d*30
xc = xe[-1] + cos(norm_angle)
yc = ye[-1] + sin(norm_angle)
xe.append(xe[-1] + m*cos(trav_angle))
ye.append(ye[-1] + m*sin(trav_angle))
theta = np.linspace(0, 30, 5)
a = angle + d*(theta - 90)
ax.plot(xc + cos(a), yc + sin(a), 'r' if d==1 else 'b')
angle = new_angle
ax.plot(xe, ye, 'k.', markersize=1)
def count_turns(s):
if all(x == 1 for x in s):
return (0, -len(s))
if all(x == -1 for x in s):
return (0, -len(s))
while s[0] == 1:
s = s[1:] + s[:1]
while s[-1] == -1:
s = s[-1:] + s[:-1]
want = -1
idx = [0]
for i, v in enumerate(s):
if v != want:
idx.append(i)
want = -want
idx.append(len(s))
diff = [b - a for a, b in zip(idx, idx[1:])]
for i in range(1, len(diff), 2):
diff[i] = -diff[i]
return tuple(diff)
seen = {}
def canonical(s):
a = min(s[i:] + s[:i] for i in range(0, len(s), 2))
s = s[::-1]
s = s[1:] + s[:1]
b = min(s[i:] + s[:i] for i in range(0, len(s), 2))
return min(a, b)
fig, ax = plt.subplots(5, 8)
for i, s in enumerate(sols24):
turns = count_turns(s)
t = canonical(turns)
if t in seen:
txt = f'[{seen[t]}]'
else:
seen[t] = len(seen) + 1
txt = f'{seen[t]}'
axis = ax[i//8][i%8]
plot_sol(axis, s)
axis.text(0, 0, txt)
print(f' {txt}'[-6:])
for a in ax:
for b in a:
b.axis('off')
b.set_aspect(1)
plt.show()</lang>
BTW, 27 is the correct answer for 24 track segments.
--[[User:Katzenbaer|Katzenbaer]] ([[User talk:Katzenbaer|talk]]) 08:10, 3 July 2022 (UTC)
| |||