Advent of code 2023

General
90

If the last letter of the first word is the same as the first letter of the next word then you can chain them (there are only 8 such possibilities). E.g. twone. But this is a problem for the conversion of words to numbers because neither 2ne or tw1 is desirable in the above case. I first convert twone into twoone, and then it can be converted to numbers unambiguously.

One transform (tr) does both and is called twice on the phrase_from_file/2 line. Disambiguation cannot take more than one call because of what it does.

Hopefully that helps clarify it?

91

Regarding “where” the compound pairs come form, it was evident to me by just looking at the 9 number words. Again, that last/first letters must correspond makes the comparisons simple to do mentally. Just start with the first, check it against the other eight, right down any pairs, and continue to the next.

93

I see some problems though. Sequences like threeight could technically be chained indefinitely, so searching first backwards and then forward as others have done is the more general solution: I’ll change it for the repository.

94

You could also define “last match” as “match without any matches after it”. This way you can skip searching backwards and forget about “oneight” sort of things. This was my attempt (which seemed to work for the input):

first_digit(L, D) :-
    phrase(( string(_), d(D) ), L, _), !.

last_digit(L, D) :-
    phrase(( string(Prefix), d(D) ), L, _),
    \+ phrase(( string(Prefix), string([_|_]), d(_) ), L, _),
    !.

d(D) --> digit(D0),
    { D is D0 - 0'0 }.
d(D) --> spell(D).

spell(1) -->  "one".
spell(2) -->  "two".
spell(3) -->  "three".
spell(4) -->  "four".
spell(5) -->  "five".
spell(6) -->  "six".
spell(7) -->  "seven".
spell(8) -->  "eight".
spell(9) -->  "nine".

If anyone can come up with a cleaner way to restart searching please let me know. I mean this part:

string(Prefix), string([_|_])

Here string(Prefix) consumes the prefix matched so far and string([_|_]) steps one or more ahead before matching again.

95

So here is a solution in the same vain (forward backward search) in 21 LOC. Do you think its cleaner?

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

line(Fs,Frs-Lst) --> string_without(`\n`,S),{fwd(S,Frs,Fs),bck(S,Lst,Fs)}.
lines(_,[]) --> [].
lines(Fs,[L|Ls]) --> line(Fs,L),`\n`,!,lines(Fs,Ls).
lines(Fs,[L]) --> line(Fs,L).

words(X,N) :-
    Cs=[`one`,`two`,`three`,`four`,`five`,`six`,`seven`,`eight`,`nine`],
    nth1(I,Cs,X),number_codes(I,[N]).
digits([X],X) :- member(X,`123456789`).

fwd(L,N,Fs) :-
    append(_,R,L), member(F,Fs), call(F,X,N),
    append(X,_,R),!.

bck(L0,N,Fs) :-
    reverse(L0,L), append(_,R,L),
    member(F,Fs), call(F,X0,N),
    reverse(X0,X), append(X,_,R),!.

solve(File,Part1,Part2) :-
    phrase_from_file(lines([digits],Ls),File),
    aggregate_all(sum(X),(member(A-B,Ls),number_codes(X,[A,B])),Part1),
    phrase_from_file(lines([words,digits],Ls2),File),
    aggregate_all(sum(X),(member(A-B,Ls2),number_codes(X,[A,B])),Part2).

@anon95304481 what do you think? Tick all the boxes (other than code comments and meaningless variable names :slight_smile: )

97

Well other than the fwd/bck append chain, which is pretty magical :slight_smile: I thought I may be able to make it shorter using append/2 … and then I discovered how much the order of the clauses matters.

99

Gonna post it since I wrote it before your edit :slight_smile:

?- member(R,`abc`), append([_,[R],_], `cba`).
R = 97 ;
R = 98 ;
R = 99 ;
100

How long does this take? My solution for part 1 is… extremely slow to say the least.

101

That’s probably because you are running some part of your DCG over the whole input for every line. The solution above is sub-second.

102

Day 10 part 2 is HARD. I’m still working on it but doubt I’ll crack it today. Not giving up though :slight_smile:

103

My solution for day 10. Combined, both parts run in 0.5 seconds. While the combined LOC was around 60, I followed the feedback on documentation to try to explain the solution in the hope it’s more useful here. Let me know if this is an improvement over the previous entries.

@anon95304481 I like your remarks, especially the one about people mangling the language not using backtracking enough and instead relying on functional patterns (I’m surely guilty of this, since I come from the Haskell world). Please continue highlighting improvements to the code I write, if you happen to read it. Mostly I’m interested in how to architect the code to get maximal mileage out of logical patterns.

105

I’ve finally solved day 10 :slight_smile: My code for it is puke (58 LOC), I’ve put it here with a “first attempt caveat”. @meditans I’m in awe of you if your code runs in 0.5sec for both points. I’m going to struggle on this for another few days independently but then I really look forward to see seeing your solution.

Taking part 1 as give above, I solved part 2 by:

  1. Replacing “S” with an actual tile.

  2. Homogenising all points which are not a boundary point, so that all points are either in the boundary or not.

  3. Adding in-between (+/- 0.5) tiles so that its possible to navigate between pipes.

  4. Pick any point, get its connected component (takes ~20 minutes). The points in that component are either in the boundary or they are not. If not, the boundary points are the complement of it.

106

@anon95304481 I can’t understand what it is in @meditans code which makes it run so much faster than mine. It runs for part 1 in 0.5 seconds allegedly, mine takes 30 seconds:

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

ns(N,V) :- number_string(N,V).

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).

