RabbitFarm
2020-12-24
Advent of Code 2020
AoC 2020 in Prolog
I had never heard of Advent Of Code before this year although it seems to have been around for six years running now! On Twitter I noticed some related posts about a week into this year’s event. After checking out what this was all about I decided this would be a fun way to continue honing my Prolog skills. I have been making a serious attempt to master Prolog and part of that has been doing a variety of programming challenges to get experience with different capabilities and nuances of the language.
Between the late start, wrapping up work projects before the end of year, and personal tasks related to the upcoming holidays (such as they will be this year) I got about halfway through the tasks. Now that I am aware that this event exists I’ll make sure to start off on day one next year!
Below are links to my solutions. The problem statements are all fairly lengthy so refer to the AoC 2020 website for details on what these are supposed to be doing.
- The solution to Part 2 should finish running sometime in late 2021. My initial approach was to create a tree of all possible adapters and then just count the leaves. It runs in just milliseconds for test cases but for the data set given … Yikes! … the run time will be very long. This is what happens when you write code too late at night! After sleeping on it I realized that something along the lines of using memoization to count and sum all the branches of the adapter tree should run reasonably quickly. However, I was using a slightly older version of SWI-Prolog that seemed to have an incomplete tabling implementation so I had to upgrade, which is easy enough I suppose, but after doing so I just decided to move on to Day 11 since I already had a late start as it was.
2020 Advent of Code Day 11 (Part 1)
2020 Advent of Code Day 11 (Part 2)
2020 Advent of Code Day 12 (Part 1)
2020 Advent of Code Day 12 (Part 2)
Notes
I kept the solutions about as “vanilla” (i.e. no libraries) as can be. As a result all the solutions have some boilerplate code for reading and preparing the input data. Each of the solutions are otherwise fairly compact, a testament to the power of Prolog.
References
posted at: 15:35 by: Adam Russell | path: /prolog | permanent link to this entry