Railway circuit: Difference between revisions
→{{header|Phix}}
(Added Go) |
|||
Line 750:
1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0
1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0
</pre>
=={{header|Phix}}==
{{trans|Go}}
<lang Phix>constant right = 1,
left = -1,
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)
if nStraight == 0 then
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
sequence straightTracks =repeat(0,12)
integer idx = 0
for i=1 to length(tracks) do
if tracks[i] == straight then
straightTracks[mod(idx,12)+1] += 1
end if
idx += tracks[i]
if idx<0 then exit end if
end for
bool any1 = false, any2 = false
for i=1 to 6 do
if straightTracks[i] != straightTracks[i+6] then
any1 = true
exit
end if
end for
for i=1 to 8 do
if straightTracks[i] != straightTracks[i+4] then
any2 = true
exit
end if
end for
return not any1 or not any2
end function
function fullCircleRight(sequence tracks)
-- all tracks need to add up to a multiple of 360
integer tot := 0
for i=1 to length(tracks) do
tot += tracks[i] * 30
end for
if mod(tot,360)!=0 then
return false
end if
-- check symmetry of right turns: i and i + 6, i and i + 4
sequence rTurns = repeat(0,12)
integer idx = 0
for i=1 to length(tracks) do
if tracks[i] == right then
rTurns[mod(idx,12)+1] += 1
end if
idx += tracks[i]
if idx<0 then exit end if
end for
bool any1 = false, any2 = false
for i=1 to 6 do
if rTurns[i] != rTurns[i+6] then
any1 = true
exit
end if
end for
for i=1 to 8 do
if rTurns[i] != rTurns[i+4] then
any2 = true
exit
end if
end for
return not any1 or not any2
end function
procedure report(sequence sol, integer numC, numS)
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)
p[carry] = 1
/* The generator skips the first index, so the result will always start
with a right turn (0) and we avoid clockwise/counter-clockwise
duplicate solutions. */
for i=2 to length(p[indices]) do
p[indices][i] += p[carry]
p[carry] = 0
if p[indices][i] != length(p[choices]) then exit end if
p[carry] = 1
p[indices][i] = 0
end for
for j=1 to length(p[indices]) do
p[sequnce][j] = p[choices][p[indices][j]+1]
end for
return p
end function
function hasNext(sequence p)
return p[carry] != 1
end function
function NewPermutationsGen(integer numPositions, sequence choices)
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")
end if
sequence trackTypes
switch nStraight do
case 0: trackTypes = {right, left}
case 12: trackTypes = {right, straight}
default: trackTypes = {right, left, straight}
end switch
return NewPermutationsGen(nCurved+nStraight, trackTypes)
end function
procedure circuits(integer nCurved, nStraight)
integer norms = new_dict()
sequence solutions = {},
gen := getPermutationsGen(nCurved, nStraight)
while hasNext(gen) do
gen = next(gen)
sequence tracks := gen[sequnce]
if fullCircleStraight(tracks, nStraight)
and fullCircleRight(tracks) then
string norm = normalize(tracks)
if getd_index(norm,norms)=0 then
setd(norm,true,norms) -- (data (=true) is ignored)
solutions = append(solutions,tracks)
end if
end if
end while
destroy_dict(norms)
report(solutions, nCurved, nStraight)
end procedure
for n=12 to 28 by 4 do
circuits(n, 0)
end for
circuits(12, 4)</lang>
{{out}}
<pre>
1 solution for C12,0
{{1,1,1,1,1,1,1,1,1,1,1,1}}
1 solution for C16,0
{{1,-1,1,1,1,1,1,1,1,-1,1,1,1,1,1,1}}
6 solutions for C20,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,1,1,1,-1,-1,1,1,1,1,1,1},
{1,-1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,1,1,1,1,1},
{1,-1,1,1,1,-1,1,1,1,1,1,-1,1,1,1,-1,1,1,1,1},
{1,-1,1,1,1,1,-1,1,1,1,1,-1,1,1,1,1,-1,1,1,1}}
40 solutions for C24,0
243 solutions for C28,0
4 solutions for C12,4
{{1,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1},
{1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1},
{1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1},
{1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1}}
</pre>
| |||