m(A,B) :- memberchk(A,B).

above(p(X0-Y,V0),p(X-Y,V)) :- X0-X=:=1,m(V0,`S|LJ`),m(V,`S|7F`).
below(p(X0-Y,V0),p(X-Y,V)) :- X-X0=:=1,m(V0,`S|7F`),m(V,`S|LJ`).
left(p(X-Y0,V0),p(X-Y,V))  :- Y0-Y=:=1,m(V0,`S-J7`),m(V,`S-FL`).
right(p(X-Y0,V0),p(X-Y,V)) :- Y-Y0=:=1,m(V0,`S-LF`),m(V,`S-7J`).

link(P1,P2) :- above(P1,P2);below(P1,P2);left(P1,P2);right(P1,P2).

cycle([H|T],Term,End) :-
    p(A-B,C), link(H,p(A-B,C)),
    \+ (T\=[],p(A-B,C)=Term),
    \+ memberchk(p(A-B,C),T),!,
    cycle([p(A-B,C),H|T],Term,End).
cycle(Acc,_,End) :- reverse(Acc,End).

solve(File,Part1) :-
    phrase_from_file(t(1,1,Xs),File),
    retractall(p(_,_)),maplist(assertz,Xs),
    p(X-Y,83), cycle([p(X-Y,83)],p(X-Y,83),Bs0),
    length(Bs0,N), Part1 is N/2.

cycle/3 takes all the time in my code, the majority of it is spent in the link/2 predicate. Is there something more I can do to above that stands out to you? @CapelliC, I don’t know if there is a more specialised or lazy data structure which would make more sense? Is there some inherent advantage to using a DCG for this?

108

Please let me know if you figure it out, mine also takes 30 seconds for part 1!
I’m doing day 11 right now, and it’s also taking a very long time to run, so I need to figure out how to optimize Prolog :grin:

109

:smile: it’s surely very idiosyncratic: as I mentioned at the beginning of this AOC thread, I’m using prolog to explore different ways of writing programs. It’s not meant to provide an exemplary style, and in fact I myself wouldn’t write this code in another setting. But here, I want to have fun and explore language design. Caveat emptor.

This is one of the questions I’m trying to explore: how much evaluation could we have in a prolog system. Of course, one can say none, but I think there is a reason for which
pack(func) or pack(function_expansion) exist, and arguably the dict function syntax in swi prolog is a step in the same direction. ξ is for in-place numerical evaluation.

