Advent of Code 2024
My solutions to the Advent of Code 2024 contest, written in a different language each day.
Clone the repository with Git:
git clone https://github.com/salvipeter/advent2024.git
Last update: 2024.12.25.
My solutions to the Advent of Code 2024 contest, written in a different language each day.
Clone the repository with Git:
A Prolog program (htmlized version) for solving the Ball Tower problem: build a 4-story tetrahedral tower from 6 shapes, each composed of 3 or 4 connected balls. A list of all solutions (not counting symmetric/mirrored ones) is also available.
A Prolog program (htmlized version) for solving ThinkFun's Solitaire Chess problems, and generating new ones. Each puzzle sets a few pieces (of one color) on a 4x4 chessboard, and one has to find the correct series of moves, each one taking a piece, until only one remains.
A Prolog program (htmlized version) evaluating Sushi Go deals for N players. Running thousands of simulations, and assuming that wasabi cards are always used in the best possible way, random hands are worth about 37 points for 3 players, 30 points for 4 players, and 25 points for 5 players.
A Prolog program (htmlized version) solving the puzzle game "IQ Mini", along with various experiments, and a graded list of puzzles. The list contains only the positions of the three pins (with 1-1 being the top-left corner), and has a decreasing number of solutions: the first has 126 solutions, while the last only 1.
Conclusions include that
A Prolog solver (htmlized version) for the puzzle game "Block by Block" by ThinkFun. The models are read from text files, and the solution can be output to VTK files, where the points are furnished with a group number, so they can be colored appropriately with ParaView.
As an example, here's Puzzle 3 with its solution (there is only one other solution, its symmetric counterpart), and also Puzzle 8 which demonstrates that the solver does not care about gravity, so solutions like this are also accepted. For the cube (Puzzle 60), 11520 solutions are found - 48 times the number of unique solutions (240) because of the model's internal symmetries (all 24 rotations and their mirror images are the same).
Here are some of my own problems: corner1, corner2, the letter G, an ukulele, the number 6, and a strange creature.
A literate Prolog solver for the puzzle game "Gold Mine". (Markdown source here.)
A Prolog program (htmlized version) solving my puzzle game "Rainbow Snake", and which I also used extensively to experiment and try out different variants.
A Prolog program (htmlized version) solving the puzzle game "Busy Bugs", along with various experiments, and a bunch of additional puzzles.
I also drew an A4-paper DIY board (you will still need to cut out the 9x9 cm tiles), and compiled a randomized list of puzzles/solutions (in Hungarian). The solutions are the tile names (A/B/C/D) in row-major order, each supplied with the number of clockwise 90-degree rotations.
A literate Prolog solver for the puzzle game "Rush Hour". (Markdown source here.)
I have found a nice and simple dodecahedron unit origami on Mathigon, which is of course just an approximation of the regular pentagon. I had three questions:
The answers to the first question are shown on my version of the folding diagram. As for the other questions, I wrote a literate Prolog program to find a solution - it seems that there is trade-off between stability and gaplessness. (Markdown source here.)
The version by Miyuki Kawamura (in Polyhedron Origami for Beginners), folded from a square, is similar in complexity, but slightly worse in approximation quality: the top angle is 2 arcsin(4/5) ~ 106.3 degrees, while the others are 90 + 1/2 arcsin(3/5) ~ 108.4 degrees; the pocket sides are 25/104 ~ 0.24, the flap sides are sqrt(10)/13 ~ 0.24, and the bottom side is 3/13 ~ 0.23 units long.
A literate Prolog solver for the Katamino-like puzzle game "Noah's Ark". (Markdown source here.)
A literate Prolog solution to (the generalization of) the classic puzzle of swapping the white and black checkers placed in a single row. (Markdown source here.)
The classic game SET uses 81 cards formed by 3 possible values of 4 properties. But what if we had 4 possible values of 3 properties? Then we would have 64 cards instead of 81, and a set would consist of 4 cards. The question is, how many cards should we lay down on the table so that we have similar probabilities of finding a set to those in the original game?
Since the maths is fairly complex, I wrote a Prolog program (htmlized version) to do some Monte-Carlo experiments. Turns out that with the classic cards there is a set in 12 cards with probability ~97%, and almost always in 15 cards. With the alternative set, similar probabilities are achieved with 16 cards (~94%) and 20 cards, respectively.
A literate Prolog solution to an interesting problem: visit all squares on a chessboard with a knight, evading those attacked by the opponent's queen. Includes graphical (PDF) output. (Markdown source here.)
The solution, however, is not optimal. There are 10 squares with only 1 valid neighbor (including the starting square). If we also end on such a square, we still have to go out of our way to visit 8 of these, which means that a lower bound is 35 + 8 = 43 steps.
The problem can be converted into a traveling salesman problem by completing the graph, using the shortest path lengths as edge weights (computed by the Floyd-Warshall algorithm). Indexing the goal squares in the order (a1, a3, a4, a6, a7, b1, b2, b4, ...) we can generate an edge weight matrix. Now a TSP solver (such as Concorde) can solve it. Using Dijkstra's algorithm to generate the intervening steps, we can reconstruct the whole path that has only 48 steps! Note that this solves a stricter problem (finds a cycle), so the real optimum may be still lower.
Another trick is to change the distance of the starting square (node 35) from another one to 0, thereby virtually severing the connection. Trying all 35 variations, it turns out that the best is 46 steps long (e.g. by finishing at the bottom-left square, although many other squares are good, as well). This is now truly optimal.
A book version of my Prolog lessons largely based on the first part of Ivan Bratko's wonderful Prolog Programming for Artificial Intelligence.
You can also download the example code.
Clone the repository with Git:
A Prolog program finding solutions to water sort puzzles such as this one using exhaustive search.
My solutions to the Advent of Code 2016 contest, written mainly in Prolog.
Clone the repository with Git:
My solution to the Synacor Challenge. The virtual machine is written in C++, other parts are solved using Common Lisp and Prolog.
Clone the repository with Git:
A short series of lessons on Prolog and general programming, which I wrote for a friend of mine (in Hungarian). Largely based on the first part of Ivan Bratko's wonderful Prolog Programming for Artificial Intelligence, but also contains some other interesting extended examples.
Clone the repository with Git:
My solutions to the Advent of Code 2019 contest, written in Prolog.
Clone the repository with Git:
2023.11.17. Forth implementations for the first half are added.
I tried to sum up a few interesting topics in generative grammar & automata theory (in Hungarian), also including Prolog code for simulating Turing machines, and generating plants with Lindenmayer systems.
Read the HTML or get the latest MarkDown source with Git:
A Prolog program that solves all Katamino puzzles. There is a user-friendly interface, and also a convenience function that generates one solution for all problems. Another interesting feature is to look for "split" solutions, like these:
3+9: p p p|s t t t l l l l y p p r|s s t w w z z l y r r r|v s t + w w z y y c r c|v s + + + w z z y c c c|v v v + i i i i i 5+7: p p c c c|s s i i i i i p p c + c|t s s s w z z p r + + +|t t t w w z v r r r + l|t y w w z z v r l l l l|y y y y v v v 6+6: s r r p p p|w l l l l y s s r r p p|w w z z l y v s r + c c|t w w z y y v s + + + c|t t t z z y v v v + c c|t i i i i i
A Dobble deck generator, or equivalently, a finite projective plane generator, written in Prolog (and Julia). There are three algorithms: (i) naive backtracking, (ii) optimized backtracking, and (iii) direct solution for prime orders.
The programs are embedded in a Markdown memo (source), written in Hungarian. It also shows that the Dobble deck lacks 2 cards, while the Dobble Kids deck lacks 1 (the latter is also found by a snippet at the end).
A Prolog program that solves the color hexagon puzzle, where 7 hexagons with different colors on each sides have to be arranged in a flower pattern (6 outside 1 inside) in a way that all colors match. There is only one solution (and >200 million arrangements).
Brute force solution of the snake cube problem in Prolog, loosely based on a Haskell pearl article. My version also features puzzle generation (and Japanese output).
Download the source code, or see the htmlized version.
