Dec 2017  Dec 2016  Dec 2015  Dec 2014  Dec 2013  Dec 2012  Dec 2011  Dec 2010

Subscribe

Reading

About
Being the thoughts and writings of one Gustaf Erikson; father, amateur photographer, technologist.
Frequently updated microblog.
More stuff can be found at gerikson.tumblr.com and Flickr.
I toot at @gerikson@mastodon.social.
Follow my bookmarks at Pinboard.
This year was a tough one. I believe the abundance of weekends this December added to the number of quite tough problems. Day 15 seems to have been a really big stumbling block for many people.
I’m still not finished at time of writing, I’m at 38 of 50 stars. The TODO list is at the main entry for this year’s contest.
Despite miserably failing in completing each challenge in the day it was released I’m still happy I have some problems remaining going forward.
Project website: Advent of Code 2018.
Previous years: 2015, 2016, 2017.
I use Perl for all the solutions.
Most assume the input data is in a file called input.txt
in the same
directory as the file.
I score my problems to mark where I’ve finished a solution myself or given up and looked for hints. A score of 2 means I solved both the daily problems myself, a score of 1 means I looked up a hint for one of the problems, and a zero score means I didn’t solve any of the problems myself.
My goals for this year (in descending order of priority):
This year’s todo list:
Day 1  Day 2  Day 3  Day 4  Day 5  Day 6  Day 7  Day 8  Day 9  Day 10  Day 11  Day 12  Day 13  Day 14  Day 16  Day 18  Day 19  Day 22  Day 24  Day 25
Capsule summary:
Investigate the properties of summing an infinite list of integers.
A nice start to this year’s puzzles.
I had planned on getting up at 6AM to start with this but I spent the night before playing Fallout 4 so that didn’t happen.
Score: 2.
Capsule summary:
Investigate the properties of the strings given as input.
Another O(n^2) solution, but for the small sizes involved it barely matters.
Perl’s string munging is helpful as always.
Score: 2.
Capsule summary:
Investigate the properties of overlapping areas given as input.
Nice and clean. I was worried I’d have to do some complicated lookups to single out the correct swatch in part 2, but it turns out that there was only one possible solution in my input.
Score: 2.
Capsule summary:
Given a list of activities, determine properties about the times these activities occur.
Getting the correct answer without resorting to an external run
through sort n
was the hardest part of this problem!
There are some nice solutions using a Schwartzian transform out there but to be honest I’d rather have something straightforward and dumb that can understood later.
TODO: better variable naming.
Score: 2.
Capsule summary:
Remove elements from a list, based on rules on which neighbors an element has.
A quick and simple problem.
Score: 2.
Capsule summary:
Investigate areas on a grid, expressed in Manhattan coordinates.
Keywords: Voronoi diagram
This took some careful perusal of the text and example to figure out. I had a lot of problems with my solution when I tried to merge part 1 and part 2 into one solution. Unfortunately I had overwritten the code that actually gave me the first star, and I broke it.
I felt justified to check out other solutions and finally rewrote using those (essentially using a representation of the board to keep track of the data). The day after I took the time to rewrite it again into a version closer to my original idea.
Runtime is a dismal 16s.
Score: 2.
Capsule summary:
Find a path through a graph, given that some steps must be done to proceed.
Keywords: DAG, directed acyclic graph, topological sort
I’m really happy with solving this. I’m graphaphasic, as in I’ve never ever grokked them in code, and was dreading finding some random Perl module that I didn’t really understand. In the end I just found the “endpoints” and processed it using a queue.
This made part 2 reasonably easy to code.
Score: 2.
Capsule summary:
Investigate the properties of a tree structure given in the form of a string of integers.
Keywords: tree structure, recursive
I had a lot of trouble with this, which wasn’t helped by stuff like people coming over to visit, dinner to cook and eat, and wine to drink. After these distractions were done with I could revisit the problem with fresh eyes.
Score: 2.
Capsule summary:
A game is played by placing marbles in a circle. Investigate the end state given the puzzle input.
Keywords: doubleended circular list
This was a fun problem that was marred by some irritating offbyone errors in the results. We were blessed with a wealth of example inputs, and I could make most of them work by taking the largest or the next largest value. This gave me my second star, but it was hardly repeatable.
Doublechecking my logic against other solution revealed I was thinking correctly, but had a stupid overrun where I managed to take more marbles than were actually available…
Runtime for part 2 is 30s, but you need quite a lot of memory to run it. My wimpy VPS cannot run it natively.
Score: 2.
Capsule summary:
Given a number of points, their positions and velocities, investigate whether they form a coherent message when printed.
Keywords: visualization
A nice palatecleanser after the horrors of the weekend.
Runtime: 4.6s.
Score: 2.
Capsule summary:
Investigate the values of subsquares on a 300x300 grid.
Keywords: summedarea table
Trying to solve part 2 using brute force took 173 minutes. Implementing a summedarea table reduced it to 3s.
Score: 2.
Day 12  part 1 Day 12  part 2
Capsule summary:
A number of plants grow in an infinite line of pots. The existance of a plant for the next generation depends on its neighbors. Investigate what plants remain after a number of generations.
Keywords: cellular automata
This was a fiddly one. I got bit by the shallow copying nature of
Perl’s data structures, but implementing the Clone
module took care
of that.
Then is was just a question of dealing with the inevitable offbyone errors.
Part 2 was found by reasoning that the pattern would stabilize, and after that is was just a matter of finding the pattern and identifying the offsets.
My Part 1 code can either give the answer to the question with no input, or output some useful metadata if given another argument.
Part 2 answers the question by default, and gives the value for an arbitrary input if that’s given as an argument.
Score: 2.
Capsule summary:
Carts move along a track with turns and junctions. Determine whether they collide.
I’m both proud and ashamed of this one. Proud because my basic code determining how the carts move was correct from the getgo. Ashamed because it took me all day to figure out the collision detection.
Runtime: 0.4s
Score: 2.
Day 14  part 1 Day 14  part 2
Capsule summary:
A list is generated programmatically. Investigate its properties as it grows.
Keywords: pattern matching, brute force
Not my favorite problem, not least because my bruteforce solution is killed by my VPS.
Runtime for part 2: 2m14s.
Score: 2.
Capsule summary:
An obfuscated register manipulation routine is presented. Solve the program.
Keywords: registers
This years Register Rodeo! It was fun apart from the horrid input parsing.
Score: 2.
Capsule summary:
Investigate the properties of a Game of Life setup.
Keywords: game of life
A scruffy solution. I had no problems with part 1, but part 2 was plagued by offbyone errors.
Score: 2.
Capsule summary:
Decompile a deliberately inefficient algorithm.
Keywords: registers, decompilation
Decompilation problems are not my favorite problems.
Score: 2.
Capsule summary:
Find the quickest path between two points on a graph.
After some struggle, I finally figured out a good way to conceptualize this.
Right now I’m using straight Djikstra’s which is way too slow.
Edit 20210109 it turns out my issue wasn’t with the Dijkstra’s algo per se, but instead with my implementation of the required priority queue. After using a highperformance version from CPAN I got my runtime down from 15 minutes to around 2 seconds.
Score: 2.
Man, this was a slog. I coded it all myself, but got help online from working solutions to figure out where I was doing it wrong.
Part 2 was found manually.
Score: 2.
Capsule summary:
Investigate points in 4D space.
Keywords: union
Last problem this year. Figured this out through brute force.
Score: 1 (final star only awarded if all other solutions are done!)