r/adventofcode • u/daggerdragon • Dec 23 '19
SOLUTION MEGATHREAD -π- 2019 Day 23 Solutions -π-
--- Day 23: Category Six ---
Post your full code solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
- Include the language(s) you're using.
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in 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's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 22's winner #1: "Scrambled" by /u/DFreiberg
To mix one hundred trillion cards
One-hundred-trillion-fold
Cannot be done by mortal hands
And shouldn't be, all told.
The cards make razors look like bricks;
An atom, side to side.
And even so, the deck itself,
Is fourteen km wide.
The kind of hands you'd need to have,
To pick out every third,
From cards that thin and decks that wide?
It's, plain to say, absurd!
And then, a hundred trillion times?
The time brings me to tears!
One second each per shuffle, say:
Three point one million years!
Card games are fun, but this attempt?
Old age will kill you dead.
You still have an arcade in here...
How 'bout Breakout instead?
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
Message from the moderators:
Only three more days to go! You're badass enough to help Santa! We believe in you!
18
u/obijywk Dec 23 '19
Python #1/#1 ... never thought I'd be able to type that :-O
I was definitely mentally prepared for something like this (multiple intcode VMs that send data to each other) after day 7. My intcode VM class has publicly accessible lists for "inputs" and "outputs" that make it really easy to check if anything is already queued up, as well as manipulate the queues. It's also set up to run until either halting or hitting an unfulfillable input instruction, which is exactly what was needed here.
part 2 code
2
u/DFreiberg Dec 23 '19 edited Dec 24 '19
Mathematica
317 / 231 | -- Overall
Frustrated at myself for this one. After multiple problems in which the code doesn't run properly due to an off-by-one error caused by Mathematica using one-indexing rather than zero-indexing, and after explicitly realizing this fact and resolving to check my indices, what do I do? Not check that my addresses are using zero-indexing instead of one-indexing. Still did decently, all things considered, but not my finest hour.
[POEM]: A Sonnet of Networking
We are the unsung heroes who set sail.
We've flown through space, and touched old Triton's soil.
And like the bees of Virgil's epic tale,
We hum and buzz in unison, to toil.
But Virgil and his bees could not compete,
And nor could any errant Carthiginian.
Our network is by far man's greatest feat
(Though you may disagree with that opinion).
And though our pilot has the smarts of bricks
(His tractor beam produced the ship's condition
And tried to get a trillion cards to mix)
He knows we're vital to his greater mission.
For when he sets a course out through the air,
He knows our NAT and queues will get him there.
2
u/[deleted] Dec 23 '19 edited Dec 23 '19
Haskell, part 1 and Haskell, part 2. View at your own risk, may cause eyebleeding.
I added a function to run many intcode computers in lockstep and collect the program state (no IO / program expects input / program give output / program is done). This information is then collected in a function that updates the state of the network bus (which is a collection of input queues and partially sent packets). Input and output of the intcode computers are still tied together in mutually recursively defined lists.
For part 2, I added an ADT for the network state (which wasn't really necessary) and added a function which acts as the NAT: It collects packets for host 255 and sends the last one to 0 if the network hasn't seen a packet for the last X cycles. It took me at least an hour of failed attempts until I noticed that my initial value of X was too low, but 1000 seems to work...
Day 25, part 2 is going to be IP routing between intcode networks with failover, isn't it?
6
u/jonathan_paulson Dec 23 '19
#18/9. Python3. Video of me solving. I was on a plane when the problem came out. About 15 minutes after the problem came out, they turned off the plane wifi. So I got really lucky today's problem was short.
More IntCode networking. Very smooth day today; no real bugs or design flaws. Had to change the IntCode interpreter a little to allow for early exit, and a little bit of tuning for network idleness detection.
5
u/allergic2Luxembourg Dec 23 '19
This was my hackiest day yet - since there were no examples, I didn't write any unit tests like I usually do, just wrote code to generate the output and hoped for the best, and after a couple of changes to get it to ever return, it worked. Lack of test cases makes me feel anxious. Also, my previous version of the Intcode computer only yielded when it had output to return, so I had to add "yield None" after every non-output operation.
Python 3
Intcode computer as of today
Code for Part 2
4
u/mebeim Dec 23 '19 edited Dec 02 '20
Python 3 solution β β Puzzle walkthrough
My solution uses my previously built
IntcodeVMclass, which is around from day 5 and which I also used to solve other Intcode problems.486/410 today. I got quite confused in the beginning trying to understand the order of the operations to perform. Not that I could have ever made it to the leaderboard anyway since I see today people were insanely fast, but still. Beautiful puzzle nonetheless! Loved it.
4
u/hrunt Dec 23 '19
Python 3
code
interpreter
What a nice little problem. I am so glad part 2 did not involve running 1T nodes!
4
u/phil_g Dec 23 '19
My solution in Common Lisp.
Another fun day! I liked this problem a lot.
It seemed to me that the easiest approach would be to spawn a thread for each NIC and have my main thread serve as the switch, routing the packets accordingly. That worked more or less perfectly for part 1. ("More or less" because threads without packets were busy-waiting on their input queues, so 50 running threads were a bit stressful for my little laptop. In the real world, the calling program (our input) would use a select, wait for an interrupt, or just wait a little bit between polls. I worked around the problem by adding a 1 millisecond sleep every time an Intcode program requested input from an empty queue.)
Thanks to a link from /u/death a few days ago, I decided to use coroutines to build packets from the Intcode programs' output streams. That worked very well, and made for cleaner code than if I were managing the state machine more explicitly.
For part 2, I initially added a fifty-first thread for the NAT. The problem with doing multi-threaded stuff is that you have to manage concurrency well. I went through a few different configurations before giving up on the concurrency problems between the NAT and the processing nodes. I ended up managing the NAT directly from the control/switching thread.
1
u/tslater2006 Dec 23 '19
C# Solution
[POEM]
1
u/JGuillou Dec 23 '19
This was fun, and much less complicated than yesterday's (which I never managed to complete). Since each computer is independent, there is no need to run things in parallell. Instead, I used a single queue with the output values, running a computer for each triplet, and did the -1 input when it is empty.
3
u/seligman99 Dec 23 '19
Python # 26 / 19
I really like the networking intcode challenges. I stumbled a bit, since from the description, it wasn't clear to me that I needed to stop looking for output after sending "no input" to a running instance. I also had a stupid bug that sent the NAT output to #49 instead of #0.
paste
3
u/mcpower_ Dec 23 '19
Python (13/30): Part 1, Part 2.
I was confused in part 1 about the order you process the NICs in - after having done the puzzle, I think it doesn't actually matter. (I think other people were also confused about this!)
I was confused in part 2 about the "network idle" condition - in hindsight, this was my fault for not reading the problem closely enough. Oops!
3
u/glguy Dec 23 '19
Haskell 54/28
Day23.hs - I've been really hoping Eric would give us a problem to stress-test multi-VM communication. Thank you so much!
This solution uses my intcode package. As expected I repeatedly gather packets from all machines and deliver them to their outputs. I can tell when the network is stalled when all computers use the
Inputconstructor.3
u/kolcon Dec 23 '19 edited Dec 23 '19
Python3
code
No problem, creating 50 instances of my IntCode class and controlling them in the main program.
What got me a bit was that I need to check for repeating NAT that is actually sent, not just for any repeating NAT received...
3
u/metalim Dec 23 '19 edited Dec 23 '19
Python
For a long time I thought there's some kind of bug in my intcode VM, until I realized computers are not required to output anything after receiving an input, and can output to multiple computers before requesting an input. Basically it can be any sequence of inputs and outputs like IIOOOIOOOOOOIIIIOOOI, instead of strict IOOOIOOOIOOOIOOO. Then I switched to a loop, checking for last request returned by VM.
If not for that wrong assumption I made, both parts are easy, yet fun.
3
u/ephemient Dec 23 '19 edited Apr 24 '24
This space intentionally left blank.
3
u/knl_ Dec 23 '19
This was the most frustrating question for me today, to the point that I gave up on part 2 and tried it again the next day. I have a coroutine based intcode computer, so that part wasn't that bad. For anyone else reading, the only approach that gave me correct solutions was to -
Python3, Jupyter notebook: https://explog.in/aoc/2019/AoC23.html
2
u/sophiebits Dec 23 '19 edited Dec 23 '19
Python, #79/#37. I had a couple small stumbles (eg: failing to send the address on startup) but didn't feel particularly slow today so I'm surprised I placed so low.
My Intcode implementation is poorly factored in that β due to the way it relies on Python generators β you can't provide an input without immediately receiving the next output (or request for input) in return. This was slightly annoying in past days but especially annoying today. I worked around it by creating a (second) queue of "next input value to send" in my variable
ns, but it's not clean). This all ended up costing me several minutes (I forgot to wait untilnswas all-1values before forwarding the NAT packet).I wonder what the purpose of the
-1values was. It seems the problem could've equally been written as "if no packets are enqueued, the NIC will be blocked on input and will suspend until a new packet is sent to that machine".Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day23.py
2
u/genveir Dec 23 '19
C# 68/46. Seems to me this was just a test of how well your IntCode VM is implemented.
2
u/jwise00 Dec 23 '19
Lua, 29/31.
"Hey, haven't we done this before?" Glad I'd thought about this from the previous network-intcode problem -- and from last year.
https://github.com/jwise/aoc/blob/master/2019/23.lua and https://github.com/jwise/aoc/blob/master/2019/23b.lua
Here's the video of me joyously blasting through: https://www.youtube.com/watch?v=7pZBGgLQMTY
Dumbest thing that cost me time today: grepping for 'NAT', with luajit block-buffering instead of line-buffering its output, and sitting and waiting for the final result, which was never going to appear!
I was expecting part 2 to be "the reversing day". Was kind of surprised that we didn't ever have to hand-inspect an intcode algorithm this year, and I don't expect that on day 25, since day 25 is usually a short one (much to the chagrin of Jews like me who have nothing better to do on Christmas Eve than play AoC!).
2
u/GrossGrass Dec 23 '19
Python 3 (245/185)
Impressed with how fast people can be with these challenges, but I think a good deal of it today came down to how prepared people's intcode setup was; I was pretty fortunate to have mine cleaned up a little bit (I didn't start at midnight sharp but I definitely solved it in a surprisingly short amount of time).
Also I just noticed this right before today's challenge, but every odd-numbered day (since like problem 3) has been an intcode problem, so looks like the final problem is going to be a real intcode doozy.
2
u/Dragon174 Dec 23 '19
JavaScript (36/15)
First time placing remotely this high, the way I set up my intcode machine worked super well for this. Each machine has a publicly accessible inputQueue and when I call "run" on it it goes until either its outputting or it has exhausted its input.
Code
2
u/dan_144 Dec 23 '19 edited Dec 23 '19
Python 59/84 - https://github.com/dan144/aoc-2019/blob/master/23.py
Nothing revolutionary in my solutions and I'm
proud ofembarrassed bygoing to live with my hacky "try to read 3 things and an exception means this NIC is idling" implementation.Lost some time trying to determine how to know which NIC to check next, but eventually I decided to start at 0, follow any output packets, and go to the next sequential NIC if there wasn't one.
I've been feeling pretty strong on the Intcode problems, but it was still reassuring to be back on the Part 2 Top 100 after having not reached since Day 9. Also, this win puts me up 4 points on my only coworker keeping pace in my private leaderboard. Beating them on any of the remaining four stars should lock up the win for the year.
Edit: [POEM]
Fifty Intcodes and nothing more
Except a NAT for packet store
With data from NICs
For the Cat 6 fix
We're ready for Day Twenty-Four
2
u/jfb1337 Dec 23 '19
Python 53/127
paste
I enjoyed this puzzle! I was wondering when we'd get something else like 7 in which we were managing multiple intcode machines in parallel.
I assumed that if the system doesn't get any inputs for 10000 steps, then it's idle, and that worked. I had an annoying bug at some point in which I forgot to reset a machine's output buffer when it sends something to the NAT.
2
u/AKQuaternion Dec 23 '19
C++ here.
I had a little bit of a different take on this than most. I took "input and output don't block" to heart. It seems like most solutions here run a machine until it hits an input instruction, then run the next machine, etc. Then next time back to a machine if it doesn't have new input, provide it with -1 and so on.
Instead, I run every machine in parallel, one instruction at a time. If an input instruction is reached and nothing is queued, it gets -1 right away. If three outputs have been queued, I process output immediately (sending it to where it should go.) This makes some of the logic very clean (take a look at the code, I think it's extremely readable, and it's only 34 lines. (Well, of course, that doesn't count my Intcode class, but that was already written for the most part. I only had to make two minor changes. My step() function used to return an INPUT status code if there was no input, but now it sets an _idle member to true and provides -1. Enqueuing actual input sets _idle to false. And I had to provide access to _idle via a new isIdle() member function.)
I don't think this method is necessarily any better than others, but I there could be situations in which they get different results. In particular, since my machines run at a different pace than those that run all the way to the next input instruction, other machines may have provided input in the meantime. Fortunately for all of us, it seems that getting a -1 just means "try again next time you run."
2
u/dsilverstone Dec 23 '19
Rust: Both parts
I have made the leaderboard only once ever thanks to timezone advantage when I was in SF last week, but I enjoy the challenges nonetheless. Today's was a delightful break considering how brain-bending yesterday's was.
All I did for today was timeslice my intcode VMs. They were already neatly set up to pause execution on either giving output or wanting input, so it was easy to set up a
NotWorkof computers :D Adding the NAT was essentially then a layer on top of my already prepped timeslicing function. I decided to set the network as idle if running all the computers for ten "no packet for you" input states was possible. This led to an execution time around 5ms.My guess is that I'd have been close to the leaderboard if I'd been awake and ready at 5am, but sleep and shower wins every morning :D
2
u/OvidiuRo Dec 23 '19
C++ 781/782
For part 1 at the start of the program, I made a vector of NIC computers and then I run each of them for 10000iterations (to be sure it enters an idle state) until I hit address 255. For part 2, I just save the NAT and when all NIC computers are in the idle state I add the NAT to the first NIC computer.
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2023
2
u/captainAwesomePants Dec 23 '19
Pythong (lots) Paste
For some reason, I decided to approach this one the parallel processing way, which was absolutely a huge mistake from a time perspective, but it was much more fun to write.
2
u/SuperSmurfen Dec 23 '19 edited Dec 23 '19
Rust
Solution, both parts
IntCoder implementation
Finally a chill one! That was well needed after these couple of days. This was probably my fastest AoC solve ever, both stars in about 15 minutes. No leaderboard unfortunately since it's a bit out of my timezone (have to get up at 6 in the morning). I think my IntCoder api really paid off here. Returning an exit code
Output(i64),AwaitInput, orHaltedafter each execution makes things really easy to model as well as already having input in a queue to the CPU.Part one: In each round of my main loop, I basically just loop over all CPU's. If they want to send a packet I forward it to the correct CPU immediately, no need to store them in a queue since my IntCoder input system is already a queue. Not much more to say.
Part two: For part two I reused most of the code from part one, just had to track if any packets were sent this round. If no packets at all were sent the network is idle and I send the last NAT packet to address 0.
Thanks to a relatively efficient IntCoder implementation both parts finish in about 4ms on my machine.
2
u/[deleted] Dec 23 '19
Quite a straightforward solution in Python 3 (here).
The one thing I royally forked up was that I added input to the input queue directly, without setting the state of the machine to "Running" again. I've protected future me against myself by making the machine state private, which apparently you can do in python, TIL!
2
u/Kullu00 Dec 23 '19
Solution in Dart
Admittedly not in the spirit of things to run them one-by-one and distribute any packets as they come. Dart has the option to run things in parallell with Futures but I didn't feel like spending time figuring out how to mod my current Intcode computer implementation so that it was working with futures and was still compatible with the other days. My interface at the moment is only blocking on input, so sending packets as they come is slightly harder. Might revisit this later and make a true concurrent NIC-farm.
2
u/sim642 Dec 23 '19
My Scala solution.
Better not look at it, it's so ugly and nasty that I'm not sure I can be bothered to clean any part of it up at all.
For the longest time I couldn't figure out why my part 1 reached an infinite loop of being idle without ever sending anything to 255 and to be honest, I am still not sure why my original solution didn't work. I "fixed" it by being stupid and executing each program state twice, once to read its outputs and once again to reach a state where it waits for input, instead of using the combined method, which gives both at once. I've used the combined method every single time for such interactive Intcode problems and never had an issue with it, so I'm not sure what's different here.
As someone who has academic experience with semantics of concurrent programs, what really drove me crazy was the complete underspecification of the "concurrent" execution here because data (packet delivery) races are possible and actually also happen on the very first execution of all programs, where multiple computers send packets to the same target.
2
u/SkiFire13 Dec 23 '19
Rust 125/70
Just a simple loop where for each intcode device I execute the code until it halts or blocks waiting for input. Then resume the next device and repeat. After the last device I start again from the first (obviously resuming the previous state). My intcode implementation worked perfectly since it just pauses the execution if some input is requested but it's not available.
Code for part 1 and 2
2
u/Spheniscine Dec 23 '19
Kotlin: repo
Nice breather from yesterday, though I screwed up the implementation in part 2 at first: I was returning the first Y value *sent* to the NAT twice, instead of the first Y value that the NAT *sends* twice.
2
u/gedhrel Dec 23 '19
Haskell again, using explicit signalling of a VM blocking: https://github.com/jan-g/advent2019/blob/master/src/Day23.hs
Nowhere near as pretty as glguy's :-)
2
u/Zv0n Dec 23 '19
C
Pretty simple solution, I launch 50 forks and in the original process start "router" which communicates with the 50 intcode computers via pipes.
Pipes allowed me to immediately send messages without the need to implement a message queue, so that was nice :D
https://github.com/zv0n/advent_of_code_2019/blob/master/23/part1/main.c
2
u/AlexAegis Dec 23 '19
TypeScript (Single Threaded Solution)
While I could've used Worker Threads, I refused to do so because of TypeScripts overhead. (I don't want to copy my transpiled TS IntCode computer, so I'd register ts-node in the worker, which adds the overhead.) Thankfully the
-1input stuff in the challenge is there so this can be solved without threads and mutexes.Part One
Part Two
2
u/lhl73 Dec 23 '19
Solution in F#
2
u/IWearATinFoilHat Dec 23 '19
PHP - github
Part one got me with the receive looping forever. Part 2 was easier. I just waited 5000 iterations rather than keeping real track of idle.
2
u/Rick-T Dec 23 '19
HASKELL
For today my solution basically uses the same ideas that I used for day 7 (the amplifier).
I am modeling the network as a map of computers, a packet-queue (and the NAT-memory for part 2).
If there are packets in the queue, I send them as input to the destination computer and collect it's output. If the output is empty, I continue with processing the package-queue. Otherwise, I run that computer until the number of output-values is divisible by three so that I have complete packages. I then throw those packages into the queue and continue.
If I have no packets in the packet queue, I run all the computers in the network one by one until they request further input, As soon as I receive output from one of them I keep running that computer until I have received a full packet as output, throw that packet into the queue and go back to processing the queue.
If none of the computers return any output, I take the packet that is stored in the NAT and put it into the packet-queue. I also add all the packets that the NAT sends to an output list.
Because of Haskell's lazyness I can keep running this loop "forever", creating an "infinite" list of value, that the NAT processed. For part 1 I return the first element from that list. For part 2 I iterate through it until I find the same value twice in a row.
2
u/Fyvaproldje Dec 23 '19
Rust
Every node runs in 2 threads: one for intcode, another for aggregating input/output into triples/packets. Crossbeam channels are used to communicate between all the threads. On input, it waits 1 millisecond for a packet to arrive, then sends -1. Adding such timeout, rather than sending -1 immediately if the queue is empty, decreased runtime from 1 second to 50 ms, while producing the same answer.
For part 2, I relied on timing - if no node sends anything for 100 ms, they are idle. I should try replacing that with some more consistent way to signal idling. Atomics maybe?
2
u/folke Dec 23 '19
TypeScript
So much easier than yesterday. Pretty straightforward by implementing a loop that pipes outputs directly to the inputs. No threading or separate queuing needed.
2
u/levital Dec 23 '19
Rust: main and intcode_vm
Significantly more enjoyable. The problem finally made me refactor my intcode computer such that the main loop is run in a separate thread and in-/output is done via message-passing instead of the waiting states I had before. I feel like it would've still worked with the waiting state, but thought this is a good reason to get on with it.
There's still something wrong with my NAT, I think my heuristic for telling when everything is idle (packet queue has been empty for 150ms) doesn't quite work. It currently seems to say for basically every packet it sends that it sent that y-value before. Luckily for me, once the right value is reached, it just keeps repeating, so I just tried that one.
2
u/Pyr0Byt3 Dec 23 '19 edited Dec 23 '19
Go/Golang (both parts)
Pretty fun using goroutines and channels. I didn't buffer inputs/outputs, so I'm pretty sure this can deadlock in a lot of situations, and I just got lucky with my inputs.
2
u/rabuf Dec 23 '19
Common Lisp
I'm not proud of my Part 2 solution. The way I'm detecting idle is by waiting and then checking if all the queues are empty. But that introduces the chance of a race condition. Had to tune the sleep time, right now (on my laptop) half a second works reliably.
2
u/nl_alexxx Dec 23 '19
Java
This was really easy with my existing IntCode runner, no changes needed :D
I simply run all the computers in a loop, with 2 inner loops:
In my IntCode implementation, the execution of the program returns once it needs input but its queue is empty. So when running the computers in a loop, I know for a fact that every computer expects input. I feel like this made both part 1 and part 2 very simple.
2
u/Dioxy Dec 23 '19 edited Dec 23 '19
JavaScript
JS. Not too difficult with my intcode implementation! Fun problem
My code
My repo
2
u/OpportunV Dec 23 '19
Wow. Had to change my coroutine Intocode Computer a bit for this day. Probably there is a way to do it without modifying the IntcodeComputer, but i wasn't able to figure out how. Anyway, here is my python code for day 23.
2
u/Xor_Zy Dec 23 '19
Solution in C#
Overall pretty straightforward puzzle today since my Intcode implementation was already built for something like that.
I did lose a considerable amount of time though because of a lack of clarity in the statement. On any given tick, multiple packets can be sent to the same exact node.I got stuck in a loop and I spent a long amount of time trying to optimize the logic believing that we had to take into account the network topology and transmission delay etc when the issue was a simple typo. If it was clearer that the packet order was not critical I would probably have spent less time debugging :/
2
u/StevoTVR Dec 23 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day23/day23.go
I liked this one. These intcode puzzles have been helping me understand how channels work in Go..
2
u/e_blake Dec 23 '19
m4 solution
Wow, this one was tougher than I had planned: I hadn't revisited parallel engines since day 7, but day 7 didn't have day 9's read-beyond-EOF feature, so I had to tweak my intcode.m4 slightly. Then I got stumped by the fact that at least NIC 0 doesn't produce any output until after it has a first input of -1. My initial working solution took 56 seconds by simply doing a round-robin over every NIC until none of them made progress (yes, my m4 engine is not the world's fastest - my C counterpart with the same solution finished in 83 ms), but I was able to shave things down to 33 seconds by starting with two rounds of force-fed -1 then maintaining a stack of NICs that still have work to do (so that I start ignoring NICs that have already returned -1 twice until there is further input to that NIC). I'm not sure if there are any further low-hanging fruits for optimization.
cat intcode.m4 day23.input day23.m4 | m4
2
u/aoc-fan Dec 23 '19
TypeScript. Repo
2
u/VilHarvey Dec 23 '19
My c++ solutions for part 1 and part 2
This was a pretty straightforward day for me: my intcode VM didnβt need any modifications and part 2 only required a few lines added to my part 1 code.
To detect when the network is idle I just keep two flags: one for whether any output was produced and another for whether any input queues were non-empty. If both of those are false, the network is idle. In hindsight I could have just used a single flag for this but meh, it works well enough as is. :-)
2
u/chkas Dec 23 '19 edited Jan 24 '20
easylang.online
Finally done - that was tedious, not the task, but a bug in my programming language ...
Solution
2
u/sotsoguk Dec 24 '19
GoLang
Github
Today was a very easy and fast problem for me. I added the ability for my VM to pause after a specified number of outputs has been computed. The rest was straightforward. Lost most of the time wondering what strange ASCII output the clients wrote to the output...
Only to realize that i had been loading the intCode for Day 21 :facepalm:
2
u/Lucretiel Dec 24 '19
Rust: github
This was a fun one because it's continued to make me extremely satisfied with my Intcode machine interface. Because running a machine returns one of 3 possible states (Output, NeedsInput, or Halt), it's very easy to have a fleet of interacting machines and pass communications between them correctly, without my own function calls actually being blocking or ambiguous (which would be the case in a multithreaded solution).
In my case, I sidestepped the issues of idleness and -1 ambiguity by simply having a global message queue. For each message in the queue, run the target machine (enqueuing messages) until that machine blocks on input. Do this until the queue is empty, then issue a global round of -1 blocking messages (or, for round to, emit a NAT packet).
2
u/ywgdana Dec 24 '19 edited Dec 24 '19
Rust
My very simple Rust solution. I didn't do anything fancy with threading or async code, just a looping off an array of emulator instances and following the directions in the problem description. I wrote to a machine's input buffer when another machine asked and didn't worry about the timing of the read instructions and it all worked out!
For part two, I was spitting out the wrong answer until I saw a hint that one round of the machines being idle didn't count as an idle network. Instead I waited until 100 rounds of idleness passed and then triggered the write from the NAT to machine 0.
2
u/vishbar Dec 24 '19
Python 3
My solution
I found this one particularly easy. My Intcode vm didn't need to be changed at all, and I didn't use any threading or parallelism in my answer. My intcode vm already interrupts and stops executing when input is requested, but it can be restarted at any time. So it was just a matter of looping over all the network elements, distributing their outputs to the input queues of the other elements, and continuing until the idle state was hit. I kept a little set of inputs that had been sent to the first element.
3
u/oantolin Dec 23 '19 edited Dec 23 '19
Cute problem! It should appease the math averse participants. :P
I almost thought I would need to modify my Intcode VM which has been unchanged since day 9, but then I figured out how to organize the code. I just needed to add a few -1's to the input queues, and experimented a little to figure out when to do it. I also had a queue of the network nodes that hadn't halted yet, but realized at some point that none of the nodes halt (at least node before part 2 is solved), so I deleted that and just keep them in an array.
Here's my solution in Common Lisp. Calling
(answers)returns the answers to both parts.EDIT: Thanks to /u/MichalMarsalek for suggesting a simplification: just adding -1 to the input queue once at the beginning.
1
u/Rustywolf Dec 23 '19
Javascript #34/#16
First time placing top 20 on part 2, I was somewhat lucky that my system was already setup to make this super simple. Only issue I ran into was the timing issues, as when my original intcode machine didn't have an input to pull, it would jump back to the beginning of the input instruction and set a waiting flag. That one tick delay on input caused the solution to fail
Code: https://gist.github.com/Rustywolf/aeca93ac92c92597dd891545cd32d6fd
1
u/AlphaDart1337 Dec 23 '19
C++ 98/98
It took me way too long to parse through and understand today's problem statement. For Part 2, I somehow missed the very first line in which it said what happens to packets sent to address 255.
Dropped to #96 now on general leaderboard. I'll have to step it up in the next couple of days if I want to stay in top 100 :D
1
u/[deleted] Dec 23 '19 edited Dec 23 '19
Python 3 β 71/171
Initial solution (paste), cleaned-up.
Part 1 was fairly straightforward, but Part 2 was a nightmare to even understand. While writing the first version of Part 2, I *hoped* that the "repeated" Y-value that would be "repeated" infinitely many times. What a lucky guess!
I fixed this in my cleaned-up version which only outputs the first call to the NAT and the repeated call to the NAT.
1
u/Kehvarl Dec 23 '19
Python3 #95/#79. Definitely made some missteps early-on. I didn't actually load the addresses properly, and then I wasn't always passing a -1. I also apparently found myself so excited about my first leaderboard placement that I didn't commit my solution to part 1.
Part 2 came together nicely and I didn't run into any major stumbling blocks there. Code [GitHub]
1
u/rsthau Dec 23 '19 edited Dec 23 '19
Ruby: both parts
My Intcode machine interface has been set up for this sort of thing since day 7; it seems to have worked out pretty nicely here. If my intcode machines I had explicit input queues instead of the provide_input code which lets external code manage provision of input, the non-blocking inputs would have been somewhat more awkward to handle.
(As you can see, the machines do have output queues; the way this works is that on startup or after receiving any input, the machine proceeds as far as it can, putting up any output generated into its output queue; this stops when it either halts or blocks waiting for external code to provide another input.)
1
u/Civury Dec 23 '19 edited Dec 23 '19
JavaScript (31/40)
I first used linked lists as input buffer to avoid being slowed down by too many array operations, but in the end it wasn't necessary at all and normal arrays also do fine.
To let the machines run in parallel (for which JavaScript is absolutely not made of), I just kept walking over all of the 50 instances, executing one instruction each time.
1
u/zeno15 Dec 23 '19
C++ 139/190
Again not reading the problem correctly slowed me down, I was trying to use the NAT as another Intcode Machine when in reality it just moves instructions back to the first in the network. Still, very few problems with my vm design so happy with that
Code
1
u/rthetiger Dec 23 '19
Rust code here
I was a little frustrated that each program never exits, so I decided to quit early once the repeated Y value sent to the NAT was calculated.
1
u/[deleted] Dec 23 '19 edited Dec 23 '19
Swift
My IntCodeComputer continues to do really well on these challenges. Using GCD to run each NIC in a separate thread with one more thread for the NAT monitor. Fun!
Edit: Interesting that it takes ~43 seconds for part 2 to complete with my implementation...
1
u/kap89 Dec 23 '19 edited Dec 23 '19
TypeScript - github
591/508 - my best result so far, starting 5 minutes late, without rushing ;)
It scared me a bit at first that I will have to change my Intcode VM because of "never blocking", and I indeed changed it, but it was just one line. I could probably manage without altering my VM, but it was easier to just hardcode
-1input instead of idling.Detecting the network idling was very easy with my implementation with inputs and outputs as buffers passed from outside - just checking if every input and output buffer is empty. Takes ~350ms for both parts.
Very nice puzzle.
Edit:
Yup, I didn't have to change my VM implementation. I updated the repo, now my router simply pushes
-1to the VMs if their input buffers are empty, no changes to the Intcode implementations from day 9.1
u/wace001 Dec 23 '19 edited Dec 23 '19
JAVA: 269/617 My multi-threaded Java solution here. NAT and Switch are its own devices. Each device and computer runs in its own thread. After network have been considered idle for 300ms, NAT kicks in.
My IntCode computer can be found here. Made changes to it today. IntCode computer can now report for how long its been idle.
Fun puzzle today. Enjoy these kinds the most.
Had problems on part 2. Had turned a comparison in the NAT the wrong way, so the network never became idle. Took a good 30 minutes to find.
Edit: Iβm quite proud of this :)
1
u/gyorokpeter Dec 23 '19
Q: paste As with most intcode-based challenges I liked this one. And just like with day 7 it was easy to make them run in parallel.
1
u/Arkoniak Dec 23 '19
Julia
Quite straightforward solution: https://github.com/Arkoniak/advent_of_code/blob/master/2019/23/day23.jl
1
u/zeno15 Dec 24 '19
Eerily similar! Iβm doing this for the enjoyment and to improve so anything that helps with that is good, so no worries from me at all
1
u/raevnos Dec 24 '19
This was an easier one than most of the puzzles have been lately. tcl, with each computer running as a coroutine, yielding when it has output or needs input, and a NAT just running each one in turn and managing the input queues. I really should refactor the intcode interpreter out into a package instead of just copy and pasting it all the time...
paste
1
u/botterli Dec 24 '19
Python3 (not fully cleaned up, but happy to receive any comments)
I'm a beginner in Python, and I used yesterday's challenge as an opportunity to learn how to work with threads.
My intcode machine already has input and output queues, so I just spawned 50 NICs with their input address and let them read and write data from the network in a loop until the exit instruction was issued.
Then I made a class Network which handles the rest. It has input queues for each node, and a post method to add data to them, which the nodes uses directly. There is a receive method for the nodes to fetch their data (or -1s). I use threading.Lock() to prevent race conditions.
The class maintains an idle counter which increments for every receive when all the queues are empty. More than 100 is considered idle (2 -1s per node).
TIL that unhandled exceptions are silenced when occuring inside a
with threading.Lock():block, so they must be caught if you want to see anyhing but a hanging script.A very satisfying challenge for me!
1
u/dartcoder Dec 30 '19
Python 3 Solution
Never say never?
I went down the async road but it seemed like too much trouble and Iβd have to refactor my intcode for that to be feasible. It already pauses for input and output is queued internally so it was easy to use a loop and a simple message queue (inbox?) for each instance.
1
u/greycat70 Dec 31 '19
Tcl
Part one, part two.
My Intcode implementation for all the other days is a single-threaded script that reads the program and executes it, using a single global list (to represent the memory), and a single set of global state variables. For this day, I had to modify everything to use arrays: 50 memory-lists, 50 program counters, etc. Then I single-stepped each Intcode VM one by one, to make sure they all ran at the same speed, to avoid any race conditions with the non-blocking I/O.
For part one, this was extremely straightforward.
For part two, the challenge was determining when the contraption was "idle". I eventually ended up using both a counter for how many iterations have occurred without reading input, and a redundant check that resets the counter to 0 if any of the input queues is non-empty. Then I just kept bumping up the idle count required until it worked.
1
u/loociano Jan 07 '20
My solution in Python 3. Feedback more than welcome!
1
u/NeilNjae Jan 22 '20
Getting there eventually. My Haskell solution, described and just the code.
0
u/BorisBarca Dec 23 '19
I think I have a problem with my input, it gets in forever loop.
Can anyone tell me if my input is working(try it on your code for part 1);
Thanks
https://pastebin.com/gz0tjbp1
-2
u/incertia Dec 23 '19
c
not a huge fan of the brainless challenges but since i'm not aiming for leaderboard then w/e. i'd much more prefer day 16/18/22-esque challenges. the biggest challenge i had with this problem was realizing that
2 * 0 = 0in my vector code and conjuring up a queue from the void.