I think that @tatut is using "hashtbl" pack for SWI-Prolog because it has a non-backtrackable hash table implementation. The crux of day 12 is memoising partial calculations during a depth first search to be recycled in adjacent branches. @jan would I be right in saying that a backtrackable hashtable cannot facilitate this?
… I’m struggling to find a way of solving day 12 without resorting to something like this as well, but it feels like it breaks every rule in Prolog.
Probably. The obvious solution to this is of course tabling. Does this fail due to the use of constraints?
Success. It is nearly always possible to find a clean solution. Sometimes requires rethinking every aspect of the problem though …
Day 14 aoc2023-prolog/day14.pl at caa1569736ad92d70744bae0705036d97b9634cf · tatut/aoc2023-prolog · GitHub
I’m not particularly happy with the code. Part 1 was easy, just transpose the lists and move rocks towards the start.
But the 2nd part, I decided to go with a completely different approach, using a compound term g(W,H,data(...)) and mutating that as I figured there would be lots those even with the cycle detection.
I find these 2d grid challenges difficult to model in Prolog, but I haven’t programmed Prolog for long, so maybe it is just that. You need so many ways of looping and navigating around it.
I don’t know if I necessarily needed non-backtracking in this solution, but as there would not be any backtracking it would be waste.
I didn’t know hashtables existed outside of the pack 
I couldn’t find it with apropos.
I again went with non-backtracking stuff, namely nb_setarg as we are just modifying the one huge compound term.
There is a deprecated arrays.pl but I didn’t try that, are compound terms ok to use as makeshift arrays? Or is there something better.
No 
Prolog always finds an elegant way. Took me a while, but the trick is to structure the parser so that there is a predicate which can be neatly tabled (act/3 in my case). Behold, day 12, both parts, 49 LOC in vanilla Prolog with tabling.
:- use_module(library(dcg/basics)).
:- set_prolog_flag(table_space, 2_000_000_000).
:- table act/3.
act([63|Rest], Gs, Count) :- % ?
act([46|Rest], Gs, Count1),
act([35|Rest], Gs, Count2),
Count is Count1 + Count2,!.
act([46|Rest], Gs, Count) :- % .
act(Rest, Gs, Count),!.
act(Code,[G], 1) :-
length(Code, G), \+ memberchk(46, Code),!.
act(Code,[G], 1) :-
length(X, G), append(X, Rest, Code),
\+ memberchk(46, X), \+ memberchk(35, Rest),!.
act(Code,[G|Gs], Count) :- % #s
length(X,G), append([X,[Next],Rest],Code),
\+ memberchk(46, X), Next \= 35, !,
act(Rest,Gs,Count).
act(_,_,0).
expand,[] --> call(eos),!.
expand,`\n` --> `\n`,!,expand.
expand,X --> string_without(` `,S),{unfold(5,S,`?`,E1)},
" ",string_without(`\n`,S2),
{unfold(5,S2,`,`,E2), append([E1,` `,E2],X)},expand.
unfold(1,S,_,Acc,Res) :- append(Acc,S,Res),!.
unfold(N0,S,Sep,Acc0,Res) :-
append([S,Sep,Acc0],Acc),
N is N0-1,!,unfold(N,S,Sep,Acc,Res).
unfold(N,S,Sep,Res) :- unfold(N,S,Sep,[],Res).
nums([X|Xs]) --> number(X), ",", nums(Xs).
nums([X]) --> number(X).
line(Count) --> string_without(` `,Code), " ", nums(Groups),
"\n", { act(Code, Groups, Count) }.
lines([Count|Ls]) --> line(Count),lines(Ls).
lines([Count]) --> line(Count).
solve(File,Part1,Part2) :-
phrase_from_file(lines(Cs1),File),
sumlist(Cs1,Part1),
phrase_from_file((expand,lines(Cs2)),File),
sumlist(Cs2,Part2).
Interesting. I did try tabling myself, before adding the indices and a cache hashmap. Tabling just didn’t seem to do anything. Other than the table_space flag, I don’t see a huge difference to what I tried, I’ll have to try the tabling again with the space flag.
Any other tips on how to debug why tabling doesn’t work? It just silently fails.
Hmm, I tried with table_space but that alone didn’t help, but if I break up the Line-Dmgs into 2 separate parameters, they started working… perhaps some pathological case of argument comparison.
Funnily, the tabled version is still slower (by about 900ms slower on my machine) than explicit nb_hashtbl cache, but I guess that could be due to having a huge key instead of 2 integers in the hashtable case.
Possibly because you are tabling the wrong arity? E.g. my main predicate is act/3 but its easy to accidentally write :-table act/2 or :-table act/4.
This makes it sound like the wrong arity and then when you split it , it became the right arity.
The current SWI-Prolog implementation comes at a considerable overhead for any tabled goal. So, if you do not need the semantics of SLG resolution and you merely want the caching, other solutions are typically more work but faster. Some day, this should be fixed. That is doable by moving most of the “wrapper” to VM instructions.
Day 14 part 1 – started on this a bit late, by here it is as a DCG+CHR in barely 14 LOC:
:- use_module(library(dcg/basics)).
:- use_module(library(chr)).
:- set_prolog_flag(chr_toplevel_show_store, false).
t(_,_,[]) --> [].
t(X0,_,Xs) --> "\n",{ X is X0+1 }, !, t(X,1,Xs).
t(X0,Y0,[p(X0-Y0,V)|Xs]) --> [V], {Y is Y0+1}, !, t(X0,Y,Xs).
:- chr_constraint p/2.
p(X0-Y,79), p(X-Y,46) <=> X is X0-1, X > 0 | p(X-Y,79), p(X0-Y,46).
solve(File,Part1) :-
phrase_from_file(t(1,1,Ps), File),
aggregate_all(max(X), member(p(X-_,_), Ps), Max),
maplist(call, Ps),
aggregate_all(sum(X),(find_chr_constraint(p(X0-_,79)),
X is Max+1-X0),Part1).
Day 15 part 1 (below) was trivial (8 LOC!) but part 2 is trickier:
:- use_module(library(dcg/basics)).
t([H|Xs]) --> string(X), { hash(X,0,H) }, ",", !, t(Xs).
t([H]) --> string(X), { hash(X,0,H) },"\n".
hash([],A,A).
hash([H|T],A0,V) :- A is (A0+H)*17 rem 256, hash(T,A,V).
solve(File,Part1) :-
phrase_from_file(t(Ls), File),
sumlist(Ls,Part1).
Just mentioning that I managed to do a solution for day 12 using only CLPFD @emiruz, and I surely learned a lot in the process (the point being, you have to label smartly, which in my case meant writing a custom labeling strategy; also you can’t really label everything, you have to do it piecewise, then count and multiply). As some point I’ll polish the solution and put it on github.
But the solution still takes around 7m:30s to run part 2. That gave me a lot of appreciation for the dynamic programming solution (it really avoids intermediate calculations)
Oh amazing, that’s a considerable achievement. I very much look forward to seeing that.
I looked into CLPB for a while. The way SAT people do sequences is to associate a separate conjunction with every possible start index and then relate those together with an exclusive disjunction. When you have many such special conjunctions (because there are many groups in this problem) you have to layer them on top of each other, which is how SAT problems end up with 100k+ constraints (or so it seems to me).
At the end of all that I’d be able to call “sat_count” and hope for the best! Frankly, if it didn’t work after all that effort, I couldn’t gracefully handle the disappointment so I decided to stop trying and do as “when it Rome”.
Besides, having solved it quite neatly (see above!), the crux of this problem seems to be memoisation, and what I would have built (had it worked) is an efficient solver. However, the problem would only have to be larger for it not to work. E.g. in your case if 5 copies is taking 7 minutes, 6 copies may end up taking hours, and 10 copies would never finish.
Although I must say, for part 1, this is quite amazing:
%Example: ".??..??...?##. 1,1,3",
solve(Sol) :-
append([[0],[_,_],[0,0],[_,_],[0,0,0],[_],[1,1,0]], Sol),
append([_,[1,0],_,[1,0],_,[1,1,1,0],_], Sol),
Sol ins 0..1, sum(Sol, #=, 5).
Its all you need to produce all the solutions using CLPFD.
You’ll want to move that sum to be before the appends, so it’s only run once instead of many times.
It needs variables and a domain to operate over, so the soonest it can be called is after append/2 I think.
Oops, true. If the list length is known, can start the predicate with e.g.:
length(Sol, 14),
Sol ins 0..1,
sum(Sol, #=, 5),
Yeah, its a fiddly one. The code in the actual solver looked like this:
solver(Code,Cons0,Count) :-
foldl([A,B,C]>>(append([B,[_],[A],[[0]]],C)),Cons0,[],Cons1),
append(Cons2,[_],Cons1), append(Cons2,[_],Cons),
foldl([A,B,C]>>(length(A,N0),C is B+N0),Cons0,0,N),
Code ins 0..1, sum(Code,#=,N),
aggregate_all(count,append(Cons,Code), Count).
It works, but its many times slower than this:
solver(Code,Cons0,Count) :-
foldl([A,B,C]>>(append([B,[_],[A],[[0]]],C)),Cons0,[],Cons1),
append(Cons2,[_],Cons1), append(Cons2,[_],Cons),
foldl([A,B,C]>>(length(A,N0),C is B+N0),Cons0,0,N),
aggregate_all(count,(append(Cons,Code),
Code ins 0..1,
sum(Code,#=,N)), Count).
I don’t know why, but it is the case.
Day 15 solution here in 34 LOC. I got the opportunity to use the hash table from the standard library.