Railway circuit: Difference between revisions

Content added Content deleted
(julia example)
m (→‎{{header|Phix}}: 50% faster)
Line 908: Line 908:
left = -1,
left = -1,
straight = 0
straight = 0

function normalize(sequence tracks)
integer size := length(tracks)
string a := repeat('?',size)
for i=1 to size do
a[i] = "abc"[tracks[i]+2]
end for
/* Rotate the array and find the lexicographically lowest order
to allow the hashmap to weed out duplicate solutions. */
string norm = a
for i=1 to size do
if a < norm then
norm = a
end if
a = a[2..$]&a[1]
end for
return norm
end function
function fullCircleStraight(sequence tracks, integer nStraight)
function fullCircleStraight(sequence tracks, integer nStraight)
if nStraight == 0 then
if nStraight == 0 then return true end if

return true
end if
-- do we have the requested number of straight tracks
integer count := 0
for i=1 to length(tracks) do
if tracks[i] == straight then
count += 1
end if
end for
if count != nStraight then
return false
end if
-- check symmetry of straight tracks: i and i + 6, i and i + 4
-- check symmetry of straight tracks: i and i + 6, i and i + 4
sequence straightTracks =repeat(0,12)
sequence straightTracks =repeat(0,12)
Line 955: Line 922:
if idx<0 then exit end if
if idx<0 then exit end if
end for
end for
bool any1 = false, any2 = false
bool any = false
for i=1 to 6 do
for i=1 to 6 do
if straightTracks[i] != straightTracks[i+6] then
if straightTracks[i] != straightTracks[i+6] then
any1 = true
any = true
exit
exit
end if
end if
end for
end for
if not any then return true end if
any = false
for i=1 to 8 do
for i=1 to 8 do
if straightTracks[i] != straightTracks[i+4] then
if straightTracks[i] != straightTracks[i+4] then
any2 = true
any = true
exit
exit
end if
end if
end for
end for
return not any1 or not any2
return not any
end function
end function
function fullCircleRight(sequence tracks)
function fullCircleRight(sequence tracks)
-- all tracks need to add up to a multiple of 360
-- all tracks need to add up to a multiple of 360, aka 12*30
integer tot := 0
integer tot := 0
for i=1 to length(tracks) do
for i=1 to length(tracks) do
tot += tracks[i] * 30
tot += tracks[i]
end for
end for
if mod(tot,360)!=0 then
if mod(tot,12)!=0 then
return false
return false
end if
end if
Line 991: Line 960:
if idx<0 then exit end if
if idx<0 then exit end if
end for
end for
bool any1 = false, any2 = false
bool any = false
for i=1 to 6 do
for i=1 to 6 do
if rTurns[i] != rTurns[i+6] then
if rTurns[i] != rTurns[i+6] then
any1 = true
any = true
exit
exit
end if
end if
end for
end for
if not any then return true end if
any = false
for i=1 to 8 do
for i=1 to 8 do
if rTurns[i] != rTurns[i+4] then
if rTurns[i] != rTurns[i+4] then
any2 = true
any = true
exit
exit
end if
end if
end for
end for
return not any1 or not any2
return not any
end function
end function
integer carry = 0, lc, sdx, tStraight
procedure report(sequence sol, integer numC, numS)
sequence choices, indices, tracks
integer size := length(sol)
string s = iff(size=1?"":"s")
printf(1,"\n%d solution%s for C%d,%d \n", {size, s, numC, numS})
if numC <= 20 then
pp(sol)
end if
end procedure
enum NumPositions, choices, indices, sequnce, carry
function next(sequence p)
procedure next(integer nStraight)
p[carry] = 1
/* The generator skips the first index, so the result will always start
/* The generator skips the first index, so the result will always start
with a right turn (0) and we avoid clockwise/counter-clockwise
with a right turn (0) and we avoid clockwise/counter-clockwise
duplicate solutions. */
duplicate solutions. */
for i=2 to length(p[indices]) do
while true do
p[indices][i] += p[carry]
carry = 1
p[carry] = 0
for i=2 to length(indices) do
integer ii = indices[i]+1
if p[indices][i] != length(p[choices]) then exit end if
p[carry] = 1
if ii<=lc then
p[indices][i] = 0
indices[i] = ii
tracks[i] = choices[ii]
end for
tStraight += (ii=sdx)
for j=1 to length(p[indices]) do
p[sequnce][j] = p[choices][p[indices][j]+1]
carry = 0
end for
exit
return p
end if
indices[i] = 1
end function
tracks[i] = choices[1]
if sdx then
tStraight -= 1
end if
end for
if carry or (tStraight=nStraight) then exit end if
end while
end procedure
procedure circuits(integer nCurved, nStraight)
function hasNext(sequence p)
atom t0 = time()
return p[carry] != 1
integer seen = new_dict()
end function
sequence solutions = {}

integer nCS = nCurved+nStraight
function NewPermutationsGen(integer numPositions, sequence choices)
if mod(nCS-12,4)!=0 then
sequence indices := repeat(0, numPositions),
sequnce := repeat(0, numPositions)
integer carry := 0
return {numPositions, choices, indices, sequnce, carry}
end function

function getPermutationsGen(integer nCurved, nStraight)
if mod(nCurved+nStraight-12,4)!=0 then
crash("input must be 12 + k * 4")
crash("input must be 12 + k * 4")
end if
end if
sequence trackTypes
switch nStraight do
switch nStraight do
case 0: trackTypes = {right, left}
case 0: choices = {right, left}
case 12: trackTypes = {right, straight}
case 12: choices = {right, straight}
default: trackTypes = {right, left, straight}
default: choices = {right, left, straight}
end switch
end switch
lc = length(choices)
return NewPermutationsGen(nCurved+nStraight, trackTypes)
sdx = find(straight,choices)
end function
tStraight = 0

indices := repeat(1, nCS)
procedure circuits(integer nCurved, nStraight)
integer norms = new_dict()
tracks := repeat(right, nCS)
sequence solutions = {},
carry := 0
while carry=0 do
gen := getPermutationsGen(nCurved, nStraight)
while hasNext(gen) do
next(nStraight)
gen = next(gen)
sequence tracks := gen[sequnce]
if fullCircleStraight(tracks, nStraight)
if fullCircleStraight(tracks, nStraight)
and fullCircleRight(tracks) then
and fullCircleRight(tracks) then
string norm = normalize(tracks)
if getd_index(tracks,seen)=0 then
if getd_index(norm,norms)=0 then
setd(norm,true,norms) -- (data (=true) is ignored)
solutions = append(solutions,tracks)
solutions = append(solutions,tracks)
-- mark all rotations seen
for i=1 to nCS do
setd(tracks,true,seen) -- (data (=true) is ignored)
tracks = tracks[2..$]&tracks[1]
end for
end if
end if
end if
end if
end while
end while
destroy_dict(norms)
destroy_dict(seen)
integer ls := length(solutions)
report(solutions, nCurved, nStraight)
string s = iff(ls=1?"":"s")
printf(1,"\n%d solution%s for C%d,%d \n", {ls, s, nCurved, nStraight})
if nCurved <= 20 then
pp(solutions,{pp_Nest,1})
end if
end procedure
end procedure

for n=12 to 28 by 4 do
for n=12 to 28 by 4 do
circuits(n, 0)
circuits(n,0)
end for
end for
circuits(12, 4)</lang>
circuits(12,4)</lang>
{{out}}
{{out}}
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/Railway_circuit"