# Advent of code 2023 **URL:** \ **Category:** General\ **Created:** [December 2, 2023, 9:21pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025 "2023-12-02T21:21:24Z")\ **Posts on this page:** 20\ **Page:** 10
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 23, 2023, 7:40pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/208 "2023-12-23T19:40:25Z")
Thanks @CapelliC … that’s kind of you. @Boris, I note the LOC when I code stuff and then try to improve on it as a heuristic for how well I’ve used the language. How exactly you count things doesn’t matter for that purpose. Compare for example my github repo with @BarrensZeppelin – he literally solves the same things in half the LOC and if you compare the code it means what you expect: more direct solutions and/or a wider vocabulary of standard predicates. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 23, 2023, 8:01pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/209 "2023-12-23T20:01:25Z")
Is anyone else still working on day 21 part 2? I’m working on a simpler sub-problem. Rather than working on the infinite grid straight away, I’m consider how I’d handle a grid copied just once to the left, and then copied twice. I think the gist is there. It looks to me like the whole calculation has to be repeated for 1 copy, but I suspect that for the 2nd copy, it will be entirely determined by the first. Then it is easy to extend it for any number of copies, and hopefully in all directions. I expect the final answer to be something on the same order of 3751 \* 26501365/131 ~ 7.6e8, so it should be feasible to count all the cells in the worse case scenario. The fastest solution for part 1 of this problem was 1m24sec, but for both parts it was 14m35. I suspect that’s because the solution has some calculation time involved so something like the above might be the ticket 🙂 ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [December 23, 2023, 10:44pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/211 "2023-12-23T22:44:23Z")
> [@anon95304481](#): > > odd-even counting Presumably this is because: if we can only move up, down, left or right, then a position which is reachable in `N` moves _cannot be_ reachable in `N-1` or `N+1` moves (or +/- 3,5,7, etc.). Because diagonal moves are not allowed. With up, down, left or right, each move either: - Takes 1 step towards the position - Takes 1 step away from the position … and it would take another step (totalling **2** steps) to get back on track. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 23, 2023, 10:50pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/212 "2023-12-23T22:50:25Z")
Shockingly 1m24 refers to the time it took someone to read the question, solve it and post the answer as opposed to the run time of their code. I don’t even know how that’s possible but alas it is … ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 24, 2023, 9:23pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/215 "2023-12-24T21:23:20Z")
would you mind explaining a bit about how your solution works? I haven’t had time to look into part 2 any more until now. gonna put in an hour or so to see if i can progress a bit. i’ll spend some time trying to understand why your part 1 solution is so efficient – it is much faster than mine. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 25, 2023, 12:21pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/217 "2023-12-25T12:21:29Z")
I’ve cracked part 2; empirically again unfortunately rather than through computer science. Say you have a function link(X-Y, S) which is true iff a coordinate X-Y connects with the starting point in S steps, and you run this: ```prolog between(0,10,S), X is 1+(11*S), link(X-1,50). ``` Here 11 is the width of the sample grid. What you’ll see is that link/2 will alternate between true/false. I.e. the point 1-1 in the original grid is true, in the grid next to it its false, and in the grid next to that its true, and so on. Easy peasy. I still don’t know _why_ its true, but that’s a story for another day. I’ll edit this post to add a Github link as soon as I have a chance to finish the code. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 25, 2023, 7:04pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/219 "2023-12-25T19:04:39Z")
Here is an answer to your question and a curiosity. The sum of the first n odd numbers is n^2 E.g. 1+3+5+7+9 = 5^2 = 25 ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 26, 2023, 2:17pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/221 "2023-12-26T14:17:23Z")
What I’m still struggling with on Part 2 is how to scale a calculation to the whole area. I can calculate the number of times any given cell in the original map will occur in its column for the whole area, but not how it spreads out to columns in adjacent maps. For example, for 40 steps, cell 6,6 will scale across the maps in this pattern: ```prolog 1 2 3 2 1 ``` for a total occurrence in the whole area of `1+2+3+2+1 = 12`, whilst cell 1,1 will scale like this: ```prolog 1 2 3 3 2 1 ``` I can’t figure out what decides which it will be for any given cell. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 26, 2023, 9:11pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/224 "2023-12-26T21:11:19Z")
Here is a 33 LOC solution to day 22. Straightforward; a nice change from working on day 21 part 2 🙂 Solution is naive and inefficient but conceptually simple. > ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 26, 2023, 9:30pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/225 "2023-12-26T21:30:15Z")
> [@anon95304481](#): > > And I saw quadratic growth after and including N=44. Now you can do > the same for the 131x131 grid. Try it if you have time 🙂 Its super fiddly. This is basically where I’m at but using another method. I’m calculating a whole column (for the whole area) and then trying to work out what the other columns should be from it. EDIT: Oh wait, I think I’ve understood. I’ll give it a shot now. If it works I suspect it will be amongst the simplest solutions around. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 26, 2023, 10:33pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/227 "2023-12-26T22:33:41Z")
Its a weird solution since it doesn’t work for just any numbers. I’ve no idea why it works for 11 and 5 in the sample, and for 65 for the whole data. EDIT: @anon95304481 at what value did 65 steps converge for you with the input data? ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 27, 2023, 3:50pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/229 "2023-12-27T15:50:48Z")
Just want to say thank you @anon95304481 for your thoughts on this thread. It has at least taught me how/where/why to use mode directed tabling and how to code from inside out by writing predicates as if they were generators rather than functions. This latter learning especially is reshaping how I think in Prolog drastically at the moment and causing me to refactor everything. Very grateful! ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 27, 2023, 5:29pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/231 "2023-12-27T17:29:33Z")
Sorry to dwell on part 1 day 21 @anon95304481, which by now has been solved 5 different ways on this thread, but I think that the fastest possible solution would be the following which takes advantage of the odd even counting: 1. Dijkstra’s algorithm to find the shortest path between **S** and all other points with early stopping at 64 steps. 2. Count cells reached at an even steps as it goes. I think everything we’ve discussed so far will have higher time complexity than that for part 1. EDIT: Technically it doesn’t even have to be shortest paths – it can be any path at all between S and the rest of the nodes. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 27, 2023, 6:16pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/233 "2023-12-27T18:16:18Z")
I tried the above on the whole input – seems to take ages and then blow up on account of memory. Did you get it working? Also this [15 LOC solution](https://github.com/emiruz/adventofcode2023/blob/761f5bc415fdc463931fd38b7a96c1a60ab94681/day21/solution.prolog) completes in about 1.3M inferences for the 64 step problem which I think might be faster than the min based tabling solution above, even though it doesn’t use any optimisation. It suggests that maybe a bit too much is happening behind the scenes. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [December 27, 2023, 7:11pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/235 "2023-12-27T19:11:50Z")
> [@anon95304481](#): > > thank him for bringing mode directed tabling to [SWI-Prolog](https://www.swi-prolog.org/pldoc/doc_for?object=manual) Thanks, but the credits should mostly go to @friguzzi 🙂 ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 27, 2023, 10:24pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/236 "2023-12-27T22:24:36Z")
@anon95304481 I did a quick hard-coded to 64 steps solution on this basis to see what I’d get. Would you mind comparing it to your min tabling solution for time (not inferences, they seem to completely not correspond to time when comparing tabled solutions) ? With the [15 LOC implementation](https://github.com/emiruz/adventofcode2023/blob/761f5bc415fdc463931fd38b7a96c1a60ab94681/day21/solution.prolog) I get **0.7-1.5 sec** to calculate for 64 steps on the whole input. With this walk + odd/even I get **0.16-0.26 sec** : a massive improvement even in the worse case scenario. ```prolog grid(_,_,[]) --> []. grid(X0,_,Xs) --> "\n", {X is X0+1}, !, grid(X,1,Xs). grid(X0,Y0,[p(X0-Y0,V)|Xs]) --> [V],{Y is Y0+1}, !, grid(X0,Y,Xs). grid(X0,Y0,Xs) --> `.`, {Y is Y0+1}, !, grid(X0,Y,Xs). next(X0-Y, X-Y) :- X is 1+X0, p(X-Y,_). next(X0-Y, X-Y) :- X is -1+X0, p(X-Y,_). next(X-Y0, X-Y) :- Y is 1+Y0, p(X-Y,_). next(X-Y0, X-Y) :- Y is -1+Y0, p(X-Y,_). tourist(_,[],Acc,Acc) :- !. tourist(Vs,[_-N|T],A,C) :- N > 64, !, tourist(Vs,T,A,C). tourist(Vs,[H-_|T],A,C) :- ht_get(Vs, H, _), !, tourist(Vs,T,A,C). tourist(Vs,[H-N0|T],A,C) :- (N0 mod 2 =:= 0-> A1 is A+1; A1=A), ht_put(Vs, H, N0), N is N0+1, findall(X-N, (next(H,X), \+ ht_get(Vs,X,_)), Next), append(T,Next,Stack), !, tourist(Vs, Stack,A1,C). solve(File, Part1) :- phrase_from_file(grid(1, 1, Ps0), File), include([p(_,V)]>>(V\=0'#), Ps0, Ps), retractall(p(_,_)), maplist(asserta, Ps), ht_new(Vs), tourist(Vs, [66-66-0], 0, Part1). ``` ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [December 30, 2023, 7:30pm UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/239 "2023-12-30T19:30:18Z")
Day 23 was straightforward, [here is an implementation](https://github.com/emiruz/adventofcode2023/blob/69db0c10a00898685c08657ee5a608f2bcce83e5/day23/solution.prolog) in 46 LOC. I feel these later day problems are getting a bit too “just-so”. I feel like I learned more transferable things from the earlier problems. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [January 4, 2024, 8:29am UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/240 "2024-01-04T08:29:33Z")
[Here is day 24](https://github.com/emiruz/adventofcode2023/blob/71f10e6ab233b87da52b98b4d8b0fc4de6b9a493/day24/solution.prolog) in 29 LOC. Part1 was easy using either the simplex or clpq library. Part 2 is easy with Python (due to sympy or z3) but hard in Prolog. The problem: you have objects in 3D space defined by their positions X and their velocity V – both given as 3D vectors. Define a new object given by \bar{X},\bar{V}, which collides with all other objects at some time. I.e. X\_i + V\_iT\_i = \bar{X} + \bar{V}T\_i where i indexes all the other objects. For languages with a symbolic or SMT solver, you can just transcribe this and get a solution. In Prolog, under clpq, the non-linear constraints remain passive, so it produces no solutions. It so happens that the position and velocity are specified to be integers, but under clpfd, the problem requires domains to be specified. All the numbers in the question have massive ranges other than velocity, which I only know because I solved the problem by other means, so in my answer I specify is the domain for velocity: deeply unsatisfying. Then there are the idiosyncrasies of clpfd. The domain for velocity is -900 to 900, but if I change it to -1000 to 1000, I get “variables are uninstantiated” related errors. It was surprising that the range of a domain could cause errors like those in the first place! @BarrensZeppelin, am I right in saying you had the same issues? Is there a neat way to tackle this in Prolog? ---
**Author:** ![BarrensZeppelin](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/barrenszeppelin/32/6043_2.png) [@BarrensZeppelin](https://swi-prolog.discourse.group/u/BarrensZeppelin)\ **Post date:** [January 4, 2024, 8:51am UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/241 "2024-01-04T08:51:29Z")
I experienced the same issues, yes. I used an even smaller domain for the velocities. It turns out that you can turn the problem into solving a system of _linear_ equations. See [here](https://old.reddit.com/r/adventofcode/comments/18pnycy/2023_day_24_solutions/kepu26z/). But I didn’t explore that idea. ---
**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\ **Post date:** [January 4, 2024, 11:40am UTC](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025/242 "2024-01-04T11:40:44Z")
This is an excellent observation – I’ll look to refactor into it, but I still feel there is a SMT solver shaped hole in the Prolog toolbox 🙂 [Previous page](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025.md?page=9) [Next page](https://swi-prolog.discourse.group/t/advent-of-code-2023/7025.md?page=11)