:- module day9.
:- interface.
:- import_module basics.

:- pred run(part::in, lines::in, answer::out) is cc_multi.

:- implementation.
:- import_module int.
:- import_module string.
:- import_module list.
:- import_module set_bbbtree.

:- type set(T) == set_bbbtree(T).


:- type coord ---> c(x :: int, y :: int).
:- type rope == list(coord).

:- type direction ---> up; down; left; right.

:- pred to_direction(string, direction).
:- mode to_direction(in,  out) is semidet.
:- mode to_direction(out, in)  is det.
to_direction("U", up).
to_direction("D", down).
to_direction("L", left).
to_direction("R", right).

:- pred orth(direction::in, direction::in) is semidet.
orth(A, B) :-
  ((A = up   ; A = down),  (B = left ; B = right));
  ((A = left ; A = right), (B = up   ; B = down)).

:- pred line(string::in, list(direction)::out) is semidet.
line(Str, replicate(N, D)) :-
  words(Str) = [DD, NN],
  to_direction(DD, D),
  to_int(NN, N).

:- pred move_head(direction::out, coord::in, coord::out) is multi.
move_head(up,    c(X, Y), c(X,   Y+1)).
move_head(down,  c(X, Y), c(X,   Y-1)).
move_head(left,  c(X, Y), c(X-1, Y)).
move_head(right, c(X, Y), c(X+1, Y)).

:- pred ok(coord::in, coord::in) is semidet.
ok(A, B) :- abs(A^x - B^x) =< 1, abs(A^y - B^y) =< 1.

:- pred ok(rope::in) is semidet.
ok([]). ok([_]).
ok([A, B | Rest]) :- ok(A, B), ok([B | Rest]).

:- pred same_rc(coord::in, coord::in) is semidet.
same_rc(A, B) :- A^x = B^x ; A^y = B^y.

:- pred move_tail1(coord::in, coord::in, coord::out) is nondet.
move_tail1(H, !T) :- ok(H, !.T).
move_tail1(H, !T) :-
  if same_rc(H, !.T) then
    move_head(_, !T),
    ok(H, !.T)
  else
    move_head(D1, !T),
    move_head(D2, !T),
    orth(D1, D2),
    ok(H, !.T).

:- pred move_tail(coord::in, rope::in, rope::out) is nondet.
move_tail(_, [],           []).
move_tail(H, [!.T | !.Ts], [!:T | !:Ts]) :-
  move_tail1(H, !T),
  move_tail(!.T, !Ts).

:- pred move(direction::in, rope::in, rope::out) is nondet.
move(_, [],          []).
move(D, [!.H | !.T], [!:H | !:T]) :-
  move_head(D, !H),
  move_tail(!.H, !T).


:- type seen == set(coord).

:- pred next(direction, rope, rope, seen, seen).
:- mode next(in, in, out, in, out) is nondet.
next(D, !Rope, !Seen) :-
  move(D, !Rope),
  last(!.Rope, Tail),
  insert(Tail, !Seen).

:- pred run0(part::in, lines::in, int::out) is cc_nondet.
run0(Part, Lines, Out) :-
  Start = replicate(part(Part, 2, 10), c(0, 0)),
  map(line, Lines, Dirs),
  foldl2(next, condense(Dirs), Start, _, init, End),
  count(End, Out).

run(Part, Lines, int(Out)) :-
  disable_warning [no_solution_disjunct] (
    not run0(Part, Lines, Out) => die("bad input")
  ).