Advent of Code 2025

[Neng-Fa Zhou]

This year’s Advent of Code began a few days ago. I know some of you are already enjoying the puzzles with Picat. The four puzzles released so far are quite approachable. If you haven’t started yet, it’s not too late to catch up.

I’ve posted my solutions here: https://github.com/nfzhou/aoc. Let’s share our solutions and experiences.

I believe Picat is an excellent language for solving AoC puzzles. Although I don’t currently have funding to support participation using Picat, I would love to explore possibilities. If you have ideas for providing such support, similar to what Jane Street and Kotlin offer, please share them in the newsgroup.

Cheers,

Neng-Fa

[Oisín Mac Fhearaí]

One of my favourite things to look forward to every year! My solutions are here: https://codeberg.org/DestyNova/advent_of_code_2025

I've been relying more and more on Picat's backtracking which allows for some really nice and tidy solutions.

Oisín

[Kenneth Brown]

Really enjoying this year's problems. Here are my solutions https://github.com/siegelzero/advent2025/

[Oisín Mac Fhearaí]

While solving the puzzles I implemented a couple of generic data structures/algorithms that aren't in the Picat stdlib. I've started extracting them to a new repo: https://codeberg.org/DestyNova/picat_dsa

There's not much there yet, so don't look yet if you don't want spoilers for AoC 2025 :)

Maybe in future we can move some of them (and/or reimplement them more efficiently) to the standard Picat distribution?

[Neng-Fa Zhou]

That's a great idea. Let's expand the util module and invite people to contribute after AOC'26 ends.

Cheers,

NF

--
You received this message because you are subscribed to the Google Groups "Picat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to picat-lang+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/picat-lang/51978c43-b068-4bb6-a8b0-9d0458f1c8cdn%40googlegroups.com.

[Neng-Fa Zhou]

Today is a happy day for Picat in this year’s AoC: the Day 10 problem really showcases Picat’s strengths in tabling and constraint solving. I solved Part 1 easily using tabling, but applying the same approach to Part 2 turned out to be too time-consuming. After formulating a COP model using SAT, I was able to solve it!

https://github.com/nfzhou/aoc/blob/main/aoc_25_10_part1.pi
https://github.com/nfzhou/aoc/blob/main/aoc_25_10_part2.pi

Cheers,

NF

[Oisín Mac Fhearaí]

I solved part 1 using the planner, but it was too slow for part 2 (and doing too much work, since the ordering of button presses doesn't matter in the problem). After a while I got a SAT formulation working which produced the correct answer in about a minute. Amazingly, I then tried the "mip" module with the GLPK solver option, which produced the correct answer in 0.9 seconds!

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/CAFOC6HTXpg0cya_5hS4qLFD6vr4ACR_gYC78Pn%3D7NmntCwjG%3DQ%40mail.gmail.com.

[C. G.]

Here are my solutions: https://github.com/cgrozea/AdventOfCode2025-Picat

I compete with Oisin (DestyNova) on the leaderboard from the last year - he is faster and also explains his solutions, but now and then one of my solutions is simpler or runs faster, so it is potentially interesting to look at them.

C.G.

[Peter Bernschneider]

Day11 also is perfect for Picat! See Link

[Oisín Mac Fhearaí]

Peter, your code is very clear, concise and effective.

I still have to study some of Cristian's clever tabling solutions from last year; it seemed like you were able to very quickly solve problems just using tabling, where I tried the planner with little success.

Thanks all for sharing your solutions! I always learn something new from everyone's different approaches. Today I wasted a lot of time trying to bottom-up DP but eventually went back to tabling and got it to work.

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/634dcd45-d844-41c9-84d8-e973860b6f86n%40googlegroups.com.

[C. G.]

I agree, the code of Peter for problem 11 is really nice.

[Neng-Fa Zhou]

Here is my solution to the day-11 part-2 problem:

https://github.com/nfzhou/aoc/blob/main/aoc_25_11_part2.pi

It follows the same idea as Peter's, but it runs ten times faster because it represents device names as atoms rather than strings, and it uses the nt mode to avoid tabling the graph. 

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/e2ab5925-0673-4c87-803a-a2bc6aa19be9n%40googlegroups.com.

[Neng-Fa Zhou]

As expected, the day-12 problem is brutal. Here is my first attempt to formulate it as a CSP for sat:

https://github.com/nfzhou/aoc/blob/main/aoc_25_12_part1.pi

It works for the example instance but is unable to pack presents in any region (it takes too long to even  generate constraints). 

Cheers,

NF

[C. G.]

Hi NF,

The problem would have been brutal weren't for the too easy instances proposed (both the positive and the negative ones). Anyway, I also tried to solve it truly for the general case with constraints and SAT solver in Picat: https://github.com/cgrozea/AdventOfCode2025-Picat/blob/main/day12/part1.pi

My version works, it takes some minutes per instance. Just for fun (and having access to a machine with a lot of RAM) I tried after the fact to ran it with parallelism 50 (one instance per call), and thus in a few hours it solved the 1000 instances but for 15, which exceeded Picat stack+heap area size. I've tried for one of those to call Picat with -s and to give it 20 GB, it seemed interestingly to build the model faster (fewer GCs I guess) and then got to solving it.

What I find interesting, after realising that all instances are easy, is that my modelling leads to instantaneous refutation of the instances without solution, but requires several minutes for equally easy instances for which trivial solution exist. I thought I'll just change the variable search mode to random or something like this, to "spread" the translations, but the solve prredicatr for sat doesn't seem to have this sort of option, only cp - and cp was very slow even on the smaller examples from the text of the problem.

So I'm left wondering, how to model or call the solver in such a way that also the trivial positive instances are also quickly solved by the solver, not only the negative ones.

best regards,

CG

[Oisín Mac Fhearaí]

Day 12 was very frustrating. I also tried a SAT formulation first, and it works for the example but takes maybe 10-15 minutes or more per line of the real data. It was also extremely painful to produce a working SAT program this time...

I also tried a planner solution but it got stuck in the same place. As is often the case when (misusing) the planner for this type of problem, the order of placing pieces doesn't matter, so the planner is probably an inappropriate tool.

Someone gave me a hint that caused me to visit something I tried earlier that does NOT work for the sample data, but allows a completely trivial (but *very* unsatisfying) solution to the full input. I'd like to revisit this one and "properly" solve the general case!

--

You received this message because you are subscribed to the Google Groups "Picat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to picat-lang+...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/CAFOC6HTjeYTHBHogJEv-cqAXk8jM-XLeXah%2B8iC492Frda2aYQ%40mail.gmail.com.

[Neng-Fa Zhou]

You are a genius, Cristian! I really need to reformat your code in order to comprehend it:-)  Could you explain what trivial cases are? You could use double negation (not not p(X)) to mitigate memory issues.

