[Spoilers] Advent of Code 2023 Day 6

[Mousaka]

Hi!

I've been enjoying and struggling with solving a few AoC problems every year in Prolog and lately specifically in Scryer Prolog :). I have spent a lot of hours but I feel very much like a beginner. I happened to find a nice solution to part 2 but that felt kind of lucky. Wanted to share and discuss. Any feedback is welcome. This solution and those I've done can be found here.

I had this approach for Day 6 Part 1 (Link to problem):

% Part 1
records([(48, 261),(93, 1192),(84,1019),(66,1063)]).

beats_record(B, (T, D)) :-
  B #>= 0,
  TravelT #= T - B,
  TravelT * B #> D.

product_of_list([], 1).
product_of_list([H|T], Product) :-
   product_of_list(T, Rest),
   Product #= H * Rest.

button_times(All,L):-
  records(Rs),
  member((T,D), Rs),
  findall(B,(beats_record(B,(T,D)), label([B])), All),
  length(All,L).

solve(S):-
  findall(L, button_times(_,L), All),
  product_of_list(All,S).

When I was about to do part 2 which changes the input to one big time and distance in stead of several small ones I initially just tried using the exact same code but it turned out it was way too slow and never terminated. At first I tried labeling with min and max to try find the boundaries in order to calculate the number of solutions with something like this:

beats_record(B, (48938466,261119210191063)), labeling([max(B)], [B]).

but I could never get the upper end of the boundary because max would not terminate (in reasonable time at least). Is there a faster way to start labeling from max even when the answer is "big"?

While experimenting a bit I noticed that the boundaries I was looking for would be printed by clpz when I did not label B:

beats_record(B, (48938466,261119210191063)).
   clpz:(B in 6094682..42843784), clpz:(_A+B#=48938466), clpz:(_A*B#=_B), clpz:(_A in 6094682..42843784), clpz:(_B in 261119210191064..1835589827438656)

At this point I manually copied and subtracted the lower boundary from the upper and got my answer to Day 6 part 2!

Looking through some documentation a bit I found that I can use fd_size/2 to get the size of B's value space which was just what I was after. This led to a quite short and neat solution for part 2.

% Part 2
% example
example_input((71530,940200)).
% real input
input((48938466,261119210191063)).

beats_record(B, (T, D)) :-
  B #>= 0,
  TravelT #= T - B,
  TravelT * B #> D.

% Can I hide the domain printing somehow?
solve(S):-
  input(R),
  beats_record(B, R), fd_size(B, S).

Happy coding days. Cheers!

[triska]

Very interesting, thank you a lot for sharing this!

You can use the down labeling option to try the domain elements in decreasing order, starting from the greatest domain element (notice that max(B) is entailed in that concrete case, and can be omitted):

?- beats_record(B, (48938466,261119210191063)), labeling([down], [B]).
   B = 42843784
;  B = 42843783
;  B = 42843782
;  B = 42843781
;  B = 42843780
;  ... .

Note that the domain (i.e., what fd_dom/2 yields) of variables depends heavily on implementation choices of the constraint solver, in particular the chosen trade-off between strength and speed of constraint propagation, and is also subject to change, whereas labeling/2 yields concrete integers, and a solution if all variables are successfully labeled. It therefore seems advisable to fetch the greatest admissible element (if there is one) with labeling/2, because it does not rely on internal specifics of the constraint solver.

[Mousaka]

Thank you for the feedback! Reading the documentation I did get the feeling that fd_dom/2 was more of a developer/inspection tool rather than a core feature but I never thought about that it could be unstable in some way. I had also totally missed the down labeling strategy but that one works great! I added this as an alternative solution:

alt_solve(S):-
  input(R),
  once((beats_record(Upper, R), labeling([down],[Upper]))),
  once((beats_record(Bottom, R), label([Bottom]))),
  S #= Upper - Bottom + 1.

[triska]

Yes that seems better!

Two small additional things that may be useful: label([Var]) can also be written as indomain(Var), and once(G1), once(G2) can also be written as once((G1,G2)), I think it could be a bit easier to read.

[aarroyoc]

I solved day 6 using a similar strategy, using different strategies in labeling/2: https://github.com/aarroyoc/advent-of-code-2023/blob/main/day6/main.pl

[Mousaka]

@triska That makes sense. Thank you.