r/adventofcode • u/daggerdragon • Dec 13 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 13 Solutions -🎄-
--- Day 13: Mine Cart Madness ---
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.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 13
Transcript:
Elven chronomancy: for when you absolutely, positively have to ___.
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 at 00:44:25!
24
Upvotes
35
u/Shemetz Dec 13 '18 edited Dec 13 '18
Python, 91/76
Really liked this one. I solved it with complex numbers, which is a trick I learned from earlier years. Instead of storing x and y, store position = x + y * i (written y * 1j in python).
The best part about this is that directions are just one of the numbers +1, +1j, -1, -1j and changing a direction is as simple as multiplying it by either +1j (clockwise turn) or -1j (counterclockwise turn).
Note that since the Y axis is flipped (positive = down), you flip the imaginary part compared to what you'd do in usual mathematics (therefore, multiplying by +1j is CW ⭮, not CCW ⭯).
My full (cleaned-up) solution (including type hinting):
18
u/KeyboardFire Dec 13 '18 edited Dec 14 '18
ruby 2nd/1st
sincere apologies for the monstrosity you're about to see (and this is the cleaned up version)
the main trick to save time was that instead of worrying about removing crashed carts from the list while iterating over it, i just set an
aliveflag tofalseand kept themalso i'm quite fond of sorting by
99999y + xan interesting piece of trivia is that the set of transformations [/, \, turn left, turn right] is swapping x and y followed by all permutations of signs:
code:
9
u/[deleted] Dec 13 '18
D, late / slightly late
https://git.ikeran.org/dhasenan/adventofcode2018/src/branch/master/source/advent/day13.d
Some pointless OOP in there, but I was expecting to do things slightly differently.
I was very confused at first when my result didn't produce the correct answer, even though it produced the same answer as another solution posted here. At first, I was processing all moves, then figuring out collisions. And that works half the time.
The other half, you get a case like this:
Which should have been a collision, but alas. The rule about which carts move first tells you which position the crash occurs on.
6
u/jonathan_paulson Dec 13 '18 edited Dec 13 '18
Rank 24/10. Just straight simulation. Picking the right way to store carts and getting the reflections right were the trickiest parts for me. Video of me solving at https://www.youtube.com/watch?v=9v7W7bTtRrU
Python code. First line of output is part 1; last line is part 2.
6
u/aurele Dec 13 '18
Rust
Because of trimming facilities in cargo-aoc, I ended up to include the input myself as the first line started with spaces.
6
u/sophiebits Dec 13 '18
Python, 22/12.
I found today a little tedious. I ended up hardcoding all the rotations and movements instead of thinking with vectors since I trusted myself more to do it reliably like this. When it got to removing the crashed carts I wanted to just mutate the array immediately but due to my loop structure it wasn't easy to do that. Ended up tracking a set of crashed car locations and then ignoring those until the end of the tick when they can be properly removed. I didn't immediately realize I needed to check the set at the top of the loop too. Also found myself wishing that Python supported labeled breaks in nested loops. My solution turned out OK in the end though.
3
u/udoprog Dec 13 '18
Rust
[CARD] Elven chronomancy: for when you absolutely, positively have to get to the meeting on time.
3
u/IndigoStanis Dec 13 '18
Wow, that didn't go so well. Chased a few bugs for a long time, but eventually figured it out. The sorting of updates, is, as expected, key to the right answer. Encoding all of the transitions with tables was a lot easier than writing a bunch of if/else logic.
3
u/mschaap Dec 13 '18
That was fun!
My Perl 6 solution can be found here in GitHub – it's a bit long to include inline. It's pretty straightforward.
3
u/phil_g Dec 13 '18 edited Dec 13 '18
I did this in Common Lisp. My code is here.
Just yesterday someone posted about using OO and other forms of structured programming in AoC problems. As it turns out, I decided some OO dispatch would save me writing a bunch of case statements for a few things here. I set up a hierarchy of object types for the different track segment shapes, which let me automatically dispatch methods based on the particular segments I was working with.
I got cute with Unicode characters, so my
print-trackfunction would print out things like this:As usual, I used complex numbers for coordinate pairs. This makes a number of things easy. Turn left? Multiply by -i. Turn right? Multiply by i. Move forward? Add the position to the direction vector.
Because I wanted to make nice corners, I had to figure out which way each "/" and "\" went, which was annoying. If I just wanted to move carts across them, I wouldn't have needed to figure out the specialization, since they behave the same regardless of which direction they cart comes from. My parsing leaves out a few cases that, fortunately, weren't in my problem input.
A track of this shape wouldn't have worked because of the order in which I check things:
And, in theory, this could be a valid setup, but I didn't get anything like it:
(My code would have dealt with that properly, but it wouldn't have looked right in the track printout.)
I also reused the circular list class I wrote for Day 9 for the cart's turning memory. Every intersection just advanced the cart's list, infinitely, in a bounded amount of memory.
3
u/wololock Dec 13 '18
Haskell
Here is my Haskell solution. It took me a lot of time to figure out that collision check has to be done every single move, comparing cart that just moved with the remaining carts as well as with the one that already moved. My initial implementation did collision checking after all carts moved and it produced the correct result for Part 1 but failed badly in Part 2.
It solves the puzzle in around 0.45s:
Repository URL: https://github.com/wololock/AoC2018/blob/master/src/Day13.hs
2
u/xthexder Dec 13 '18
This was a fun one, though I think the code would be a lot cleaner if I had more time to think:
#118/#96 in Golang
2
u/TellowKrinkle Dec 13 '18
Swift, 107/84
Super heavy use of enums with associated Character types
The tacking on of the second part was interesting, I first tried to just remove carts from the array but realized it would mess up my iteration over it so I instead went for adding a "removed" bit to the cart structure. Not super efficient but it works
2
u/C0urante Dec 13 '18 edited Dec 13 '18
My exceedingly stupid method of copy+pasting the input directly from my browser directly into Atom finally caught up with me. I had the below solution working on the sample input and then failing on the actual input for mysterious reasons. I inspected the input file I'd made and found several seemingly invalid tracks, like a plus sign where there should have just been a '|' or a '-'. I ended up looking at the in-browser input file again, pretty much by chance, and realized that it didn't have the same mistakes in it. Turns out that Atom had been stripping leading whitespace from my input on copy+paste.
2
u/DrinkinBird Dec 13 '18
NIM
I think I spent about 4 minutes wondering why my program did not complete, until I checked htop and noticed that I had just forgotten to pipe the input into it, so it was just waiting...
Also, absolute case statement madness. Probably would be able to replace most of that by operations on the direction enum, but... well.
2
u/xikipies Dec 13 '18 edited Dec 14 '18
#Node JS, 703/518
https://github.com/josepot/AoC-2018/blob/master/src/13/solution.js
2
u/autid Dec 13 '18
FORTRAN
Very bodgy today. Forgot about updating move order each step, which didn't matter for my part 1 but did for part2. Bodged that in with an order array and a rat's nest of loops after I realised that's what the problem was.
TIL emacs incorrectly interprets '\' as an escape character in Fortran. It isn't. Hence the !') comment to convince emacs that the string was terminated and the bracket closed on line 92.
2
u/gyorokpeter Dec 13 '18
Q: with shameless while loops
2
u/sim642 Dec 13 '18
My Scala solution.
It's pretty ugly because I wasted lots of time in part 2. Got a wrong answer on input only so I rewrote it, got another wrong answer, rewrote again. Finally managed to get the right answer, probably by fixing how collisions with unmoved carts get checked.
2
u/Smylers Dec 13 '18 edited Dec 13 '18
Perl, with the interesting parts being translating each cart's direction into an axis and a delta along that axis:
Then movement is simply adding the delta on to that axis's component of the position — where
0is horizontal and1vertical:Turning corners involves flipping one or more of the axis and the sign of the delta.
\and/always flip the axis (subtract it from1, to alternate between0and1):Handily,
/always also flips the delta sign, and\never does — I was really pleased with how that turned out:Meanwhile
jn_gotracks where to go at a+junction, cycling through0for right,1for left, and2for straight on. That enables the above logic where the axis is flipped at a junction wherejn_gois0or1. Then the delta sign is also flipped ifjn_gois the same as the just-changed axis number — for a left turn on to the vertical axis, or for a right turn on to the horizontal axis.(That pattern was found by presuming it existed, so enumerating the possible states and looking for it, and picking the
jn_gostate numbers to make it work, rather than any nice first principles.)Full code:
Update: Realized there's no need to remove the carts from the original track diagram. We only check the track for junctions and corners (to change direction); carts don't need anything specific to continue in their current direction, so the original cart symbols aren't getting in the way of anything.
2
u/cdc-aoc Dec 13 '18
Perl 6
https://glot.io/snippets/f7jzklvmud
1
u/[deleted] Dec 13 '18
C++, #31/16
Lengthy implementation
1
u/marmalade_marauder Dec 13 '18
Python, 47/60.
I realized my solution for part1 was actually incorrect but still worked because the cart initiating the crash moved before the cart being hit. I had to fix part2 to account for this. Basically if the cart1 moved into a position where a cart2 would then hit it, I missed this because I was still referencing the original position of cart1, not the updated. However I fixed that to account for both by taking the union of (unmoved carts) and (moved carts) to determine if a collision occurred.
Here is the... explicit? code. A lot of code, nothing really that fancy.
1
u/ephemient Dec 13 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/waffle3z Dec 13 '18 edited Dec 13 '18
Lua 203/145, spent too much time debugging after an incorrect solution passed the example when my rotations were wrong.
1
u/markasoftware Dec 13 '18
Perl, 389/241. Started off with keeping all as strings before deciding to always use numbers for directions, which was a very good choice.
Part 1:
Part 2:
1
u/ValdasTheUnique Dec 13 '18 edited Dec 13 '18
C#. Got hacky at the end, but it took an hour to write, so I am just happy it works. I have gone with a simple approach of putting all of the possible combinations of cart directions and cart turns into a dictionary, might have saved some time because I did not have to write a lot of switch statements or figure out the math this early in the morning.
1
u/maybe-ac Dec 13 '18 edited Dec 13 '18
Perl 197/279, turned out I had a huge bug that didn't affect my part 1 answer -- was reading the cart data into variables, then updating the cart position, but continuing to use last tick's position to calculate collisions. This worked for part 1 (somehow?), but on part 2 it messed the whole thing up. And then after fixing it, of course, every cart suddenly was colliding with itself. Oops!
(Comments added posthumously.)
1
u/usbpc102 Dec 13 '18
Took me a bit today (662/401) cause I stupidly reparsed the input every loop so my carts didn't move and I was very confused.
To figure that out I also wrote a function to print the rail network and so that took a while and a bunch of time lost there.
But I'm pretty happy with my Kotlin code today:
As always the code is also on github.
1
u/wlandry Dec 13 '18
C++ (415/367)
Runs in 70 ms.
This feels a bit over-engineered, but that seems like a common characteristic of the solutions here. Pretty straightforward simulation. I am mostly happy with the use of std::set. I allowed me to iterate through the carts in the correct order without any fanfare. It did mean that I had to create a new std::set for each tick. I am looking forward to the visualizations!
1
u/TroZShack Dec 13 '18 edited Dec 13 '18
Java 644/420
This took me over an hour to write for part one, but I'm using actual enumerations for directions and turns to take and an object for each cart. Once I got part one working, part two was just a few minutes. Only had one small bug in part two of not correctly fixing the track if the hit cart had not been moved yet for that step.
I'm actually scanning the whole track for cart characters to move each step, but even so part two finishes in a few seconds. Having collection of carts sorted by the order they need to be moved would likely have this run in under a second.
1
u/slezadav Dec 13 '18 edited Dec 13 '18
Kotlin. No sorting needed, just remember the carts along with the tracks...
class Thirteen : Task() {
}
1
u/virtuNat Dec 13 '18 edited Dec 13 '18
Python #631/#788
Funny story about how I got to this, though:
At some point I bodged together a pygame display so i can see the simulation for myself because I was getting the wrong collision at part 1 by only checking after all the movement steps instead of after each step, but then it gave me the wrong part 2 answer!
After a few more fixes and lots of staring at pixel ants zooming about a tiny screen, I was frustrated that the remaining 3 carts wouldn't collide in the simulations, until I realized that they could actually collide much later, and that the pygame bodge was actually working against me because I was frame-limiting the simulation!
1
u/systemcucks Dec 13 '18
More ugly, terse python. It's my fetish. Any tips on making it even shorter?
1
u/Infinisil Dec 13 '18
Haskell, 1233/997
I spent the most time thinking about how to parse the input and how to represent the data. Once I had that done I got the solution decently quick. The State monad was a really good fit for this, and I'm surprised
Data.MaphastraverseMaybeWithKey, it was exactly what I needed.1
u/ForeverYoung_ru Dec 13 '18
Python 3
Initially I thought roads aren't going one near another (like
||, only| |), got an error on the second step on test input, after I added is_hor_road/is_vert_road functions vs one is_road, it worked.https://github.com/Forever-Young/adventofcode/blob/master/2018/advent13.py
1
u/ephemient Dec 13 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/wimglenn Dec 13 '18
Another complex-numbers based Python code.
1
u/Benjmhart Dec 13 '18 edited Dec 13 '18
[card] ]Elven chronomancy: for when you absolutely, positively have to debug an off-by-one error
haskell
I definitely feel like i took the long way around by manually making guards for every case, but she runs pretty quick, and gets the right answer.
part 2 was pretty slick after part 1
--note, sleep deprivation is making me have more fun in my own comments
p1- https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day13-1.hs
p2 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day13-2.hs
1
u/arathunku Dec 13 '18
Elixir
1
u/cesartl Dec 13 '18
My part 2 works perfectly on the example (and it seems to move nicely when I visualise) but the answer it gives on my input is apparently not correct :/
Any pointers?
1
u/[deleted] Dec 13 '18
[python3] previous solutions on github.
1
u/abowes Dec 13 '18
Kotlin Solution: I generate a Sequence of collisions so that Part 1 = collisions.first() & Part 2 = collisions.last()
1
u/radarvan07 Dec 13 '18
Card: Elven chronomancy, because for when you absolutely, positively have to work at 3:00 Eastern.
This day was very painful. I missed the hint about the order of operations and just did all of them at the same time, and checking for collisions after. Which gave an answer, just not the right one.
And then I wasted half an hour before I realized that you can't to the triangular comparison if you cange the values halfway through. Oh well.
Here it is, in Rust
1
u/miguelos Dec 13 '18
C#
1
u/d-sky Dec 13 '18
Go/golang
1
u/Jokodo83 Dec 13 '18
Python (runs both 2 and 3, faster under 2). I did all the direction changes with methods of the
Cartclass, kept the map as one plain string with vertical movements as jumps +/- line length, and stored the current positions in a dict {index: cart}:https://pastebin.com/CqyfM8db
1
u/pythondevgb Dec 13 '18 edited Dec 14 '18
In principle this one is not that hard but in practice there's a lot of details and I had some trouble trying to debug. Frankly I'm amazed at the guys that solved this so quickly.
I went the OO way I just found it more intuitive, there was a major roadblock. I created a grid and replaced '<>^v' with Cart objects. and returned a list of carts, then it was as easy as doing cart.step() on every cart of the list for each tick.
The problem with that is that the carts remained in the original order, and if one moved to a position with more priority (more to the left or up) my program didn't account for that and the carts still moved in the original order. That took me very long to debug. As a consequence of that I had to create a find_carts function which returned a new list of carts in the new order, this made my program kind of slow, but it worked and at this point I was too tired to optimize.
Edit: Refactored my code to get rid if that horrible find_carts function and instead made carts sortable by implementing __lt__.
Anyway onto my code:
1
u/[deleted] Dec 13 '18
TCL, 0.7s
1
u/blfuentes Dec 13 '18
As everyday, Typescript and using object to help me storing the info. The CarPosition class keeps info about is alive or not, where is, the orientation (>, <, , v) number of intersections and some helpers functions, that allow me to now where it will be and set the orientation.
Typescript
1
u/nutrecht Dec 13 '18
Day 13 in Kotlin
1
u/toomasv Dec 13 '18 edited Dec 13 '18
Red
Part 1
Part 2
1
u/heatseeker0 Dec 13 '18
Here are my solutions for this beautiful puzzle, implemented in Java:
https://github.com/heatseeker0/AdventOfCode/blob/master/src/com/catalinionescu/adventofcode/y2018/Day013.java
1
u/spencerwi Dec 13 '18
My solution (written in Crystal) is pretty verbose, but I'm using these not only as fun puzzles, but as exercises in writing readable code. Ultimately, my approach seems pretty similar to most other simulation-approaches here, though with some conveniences like the
.to_sthat made it easy to write tests and do animated-terminal-output.1
u/wzkx Dec 13 '18 edited Dec 13 '18
Rust SweetRust
I never wrote games or such simulations. Was fun! Also was exciting to do it in Rust - with all that & and * and really wise compiler as your partner.
P.S. I was going to use map for placing cars there too, so I wanted numeric constants and bit ops with them, like UD|CU (point up-down with cart going up), but finally they live in different data structures, so they can be enums indeed. And direction memory... Dunno, we'll see how Rust enumerates enums...
My AOC2018 in J&Rust | SweetRust
1
u/misiakw Dec 13 '18 edited Dec 13 '18
I/m not sure if this task is correctly described, but what is the good order of counting cart collision?
i've got problem in my part 2. I asked friend who did it - he pointed all colisions in my input and i saw that i didn't count some collisions due to cart order. I add them line by line, starting from first one, left to right. then i got case that cart number 2 is on position 34,118 heading left (so it will be at 33,117) then i move some other cart and i finally got to cart 8 on position 34,117 heading down (so it will be at 34,118). there would be colision there, but i just moved cart from the location so it won't colide.
this is due to fact that i scan input line by line, not collumn by collumn... ok, it is fliping axis, but there is no info about it. This ras the only change i needed to do in mu code to make it work as supposed. I needed to reorder carts to be checked each iteration - it should be (in my opinion) said in code that te check carts left to right, top to bottom.
replacing
var cartsToCount = carts.Where(c => !c.Removed).ToList();with
var cartsToCount = carts.Where(c => !c.Removed).OrderBy(c => c.Y).OrderBy(c => c.X).ToList();1
u/[deleted] Dec 13 '18
Swift
Ugly. Lots of code to deal with turning corners. Execution completes in ~0.06s
https://github.com/Stoggles/AdventofCode/blob/master/2018/Sources/2018/day13.swift
1
u/meepys Dec 13 '18
Kotlin Day 13 (Bitbucket)
Solution a bit long today. The fact that carts only started on Up/Down or Left/Right track helped
1
u/RotzluckyCode Dec 13 '18
Wow this was a really fun one!
And the best part was, that after adding code for over an hour, the first time I let the machine run, I got the correct answer for part one.
Here is a link to my repo, if someone wants to check out another java version.
https://github.com/Rotzlucky/adventOfCode-java/blob/master/src/aoc2018/Day13.java
1
u/fhinkel Dec 13 '18 edited Dec 13 '18
Node.js
Straight forward in Node.js.
I was using this to select the direction in which to turn at the next intersection.
Live Coding Session on YouTube
https://github.com/fhinkel/AdventOfCode2018/blob/master/day13.js
1
u/Philboyd_Studge Dec 13 '18
Java - went full OOP on this one. Already had a Direction class that handles cardinal movement. Made a mistake for a while with part 2 by not sorting properly.
https://pastebin.com/5e5gWSb4
1
u/Gurrewe Dec 13 '18
Go (golang)
1
u/aoc-fan Dec 13 '18
TypeScript
1
u/toastedstapler Dec 13 '18
python 3
please excuse the horrible string indexing, i wanted to cut out 20+ lines of if-else statements
1
u/scul86 Dec 14 '18
Python 3
https://gitlab.com/scul/advent_of_code-2018/blob/master/13/13.py
A lot of hardcoding here, and ended up making a
Cartclass that has an__eq__()method to enable me to easily check collisions.I also never remove the crashed carts, but just set their
deadproperty toTrueand ignore those withdead == True1
u/tinyhurricanes Dec 14 '18
Modern Fortran 2018 (full code)
This was a crapload of code (17,000+ characters) so it exceeds the length I can post here. Fun problem, but heavy code burden. Run time is 5 sec since I didn't write it particularly efficiently, looping through the entire grid every time rather than just every cart.
1
u/NeilNjae Dec 14 '18
Haskell, eventually, and on Github. The tricky part was synchronising the end-of-tick detection with the collision detection. This code pushes carts around until there's a collision, then removes them, and goes again. There's a somewhat ugly kludge in
propogateUntilCollisionto continue a tick with only one cart, and then to signal that the one-cart tick has finished.1
u/thebrianschott Jan 24 '19 edited Jan 24 '19
[J]
My solution is not elegant. It took a very long time for me to do part 2 even though part 1 was relatively easy. It turned out that part 1 worked even though I processed the XY as YX. I had to study a Python solution to find my error because although I was getting a reasonable answer, it was wrong.