Cheers,

NF

--

You received this message because you are subscribed to the Google Groups "Picat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to picat-lang+...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/895a445a-a49d-4244-bbba-a4eb40ddfd1an%40googlegroups.com.

[Cristian Grozea]

Hi NF,

I still wish I was, but I'm not.

The trivial negative cases are the ones where the total number of squares to set is over the total number of squares in the rectangle (fast fail with predicate "check" in my code).

The trivial positive cases are the ones for which the number of 3x3 squares required fits without overlapping. Fast success with predicate "trivial" in my code. 

Concerning the memory, what happens when one keeps building and solving CSPs in a Picat program? It looked to me the memory used keeps growing, is there a way to free the memory used by one problem before going to the next one? Or is exactly that what the not(not)) technique achieves?

best regards,

CG

[Neng-Fa Zhou]

Thanks, Cristian, for your explanation.  That's interesting. With these two trivial cases treated specially, my program also easily solves the problem (in 0.033s). 

My initial program used StartR2 #!= StartR1+Dr #\/ StartC2 #!= StartC1+Dc inside a nested loop. After introducing two variables DiffR and DiffC (DiffR #= StartR2-StartR1,  DiffC #= StartC2-StartC1) outside the loop, and rewriting the constraints in terms of these new variables, I made the program run several times faster. The Picat compiler should do this automatically by eliminating common subexpressions in constraints.

Regarding repeated calls to solve, as solve(Vs) is nondeterministic, it doesn't clean up the data created during encoding. You can use solve_once, defined below, to make solve deterministic and reclaim the memory through backtracking:

solve_once(Vs) =>
    M = get_global_map('_solve'),
    solve_once_aux(Vs,M).

solve_once_aux(Vs,M) ?=>
    once solve(Vs),
    M.put(answer,Vs),
    fail.
solve_once_aux(Vs,M) =>
    Vs = M.get(answer,[]).

I think this predicate should be added into the Picat library.

Cheers,

NF 

[Neng-Fa Zhou]

I realized that this implementation of solve_once does not clear the constraint store after it succeeds, so constraints posted after the call are accumulated in the store. I will consider how to implement this at a lower level.

Cheers,

NF

On Sat, Dec 13, 2025 at 6:57 PM Oisín Mac Fhearaí <denpa...@gmail.com> wrote:

Hmm... perhaps I'm using it wrong, but I tried replacing my SAT solution's call to "solve" with a call to "solve_once", and it seems to break the program.

https://codeberg.org/DestyNova/advent_of_code_2025/src/branch/main/12/part1_sat_infeasible.pi#L56-L62

Specifically, for the third example in the sample data, it should fail to solve because the 7th shape can't be placed in the grid.

My solution writes a unique Id (sequence number) of each shape placed into the grid. Then, to avoid having non-constrained values of the grid take some random value (probably not necessary), I added a flattened version of the grid and used "exactly(7,Flat,Id)", since all shapes consist of 7 filled tiles and 2 blank tiles.

The third call to solve_once produces an invalid solution -- both Grid and Flat contain only 6 nonzero ID values, meaning the 7th shape was not written. So the "exactly" constraint should fail, but doesn't.

However, if I just use "solve" as before, it correctly fails to solve that instance.

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/CAFOC6HTAcjUuka3-qeeEWSr9ZQ0%2BHXDSpGFwpNg%2B1VMyfNOG6g%40mail.gmail.com.

[Oisín Mac Fhearaí]

Hmm... perhaps I'm using it wrong, but I tried replacing my SAT solution's call to "solve" with a call to "solve_once", and it seems to break the program.

https://codeberg.org/DestyNova/advent_of_code_2025/src/branch/main/12/part1_sat_infeasible.pi#L56-L62

Specifically, for the third example in the sample data, it should fail to solve because the 7th shape can't be placed in the grid.

My solution writes a unique Id (sequence number) of each shape placed into the grid. Then, to avoid having non-constrained values of the grid take some random value (probably not necessary), I added a flattened version of the grid and used "exactly(7,Flat,Id)", since all shapes consist of 7 filled tiles and 2 blank tiles.

The third call to solve_once produces an invalid solution -- both Grid and Flat contain only 6 nonzero ID values, meaning the 7th shape was not written. So the "exactly" constraint should fail, but doesn't.

However, if I just use "solve" as before, it correctly fails to solve that instance.

On Sat, 13 Dec 2025 at 16:08, Neng-Fa Zhou <neng...@gmail.com> wrote:

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/CAFOC6HTAcjUuka3-qeeEWSr9ZQ0%2BHXDSpGFwpNg%2B1VMyfNOG6g%40mail.gmail.com.