Talk:Railway circuit: Difference between revisions
No edit summary |
mNo edit summary |
||
| Line 200: | Line 200: | ||
--[[User:Katzenbaer|Katzenbaer]] ([[User talk:Katzenbaer|talk]]) 08:10, 3 July 2022 (UTC) |
--[[User:Katzenbaer|Katzenbaer]] ([[User talk:Katzenbaer|talk]]) 08:10, 3 July 2022 (UTC) |
||
: What do you use to decide whether a mirror image can be dropped? Some paths are right and left handed. --[[User:Wherrera|Wherrera]] ([[User talk:Wherrera|talk]]) 08:34, 5 July 2022 (UTC) |
|||
Revision as of 08:34, 5 July 2022
C24 solutions
A very interesting and challenging task. Could you perhaps post the 35 solutions for C24? (Maybe on the talk page). I'm getting 38 :-) Fwend (talk) 23:32, 4 April 2016 (UTC)
- Here are my solutions :
(gen 24) gen-counters (2574175 . 286) Number of circuits C24 : 35 0 #( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) 1 #( 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1) 2 #( 1 1 1 1 1 1 -1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 -1 1) 3 #( 1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 1 -1 1 -1 -1 1 1) 4 #( 1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 -1 1) 5 #( 1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1) 6 #( 1 1 1 1 1 1 -1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 -1 1) 7 #( 1 1 1 1 1 1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1) 8 #( 1 1 1 1 1 1 -1 -1 1 -1 1 1 1 1 1 1 1 1 -1 -1 1 -1 1 1) 9 #( 1 1 1 1 1 1 -1 -1 1 -1 1 1 1 1 1 1 1 -1 1 1 -1 -1 1 1) 10 #( 1 1 1 1 1 1 -1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1) 11 #( 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 1 -1 -1 -1 1 1 1) 12 #( 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 -1 1) 13 #( 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1) 14 #( 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1) 15 #( 1 1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1) 16 #( 1 1 1 1 1 -1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 -1 1 1) 17 #( 1 1 1 1 1 -1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1) 18 #( 1 1 1 1 1 -1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1) 19 #( 1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 1 -1 -1 1 1 1 -1 1) 20 #( 1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1) 21 #( 1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1) 22 #( 1 1 1 1 -1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 -1 1) 23 #( 1 1 1 1 -1 1 1 1 -1 -1 1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1) 24 #( 1 1 1 1 -1 1 1 1 -1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1) 25 #( 1 1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1) 26 #( 1 1 1 1 -1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 -1 1) 27 #( 1 1 1 1 -1 -1 1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 -1 1) 28 #( 1 1 1 1 -1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 -1 1) 29 #( 1 1 1 -1 1 1 1 1 -1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 -1 1) 30 #( 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 1 -1 -1 1 1) 31 #( 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 -1 1) 32 #( 1 1 1 -1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 1 -1 1 1 -1 1) 33 #( 1 1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 -1 1) 34 #( 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1)
--G.Brougnard (talk) 08:33, 5 April 2016 (UTC)
- Thank you. I didn't have the two first ones, with the overlapping tracks. So now I do have 35 for C24 based on i + 6 symmetry. I've found 5 additional solutions, however, based on a 3-way symmetry of i + 4. They look valid to me, unless I've misunderstood the criteria:
1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1
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:
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
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.
--Katzenbaer (talk) 08:10, 3 July 2022 (UTC)