79 lines
2.9 KiB
Perl
79 lines
2.9 KiB
Perl
|
:- table direction_loop/1.
|
||
|
|
|
||
|
|
:- op(700, xfx, l).
|
||
|
|
:- op(700, xfx, r).
|
||
|
|
From l To :- From to To-_.
|
||
|
|
From r To :- From to _-To.
|
||
|
|
|
||
|
|
answer(Answer) :-
|
||
|
|
starts(Starts),
|
||
|
|
maplist([S, S-Off-Stride-Loop]>>(zloop([], S, 0, [], Off, Stride, Loop)),
|
||
|
|
Starts, Events),
|
||
|
|
maplist([Node, Node-0-0]>>(true), Starts, StartPositions),
|
||
|
|
next_zevent(Events, StartPositions, Answer).
|
||
|
|
|
||
|
|
next_zevent(AllZEvents, CurrPositions, Index) :-
|
||
|
|
maplist(index_of, AllZEvents, CurrPositions, Candidates),
|
||
|
|
writef('curr=%t, cand=%t, idx=%t\n', [CurrPositions, Candidates, Index]),
|
||
|
|
( same_elements(Candidates)
|
||
|
|
-> Candidates = [Index-_ | _]
|
||
|
|
; min_member(_-Z, Candidates),
|
||
|
|
member(Z-NLoops-SubLoop, CurrPositions),
|
||
|
|
member(Z-Offset-Stride-Loop, AllZEvents),
|
||
|
|
next(Z-Offset-Stride-Loop, Z-NLoops-SubLoop, Z-NextNLoops-NextSubLoop),
|
||
|
|
select(Z-_-_, CurrPositions, Z-NextNLoops-NextSubLoop, NextPositions),
|
||
|
|
% writef('next=%t, z=%t, idx=%t\n', [NextPositions, Z, Index]),
|
||
|
|
next_zevent(AllZEvents, NextPositions, Index)
|
||
|
|
).
|
||
|
|
|
||
|
|
index_of(A-Offset-Stride-Loop, A-NLoops-SubLoop, Index-A) :-
|
||
|
|
nth0(SubLoop, Loop, LoopPosition-_),
|
||
|
|
Index is Offset + NLoops*Stride + LoopPosition.
|
||
|
|
|
||
|
|
next(A-_-_-Loop, A-NLoops-SubLoop, A-NextNLoops-NextSubLoop) :-
|
||
|
|
length(Loop, LoopLen),
|
||
|
|
( SubLoop < LoopLen - 1
|
||
|
|
-> NextNLoops is NLoops, NextSubLoop is SubLoop + 1
|
||
|
|
; NextNLoops is NLoops + 1, NextSubLoop is 0).
|
||
|
|
|
||
|
|
% Everything above this is not needed to get the input answer
|
||
|
|
% starts(Starts),
|
||
|
|
% maplist([S, S-Off-Stride-Loop]>>(zloop([], S, 0, [], Off, Stride, Loop)),
|
||
|
|
% Starts, Loops).
|
||
|
|
% then find the LCD of the strides (which are equal to offsets).
|
||
|
|
|
||
|
|
zloop(_, _, _, Zs, Offset, Stride, Loop) :-
|
||
|
|
Zs = [FirstZIndex-Z | _], reverse(Zs, [LastZIndex-Z | ReversedZs]),
|
||
|
|
DeltaZ is LastZIndex - FirstZIndex, DeltaZ =\= 0,
|
||
|
|
direction_len(Len),
|
||
|
|
divmod(DeltaZ, Len, _, 0),
|
||
|
|
Offset = FirstZIndex, Stride = DeltaZ,
|
||
|
|
foldl([Idx-Z, NewIdx-Z, Off, Off]>>(NewIdx is Idx - Off),
|
||
|
|
ReversedZs, ReversedLoop, Offset, _),
|
||
|
|
reverse(ReversedLoop, Loop),
|
||
|
|
!.
|
||
|
|
|
||
|
|
zloop(Directions, Node, Index, Zs, Offset, Stride, Loop) :-
|
||
|
|
( is_end(Node)
|
||
|
|
-> append(Zs, [Index-Node], NewZs)
|
||
|
|
; NewZs = Zs
|
||
|
|
),
|
||
|
|
next_step(Directions, Move, Remain),
|
||
|
|
G =.. [Move, Node, To], G,
|
||
|
|
NewIndex is Index + 1,
|
||
|
|
zloop(Remain, To, NewIndex, NewZs, Offset, Stride, Loop).
|
||
|
|
|
||
|
|
starts(Starts) :- findall(X, X to _, Nodes), include(is_start, Nodes, Starts).
|
||
|
|
|
||
|
|
is_start(Node) :- atom_chars(Node, [_, _, a]).
|
||
|
|
is_end(Node) :- atom_chars(Node, [_, _, z]).
|
||
|
|
|
||
|
|
next_step([Move | Remain], Move, Remain).
|
||
|
|
next_step([], Move, Remain) :- direction_list([Move | Remain]).
|
||
|
|
|
||
|
|
direction_list(Dir) :- direction(Str), atom_chars(Str, Dir).
|
||
|
|
direction_len(Len) :- direction_list(D), length(D, Len).
|
||
|
|
|
||
|
|
same_elements([_]).
|
||
|
|
same_elements([X-_, Y-Z2 | Cdr]) :- X =:= Y, same_elements([Y-Z2 | Cdr]).
|