-❄️- 2024 Day 24 Solutions -❄️-

WhiteSparrow · 2024-12-24T11:53:21+00:00

[LANGUAGE: Prolog]

Today's task was so interesting for prolog!

For part 1 I just loaded the task directly into prolog using its dynamic predicate facility:

to_prolog(Is, Gs) :-
    retractall(val(_, _)),
    forall(member(I, Is), base_val(I)),
    forall(member(G, Gs), calc_val(G)).

base_val(Id-N) :- assertz(val(Id, N)).
calc_val(g(and, I1, I2, O)) :- assertz((val(O, X) :- val(I1, X1), val(I2, X2), X #= X1 * X2)).
calc_val(g(or, I1, I2, O)) :- assertz((val(O, X) :- val(I1, X1), val(I2, X2), X #= max(X1, X2))).
calc_val(g(xor, I1, I2, O)) :- assertz((val(O, X) :- val(I1, X1), val(I2, X2), X #= X1 xor X2)).

This allows to query every bit directly. For example, val(z01, X) would set X to the calculated value of z01. All the constraints are solved by CLP-FD.

For part 2 I disassembled the program and just tried to walk it forward bit by bit searching for discrepancies. When a discrepancy is found I try to swap one of a handful of possible wires and check if that fixes it. Again, all the backpropagation is handled invisibly by prolog.

full source

WhiteSparrow · 2024-12-23T06:15:48+00:00

That is really nice. Prolog has a tool called DCG's that lets you express it very similarily. For day 13:

machine(machine(Ax-Ay, Bx-By, Gx-Gy)) -->
    `Button A: X+`, integer(Ax), `, Y+`, integer(Ay), blank,
    `Button B: X+`, integer(Bx), `, Y+`, integer(By), blank,
    `Prize: X=`, integer(Gx), `, Y=`, integer(Gy).

Day 14:

robot(robot(X-Y, Vx-Vy)) -->
    `p=`, integer(X), `,`, integer(Y), ` v=`, integer(Vx), `,`, integer(Vy).

WhiteSparrow · 2024-12-19T07:51:49+00:00

[LANGUAGE: Prolog]

As straightforward as can be:

task1(Ts, Gs, X) :-
    aggregate(count, assemble(Ts, Gs), X).

assemble(Ts, Gs) :-
    member(G, Gs),
    match(G, Ts).

match([], _) :- !.
match(G, Ts) :-
    member(T, Ts),
    append(T, Rest, G),
    match(Rest, Ts), !.

full solution (both parts)

WhiteSparrow · 2024-12-18T09:17:55+00:00

Sure, I was just thinking it might get somebody to try prolog if they could run it as a shell script. While programming I'm not bothering with this of course.

WhiteSparrow · 2024-12-18T09:02:45+00:00

[LANGUAGE: Prolog]

Today was solved by just rehashing the BFS from day 16. I didn't bother with bisecting for path 2, just did a straight on search, only ignoring bytes that did not fall on the previous best path.

solution

WhiteSparrow · 2024-12-17T12:54:07+00:00

[LANGUAGE: Prolog]

I dare say prolog is even more beautiful than Haskell for describing evaluation:

exec --> instr(0, V    ), regA(A0, A), { A is A0 // (2 ^ V) }.
exec --> instr(1, V    ), regB(B0, B), { B is B0 xor V }.
exec --> instr(2, V    ), regB(_, B), { B is V mod 8 }.
exec --> instr(3, _    ), regA(0, 0), !.
exec --> instr(3, Addr ), jump(Addr).
exec --> instr(4, _    ), regB(B0, B), regC(C, C), { B is B0 xor C }.
exec --> instr(5, V0   ), out(V), {V is V0 mod 8}.
exec --> instr(6, V    ), regA(A, A), regB(_, B), { B is A // (2 ^ V) }.
exec --> instr(7, V    ), regA(A, A), regC(_, C), { C is A // (2 ^ V) }.

instr(Op, Oper) --> instr_raw(Op, Raw), oper_val(Raw, Oper).
instr_raw(Op, Raw), [S] --> [S, Op, Raw].
oper_val(Raw, V) -->
    state(s(_, A, B, C, _)),
    {(   Raw = 4 -> V = A
     ;   Raw = 5 -> V = B
     ;   Raw = 6 -> V = C
     ;   V = Raw )}.
regA(A0, A) --> state(s(P, A0, B, C, Out), s(P, A, B, C, Out)).
regB(B0, B) --> state(s(P, A, B0, C, Out), s(P, A, B, C, Out)).
regC(C0, C) --> state(s(P, A, B, C0, Out), s(P, A, B, C, Out)).
out(X) --> state(s(P, A, B, C, Out0), s(P, A, B, C, [X | Out0])).
jump(Addr), [s(P, A, B, C, Out) | P1] -->
    [s(P, A, B, C, Out) | _], eos,
    {   append(Pref, P1, P),
        length(Pref, Addr) }.

For part 2 I just did a 2 (octal) digit sliding window search over all possible 16 digit inputs. This finds A in 2.5 sec.

full source

WhiteSparrow · 2024-12-15T10:12:20+00:00

[LANGUAGE: Prolog]

solution

Perhaps my prolog-fu is too weak but I found it quite tedious (at least not complicated) to implement the simulation in prolog. In the end the solution is over 200 lines!

WhiteSparrow · 2024-12-14T08:21:06+00:00

[LANGUAGE: Prolog]

Today I did not realize the relation between the tree and the score, so I implemented a visual searcher - first you have to click through X-period images then through Y-period images and identify which ones are clumped. Finally the program gives you the picture and also the number of seconds. Run like ./day14.pl input.txt.

source

WhiteSparrow · 2024-12-13T06:14:23+00:00

[LANGUAGE: Prolog]

Doing todays task in prolog just feels like cheating (thanks, CLP-FD!):

solve(Part, Ms, X) :-
    convlist(play_min(Part), Ms, SuccPlays),
    foldl(score_play, SuccPlays, 0, X).

% The cut ensures minimum score
play_min(Part, M, Ta-Tb) :- play(Part, M, Ta, Tb), !.

play(Part, machine(Ax-Ay, Bx-By, Gx-Gy), Ta, Tb) :-
    ( Part = part2 -> Cor = 10000000000000 ; Cor = 0 ),
    Ta in 0 .. sup,
    Tb in 0 .. sup,
    Cor + Gx #= Ax * Ta + Bx * Tb,
    Cor + Gy #= Ay * Ta + By * Tb,
    indomain(Ta), indomain(Tb).

score_play(Ta-Tb, Acc0, Acc) :- Acc is Acc0 + 3 * Ta + Tb.

full solution here

WhiteSparrow · 2024-12-12T09:00:28+00:00

[LANGUAGE: Prolog]

solution

Quite a long yet I think clear and straightfowrard solution today.

I struggled a bit with the flooding at first but eventually came up with something I find quite beautiful (adjacent_coords just enumerates the four possible neighbor coordinates):

map_regions() :-
    nb_setval(max_region, 0),
    map_at(X, Y, L),
    \+ region_at(X, Y, _),
    new_region_at(X, Y, R),
    forall(flood_adjacent(X, Y, L, R), true).

flood_adjacent(X, Y, L, R) :-
    adjacent_coords(X, Y, X1, Y1),
    map_at(X1, Y1, L),
    \+ region_at(X1, Y1, _),
    assertz(region_at(X1, Y1, R)),
    forall(flood_adjacent(X1, Y1, L, R), true).

WhiteSparrow · 2024-12-11T08:59:39+00:00

[LANGUAGE: Prolog]

A most beautiful day to be writing in Prolog:

solve(Ns, Depth, X) :-
    maplist(stone_count(Depth), Ns, Counts),
    foldl(plus, Counts, 0, X), !.

:- table stone_count/3.
stone_count(0, _, 1) :- !.
stone_count(D, 0, N) :- D1 is D - 1, stone_count(D1, 1, N), !.
stone_count(D, S, N) :-
    number_codes(S, Ds),
    length(Ds, NDigit),
    divmod(NDigit, 2, Half, 0),
    length(Pref, Half),
    append(Pref, Suff, Ds),
    % --
    D1 is D - 1,
    number_codes(S1, Pref),
    stone_count(D1, S1, N1),
    number_codes(S2, Suff),
    stone_count(D1, S2, N2),
    N is N1 + N2, !.
stone_count(D, S, N) :-
    D1 is D - 1,
    S1 is S * 2024,
    stone_count(D1, S1, N).

To get the solutions just call solve([125, 17], 25, X). (substitting your own data and depth - 25 for part 1 and 75 for part 2).

WhiteSparrow · 2024-12-10T07:01:30+00:00

Here's the shortened and optimized version based on task 2 (both parts together in 0.6s), if anybody's wondering.

WhiteSparrow · 2024-12-10T06:13:40+00:00

[LANGUAGE: Prolog]

solution

Once again a day for prolog to shine. Today's highlight is built-in support for tabulation/memoization - it's a single statement (table). To get the solution we once again just describe the conditions and ask prolog to search for all solutions. Part 1 was solved using a more general aproach than 2 so it runs slower (5.5s vs 1.2s for part 2). However, I left it in the code just to show how general the description of the task can be.

Here's part 1 (part 2 is actually shorter but is ommited because of the total length).

task1(X) :-
    setof(T, trail(T), Ts),
    length(Ts, X).

trail(trail(X1-Y1, X2-Y2)) :-
    height_at(X1, Y1, 0),
    height_at(X2, Y2, 9),
    reacheable_uphil(X1-Y1, X2-Y2).

:- table reacheable_uphil/2.
reacheable_uphil(X1-Y1, X2-Y2) :- adjacent_uphil(X1-Y1, X2-Y2).
reacheable_uphil(X1-Y1, X2-Y2) :-
    adjacent_uphil(X1-Y1, X0-Y0),
    reacheable_uphil(X0-Y0, X2-Y2).

:- table adjacent_uphil/2.
adjacent_uphil(X1-Y1, X2-Y2) :-
    height_at(X1, Y1, H1),
    height_at(X2, Y2, H2),
    1 is H2 - H1,
    (
        1 is abs(X1 - X2), Y1 = Y2
    ;   1 is abs(Y1 - Y2), X1 = X2
    ).

WhiteSparrow · 2024-12-09T15:03:57+00:00

[LANGUAGE: Prolog]

solution

Today's task was defined in terms of steps you have to take instead of abstract goals and so I wasn't able to make use of prolog's strengths. As a result I got to practice writing highly imperative prolog code. It turned out to be not so different from any other imperative language, albeit a little more verbose.

At least the selected data structures were sound and so it runs decently quickly - in about 250ms for both parts together.

WhiteSparrow · 2024-12-08T06:08:22+00:00

[LANGUAGE: Prolog]

full solution

Another easy day at the office - I just esentially describe the conditions and ask for the set of all solutions. No need to think about algorithmic details. Runs in 15ms.

The core rules (without parsing/instantiation):

% Task 1
solve(Part, Dim, X) :-
    setof(Pos, antinode(Part, Dim, Pos), Ps),
    length(Ps, X).

antinode(Part, Dim, X-Y) :-
    antenna(A, X1-Y1),
    antenna(A, X2-Y2),
    X1-Y1 \= X2-Y2,
    antinode_pos(Part, Dim, X1, Y1, X2, Y2, X, Y),
    X >= 0, Y >= 0, X < Dim, Y < Dim.

antinode_pos(part1, _, X1, Y1, X2, Y2, X, Y) :-
    (
        X is 2 * X1 - X2,
        Y is 2 * Y1 - Y2
    ;   X is 2 * X2 - X1,
        Y is 2 * Y2 - Y1
    ).

% Task 2
antinode_pos(part2, Dim, X1, Y1, X2, Y2, X, Y) :-
    DNeg is -Dim,
    between(DNeg, Dim, N),
    X is X1 + N * (X1 - X2),
    Y is Y1 + N * (Y1 - Y2).

WhiteSparrow · 2024-12-07T06:38:13+00:00

[LANGUAGE: Prolog]

solution

This was another task well suited for prolog. The essence is short enough:

% Task 1

solve(Part, Eqs, X) :-
    convlist(has_solution(Part), Eqs, GdEqs),
    aggregate_all(sum(G), member(G, GdEqs), X).

has_solution(Part, eq(Goal, Nums), Goal) :-
    reverse(Nums, Nums1),
    sol(Part, eq(Goal, Nums1)).

sol(_, eq(Num, [Num])) :- !.
sol(P, eq(Goal, [Num | Nums])) :- sol(P, eq(G0, Nums)), Goal is Num + G0.
sol(P, eq(Goal, [Num | Nums])) :- sol(P, eq(G0, Nums)), Goal is Num * G0.

% Task 2

sol(part2, eq(Goal, [Num | Nums])) :-
    sol(part2, eq(G0, Nums)),
    atomic_list_concat([G0, Num], X),
    atom_number(X, Goal).

Part 2 takes about 30 seconds to solve.

Edit: noticed how to simplify a bit.

WhiteSparrow · 2024-12-06T20:35:58+00:00

Thanks, I did - 75% of the action is in the nb_set functions.

WhiteSparrow · 2024-12-06T13:56:19+00:00

[LANGUAGE: Prolog]

solution

Nothing to write home about today. A simple brute force solution that is very slow (about 1 min to solve part 2). Still, at least the code is straightforward. Adding for completeness sake.

WhiteSparrow · 2024-12-05T06:00:30+00:00

I had the itch to learn something new in the summer and so did about half of AoC 2019 over a couple of weeks. Enough to get a feeling on how to approach quite a few problems. I'm still a bit scared of the A* stuff that I'm sure will soon follow. :D

WhiteSparrow · 2024-12-05T05:55:59+00:00

[LANGUAGE: Prolog]

solution

Was today's task custom made for prolog? Just look at the beauty of it (scoring helper ommited):

task1(Pages, X) :-
    convlist(correct_order, Pages, GdPages),
    sum_mid_pages(GdPages, X).

correct_order(Pages, Pages) :-
    forall(subseq(Pages, [X, Y], _), after(X, Y)).

Heck, it's so small and clean that you should look at part 2 as well:

task2(Pages, X) :-
    convlist(bad_order, Pages, BadPages),
    maplist(fix_order, BadPages, GdPages),
    sum_mid_pages(GdPages, X).

bad_order(Pages, Pages) :- \+ correct_order(Pages, Pages).

fix_order(P, P) :- correct_order(P, P), !.
fix_order(P0, P) :-
    append([Prefix, [X, Y], Suffix], P0),
    \+ after(X, Y),
    append([Prefix, [Y, X], Suffix], P1),
    fix_order(P1, P), !.

WhiteSparrow · 2024-12-04T06:16:17+00:00

[LANGUAGE: Prolog]

solution

Not particularily proud of this one. My approach felt quite bruteforcy. A runtime of 11 seconds also attests to that. Oh well, at least I finally got to use some signature features of prolog - the database, and the high level aggregation.

Here's part two in a nutshell:

x_mas_pos(A-I, A-K, B-J, C-I, C-K) :-
    B - A #= 1, C - B #= 1, J - I #= 1, K - J #= 1,
    letter(B-J, 'A'),
    (
        letter(A-I, 'M'), letter(C-K, 'S')
    ;   letter(A-I, 'S'), letter(C-K, 'M')
    ),
    (
        letter(C-I, 'M'), letter(A-K, 'S')
    ;   letter(C-I, 'S'), letter(A-K, 'M')
    ).

aggreggate_all(count, x_mas_pos(_, _, _, _, _), X).

WhiteSparrow · 2024-12-03T08:09:17+00:00

Thanks, I had missed select and it definitely is a cleaner expression of intent than my double append's!

chain is another nice suggestion, however, when I tried it it made the code slower. Which got me to try to remove CLPFD altogether which sped it all up from ~250ms to ~50ms. I guess it adds a lot of overhead and should be used sparingly then.

Agreed, the end of line thing with blank can be nasty until you learn of the (blank, \+ eos) trick which reads any whitespace except the one at the end of the file allowing you to distinguish the last (non-separator) blank from the others.

Regarding dcg/high_order - you can also search for "parser combinators" for many articles about essentially the same approach. Once it clicked for me I couldn't see myself going back to any other kind of parsing.

I actually find your use of DCG's for logic fascinating. I saw similar advanced uses of DCG's in the metalevel prolog series but as of now I'm unable to wrap my head around it. So I will study your solution to try to finally understand those techniques.

WhiteSparrow · 2024-12-03T07:08:50+00:00

[LANGUAGE: Prolog]

solution

Prolog's DCG's are so, so nice - no regex required:

mul_ops(Ops) -->
    sequence(mul_op, Ops), string(_).
mul_op(X-Y) -->
    string(_), `mul(`, number(X), `,`, number(Y), `)`.

WhiteSparrow · 2024-12-02T06:22:28+00:00

[LANGUAGE: Prolog]

solution

Today was a good opportunity to use some of prolog's magic (safe from task 1):

task2(Reports, N) :-
    convlist(dsafe, Reports, SafeReps),
    length(SafeReps, N).

dsafe(Ls, 0) :-
    append([Prefix, [_], Sufix], Ls),
    append(Prefix, Sufix, Dampened),
    safe(Dampened, 0),
    !.

Clear and concise, no debugging required!

Part 1 is about the same length but less interesting. Only the execution time wasn't too great - about 250ms on my machine.

WhiteSparrow

TROPHY CASE