This stems from the tension between two (exploratory) ideals:

  • On one end, I really don’t like uncontrolled side effects (like assert). They make the code difficult to understand for me, and especially in the context of AoC where I often switch input examples, they allow errors that stem from inconsistency. So set_knowledge is the only point in which knowledge is asserted, and it gives me some guarantees I like.
  • On the other I am trying to eschew usage of data structures to store facts. I want to explore a style in which everything I know about the problem is asserted as a fact and see where that leads.

So the tradeoff among the two is collecting all the knowledge, and then asserting it in one transaction. Using subterms gives me more liberty in how I create the datastructure that holds the knowledge, and I can selectively choose which predicates to assert, without changing the collection process.
For me, the ideal solution would be prolog having a notion of a local knowledge base, thus making set of predicates a composable first-order notion.

It’s difficult to say without profiling your code, which unfortunately I can’t do at the moment. I would suggest using profile/1 when poking around both programs. At a first and superficial glance, it seems to me that there are big lists in your solution, and they get traversed a lot. Since I assert the terms, I’m not paying that cost (because of indexing).

110

Actually, having loaded your solution and profiled it for a minute, I can suggest a better course of action. After having run the solution once, so the predicates are asserted, try to run:

p(X-Y, 83), trace, cycle([p(X-Y, 83)], p(X-Y,83), Bs0).

which is the query in your main program. By stepping manually in the execution, you can observe that:

cycle([H|T],Term,End) :-
    p(A-B,C), link(H,p(A-B,C)),

the first term, p(A-B,C) makes us backtrack over any possible place. And we will do it again when we need to choose the next step. All of this is incredibly wasteful! If you have two consecutive pieces of the loop, you know where the third one is (in fact this is what is accomplished in my code with:

path_triple(p(Pos1, _), Middle, p(Pos2, _)) :-
    p_near(Middle, Positions),
    permutation(Positions, [Pos1, Pos2]).

If I pass to path_triple/3 two concrete terms, the position of the last one will be determined without any search or backtracking. I’d suggest to fix this, and then we’ll try to find another improvement.

111

Part 1 now runs in 2.283 sec :slight_smile: Check it out @Garklein

I made a minor change to cycle and added a possible/2 predicate which looks for nearby candidates:

possible(p(X0-Y0,_),X-Y) :- 
    X is X0+1,Y=Y0; X is X0-1,Y=Y0; X=X0,Y is Y0+1; X=X0,Y is Y0-1. 

cycle([H|T],Term,End) :-
    possible(H,A-B), p(A-B,C), link(H,p(A-B,C)),
    \+ (T\=[],p(A-B,C)=Term),
    \+ memberchk(p(A-B,C),T),!,
    cycle([p(A-B,C),H|T],Term,End).
cycle(Acc,_,End) :- reverse(Acc,End).

An important thing to note that makes this work is that possible(H,A-B) limits what p(A-B,C) can be and due to first variable indexing looking up p(A-B,C) is very fast. This doesn’t work with p(A,B,C).

112

I think part 2 runs quickly due to this:

We know from elementary geometry that we can determine if a point is inside a
loop by tracing a straight line in a random direction, and counting the number
of intersection points: if the number is odd, we are inside, if even, outside.

I.e. it doesn’t run a fill to try and work out what’s within the boundary like my code does which is necessarily more compute intensive. You just basically go left and see how many boundary points you hit: if its an odd number then you must be in the boundary. This also means there’s no need to do anything fancy with the coordinate system (like I did) to work out if things are squeezing between pipes.

Its a highly leveraged insight, but I don’t really lament its absence: you either know the fact above or you don’t at the time of the problem, you’re unlikely to work it out during, unless you look it up, but that isn’t the point of the exercise for me :slight_smile:

113

Logtalk embeds your wishes ! Alas, Paulo left our community some time ago…

114

Ok, a solid day 10 solution in 43 LOC, with no magic (wink wink @anon95304481). Repo with comments is here.