Railway circuit: Difference between revisions
m
→{{header|Phix}}: 50% faster
(julia example) |
m (→{{header|Phix}}: 50% faster) |
||
Line 908:
left = -1,
straight = 0
function fullCircleStraight(sequence tracks, integer nStraight)
if nStraight == 0 then return true end if
-- check symmetry of straight tracks: i and i + 6, i and i + 4
sequence straightTracks =repeat(0,12)
Line 955 ⟶ 922:
if idx<0 then exit end if
end for
bool
for i=1 to 6 do
if straightTracks[i] != straightTracks[i+6] then
exit
end if
end for
if not any then return true end if
any = false
for i=1 to 8 do
if straightTracks[i] != straightTracks[i+4] then
exit
end if
end for
return not
end function
function fullCircleRight(sequence tracks)
-- all tracks need to add up to a multiple of 360, aka 12*30
integer tot := 0
for i=1 to length(tracks) do
tot += tracks[i]
end for
if mod(tot,
return false
end if
Line 991 ⟶ 960:
if idx<0 then exit end if
end for
bool
for i=1 to 6 do
if rTurns[i] != rTurns[i+6] then
exit
end if
end for
if not any then return true end if
any = false
for i=1 to 8 do
if rTurns[i] != rTurns[i+4] then
exit
end if
end for
return not
end function
integer carry = 0, lc, sdx, tStraight
sequence choices, indices, tracks
/* 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. */
integer ii = indices[i]+1
tracks[i] = choices[ii]
tStraight += (ii=sdx)
indices[i] = 1
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)
atom t0 = time()
integer seen = new_dict()
sequence solutions = {}
integer nCS = nCurved+nStraight
if mod(nCS-12,4)!=0 then
crash("input must be 12 + k * 4")
end if
switch nStraight do
case 0:
case 12:
default:
end switch
lc = length(choices)
sdx = find(straight,choices)
tStraight = 0
indices := repeat(1, nCS)
while carry=0 do
if fullCircleStraight(tracks, nStraight)
and fullCircleRight(tracks) then
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 while
destroy_dict(
integer ls := length(solutions)
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
for n=12 to 28 by 4 do
circuits(n,
end for
circuits(12,
{{out}}
<pre>
|