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.
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.
Dec 2015 | Dec 2014 | Dec 2013 | Dec 2012 | Dec 2011 | Dec 2010
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.
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):
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.
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.
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.
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.
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!
All done! Quick and dirty solution using brute force with crappy pattern detection.
Score: 2, 4h24m.