Advent of code 2023

General
115

Day 11 solution in 22 LOC.

:- use_module(library(dcg/basics)).

ns(N,V) :- number_string(N,V).
t(_,_,_,[]) --> [].
t(X0,_,N,Xs) --> "\n",{X is X0+1},!,t(X,1,N,Xs).
t(X0,Y0,N0,[p(X0-Y0,N0)|Xs]) --> `#`,{Y is Y0+1, N is N0+1},!,t(X0,Y,N,Xs).
t(X0,Y0,N,Xs) --> `.`,{Y is Y0+1},!,t(X0,Y,N,Xs).

expand(Gs,F,Es) :-
    findall(X,member(p(X-_,_),Gs),Xs), max_list(Xs,Maxx),
    findall(Y,member(p(_-Y,_),Gs),Ys), max_list(Ys,Maxy),
    findall(X,(between(1,Maxx,X), \+ memberchk(p(X-_,_),Gs)),Rows),
    findall(Y,(between(1,Maxy,Y), \+ memberchk(p(_-Y,_),Gs)),Cols),
    findall(p(I-J,V),(member(p(X-Y,V),Gs),
		      aggregate_all(count,(member(R,Rows),R<X),Offx),
		      aggregate_all(count,(member(C,Cols),C<Y),Offy),
		      I is X+Offx*(F-1), J is Y+Offy*(F-1)), Es).

sum_paths(Es,Sum) :-
    aggregate_all(sum(Total), (member(p(X-Y,V1),Es), member(p(I-J,V2),Es),
			       V1<V2, Total is abs(X-I)+abs(Y-J)),Sum).

solve(File,Part1,Part2) :-
    phrase_from_file(t(1,1,1,Gs),File),
    expand(Gs,2,Es), sum_paths(Es,Part1),
    expand(Gs,1000000,Es2), sum_paths(Es2,Part2).
116

Ill try it later, but look at the stats for day 12 – looks like the hardest day by a long way.

image

EDIT: just had a peek. It looks like a CLPFD problem :slight_smile: Come on veterans, @CapelliC @anon95304481, have a go!

