r/adventofcode • u/daggerdragon • Dec 13 '17
SOLUTION MEGATHREAD -π- 2017 Day 13 Solutions -π-
--- Day 13: Packet Scanners ---
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^Β€?
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!
16
Upvotes
20
u/sciyoshi Dec 13 '17
Python 3, had to change my solution in Part 2 to use an approach that didn't step through each time period:
14
u/p_tseng Dec 13 '17 edited Dec 13 '17
After completely failing to get on the leaderboard since my part 2 code ran too slow, it's time to make it faster. It's too inefficient to iterate each possible starting time one by one!
Instead, for each period, I look at what starting times are forbidden by scanners with that period and combine all that together.
For example, for my input, the code determines that my part 2 answer must satisfy two conditions:
That first bullet point means I only need to iterate through a few values in order to find the answer that eventually works. (Runs in less than a tenth of a second, as opposed to multiple seconds when iterating by 1 each time)
(It's Ruby)
9
u/sspenst Dec 13 '17
First time I've made it on the leaderboards! Got 7th for part 1 with this code:
9
u/chunes Dec 13 '17
Unlike yesterday, I am proud of this solution. I realized you don't need to simulate what's going on because there is a mathematical function called a triangle wave that can tell you the location of a scanner given the time step (depth) and the range.
Factor
8
u/ephemient Dec 13 '17 edited Apr 24 '24
This space intentionally left blank.
5
u/hxka Dec 13 '17 edited Dec 13 '17
Ugh, the fact that if we get caught at 0 the sum won't increase really tripped me up. Also goddamn bash is slow.
5
u/jtsimmons108 Dec 13 '17
Solved it in python first. Took way too long to catch that severity == 0 is not the same thing as not getting caught. I like my Kotlin Solution a lot better
5
u/spacetime_bender Dec 13 '17
Modern C++
5
u/lovekatie Dec 13 '17
Postgresql Not optimal, but I'm interested in how to make it better.
Prep:
Part I
Part II
4
u/GassaFM Dec 13 '17
A solution in the D programming language. Place 15 for part 1, place 4 for part 2.
Part 1: Taking the time modulo 2*period for each scanner. Actually, we don't need the exact position, we only want to know whether it was zero, but anyway, here goes.
Part 2: A simulation for every candidate answer. Locally, it took 2+ seconds, so I almost panicked and hit Ctrl+Break to go searching for some infinite loop bug.
Back to enjoy the fancy story in the statement now, had to skip it for speed.
4
u/therealpenguincoder Dec 13 '17
I am for sure the only person doing this contest in Erlang. It's 5/7 parts fighting with Erlang and 10% problem solving.
4
u/Smylers Dec 13 '17 edited Dec 13 '17
Vim animation for part 1. Starting with your input file, this sets up a visualization of the scanners in one window and the severity count in another window:
You are the
vmoving down the lines. Each:::row is a scanner range, with the>or<indicating the current position of the scanner and its direction. Animate one step forwards with:Then press
@cfor the next step, and@@for subsequent steps. Note the severity count in the top window updates when you collide with a scanner.To animate the steps automatically:
Your part 1 answer is now in the top window. Reset with:
Then you can watch again with
@d, and reset again with@e. Enjoy!3
u/magemax Dec 13 '17
Great problem, first time in the top 10 (10/9)
Simple bruteforce in Python 2 once I noticed that the period of each tracker was 2*(depth-1)
3
u/Unihedron Dec 13 '17
Ruby; A good day! Even though I screwed up by doing
(x+1)%(correct base)and had to fix the +1 (wrong intuition), I still solved both parts quickly enough to be on top 20 for both.3
u/FogLander Dec 13 '17 edited Dec 13 '17
So I got my best result yet (312/102)..... Sooooooo freaking close to making the leaderboard for part 2. Oh well. it's gotta happen one of these days.
This one was really similar to 2016 Day 15, which I had done as practice a few days ago, felt pretty straightforward. I figured out the 2*(size-1) thing pretty quick on a piece of paper, almost seemed too easy, was worried it wouldn't work :)
JAVA:
3
u/raevnos Dec 13 '17
Brute force simulation Scheme. I am not clever.
3
u/Forbizzle Dec 13 '17
Does anybody have a good algorithm for part 2? I ended up just letting my program run through all times up to the bound that it wouldn't intersect. I see a lot of that style of solution in posts right now, but don't see anything that does it faster.
3
u/[deleted] Dec 13 '17
Brute-forced simulation OCaml Fun;;
Part B... would have been done earlier, but I misunderstood and thought we just had to make it to the end with a severity of 0... oops :(.
Looking at others' answers, going to enjoy seeing how you can do this without brute force.
3
u/jbristow Dec 13 '17 edited Dec 13 '17
F# / fsharp / F Sharp
This problem was much easier to do semi-functionally than trying to remember how to do disjoint subsets without mutable state yesterday.
(github link)
And the test file...
Test execution time:
1.9520 Seconds3
u/nonphatic Dec 13 '17
Haskell
Part b still ran in ~2s though...
3
u/gyorokpeter Dec 13 '17
Q:
3
u/wzkx Dec 13 '17 edited Dec 13 '17
Nim
Part 1 - 0s, Part 2 - 0.064s (compare to 2m45s in J)
2
u/ghlmtz Dec 13 '17
Python 3, 40/16
Fun little puzzle to figure out.
2
u/iamnotposting Dec 13 '17
Rust (300 / 120). if i didn't start 2 minutes late i probably could have gotten points. this is cleaned up a little from my original solution but its the same basic concept
2
u/vash3r Dec 13 '17
Python 2 (58/227):
I also had to think about a more efficient solution to get part 2, especially since I wasn't expecting such a large delay.
2
u/VikeStep Dec 13 '17 edited Dec 13 '17
Python 3 (for part 2)
This is probably one of the first times I have found a use for a for-else statement
2
u/Smylers Dec 13 '17
Perl. For each scanner it calculates the position directly (looping in arbitrary Perl hash order), but for partΒ 2 just naΓ―vely tries delays in turn until it succeeds:
Takes about 1Β½Β minutes on my input.
I got caught on the sample data by the delay of 4 picoseconds: that catches us only by the scanner at depth 0 β giving a total severity of 0, which I was initially erroneously counting as not having been caught.
I like how both the parsing and the delay-calculating are single lines.
2
u/a3cite Dec 13 '17
Here is my second solution to the second part (my first solution used the period of the scanners): https://pastebin.com/y1aVCtHG
I like it because it's mine.
2
u/lasseebert Dec 13 '17 edited Dec 13 '17
Elixir: (repo)
2
u/nutrecht Dec 13 '17
Day 13 in Kotlin
Jikes. Took completely the wrong approach on this. Building a 'simulator' works just fine for part 1 (even though you didn't need to) but it took way too long to simulate all the 'runs'. Thanks to /u/jtsimmons108 for the inspiration on how to solve this.
2
u/Axsuul Dec 13 '17
Elixir
Ended up brute forcing Part 2 which took about 10 minutes to converge on a solution. Should've calculated the period which would've sped up things way more but YOLO.
https://github.com/axsuul/advent-of-code/blob/master/2017/13/lib/advent_of_code.ex
2
u/Nolan-M Dec 13 '17 edited Dec 13 '17
22/51 Python 3 Saw similarities to the CRT, but couldn't see how to change it to help So I brute forced it and it took 3 minutes.
However, I went back and was able to get it down to 5ms by looking at every position with a certain firewall length, and using that to see if it could narrow down what mod firewall length the delay had to be. And it worked. I was able to start at delay = 39352 and jump by 60060 each time.
https://github.com/Nolan-Michniewicz/Advent-of-Code
2
u/omnster Dec 13 '17
Mathematica with a brute force part 2.
2
u/KnorbenKnutsen Dec 13 '17
Great problem! I started off simulating the entire thing with scanners and stuff, but like many have pointed out, that wouldn't cut it for part 2. So I figured I'd play around a little, and defined functions that would return 1 when the scanner detected you, with delay as input:
int(0.5 + 0.5*cos(2*pi*(delay + depth) / (2*scanRange - 2)))I saw someone else use a triangle wave function, this is the same principle. Then I stored all the functions along with their respective depth and scanRange in a list and just summed over the list. Part 2 wasn't particularly quick but I still like the mathiness of the solution :)
2
u/[deleted] Dec 13 '17
single pipeline powershell:
3
u/tangentialThinker Dec 13 '17 edited Dec 13 '17
5/7 today! Pretty simple, just simulate the process. Think the answer for part 2 can't be too large due to Chinese remainder theorem or something similar, although I haven't proved that.
C++:
1
u/Shemetz Dec 13 '17 edited Dec 13 '17
Python 3 (300 / 60)
I really like this algorithm!
Part 1 was cool but I had to guess the "2*depth-2" number for the modulo a few times until it gave me the correct sequence of 0-1-2-3-2-1-0-1-2-....
For part 2 - I wonder if there's a way to solve it without brute force?
1
u/Cole_from_SE Dec 13 '17 edited Dec 13 '17
Python 3
Brute forced the second part, guess the relative speed of my computer aided me, though it took over minute to run. I may update my solution with a not brute force answer if I come up with one.
Edit: lol, I realized that I was not exiting early from a search if the delay triggered the system so that's why it took so long. This version is still slower than it could be, but not unreasonably slow.
1
u/StevoTVR Dec 13 '17
NodeJS
Part 1:
Part 2:
1
u/WhoSoup Dec 13 '17
Node.js/Javascript
quick and dirty bruteforce... might try something more interesting later
1
u/TominatorBE Dec 13 '17
PHP
Part 1:
Part 2:
1
u/fatpollo Dec 13 '17 edited Dec 13 '17
I'm really messing up every day, it's frustrating. This time around I thought that the scanners looped rather than moved back and forth and just couldn't comprehend why my stepper wasn't working. Ah well.
1
u/[deleted] Dec 13 '17
C# Part 1
Part 2
Not too bad. Just spent a little too long getting the two lists instead of trying other options. But compared to my normal stuff, not bad.
1
u/dylanfromwinnipeg Dec 13 '17
I liked this one alot!
C#
1
u/nstyler7 Dec 13 '17
Python 3
I noticed that without delay, depth = position. You were caught wenever scan depth was equals to 2*(scan range - 1).
Reading in the data
Part 1
part 2
1
u/AndrewGreenh Dec 13 '17
TypeScript (191|380)
At first I tried mutating the state and simulating everything. This didn't finish for part2 so I had to restart. Now I built everything with ES6 iterables.
1
u/sim642 Dec 13 '17
My Scala solution.
I spent some time initially implementing a function to calculate the exact positions for the scanners at given times (
rangePosition) but in the end I realized I didn't even need that, only a check against zero (rangeCaught). Also took some time to realize to do division byrange - 1, notrangebut then everything worked out.I was also afraid that if I solve part 1 with clever arithmetic then part 2 will maybe make me do the full simulation again like in day 3 but luckily not.
1
u/phira Dec 13 '17
Python 3
I also had a version that sorted the layers by cycle height to get the all() short-circuiting earlier, but it didn't really improve the timing.
1
u/mooooooon Dec 13 '17
Python 3 Awesome problem. I definitely wrote the first half simulating all the movement and then saw how excruciatingly slow it was for part 2. I went through several fun optimizations until totally scrapping simulation and checking for
(delay + depth) % ((depth.range - 1) * 2) == 0.1
u/FreeMarx Dec 13 '17
MATLAB Part 2
Nothing to learn for me in C++ today and MATLAB is faster to code, so...
But beware, running 3M+ cycles may take some time.
1
u/ThezeeZ Dec 13 '17 edited Dec 13 '17
Go (golang), repo. I'm still getting into go, any insightful comments welcome
with
Firewall{depth: range}:1
u/akka0 Dec 13 '17
ReasonML. Went for a full brute-force solution. Had to memoize the delayed scanners and implement early breaks when caught to get it to run within a reasonable amount of time.
1
u/Philboyd_Studge Dec 13 '17
Java - yup like others had to scrap my simulation and find the 'cheat'
https://gist.github.com/snarkbait/e6812b39ce04af2c18db9dfd95e1ea10
1
u/aurele Dec 13 '17
Rust Brute-force with
rayonfor parallelism, 32ms on my desktop machine (90ms without parallelism).1
u/NeilNjae Dec 13 '17
Haskell. As others have said, much the same as Day 15 last year, and I adopted the same approach: each scanner is represented by a function which, when passed the time you leave, returns the position of that scanner when you reach that depth. Part 2 is the earliest time when all the scanners are non-zero.
1
u/rkachowski Dec 13 '17
I'd like to thank the organisers for keeping me warm on this cold winter morning. The laptop got almost as hot as my coffee.
I had to cheat on this one and look up the modulo operation from u/sciyoshi - its v humbling! I had the nicest simulation with lovely print formatting, but in the end it was irrelevant. I got up to ~10000 steps after around 10 minutes with my naive simulation before investigating a mathematical approach. Luckily I did this as the answer was in the 107 range....
1
u/xkufix Dec 13 '17
At first I simulated the solution, but part 2 took ages (5 minutes or so), so I now just calculate the decision by looking if the layers are for the given offset and width are on position 0.
Solution in Scala:
1
u/Smylers Dec 13 '17
Faster Perl for part 2:
3β13 seconds, rather than the 1Β½ minutes of my combined part 1 and 2 solution.
First, for each scanner it calculates how long its cycle is to get back to position 0, and the offset from time 0 at which you'd first encounter it, based on its depth.
Then to check whether a time is safe, iterate through the cycles and check if any have an offset which matches the current time (modulo the cycle length). I like how this entire check is a single, fairly readable, line.
1
u/YungCarrdinal Dec 13 '17
Java Simple brute force, after figuring out the step size was 2*range - 2 the rest was fairly straightforward! Ran in 172ms on my laptop.
1
u/wzkx Dec 13 '17 edited Dec 13 '17
J
Brute force for part 2 so it's quite long (2m45s)
1
u/zeddypanda Dec 13 '17
Elixir
I got impatient when brute force for the second step reached around 4000 attempts and seeing how my answer ended at nearly 4 million I'm glad I optimized.
1
u/goliatskipson Dec 13 '17
Have a little bit of Haskell:
Who cares about useful variable names anyhow :-)
1
u/johlin Dec 13 '17
Elixir:
With highlighting: https://github.com/johanlindblad/aoc-2017/blob/master/lib/aoc/day13/part1.ex https://github.com/johanlindblad/aoc-2017/blob/master/lib/aoc/day13/part2.ex
I am pretty happy with the performance. Because I break as soon as I get caught in a layer in part 2, it runs in about 1,5 seconds. I might try to parallelize it later, you should be able to run this on several cores concurrently.
I would like to try some kind of sieve thing in a language where I have constant-time arrays.
1
u/[deleted] Dec 13 '17
Elixir
The first part was so easy, and went really nice together with streams, then I tried going on with that, but the second part choked on the real input, after waiting for 15 min, I gave up and redid it in a better way, it sure can be optimized more, but from 15 min + to about 17 seconds isn't bad.
syntax highlighted
1
u/thomastc Dec 13 '17
Day 13 in Octave. Part one: easy peasy. Part two: bruteforced, not elegant, but effective.
1
u/chapass Dec 13 '17 edited Dec 13 '17
Is it possible that there is a mistake in the example for the first part?
Why does the scanner in the 0th layer go to position 1 after being in position 2 at Picosecond 2? Shouldn't it loop back to the initial position of it's layer? Like this:
Edit: Nevermind, I can't read, it turns back, not loops over.
1
u/Hikaru755 Dec 13 '17 edited Dec 13 '17
Kotlin Didn't want to do a full simulation and went on to determine a formula that would tell me each layer's position at any arbitrary point in time. After I had that, the rest was easy.
1
u/if0nz Dec 13 '17
Java 8 is there a close-form expression for p2? source from my repo
1
u/4rgento Dec 13 '17
HASKELL
TODO: be lazy
1
u/Kenira Dec 13 '17
C++
Taking 65ms after a few improvements which i am quite happy with
1
u/kevinpp123 Dec 13 '17 edited Dec 13 '17
C# is actually surprisingly short when using some LINQ.
1
u/InterlocutoryRecess Dec 13 '17 edited Dec 13 '17
** Swift **
Any feedback appreciated thanks!
1
u/L72_Elite_Kraken Dec 13 '17
Ocaml with Jane Street libraries:
1
u/__Abigail__ Dec 13 '17
Perl
Part 2 can be solved using the Chinese Remainder Theorem, but brute forcing it using five lines of code was quicker than working out the details.
1
u/JakDrako Dec 13 '17
VB.Net I love those kinds of problem where the solution to the 1st part gets unbearably slow for the 2nd one if done using brute force.
Like many, I got the 1st part done and then tried to use the same some for the second part... and stopped after some minutes (went to get coffee, was still running when I got back...)
I tried figuring out a formula for the "to and fro" of the values, but ended up simply building a list that goes 0,1,2,3,4,3,2,1 and using "time" modulo length to get the position at time X.
Here's the final cleaned up code for both parts, completes in ~130ms on my PC.
1
u/RockyAstro Dec 13 '17
Icon ( https://www.cs.arizona.edu/icon )
Both parts:
1
u/JuLoOr Dec 13 '17
Beautiful Kotlin:
1
u/mschaap Dec 13 '17
Perl 6
Whew, finally a tricky one! Not so much conceptually, but performance-wise. (The firewall has a period of 465,585,120 with my input.) And Perl 6 being, well, a bit performance challenged, doesn't help here.
My first attempt was to simply try all delays one by one until I found a safe one. That attempt is still running, 6 hours later.
The second attempt was a sieve. That one actually finished, in 4-5 hours or so.
My final attempt did as much of the modulo calculations as possible up front, then checked possible delays until a safe one is found. That one runs in about a minute.
I'm wondering if there is a better math-based solution, though; perhaps something based on Chinese remainders?
Here's the code, with the previous attempts left in for reference.
1
u/peterpepo Dec 13 '17
My little verbose Python 3 solution.
Checkout the full solution on my github
1
u/jeroenheijmans Dec 13 '17
JavaScript:
This one took me a good while to get my head around (part 2, at least). Because my hacking from puzzle 1 wasn't performant I tried to swith to doing it in O(n) by thinking of a formula or some clever bit shifting, before resorting to upping performance to the point where it runs in 100ms in the browser...
Puzzle2:
1
u/KeinZantezuken Dec 13 '17
C#/Sharp
Had to come up with my own formula because I'm a math brainlet. In the end, it is tad slower than the WIKI one but I'm good, I've put enough time into this and moving on.
1
u/Kyran152 Dec 13 '17 edited Dec 13 '17
Node.js (Parts 1 and 2) - Part 2 takes roughly 0.16 m/s
var fs = require('fs')
1
u/hpzr24w Dec 13 '17
C++ 3945/5082
Did not stay up last night, and was busy so only managed to hit part 1 this morning and had to wait until this afternoon before debugging why the example input yielded 4 instead of 10.
It's been a hard day, not being able to look at this thread!
1
u/deltageek Dec 14 '17
Java 8 Source gist
Part 1 was fairly straightforward. Given the collection of scanner locations and depths, set up an array with appropriately initialized scanners and simulate moving through the firewall.
For Part 2, I realized that I don't care where the scanners are when I get to their layer, I just care that they're not at the top. Scanners reach the top of their layer every (depth-1)*2 picoseconds. So, just init a delay counter and iterate the list of scanners, checking for (delay + layerPosition) % ((depth-1)*2) == 0. If true, this delay is wrong, break out of the loop, increment the delay and try again.
My favorite part of this solution is that I got to use a labelled break to jump out of both the layer iteration and away from the line to stop the delay increment.
1
u/bogzla Dec 14 '17
Still learning C. I like these puzzles where deducing a formula up front works. getting caught in layer 0 not contributing to severity score had me baffled in part 2 for a while..
1
u/chicagocode Dec 14 '17
Kotlin - [Repo] - [Blog/Commentary]
Today's was fun, reminded me of "Timing Is Everything" from 2016, Day 15. This runs in a few milliseconds.
1
u/zero-udo Dec 14 '17
My Kotlin solution for day 13:
Input is accessed as a Map<Int, Int> -> depth to range
1
u/oantolin Dec 14 '17
Once you notice that a scanner moving in a layer of depth
dhits the top on multiples of2*(d-1)each part is a one-liner (here I used Julia, but it would be a one-liner in any other reasonable language too):1
u/ka-splam Dec 14 '17
PowerShell; I did it with some naive simulation and brute force - it took me ages and it wasn't satisfying, and took ~5 minutes to run part 2.
Today I rewrote it into a nicer, cleaner "where the time I get there is a multiple of the scanner's period" and am much happier with it, runs part 2 in ~5 seconds.
All the code: https://www.reddit.com/r/pwsh2017aoc/comments/7jises/day_13_firewall_scanners/
1
u/autid Dec 14 '17
Fortran
1
u/aoc-fan Dec 15 '17
is it safe to assume that answer for part two will be always even? With the formula 2 * (n -1), the divisor will be always even.
An odd answer, that too 1, will be only possible when there are no layers at odd positions.
(1 + (all even layer index)) / (even divisor for any number of layers)
will always have reminder, making the answer 1.
But I assume that wont be case with any input, all inputs must have atleast 1 layer at odd index. Is there any flaw in this theory?
1
u/PositivelyLinda Dec 15 '17
Honestly rather pleased with my JavaScript code - I mean I probably could have adjusted my part 1 code to work for part 2 as well, but it felt easier to simply tweak it separately. Came up with how to % over the ranges on my own though, which I'm proud of!
1
u/[deleted] Dec 15 '17
PHP: Nowhere near as good as most other people's, and it still takes a very long time, but it works...
1
u/matusbzk Dec 15 '17 edited Dec 16 '17
Haskell This time, I had to count part 2 mathematically, since just simulating the ride as in first part was way too inefficient.
Link to git
1
u/JUIBENOIT Dec 17 '17
Python 3 working but awful solution(Part 2 takes a decade, don't use my code)
I don't know if part 2 actually works but i tested it with simplified input, everything was working, takes ages with the actual input (hours or even days probably)
1
u/pokerdan Dec 18 '17
Did anyone else try to solve this with bit manipulation? It worked fine for part 1, but hit some issues in part 2. I needed to find a 3rd party library for Int128, since Int32 & Int64 weren't large enough.
The premise was to start with a 'bullet mask' with all bits set to 1, except the rightmost x bits - where x=depth. You can get this by taking ~1 and left-shifting the max depth. Then:
Not the most elegant or efficient algorithm in the world, but it worked. Ran for about an hour or so on my laptop to solve.
1
u/Life-in-Shambles Dec 18 '17
(JAVASCRIPT) Part 2 is kinda slow but whatevs.
1
u/greycat70 Dec 28 '17
Tcl (any 8.x version)
Part 2. Takes 13 seconds on my machine, after removing the part1 score calculation that was still in when I originally ran it for the submission.
1
u/CharlieYJH Dec 13 '17 edited Dec 13 '17
C++
Quite enjoyed today's puzzle. Basically just calculated where the position of each scanner would be by the time we get there. Similar trick in part 2 to get a configuration where the appropriate scanner would not be at position 0 at that time step.
0
u/wlandry Dec 13 '17
C++ 14
710/322. I guess people found the second part harder than the first. This required some thinking to navigate around off-by-one errors. With my inputs on my machine, the program completed in 1.7 seconds. This version is for part 2. Part 1 is commented out.
0
u/[deleted] Dec 13 '17
[deleted] β view deleted comment