[Spoilers] Advent of Code 2023 Day 9

[Mousaka]

TLDR

Sharing a AoC solution with some personal reflections and would love some feedback. And a big shoutout to jasagredo for his work that helped me when I got stuck.

---

Hi again!

I've solved another AoC using Prolog, day 9. This time there was a bit less of struggle and a bit more fun. To be honest I did struggle for a while early on with an idea that I had trouble implementing, but then I took a break and I decided to read some code for inspiration. Some might call this cheating but I found it to be very useful from a learning perspective and helped reduce the state of struggling to a level where I did not just give up. I've been a programmer for 15 years but never worked with Prolog and because of that I think Prolog is the language I have the worst write/read ratio in, meaning I don't read a lot of it. That's why I have been enjoying a few people sharing their AoC code here. I know there is a lot of other Prolog out there to read but I find it it more fun to read if you are already engaged in the problems that are being solved.

What helped me when I got stuck this time was reading jasagredo's solution where I found a lot of inspiration to get going (I also copied your utils.pl and added credits to you, I hope that's ok). Thank you for sharing your solutions! The overall approach is similar but I did some small changes. The most interesting part was that I realised that I don't need to look at the list of diffs in order to find the solution. Instead I append (in part 1) or prepend (in part 2) an unbound variable to the line we are trying to find the oasis number for and let Prolog find a solution for me. This is the specific code where I do this, the first one is for Part 1 of the problem the second for Part 2:

oasis_number(Ls, N):-
  reverse(Ls, LsRev),
  reverse([N|LsRev], LsN),
  diff_until_zeros(LsN,_).

oasis_number_p2(Ls, N):-
  diff_until_zeros([N|Ls],_).

I did put some effort in trying to remove any unnecessary backtracking. At some point it seemed like there were none but after removing some constraints that turned out to be incorrect they came back. I always get so annoyed by them and feel a strong need to remove them but a lot of times it feels very difficult and when the goal is to find the solution to the problem it rarely seems to be needed. Here is a small example where I added tracing on the call to diff_numbers\2:

?- oasis_number_p2([0, 3],N).
call:user:diff_numbers([A,0,3],B).
exit:user:diff_numbers([A,0,3],[B,3]).
call:user:diff_numbers([A,3],B).
exit:user:diff_numbers([A,3],[B]).
call:user:diff_numbers([A],B).
   N = -3. 
;  call:user:diff_numbers([0,3],A).
exit:user:diff_numbers([0,3],[3]).
call:user:diff_numbers([3],A).
false.

It finds the correct solution N = -3 but then it continues with another branch which I can't really figure out why. Any pointers here appreciated.

Full code

Here is the full solution for the readers convenience. The source can be found here.

:- use_module('../utils.pl').

zero_or_one_sum(X,Sum0,Sum):-
   if_((X #= 0 ',' Sum0 #= 0), Sum #= 0, Sum #= 1). 


diff_numbers([A,B|Ls],[Diff|Rest]):-
  Diff #= B - A,
  length([B|Ls],L),
  if_(L #< 2, Rest = [], diff_numbers([B|Ls], Rest) ).


diff_until_zeros(Ls, [Diff|Rest]):-
  $diff_numbers(Ls, Diff),
  foldl(zero_or_one_sum,Diff,0,Sum), % Sum binds to 0 if all Diffs are 0, otherwise 1.
  if_(Sum #= 0, Rest = [], diff_until_zeros(Diff, Rest)).


oasis_number(Ls, N):-
  reverse(Ls, LsRev),
  reverse([N|LsRev], LsN),
  diff_until_zeros(LsN,_).


oasis_number_p2(Ls, N):-
  diff_until_zeros([N|Ls],_).


solve(N,PartSolver):-
  phrase_from_file(lines(Lines), 'input.txt'),
  once(maplist(\X^Y^phrase(seqDelimited(' ', znumber, Y), X),
            Lines,
            Ls)),
  maplist(PartSolver, Ls, Os),
  sum_list(Os,N).


part1(S):-
  solve(S,oasis_number).


part2(S):-
  solve(S,oasis_number_p2). 

Any feedback is much appreciated.
Thank you for reading and cheers!