Project website: Advent of Code 2016.
My solutions for AoC
2015.
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. Some require extra modules from CPAN.
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.
The times are hours and minutes from the time of the puzzle release
(00:00 EST) until I posted an announcement on
Twitter.
My goals for this year (in descending order of priority):
- solve all problems myself (higher cumulative score than last year’s 43/50).
- solve all problems within 24 hours of release
- be among the first 1,000 on each day’s leaderboard
Final score
- Problems solved by myself: 49 / 50 — a big improvement over last year’s 43/50.
- 3 parts not solved within 24 hours. Shortest time for both parts: 40 minutes. Average time: 5h07m.
- Average finishing place for each day: 677.8 for part 1, 747.6 for part 2.
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 15 -
Day 16 - Day 17 - Day 18 -
Day 19 - Day 20 - Day 21 -
Day 22 - Day 23 - Day 24 -
Day 25
My solution for day 1:
part 1,
part 2.
I managed to get the correct solution in part 1 despite not taking
absolute values in consideration, fixed in code.
Part 2 was frustrating as I didn’t have time to re-think the problem,
instead I kludged something on top of part 1.
Score: 2, 9h50m.
My solution for day 2:
part 1,
part 2.
Actually reading the Wikipedia article linked from day 1 helped me with part 2.
Alternate part
2, inspired by
this
solution.
Score: 2, 4h21m.
My solution for day 3:
part 1,
part 2.
The hardest part of this problem was cleaning up the input…
Score: 2, 3h59m.
My solution for day 4:
part 1,
part 2.
A fun problem!
Score: 2, 3h38m.
My solution for day 5:
part 1,
part 2.
I already had the required modules installed since 2015 day
4 and
initially thought this was going to be straight repeat. While part 1
was indeed simple enough, part 2 threw me for a little loop due to the
requirements to keep track of previous entries.
Score: 2, 2h32m.
My solution for day 6. Alternative with more map
.
Decided to try to solve this over breakfast.
Score: 2, 0h40m.
This was the last of the warmup problems. Things will get tougher
from now
on.
My solution for day 7:
part 1,
part 2.
Not very proud of part 2, but at least I know what it does. Using
regexps would be the obvious choice but I frankly lack the regex-fu to
handle it.
Update: some quick googling revealed the existence of lookahead to
deal with overlapping matches, so I whipped together an alternative
part 2. This runs
appreciably faster (although still within a second).
Just made the first 1,000 submitters for part 2.
Score: 2, 4h36m.
My solution for day 8, both
parts.
Really didn’t want to do this, it reeked of fiddly bit-flipping, but
after thinking a bit the solution presented itself.
Again just squeeked in under the 1,000 first submitters for both parts.
Score: 2, 4h27m.
My solution for day 9:
part 1,
part 2.
I’m debating whether to award myself 2 points for this, as I had to
look for hints for part 2.
The issue was that I was running a recursive solution, but instead of
simply counting the characters of a single part and then multiplying
by the number of repetitions, I actually created a new array that was
the part repeated repetitions
times! This led to horrendous
execution times.
Score: 2, 5h11m.
My solution for day 10, both
parts.
I usually don’t forget to sort numerically but I did this time, which
led to a wild goose chase trying to find out why real input differed
from test.
Family commitments prevented a faster time but I still submitted in
the first thousand.
Score: 2, 8h15m
Finally a solution after almost 6
days.
Not fantastically proud of this, kept plugging away at some solutions
even if I’d have had better luck taking a step back and
reconsidering. But I solved it myself!
The most problems I had was with the shuffling stuff to and from
floors. The last piece fell into place when I realized I had to keep
track of the elevator too when considering already visited states.
Solves part 2 in around 11m, which is just barely acceptable.
Score: 2.
Day 12 - complete solution
Score: 2, 5h05m.
My solution for day 13:
part 1,
part 2.
I’ve been thinking a lot about day 11, so the breadth-first search
concept came in handy.
Score: 2, 4h39m.
My solution for day 14.
This was both tough and kind of boring.
Key insight was this throwaway
comment
by /u/askalski. Each candidate
index is stored in a hash keyed on the duplicate character, and any
hit of quintuples is checked
A lot of subtle off-by-one errors made this quite frustrating.
Performance is respectable, especially part 2. Example input:
$ time perl ./d14.pl
==>22728
real 0m0.601s
$ time perl ./d14.pl 2
==>22551
real 0m41.553s
Update 16 Dec 2016 alternative version with cleaner code.
Score: 2, 12h18m.
My solution for day 15.
Fast and simple brute-force solved this one.
Score: 2, 1h06m.
My solution for day 16.
The nice and tidy recursive solution I coded for part one takes 1m34s
to complete part two, but this is not a very interesting problem so I
will just leave it at that.
Score: 2, 3h22m (this is day off for me).
My solution for day 17.
Straight-forward application of techniques known so far. Key to part 2
is to realize BFS returns all solutions, not just the shortest.
Score: 2, submitted after 8h57m on a Saturday.
My solution for day 18: complete.
Quick and dirty fourth Advent Sunday breakfast solution. Part 2 runs in 2m30s
using the same code as part 1, just many more rows. Brute force baby.
I might try to improve part 2 later.
Edit: here’s a a second attempt. Credit.
Part 2 runtime is 33s for this version.
Score: 2, 3h25m.
My solution for day 19 part 1: part
1.
Part 2 defeated me, this is part
2 with copied
code, credit in source.
Update: this
alternative is
way more Perlish, credit in source!
This is the first problem I actually bailed on, which is a step up
from last year. I liked it in a way that you simply couldn’t just run
part 2 as a straight continuation of part 1, but had to rethink your
strategy, but this problem was too boring for me to bother doing that.
Score: 1, 5h49m.
Day 20 - complete solution
Straightforward. Runtime 0.11s.
Score: 2, 4h18m.
My solution for day 21:
part 1,
part 2.
A boring and fiddly part 1 led to a straight-forward brute-force
solution for part 2. That part finishes in 40s on my machine.
At least I finally got to learn how
splice
works…
TODO: implement dispatch table?
Score: 2, 5h19m
My solution for day 22:
part 1,
part 2.
For part 2, I took a chance that there was nothing hindering moving
the empty slot in straight lines apart from the “walls”. A simple
count of the needed steps gave the solution.
Score: 2, 4h22m.
Complete solution.
Entirely unoptimized, runtime for part 2 is 101 minutes!
I was sidetracked by the fact that my first attempt at part 1 gave the
correct solution, but failed for part 2.
TODO: better performance?
Score: 2.
Complete solution
I used BFS to compute the distances between all points, then used the
technique from AoC 2015 day
9 to generate all possible
permutations and print them out.
Part 2 runs in less than 2 seconds.
Score: 2, 8h52m on Christmas eve!
Complete solution
All done! Quick and dirty solution using brute force with crappy
pattern detection.
Score: 2, 4h24m.