Based on the difficulty raiting of this problem I guessed it had an analytical solution, and indeed the answer can be easily expressed in binomial terms.
Second volume in the series.
Unlike in Engines of Light, this second novel simply continues the action of the first, setting up for (hopefully) an explosive payoff.
I’m happy to read anything by MacLeod and I didn’t regret this either, but he has written better.
Another year ends. Although it has been above average for us personally, general happenings in the world have left me pessimistic about the future. Here’s hoping the fever breaks this year and we can look forward to working in the early days of a better world.
Fresh from Advent of Code 2016 I thought it would be nice if I organized my Project Euler solutions and cleaned them up a bit.
They’re being added to my Github repo as I go through them, verify they are working on newer Perls, and generally try to streamline the code.
I’ve found a few “solved” problems that don’t actually have any solutions, but where I do have access to the answer forums. I’ve used solutions there for some problems, and credited the source in the comments.
Project website: Advent of Code 2016.
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
- 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
Day 1 — No Time for a Taxicab
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.
Day 2 — Bathroom Security
Actually reading the Wikipedia article linked from day 1 helped me with part 2.
Score: 2, 4h21m.
Day 3 — Squares With Three Sides
The hardest part of this problem was cleaning up the input…
Score: 2, 3h59m.
Day 4 — Security Through Obscurity
A fun problem!
Score: 2, 3h38m.
Day 5 — How About a Nice Game of Chess?
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.
Day 6 — Signals and Noise
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.
Day 7 — Internet Protocol Version 7
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.
Day 8 — Two-Factor Authentication
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.
Day 9 — Explosives in Cyberspace
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
Score: 2, 5h11m.
Day 10 — Balance Bots
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
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.
Day 12 — Leonardo’s Monorail
Score: 2, 5h05m.
Day 13 — A Maze of Twisty Little Cubicles
I’ve been thinking a lot about day 11, so the breadth-first search concept came in handy.
Score: 2, 4h39m.
Day 14 — One-Time Pad
My solution for day 14.
This was both tough and kind of boring.
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.
Day 15 — Timing is Everything
My solution for day 15.
Fast and simple brute-force solved this one.
Score: 2, 1h06m.
Day 16 — Dragon Checksum
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).
Day 17 — Two Steps Forward
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.
Day 18 — Like a Rogue
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.
Part 2 runtime is 33s for this version.
Score: 2, 3h25m.
Day 19 — An Elephant Named Joseph
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 — Firewall Rules
Straightforward. Runtime 0.11s.
Score: 2, 4h18m.
Day 21 — Scrambled Letters and Hash
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
Score: 2, 5h19m
Day 22 — Grid Computing
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.
Day 23 — Safe Cracking
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.
Day 24 — Air Duct Spelunking
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!
Day 25 — Clock Signal
All done! Quick and dirty solution using brute force with crappy pattern detection.
Score: 2, 4h24m.