Talk:Railway circuit

From Rosetta Code

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)

What do you use to decide whether a mirror image can be dropped? Some paths are right and left handed. --Wherrera (talk) 08:34, 5 July 2022 (UTC)
If you take a solution in the form of a list of ±1s and flip the sign of each number, you get a mirror image. When checking if a solution or any of its rotations was previously seen, you need to also check the mirrored solutions. --Katzenbaer (talk) 15:24, 5 July 2022 (UTC)
Why eliminate a mirror image if it is not identical to its other-handed version? --Wherrera (talk) 17:17, 5 July 2022 (UTC)
Because the task specifically requires it: "Duplicates, either by symmetry, translation, reflexion, or rotation must be eliminated." --Katzenbaer (talk) 21:50, 5 July 2022 (UTC)
Interesting. I would usually say that this is a duplicate by reflection:
###
  #
###
  #
###

###
#
###
#
###
but this is not:
###
  #
###
  #
 ##

###
#
###
#
##
because the two are different on the plane (not in 3D). I wonder what the task author meant. --Wherrera (talk) 22:03, 5 July 2022 (UTC)
I would think duplicate by reflection is pretty unambiguous. In your examples, the first pair are already identical under rotation, so if the second pair were not considered duplicates by reflection, then why do we even have that term at all? --Katzenbaer (talk) 22:50, 5 July 2022 (UTC)
A right handed fur-lined glove can have a duplicate by rotation that is an exact duplicate. But it is not an exact duplicate of a left handed fur-lined glove, is it? I do understand your reading.--Wherrera (talk) 23:13, 5 July 2022 (UTC)
You are confusing "A becomes the same as B after reflection" with "A remains the same after reflection". A left handed glove looks like a right handed one in a mirror, no? You seem to suggest the task wants us to remove each solution that's its own mirror image, otherwise what's the distinction between "reflexion" and "rotation" in the wording in your opinion? --Katzenbaer
I also eliminated reflections that way (negation) in my much older code version, but today I wondered if we should; my `simulation intuitions` today tell me that in the model railroading world a reflection is probably considered a different layout if the links along the tracks are directed, so that since right and left curved sections are not interchangeable different numbers of components would be required. But ok, the task specifies it.

(talk) 04:24, 6 July 2022 (UTC)

Minimum example code showing the correct math for validity check. This code doesn't filter out duplicates and is of course horribly slow. <lang python>from itertools import product, accumulate from cmath import pi, exp

N = 12 # defines size of each turn; 12 means 30 degrees, but other turn angles work, too ANGLE = 2*pi/N

  1. 1: right; 0: straight; -1: left. Generates all combinations of them at given length.

sequences = lambda n: product(*([(1, 0, -1)]*n))

  1. Check the track combination is valid.
  2. This treatment requires the straight segment length equal the chord lengths of the arcs,
  3. otherwise the math is MUCH more complicated.

def valid(s):

   # a is the right turn count after each step
   a = tuple(accumulate(s))
   # "< 1e-6" really should have been "== 0" but for numerical precision
   return a[-1]%N == 0 and abs(sum(exp(x*1j*ANGLE) for x in a)) < 1e-6

for n in [12, 14]:

   print(f'{n} tracks:')
   for s in sequences(n):
       if valid(s):
           print(s)</lang>