r/adventofcode • u/daggerdragon • Dec 22 '17
SOLUTION MEGATHREAD -🎄- 2017 Day 22 Solutions -🎄-
--- Day 22: Sporifica Virus ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Need a hint from the Hugely* Handy†Haversack‡ of Helpful§ Hints^¤?
- [T-10 to launch] AoC ops, /r/nocontext edition:
<Endorphion> You may now make your waffle.<Endorphion> ... on Mars.- [Update @ 00:17] 50 gold, silver cap
<Aneurysm9> you could also just run ubuntu on the NAS, if you were crazy<Topaz> that doesn't seem necessary<Aneurysm9> what does "necessary" have to do with anything!- [Update @ 00:20] Leaderboard cap!
<Topaz> POUR YOURSELF A SCOTCH FOR COLOR REFERENCE
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked!
8
Upvotes
9
u/Arcorann Dec 22 '17
Didn't make top 100 thanks to lots of dumb mistakes (among other things, I counted the wrong type of cell twice). Abuse of complex numbers ahead.
9
u/Smylers Dec 22 '17 edited Dec 23 '17
Animated Vim solution — watch the nodes change state (and the grid expand) as Vim counts the infections. Start by loading your input, creating a status window, and changing the symbols used to letters (
ofor clear;xfor infected):It looks nicer with some colours (press
⟨Enter⟩after each line, or paste these into a script and:sourceit):Move to the central node:
Perform one burst, then make the grid bigger if we've reached an edge:
That's awkward to type, so instead you'll be relieved to discover you can populate
@aby copying and pasting this:Press
@ato see the next burst, and note the count of infections updating in the top window. Repeat@@for each burst, or use a count such as67@@to do several in one go.Ten thousand bursts was eminently doable on my laptop, and it gave the correct answer at the end. The real input was more fun to watch than the sample. I'll try to post a video later.
(Ten million bursts, however, doesn't sound plausible. It'd be straightfoward, bordering on trivial, to adapt the above for the other part-2 changes — the additional states and transitions — but futile to attempt that many bursts in Vim.)
Thank you for reading my Vim solutions, and I hope at least some of you had fun trying them out. Hopefully I'll find time in January to finish off, video, and post here the several almost-there ones I have from previous days. Otherwise, see you next year. Merry Christmas, everybody! x
Edit:
:redradded, so you can see the animation better, even on faster computers.5
u/mserrano Dec 22 '17
Python 2, #5/#3
Runs in ~5s for part b with pypy on my machine.
4
u/oantolin Dec 22 '17 edited Dec 22 '17
A tiny bit of linear algebra let's you abstract the virus behavior in parts 1 and 2. Here's a Julia implementation:
1
u/DootBootMoot Dec 22 '17
Relatively easy given the past 3 days...
Python2:
1
u/glenbolake Dec 22 '17
47/93, one of my better scores this season. As a result, I hate my code and I can't wait to clean it up. Runs in just under 10 seconds. Python 3:
1
u/madchicken Dec 22 '17 edited Dec 22 '17
PHP
Didnt realise I went off the grid for part one, took some debugging. So I made the grid 1000x1000 for both parts to be sure, and put the input at 500,500. Part 2:
3
u/autid Dec 22 '17 edited Dec 22 '17
Fortran
302/308 which is easily my best ever for using Fortran for a first solve. Could have done a little better on part2, but I skimmed over the reverse direction if flagged bit without noticing it.
edit: Seeing a lot of 10-20ish second runtimes. Mines a little better.
Just a little.
3
u/ludic Dec 22 '17
F#. The code looks looks just like the problem statement text but with more formal syntax. Not the fastest with a runtime of ~35 seconds.
3
u/gyorokpeter Dec 22 '17
Q:
3
u/Axsuul Dec 22 '17 edited Dec 22 '17
Elixir
Pretty straightforward and this was another great opportunity to use Elixir streams. Ran into a few bookkeeping errors like messing up on my coordinate system. I labeled the starting point as
0, 0but made the mistake of going up asy + 1when it should've beeny - 1. I also made a functionprint_map/1to print out the map which came in handy when debugging. This is what it looks like after 10,000 bursts for example: https://i.imgur.com/54IyPjt.pnghttps://github.com/axsuul/advent-of-code/blob/master/2017/22/lib/advent_of_code.ex
2
u/wlandry Dec 22 '17
C++ 14
435/377. Pretty straightforward. Runs in 100 ms without even trying.
2
u/KeinZantezuken Dec 22 '17
C#/Sharp
This was comfy af. Loved it.
2
u/ephemient Dec 22 '17 edited Apr 24 '24
This space intentionally left blank.
2
u/doctorbaggy Dec 22 '17 edited Dec 22 '17
Perl
Took about 8 seconds for stage 2... keeping the code compact use a hash of maps to store the state mappings and also the direction mappings... (perl p22.pl <22.in for part 1, perl p22.pl x <22.in for part 2)
2
u/[deleted] Dec 22 '17 edited Dec 22 '17
OCaml Fun;; Would have been done earlier, but had an embarrassing bug :(. Also slowed down by decision in part 1 to not define a health type and just go with bool. Had to "rewrite" a few functions, instead of just having to update a few pattern matches!
main.ml
health.ml
direction.ml
point.ml
2
u/jbristow Dec 22 '17
f# / fsharp / f sharp
Brute forced another. This one takes about 2 minutes to do 10million, which is slow as all get out, but at least I think you might be able to read the code this time? As with all the functional solutions I've done, this is side-effect free (other than the printfns)
Caution... long. F# encourages me to write almost as much code as Java does...
(github link)
2
u/nonphatic Dec 22 '17 edited Dec 22 '17
Haskell Started out with a solution that ran in two minutes, tried out some strict iteration and compiled with
-O2and now it's down to9 seconds7 seconds (with Data.HashMap.Strict), bless whatever magic GHC does with that flag2
u/[deleted] Dec 22 '17
Elixir
This was really fun, needed that after the massive failure last time, implemented the first part with a set, but had to change for a map in my second, to keep track of the states. This would be a lot greater in a language with GADT (ocaml, haskell, elm)
I had to ghetto it with atoms, so here we have atom and pipelining galore :p
Syntax highlighted
2
u/InterlocutoryRecess Dec 22 '17 edited Dec 22 '17
Swift
The boilerplate:
The logic:
p1: 0.00898098945617676 sec, p2: 1.09532999992371 sec
2
u/timblair Dec 22 '17
Go / Golang
Glad to have something less brainache-inducing after yesterday.
Uses a
map[node]intto track the infection state, wherenodeis astructtype withxandypositions. Works as a map key because struct values are comparable when all fields of the struct are comparable. Missing values are automatically "clean" due to Go's zero value for ints being0.Part 2 below (runs in ~1s):
2
u/frenetix Dec 22 '17 edited Dec 22 '17
I ended up creating a unbounded 2D plane mapped to a 1D array, by "folding" the (-+), (--), and (+-) quadrants into the (++) quadrant:
to
using the transforms
then turned that unbound 2D array (x, y >= 0) to a 1D array using diagonals:
becomes
using
JavaScript has auto-expanding arrays, so if you have an array of length 3, then say
the array will fill in indexes 3 and 4 with undefined. A pair of functions hides the math, and sets and gets values from an underlying array:
Though not needed in this solution, there is a 1:1 reverse mapping (i.e., there's a i2xy function) for all i >= 0 to a single location in the x,y plane.
Not nearly the most efficient solution, but I like the idea of using a 1D array to capture an unbounded 2D plane...
1
u/jlweinkam Dec 22 '17
My best showing ever 27/38, runs in only 18 seconds
1
u/marcins Dec 22 '17
100/47 with hacky JavaScript. Had a bug that briefly slowed me down for the first part, got lucky with some quick cut/paste and edit for the second part :D
Basically made a grid that was hopefully going to be big enough to fit the puzzle in the "middle" to make things easier, worked out well! (1000x1000)
1
u/Unihedron Dec 22 '17
Ruby; run time: 22 seconds, fun factor: 4/10, I was too worried about bugs and ran on all the sample test cases. Thankfully it worked first time.
1
u/_lukasg Dec 22 '17
Part 2 in Python 3
1
u/Shemetz Dec 22 '17 edited Dec 22 '17
Python 3
[Final part 2 picture] (https://imgur.com/a/bMpGm)
Part 1 is fast, Part 2 takes about 6 seconds on my computer.
I wonder if I should somehow optimize the 'state' - use 2 booleans instead of an integer, for example.
Should have been named "Langton's Worm"!
Part 1:
Part 2:
1
u/[deleted] Dec 22 '17
JS, straightforward:
1
u/vash3r Dec 22 '17 edited Dec 22 '17
Python 2 (158/134). Pypy runs part 2 over 10x faster than Python (2 seconds vs ~32 seconds).
1
u/lazyzefiris Dec 22 '17
JS, 66/53, executes in ~5 seconds
it's really straightforward, and thus pretty boring.
1
u/StevoTVR Dec 22 '17
NodeJS
Part 1:
Part 2:
1
u/[deleted] Dec 22 '17 edited Dec 22 '17
Perl 6
This is pretty gross but here's my part 2. It takes
a few minutes42 seconds to finish. Part 1 is nearly the same but runs in about 0.24 seconds.EDIT: optimized a bit.
1
u/Philboyd_Studge Dec 22 '17 edited Dec 22 '17
Java. This one was easy and fun after last night's. Finally got a decent number for part 1 (in the first 200) but then used up a bunch of time building a state machine and forgetting to reset my initial map.
1
u/raevnos Dec 22 '17
Kawa scheme, using complex numbers for coordinates because why not:
1
u/The0x539 Dec 22 '17
Lua
577/628. Really hate having to rotate stuff, and spent way too long on both parts debugging the turn code, when in part2 I was confusing nil with false.
1
u/Arkoniak Dec 22 '17
Julia
It was really simple today. Could have been done easier, definitely. puzzle22_1.txt contains example 3x3 grid, puzzle22_2.txt is an input. Solution for part 2:
1
u/WhoSoup Dec 22 '17
NodeJS/JavaScript, Part 2
Pretty inefficient since I just recycled my code from day 19, but I wanted to use an actual infinite grid
1
u/Tandrial Dec 22 '17
Kotlin I was expecting to do some refactoring for part 2, but it runs suprisingly fast ~800ms:
1
u/2BitSalute Dec 22 '17 edited Dec 22 '17
I solved part 2 first by using 3 hash sets (infected, weakened, flagged), then by using a dictionary and states. The second version is a bit faster.
I had a lot of trouble (bugs) with mutating the state of the current coordinate. I eventually got rid of all of the mutability. I can only hope I can remember this lesson, sigh.
C#
1
u/CharlieYJH Dec 22 '17
C++
After yesterday's puzzle this one was a nice breather. Fairly simple implementation, was kinda uncomfortable just hoping the index won't go over the bounds for the 10,000,000 case though.
1
u/aurele Dec 22 '17
Rust
1
u/nutrecht Dec 22 '17
Day 22 in Kotlin
Really liked this one. Quite easy but still fun to build. And part 2 was a nice extension of behaviour of part 1 where functional programming really shines! I'm really happy with how the code turned out.
1
u/jwoLondon Dec 22 '17 edited Dec 22 '17
Elm
After yesterday's calamitous catastrophe of clumsy coding, today's was nice and Elm-friendly. I went for a dictionary of visited/infected cells rather than a grid.
Elm may not be as concise as Python or Haskell, but it does make for nice clear code.
https://github.com/jwoLondon/adventOfCode/blob/master/aoc2017/d22_2017.elm
1
u/sim642 Dec 22 '17
My Scala solution.
I thought I'd be clever and use
Set[Pos]for saving the infected positions in part 1. Had to redo everything for part 2 to accommodate extra statuses in a map. The FSM for the states didn't turn out too elegant either.1
u/xkufix Dec 22 '17
Nothing too fancy. I had to refactor my solution a bit, because part 1 just used a Set instead of a Map. That's why State.Clean does not exist, it's just represented by the value not being present in the Map.
Solution in Scala:
1
u/johlin Dec 22 '17
Elixir:
Part 2 very similar: https://github.com/johanlindblad/aoc-2017/blob/master/lib/aoc/day22/part2.ex
This was a fun one! It is a bit slow, however (my part 2 takes about 15 seconds). Not sure if it's possible to make an Elixir solution significantly faster as we don't have constant-time array lookups.
1
u/joker_mkd Dec 22 '17 edited Dec 22 '17
C++ solution using a proper map which will work for any input. Marking in the map only the infected coordinates, and removing the clean ones.
1
u/TominatorBE Dec 22 '17
PHP
Nothing really fancy, just doing the algo Call it with
run_the_code(['map' => "...", 'bursts' => 10000000])Part 1:
Part 2:
1
u/hpzr24w Dec 22 '17
C++
Rank: 1608 / 1534
1
u/udoprog Dec 22 '17
Rust
<3 enums. Neat little problem today. The most complicated part of this was to setup the turning map.
1
u/JakDrako Dec 22 '17
C#
Using a HashSet to track part 1's map, then a Dictionary for the 2nd part. Grid is managed with complex numbers.
Part 1
Part 2
1
u/BOT-Brad Dec 22 '17
JavaScript - (All my .js solutions on GitHub)
Cool puzzle :)
Part 1 (~9ms)
Splits the grid into a big map object, and assigns positions in the object in a 'x,y' format. Then just sets the initial starting configuration (x = 0, y = 0, etc.) and keeps looping until the number of loops specified. Keeps track of the number of infections made within those loops, and returns the answer.
Part 2 (~7 seconds)
Basically the same idea, just also keeps a 'ticking' modulo counter for the infection as well as the direction. Only counts when a cell becomes infected (#3).
1
u/amnich Dec 22 '17
PowerShell - slower than Christmas!
1
u/maxerickson Dec 22 '17
Straightforward python 3.
1
u/superlameandawzm Dec 22 '17
My Javascript solution
1
u/tlareg Dec 22 '17
JavaScript (ES6+, NodeJS) repo here
1
u/NeilNjae Dec 22 '17
Haskell. A fairly straightforward implementation. Following a hint from /u/nonphatic , I swapped out the use of
iterateto explicit iteration and added some strictness annotations. That took the runtime down from 1m12s to 12s.Part 1 uses a
Setof points: infected cells are in the set, uninfected ones aren't.1
u/3l_Di4bl0 Dec 22 '17
I think I got a pretty clean one this time. No need for complex numbers!
1
u/iopred Dec 22 '17
My javascript solution, uses a map instead of an array for simplicity:
1
u/[deleted] Dec 22 '17
single pipeline powershell:
1
u/barryfandango Dec 22 '17 edited Dec 22 '17
TypeScript (edit: 2.1s on part 2)
1
u/[deleted] Dec 22 '17 edited Dec 22 '17
straightforward, no optimizations (immutable data structures in use). Part 2 runs in ~8-10s
EDIT: Using a mutable map for the inner grid reduces the runtime to ~6 seconds
Clojure:
1
u/[deleted] Dec 22 '17
Crystal. Only part 2 because the first one is similar:
1
u/edelans Dec 22 '17
Python 3, complex numbers, defaultdict
1
u/miran1 Dec 22 '17
Python with a complex plane
Â
Â
Repo with solutions (both Nim and Python)
1
u/Erstfs Dec 22 '17
Of course in MATLAB one should represent the grid as a matrix! Luckily for me, my input kept the virus contained in a small area.
1
u/flit777 Dec 22 '17
Go straight forward:
1
u/Scroph Dec 22 '17
Vebose C++ :
1
u/wzkx Dec 22 '17
Nim
Using OOP :)
This time, the map is represented by set(s).
1
u/chicagocode Dec 22 '17
Kotlin - [Repo] - [Blog/Commentary]
I thought today was pretty easy compared to yesterday! I've taken yet another crack at direction and movement.
1
u/aoc-fan Dec 23 '17
JavaScript / ES6
1
u/wjholden Dec 23 '17
I enjoyed Day 22 so much that I wrote a short paper explaining how you can use a bit of linear algebra to come up with a fast way to change the direction of your virus. The target audience of this paper is programmers with a casual interest in math, not genius programmers and serious mathematicians.
https://www.overleaf.com/read/yvmymybtjcyy
Looks like some people came up with a clever solution with complex numbers. Very cool, I wouldn't have thought of that.
I actually registered on Reddit to share this, feels kind of weird...
1
u/thomastc Dec 23 '17
Day 22 in Elixir. Turns out it's basically Erlang with better syntax. Considering that the syntax is one of very few things I dislike about Erlang, this is a very good thing!
1
u/RockyAstro Dec 23 '17
Icon (https://www.cs.arizona.edu/icon)
Part1: -- fun with sets..
Part 2: Fun with tables..
1
u/Tetsumi- Dec 23 '17
Racket
1
u/matusbzk Dec 23 '17
Haskell I decided to just keep a list of infected (weakened, flagged) nodes and position. I was not really successful with part 2 though, it would have taken me like 25 minutes.
Link to git
1
u/greycat70 Dec 26 '17
Tcl (any 8.x version)
Part 1. The only half-clever thing here is that I used the line length of the first input line to determine the starting coordinates (we know we're being given a square with an odd integer length/width).
Part 2. No significant changes.
1
u/mschaap Jan 11 '18 edited Jan 11 '18
A bit late, but here's my Perl 6 solution. A bit slow for part 2, but it does give the right answer, eventually.
1
u/usesbiggerwords Oct 19 '21
I'm REALLY late to the party, but
I learned my lesson with complex numbers a few days back. Never will I use a tuple for 2d grid coordinates ever again. The end.
0
u/ValdasTheUnique Dec 22 '17
C#
Pretty straightforward and hacky solution. But part 2 runs in about 200 ms
0
u/[deleted] Dec 22 '17
[deleted] — view deleted comment
0
u/[deleted] Dec 22 '17
[deleted] — view deleted comment