PROBLEM:
In the giant field just outside, the springs are arranged into rows. For each row, the condition records show every spring and whether it is operational (.) or damaged (#). This is the part of the condition records that is itself damaged; for some springs, it is simply unknown (?) whether the spring is operational or damaged.

However, the engineer that produced the condition records also duplicated some of this information in a different format! After the list of springs for a given row, the size of each contiguous group of damaged springs is listed in the order those groups appear in the row. This list always accounts for every damaged spring, and each number is the entire size of its contiguous group (that is, groups are always separated by at least one operational spring: #### would always be 4, never 2,2).

So, condition records with no unknown spring conditions might look like this:

#.#.### 1,1,3
.#...#....###. 1,1,3
.#.###.#.###### 1,3,1,6
####.#...#... 4,1,1
#....######..#####. 1,6,5
.###.##....# 3,2,1

However, the condition records are partially damaged; some of the springs’ conditions are actually unknown (?). For example:

???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1

Equipped with this information, it is your job to figure out how many different arrangements of operational and broken springs fit the given criteria in each row.

117

I think Prolog has a nice advantage for day 12. Here is the gist for how to solve part 1 with CLPFD and the formidable append/2:

:- use_module(library(clpfd)).

solve(Sol) :-
    %Example: ".??..??...?##. 1,1,3",
    [A,B,C,D,E] ins 0..1,
    length(Sol,14),
    append([[0],[A,B],[0,0],[C,D],[0,0,0],[E],[1,1,0]], Sol),
    append([_,[1,0],_,[1,0],_,[1,1,1,0],_], Sol),
    global_cardinality(Sol,[1-5,0-9]).

Running solve(Sol). will generate the four possible arrangements for the example.

From here it should be just a matter of a bit of parsing, and automating the above.

118

Part 1 is as indicated above – it works as expected :slight_smile: . Part 2 drastically expands the formulae. I did a few manually expanded formulae to see how the numbers change with expansion:

.??..??...?##. 1,1,3
.??..??...?##.?.??..??...?##. 1,1,3,1,1,3
.??..??...?##.?.??..??...?##.?.??..??...?##. 1,1,3,1,1,3,1,1,3
.??..??...?##.?.??..??...?##.?.??..??...?##.?.??..??...?##. 1,1,3,1,1,3,1,1,3,1,1,3

I noticed this pattern:

X = Combos_1 / Combos_0

Combos_N = Combos_0 * X^(N-1)

So to get the 5 expansion, I need the first 2 expansions. It turns out that even that will take about 8 hours to complete. So I’m analysing deeper.

119

Part 1 is here for the interested. I couldn’t work out part 2 last night. The rule above doesn’t apply outside of the sample set. E.g.

1x | ???.???###? 1,1,1,4 ---- 19 combos
2x | ???.???###???.???###? 1,1,1,4,1,1,4 ---- 469 combos
3x | … ---- 11719 combos
…

So, not an integer or a constant factor for that example.

There must be some kind of serial relationship that either makes subsequent expansions predictable from the first or offers a way to cut the string apart, analyse it in pieces and put it together again.

120

Day 12, part2 solution:

I went with the recursive solution in part2 that needs memoization. I was unable to use tabling, and I used a dynamic predicate to cache. I was unable to use the Line-Dmgs pair of lists as the key, that was very slow, I had to add I,J indexes as the cache key. Even so the solution took 95 seconds to calculate.

Any advice on improving memoization? Is there a good mutable hashtable to use for cache?

121

Found the “hasthtbl” pack, using a nb_hashtbl as the cache, improved runtime from 95 seconds to 1.4 seconds!

122

Note that the standard library provides hashtable.pl -- Hash tables

123

Garrr… I really hoped I wouldn’t have to write a solver. CLPFD + append/2 from part one is just so damn pretty. It looks like the crux of this problem is that there is significant memoisation opportunity during the solution process. I’ll have another go at part 2 soon. I had a look at the code @tatut you may consider using DCGs for the parsing. Its much prettier :slight_smile:

124

Day 13 solution here – its a bit verbose (54 LOC) and bruteforce but I’ll refactor!

125

Agreed that DCGs are mostly prettier, I’ve had both approaches in different days, just to learn.

126

This was my approach to part 1 in a nutshell for a specific example:

:- use_module(library(clpfd)).

solve(Sol) :-
    %Example: ".??..??...?##. 1,1,3",
    [A,B,C,D,E] ins 0..1,
    length(Sol,14),
    append([[0],[A,B],[0,0],[C,D],[0,0,0],[E],[1,1,0]], Sol),
    append([_,[1,0],_,[1,0],_,[1,1,1,0],_], Sol),
    global_cardinality(Sol,[1-5,0-9]).

The trouble is that its under constrained though. I think CLPFD basically ends up doing “generate and test” against what append/2 throws out under the hood. @tatut do you see any smart way of adding more constraint from your solution to it using what CLPFD comes with?

127

@jan am I doing something idiotic here again? The marvel that is append/2 produces all the structures that “Code” can be in, global_cardinality/2 and “ins 0…1”, constrain the possible assignment of the variables within it. Finally aggregate_all/3 counts the solutions. Is there some faster of way of counting the solutions that instantiating them all?

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),
    length(Code,Len), M is Len-N,
    Code ins 0..1,
    global_cardinality(Code,[0-M,1-N]),
    aggregate_all(count,append(Cons,Code),Count).

EDIT:

I got a 10x improvement by replacing global_cardinality(Code,[0-M,1-N]) with:

sum(Code, #=, N),

… isn’t obvious to me why that would be the case.

128

Hard to tell. Needs some study of the problem and what this code does :slight_smile: Bit too busy for that … aggregate_all/3 using count is pretty efficient. Yes, it has to generate all solutions on backtracking, but the counting is simply a non-backtrackable data structure that is updated. So, solutions are not copied and all runs in constant space.

What happens under the hood of clp(fd) is also for me hard to predict. Running the profiler should give a fair impression, e.g.

 ?- profile(solve).

If you want precise port counts, use

 ?- profile(solve, [ports(true)]).

This can sometimes blow up the recorded call-tree. Using the default algorithm, only the number of calls is accurate for all predicates. Correctness of the others depends on the predicate structure.

If you can, use it in the GUI environment, so you can navigate the tree and jump easily to the sources.

129

I tried to get very clever with clpfd and especially constraint reification, and as such I don’t have a working solution for day12/part2 yet.

So @jan, is there a way to check what happens to a big pile of clpfd constraints when I add another one? Basically, I would like to observe the propagation structure.

There is a tradeoff between constraint reasoning (slow but potentially big prunings) vs backtracking (fast but no pruning). But I feel like staring at a black box each time I add a constraint.

As a concrete example, if A and B are constraints, when does A #/\ B fire?

130

Any chance you can post your part 1? This is the best I’ve managed so far:

118,709,753 inferences, 5.072 CPU in 5.072 seconds (100% CPU, 23405945 Lips)

I’m guessing you tried to express the structure in CLPFD logical operators somehow?

131

Ok I think CLPFD was probably a mistake. Since the variables are Boolean CLPB makes more sense. In particular:

sat_count(+Expr, -Count): Count the number of admissible assignments. Count is the number of different assignments of truth values to the variables in the Boolean expression Expr, such that Expr is true and all posted constraints are satisfiable.

Live in learn…

132

I don’t know … Possibly the proposed attribute portray hook can simplify this a little? I’m not that a CLP person … Sure, I see its purpose of CLP on many problems. Just, these are not so frequently the problems I try to solve :slight_smile:

133

Purely academic, but here are two drastically different ways of encoding the same example in CLPFD:

:- use_module(library(clpfd)).

solve(Vs) :-
    %Example: ".??..??...?##. 1,1,3",
    length(Vs,14),
    length(Is,14),
    Is ins 1..14, Vs ins 0..1,
    all_different(Is),

    % Static values.
    element(1,Vs,0),
    element(4,Vs,0),
    element(5,Vs,0),
    element(8,Vs,0),
    element(9,Vs,0),
    element(10,Vs,0),
    element(12,Vs,1),
    element(13,Vs,1),
    element(14,Vs,0),

    % Implication of 1,1,3 on indexes and values.
    I2-I1 #= 1, element(I1,Vs,1), element(I2,Vs,0),
    I4-I3 #= 1, element(I3,Vs,1), element(I4,Vs,0),
    I7-I6 #= 1, I6-I5 #= 1, element(I5,Vs,1), element(I6,Vs,1), element(I7,Vs,1),
    I4 #< I5,
    I2 #< I3,

    % Implicitly prevents any other chains when taken together
    % with the chain constraints above.
    sum(Vs, #=, 5),

    
    label(Vs).

solve2(Sol) :-
    %Example: ".??..??...?##. 1,1,3",

    % Express static data and unknown variables.
    append([[0],[A,B],[0,0],[C,D],[0,0,0],[E],[1,1,0]], Sol),

    % Express structure of #s as an append/2 merge on Sol.
    append([_,[1,0],_,[1,0],_,[1,1,1,0],_], Sol),

    % Structure fully accounts for #s so this prevents spurious assignments.
    sum(Sol, #=, 5).

You can run them like this:

time(aggregate_all(count,solve2(_),Count)).

solve
% 173,618 inferences, 0.013 CPU in 0.013 seconds (100% CPU, 13406647 Lips)

solve2
% 2,638 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 3452102 Lips)
134

Not quite sure what your objective is, but you can use attribute_goals//1 to get at the constraints on a clpfd variable, e.g.,

?- X in 1..10, X#=Y+1, phrase(clpfd:attribute_goals(X),G).
G = [clpfd:(X in 1..10), clpfd:(Y+1#=X)],
X in 1..10,
Y in 0..9.

This would at least display something (e.g., the domain) about the clpfd attribute in the debugger. Then, if you had the patience, you could step through the propagation as it happens - maybe that’s enough?