### This blog post is a work in progress

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.

#### A note on scoring

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):

- match or beat last year’s score of 49/50.
- solve all problems within 24 hours of release

Link to Github repo.

#### TODO

This year’s todo list:

- Complete day 24
- Complete day 23 part 2
- Complete day 22 part 2
- Publish day 21
- Complete day 20
- Publish day 19
- Complete day 17
- Day 16 - solve part 2 without manual intervention.
- Complete day 15
- Day 14 - faster part 2.
- Day 12 - rewrite part 2 to find the answer programmatically.
- General - implement blogging and listing publication using templates
~~Publish day 18~~
~~Day 8 - clean up and publish solution~~
~~Day 11 - faster solution~~

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 25

Day 1 - complete solution

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.

Day 2 - complete solution

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.

Day 3 - complete solution

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.

Day 4 - complete solution

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.

Day 5 - complete solution

Capsule summary:

Remove elements from a list, based on rules on which neighbors an element has.

A quick and simple problem.

Score: 2.

Day 6 - complete solution

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 re-wrote
using those (essentially using a representation of the board to keep
track of the data). The day after I took the time to re-write it again
into a version closer to my original idea.

Runtime is a dismal 16s.

Score: 2.

Day 7 - part 1
Day 7 - part 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 graph-aphasic, 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.

Day 8 - complete solution

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.

Day 9 - complete solution

Capsule summary:

A game is played by placing marbles in a circle. Investigate the end state given the puzzle input.

Keywords: double-ended circular list

This was a fun problem that was marred by some irritating off-by-one
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.

Double-checking 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.

Day 10 - complete solution

Capsule summary:

Given a number of points, their positions and velocities, investigate whether they form a coherent message when printed.

Keywords: visualization

A nice palate-cleanser after the horrors of the week-end.

Runtime: 4.6s.

Score: 2.

Day 11 - complete solution

Capsule summary:

Investigate the values of subsquares on a 300x300 grid.

Keywords: summed-area table

Trying to solve part 2 using brute force took 173
minutes. Implementing a summed-area
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 off-by-one
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.

Day 13 - complete solution

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 get-go. 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 brute-force solution is
killed by my VPS.

Runtime for part 2: 2m14s.

Score: 2.

Day 16 - complete solution

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.

Day 18 - complete solution

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 off-by-one errors.

Day 19 - complete solution

Capsule summary:

Decompile a deliberately inefficient algorithm.

Keywords: registers, decompilation

Decompilation problems are not my favorite problems.

Day 25 - complete solution

Capsule summary:

Investigate points in 4D space.

Keywords: union

Last problem this year. Figured this out through brute force.