The Day 10 Puzzle of AOC'23 and the hcp Constraint

[Neng-Fa Zhou]

The Day 10 puzzle from Advent of Code 2023 is an interesting case study for a constraint logic programming language like Picat.

Part 1 asks for a maximum Hamiltonian cycle in a graph. This problem can be modeled naturally using the hcp constraint. However, my original model (https://github.com/nfzhou/aoc/blob/main/2023/aoc_23_10_part1.pi) did not run successfully with Picat 3.9#10 because the graph, containing more than 15,000 vertices, was simply too large. After investigating the problem, I found that the graph could be significantly preprocessed. Although the resulting graph was still too large for the original encoding, adjusting the SAT encoding strategy enabled Picat to solve the problem in about two minutes.

Part 2 asks for the number of cells enclosed by the cycle. While several algorithms exist for this problem, none of them seemed particularly straightforward to implement. I eventually devised a simple algorithm that traverses the cycle while marking the cells on its left and right. By exploiting logic variables, cells that are not directly adjacent to the cycle can be propagated and classified indirectly as belonging to the left or right region. The implementation is available here:
https://github.com/nfzhou/aoc/blob/main/2023/aoc_23_10_part2.pi

My solutions are not as efficient as Oisin's implementations (https://github.com/DestyNova/advent_of_code_2023/blob/main/10/part1.pi and https://github.com/DestyNova/advent_of_code_2023/blob/main/10/part2.pi), but I believe they are easier to understand and illustrate how naturally Picat can model the problem declaratively.

These programs require the latest version of Picat (3.9#11).

Cheers,

NF

[Oisín Mac Fhearaí]

Very elegant! I always forget about that nice conditional syntax (with -> and ;).

There's a slightly simplified part 2 solution here but still quite ugly -- I remember struggling with that logic (exactly why a more declarative / constraint-based approach would be much nicer): https://github.com/DestyNova/advent_of_code_2023/blob/main/10/part2_simpler.pi

--
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/CAFOC6HQye9xHVJx8CWqFSEYLzO4rJvRgU%3DfeCjdRCOBXbCkS-Q%40mail.gmail.com.