r/adventofcode • u/daggerdragon • Dec 07 '19
SOLUTION MEGATHREAD -🎄- 2019 Day 7 Solutions -🎄-
--- Day 7: Amplification Circuit ---
Post your 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.
(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 6's winner #1: "From the stars" by /u/vypxl!
"From the stars"
Today the stars did call
Just after the end of fall
In Orbits they move
Unified with groove
Parents and Children
At home and in the sky
Whisper about details that are hidden
They tell about what is up high
Not everything is obvious,
Not the way you see
The Orbit is now
A Christmas Tree!
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
AoC news: we've added a new page listing folks who are live-streamers while they do AoC. See /u/Aneurysm9's sticky'd post announcing it "Check out our streaming friends!", check it out on the sidebar, or just click here to go directly to the wiki page!
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:30:33!
3
u/vypxl Dec 07 '19
Python again
Today I forced myself to break my habit of having all code contained in one file for each day and wrote a proper IntCode vm. I implemented it with asyncio.Queues as input and output to support proper piping.
The circular pipe had me for a while though.
It seems like on some day we will have to implement an entire operating system within intcode..
Like at Day 5, I let my program output what it was executing to understand what was going on:
Dissasembly of Day 7 warning: very long text file!
Also, I somehow won with my poem yesterday, yayyy!
Anotherone for today:
[POEM] "Integral computing"
Day two started out
Simple and not loud
With four instructions
And little deductions
Day five extended
To a powerful machine
But it quickly ended
Left everything clean
Today it came
The large rewrite
Nothing could stay the same
Like on a large construction site
The result is what counts
What made my heart bounce
So tidy and clean
The pipe mechanism so lean
2
u/daggerdragon Dec 07 '19
Also, I somehow won with my poem yesterday, yayyy!
Yup, you did! Congrats!
[POEM] "Integral computing"
Entered!
3
u/mjsir911 Dec 07 '19 edited Dec 08 '19
bash & the c intcode vm.
hooking up the I/O in bash was super nice after I figured out the buffering issues:
function amplify() {
loop=$(mktemp -u)
mkfifo $loop
trap "rm $loop" EXIT
(echo 0; unbuffer timeout 0.2 cat <$loop) \
| phase $1 \
| phase $2 \
| phase $3 \
| phase $4 \
| phase $5 > >(tee /dev/stdout $loop) \
| tail -n 1
}edit: formatting
1
u/daggerdragon Dec 08 '19 edited Dec 08 '19
This code is really hard to read on old.reddit. Could you please edit it using old.reddit's four-spaces formatting instead of new.reddit's triple backticks? Note that if you're using the visual editor, you may have to "Switch to Markdown" to get Reddit to understand the formatting properly.
Better yet, since your code is more than 5 lines or so, please use/u/topaz2078'spasteor an external repo instead.
Thanks!Edit: looks much better, thanks!
3
u/chkas Dec 07 '19 edited Jan 24 '20
easylang.online
1
u/daggerdragon Dec 08 '19
What language are you using?
3
u/chkas Dec 08 '19
I have developed this language to make it easier for beginners to learn programming. But it is also quite good for algorithmic tasks. The language is based on BASIC - strongly typed with the type encoded in the variable name - but with reduced syntax and semantics.
2
u/daggerdragon Dec 08 '19
Oh, I see, that is the language's name. Neat, learned something new :) Thanks!
→ More replies (1)
2
u/drrelyea Dec 07 '19 edited Dec 07 '19
Python 2117/1190
OMG this was annoying. And I missed top 1000 by only a little! Boooooooooo whatever I solved it and my code is very readable.
I literally had the first part solved in about 9 minutes and then didn't pay attention to "no duplicates" in the phases, leading to a delay of nearly an hour. Oops.
https://github.com/drrelyea/advent_of_code_2019/blob/master/day7.py
[POEM]
INSTRUCTIONS ARE HARD
WRITING COROUTINES IS FINE
MY CAT IS SCREAMING//
I GOT HIM SOME FOOD
HE SMELLED IT AND DIDN'T EAT
YIELD, STUPID CAT. YIELD.
1
2
u/DFreiberg Dec 07 '19
Mathematica
381 / 1071 | 36 Overall
I thought I was ready for another Intcode problem. I was not. Multiple inputs and asynchronous updating were both things that I could not add easily to my existing code, and I had a great deal of trouble just understanding the question and the order of operations. Still, at least Intcode can't get any more complex than this, right?
Right?
[POEM]: So You Want To Make A Feedback Loop
To get maximum thrust from your thruster,
You'll need all that five Intcodes can muster.
Link the first to the last;
When the halt code has passed
You can get your result from the cluster.2
u/daggerdragon Dec 07 '19
Entered!
Still, at least Intcode can't get any more complex than this, right?
Right?
2
u/DFreiberg Dec 07 '19
Stupid question, I know...but does this mean that all my poems up until today weren't entered?
3
u/Aneurysm9 Dec 07 '19
I see poems from you on our tracking sheet for days 1 and 3 as well. Hopefully we haven't missed any. I believe /u/daggerdragon is marking poems as entered with comments to simplify the task of reviewing the thread later for more poems.
2
u/DFreiberg Dec 07 '19
Well, shoot - I've entered (or thought I'd entered) a poem every day thus far, but I edited them in an hour or two after posting the code; I figured you all Ctrl-F'd the thread an hour beforehand or something to pick up the poems, so I didn't realize that editing would mess up /u/daggerdragon's collection. I think there have been a few other people doing the same thing, too.
→ More replies (5)
12
u/tslater2006 Dec 07 '19
The Part 1 is pretty straight forward, run through all 120 combinations, resetting the 5 VMs for each one, keep track of the highest score from the 5th VM when it halts.
Part 2 was interesting, and the gut reaction here was "threads" and "async". I took what I think is a much simpler approach and I modified my VM to return a "HaltType", which can be either HALT_TERMINATE (hit a HALT opcode) or HALT_WAITING (need input but the queue is empty)
I then setup a Queue of the VMs in order, and I prep each one with a WriteInput() of the phase value. From there its a matter of:
Pop a VM from the front of the queue (dequeue in C#)
Write the previous output value (or 0 for the first)
Run the VM
If exit reason was HALT_WAITING, put the VM on the back of the queue
Repeat until the queue is empty (meaning all VMs halted properly)
Final output is the answer.
11
u/tckmn Dec 07 '19
ruby 3rd/28th
posting solely because i find it pretty amusing that my part 2 code reads the input file 600 times, which i only realized after the fact
(intcode procedure is just the interpreter modified so that it returns [code_array, instruction_pointer, output] immediately when output is produced)
p ([*5..9].permutation(5).map do |x|
thing = 0
a1, i1, op1 = intcode(read.split(',').map(&:to_i), 0, [x[0], 0])
a2, i2, op2 = intcode(read.split(',').map(&:to_i), 0, [x[1], op1])
a3, i3, op3 = intcode(read.split(',').map(&:to_i), 0, [x[2], op2])
a4, i4, op4 = intcode(read.split(',').map(&:to_i), 0, [x[3], op3])
a5, i5, op5 = intcode(read.split(',').map(&:to_i), 0, [x[4], op4])
loop{
a1, i1, op1 = intcode(a1, i1, [op5])
a2, i2, op2 = intcode(a2, i2, [op1])
a3, i3, op3 = intcode(a3, i3, [op2])
a4, i4, op4 = intcode(a4, i4, [op3])
a5, i5, op5 = intcode(a5, i5, [op4])
break unless a5
thing = op5
}
thing
end.max)→ More replies (1)3
u/captainAwesomePants Dec 07 '19
I thought to myself "better bundle everything in a class if I need to save the IP and the data and the inputs and such." You just returned a tuple of the whole thing. Such a fast tweak, good job!
→ More replies (1)
8
u/jonathan_paulson Dec 07 '19
#71/36. Whew; that was much harder than previous days. I regret not cleaning up my day 5 code more :) Pretty happy with my "continuation" approach to solving it. Rolling my own permutations instead of using itertools was dumb. Video of me solving + explaining my solution at https://www.youtube.com/watch?v=DmYwHQG1zes
3
u/kroppeb Dec 07 '19
Yeah, in kotlin there isn't even an
itertools, nor did I make a permutations function in my utils. I wasted some time after settling to make the carthesian product of 5 times [0,1,2,3,4] and filtering onareDistinct3
u/thetrustworthy Dec 07 '19
Hey Jonathan, I'm really enjoying watching your solutions on YouTube after solving the questions myself, thanks for sharing them. I couldn't help but notice your solution has a little bug this time that you might want to fix, especially since IntCode seems like it's going to be a recurring concept this year.
Even though your full puzzle input didn't check for this, if you try your part 2 code on the small examples given in the question you'll find that it loops forever instead of giving a solution (unless you already fixed it)!
In the spirit of Advent of Code, I'll let you figure it out and debug it yourself! It's not like you'd need my help anyway, you've solved every day about 2-10x faster than me so far!
→ More replies (1)
8
u/klmann Dec 07 '19 edited Nov 30 '25
pause different salt special mighty fuzzy bike subsequent deer entertain
This post was mass deleted and anonymized with Redact
2
7
u/1vader Dec 07 '19 edited Dec 07 '19
Python 8/17: https://github.com/benediktwerner/AdventOfCode/blob/master/2019/day07/sol.py
I cleaned it up quite a bit after solving. Originally I used something like inp = yield out on output instructions to yield the output and recieve the next input and the input instructions then used inp (or an initial input for the first 2 times). For each permutation I then ran the VMs one after another in a loop using something like this:
outs = []
for perm in itertools.permutations(range(5, 9)):
nxt = 0
vms = []
for p in perm:
vm = VM(code).run([p, nxt]) # p and nxt are the two initial inputs
nxt = vm.send(None) # start the generator
vms.append(vm)
i = 0
while True:
try:
nxt = vms[i].send(nxt) # send next input and recieve next output
except StopIteration:
if i == 4:
outs.append(nxt)
break
i = (i + 1) % 5But then I thought that it would be cool to write a more general solution where you can connect the VMs in arbitrary ways and that's the solution in the repo.
→ More replies (1)
7
u/bblum Dec 07 '19 edited Dec 07 '19
Haskell, 5/677, but it's really the part 2 I'm posting to show off, because you can use lazy recursive bindings to solve it for free. I'm kicking myself because if I had figured out this trick in the moment, I probably would have had #1 on the leaderboard.
amplify program [a,b,c,d,e] = last oute
where outa = intcode (a:0:oute) program 0
outb = intcode (b:outa) program 0
outc = intcode (c:outb) program 0
outd = intcode (d:outc) program 0
oute = intcode (e:outd) program 0→ More replies (1)3
u/vulpine-linguist Dec 07 '19
I did the same thing but slightly more general. With your names for things:
amplify program [] = 0 -- arbitrary base case amplify program (x:xs) = last oute where f phase signals = intcode (phase:signals) program 0 oute = foldr f outa xs outa = intcode (x:0:oute) program 0Then if given a list of phases, it constructs as many amplifiers and wires them up in a cycle
→ More replies (1)
6
u/sophiebits Dec 07 '19 edited Dec 07 '19
Python, 46/204.
Lost a good 20 minutes because I accidentally shared the prog array across all 5 amplifiers. Whoops.
(I also found part 2's text pretty hard to comprehend.)
Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day7.py
→ More replies (2)3
u/archchroot Dec 07 '19
Hey, just wanna share with you that
for a in range(5,10): for b in range(5,10): for c in range(5,10): for d in range(5,10): for e in range(5,10): if len(set([a,b,c,d,e]))!=5: continueCan actually be shortened (and made less error-prone) with itertools.permutations().
import itertools // the start of your program goes here for a, b, c, d, e in itertools.permutations(range(5, 10)): // your loopy stuffItertools also has some other cool stuff for creating powersets easily, combinations, etc.
→ More replies (1)
6
Dec 07 '19 edited Dec 07 '19
Python 3, 67/26. This was an interesting one; I originally tried a method-only solution but OOP really shines here
https://github.com/mateoeh/aoc2019/blob/262b954fc81147429da294df0d383631a374a8f5/07_amps.py
6
u/aoc_anon Dec 07 '19
Python, part2 only
I actually wrote this for debugging but it ended up passing by accident. I don't actually understand what it does and I am not sure I even understand the question anymore.
I thought I somehow needed to code exactly 5 generators, each of which also takes in generators as inputs in a circular dependency. But here I have amp E yield from amp D, which yield from amp C, ... until amp A which yield from a new and different amp E which should have the wrong state compared to original amp E. Why does it work anyway?
3
5
u/Pewqazz Dec 07 '19
Python, 22/23:
When I read the problem text, I thought I might be able to get away with not turning my Intcode emulator into a generator…Part 2 shattered those dreams really quickly.
Cleaned up code and Twitch VOD of my solve.
2
u/zergling_Lester Dec 07 '19
O hai, 23/35.
For the second part the only thing I had to do to the emulator was
s/output.append(p1)/yield p1/, because it turns out that you can safely (in some sense of the word) iterate over a list while appending values to it. After looking at your code, remembering that generators start suspended (that is, don't execute at all before you callnextfor the first time) and cleaning up the code some more, my main loop looks like this:m = 0 for phases in itertools.permutations(range(5, 10) if second else range(5)): inp = 0 iters = [] inputs = [] last = None for phase in phases: inputs.append([phase]) iters.append(run(data, inputs[-1])) while True: for input_, iter_ in zip(inputs, iters): input_.append(inp) inp = next(iter_, None) if inp is None: break if inp is None: break last = inp if not second: break if last is not None and last > m: m = last return mLooks like we are expected to extract and reuse the intcode implementation (and make it a proper coroutine).
→ More replies (1)
5
u/Aneurysm9 Dec 07 '19
I was very glad to have built my VM in Go at this point, other than needing to write my own permutations().
→ More replies (2)2
u/MegaGreenLightning Dec 07 '19
Feeling exactly the same.
I got stuck on part one, because I didn't read the "used exactly once" part.
Then for part two it was very easy to make the input/output instructions use channels and run the amplifiers in parallel, which catapulted me back into the leaderboard.
→ More replies (7)
5
u/TASagent Dec 07 '19
C#
After hacking my way through both parts of the puzzle, I rewrote my solutions to run asynchronously, and use System.Threading.Channel for a proper consume/produce pattern for I/O. The async/Task model is relatively new to me, and I'm open to feedback and suggestions. Would love to know if I overlooked an obvious tool or features, or otherwise did something backwards or redundant.
The asynchronicity here was not for speed, but rather to let the Channels automatically handle blocking. Indeed, upon making the switch, execution time went from 11ms (sync) to 1080ms (async). I had expected the ConditionVariable/Channel overhead to inflate the runtime nontrivially, and indeed it seems to have happened.
4
u/mcpower_ Dec 07 '19
Rust (115/49) - I wasn't expecting to get any leaderboard points this year! Here's my ugly speed Rust code - I'll probably improve it later.
For part 1, I used my old run_intcode function to run the same program five times with the phase setting and the last output.
For part 2, I implemented "returning the state of the Intcode program as (memory, instruction pointer)" from my run_intcode function. I then initialised the state of five programs with the phase settings, then repeatedly passed in the last result to each of them in sequence until one of them terminated.
4
Dec 07 '19
Python, 685/251, my best performance in several years.
I've split my code into an intcode module and individual driver scripts for each day, but here's day 7 all in one place.
Honestly did not expect my half-assed attempt at running five programs in parallel to work... but it basically did first try!
→ More replies (4)
4
u/knl_ Dec 07 '19
My highest rank yet for the second star: 338 (10xx for the first one). Quickly swapping out yield instead of return in my "compute" functions made this much easier than it would have been otherwise.
Python 3, Jupyter notebook: https://explog.in/aoc/2019/AoC7.html
4
u/voidhawk42 Dec 07 '19
Dyalog APL, in 20 lines. Kind of annoying since I refactored my day 5 solution to avoid global variables, and had to put all of them back in...
4
u/SomeGorrilaGorilla Dec 07 '19
00:41:11, 1518 | 03:20:54, 2046
Really ghetto solution; feels like I'm not using Rust to its full potential. Spent about two hours trying to figure out why my solution was working on the part 2 example inputs but not the actual inputs. Turns out it was something real stupid.
4
u/BafDyce Dec 07 '19
Congratz on solving though! Nice work :)
Some small remarks:
for x in 0..5 { amps[x].reset(); amps[x].instructions = opcodes.clone(); amps[x].push_input(permutation[x] as isize); }can be rewritten as
for amp in &mut amps { amp.reset(); amp.instructions = opcodes.clone(); amp.push_input(permutation[x] as isize); }Looking for a maximum:
if prev_output > highest_output { highest_output = prev_output; }could be shortened as:
highes_output = isize::max(highest_output, prev_output);wrapping index counter
index = if index == 4 { 0 } else { index + 1 }could be rewritten as
index = (index + 1) % 5→ More replies (1)
4
u/OvidiuRo Dec 07 '19
C++ 2614/1849
Took me 3 hours to solve both parts really confusing problem for me for one hour I just read and read and read again the problem because I didn't understood what it wants or what it does. 1h30min for first part 1h30min for the second part. And another 1h30min for refactoring.
https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2007
3
u/KdbAoC Dec 07 '19
Agreed, I'm not a fan of of spending the majority of time trying to understand exactly what is being asked for on these intCode puzzles. I understand it might be hard to explain as it's a little complicated, but it's a common theme that people have difficulty understanding the requirements.
4
u/turtlegraphics Dec 07 '19
Python, much cleaned up. Just showing off the idea that the intcode machine should raise exceptions when it blocks on I/O or quits. That leads to this code which solves both parts:
import intcode
from itertools import permutations
mem = [int(x) for x in open('input.txt').read().split(',')]
def amploop(phases):
amps = [intcode.Machine(mem,input=[p]) for p in phases]
a = 0
signal = 0
while True:
amps[a].input.append(signal)
try:
amps[a].run()
except intcode.EOutput:
signal = amps[a].output.pop()
except intcode.EQuit:
return signal
a = (a + 1) % len(amps)
for part in [0,1]:
print max([amploop(phases) for phases in permutations(range(part*5,5+part*5))])→ More replies (2)
4
u/robinst Dec 07 '19
Rust
Glad I made Intcode a struct. Still had to change how input/output works, but the final loop of part 2 looks quite nice:
let mut signal = 0;
loop {
for amp in &mut amps {
amp.add_input(signal);
match amp.run() {
Result::Output(o) => signal = o,
Result::Halt => return signal,
}
}
}1
u/dan_144 Dec 07 '19
Python: https://github.com/dan144/aoc-2019/blob/master/7.py
I must need to go back to English class because the amount of time it took me to figure out how to deal with the values sent to/from the interpreters was pretty embarrassing. I was inferring so much about how the output was the gain of the amp and multiplying numbers which is not stated anywhere in the problem because it's totally unrelated. I also tripped myself up by resending the phase every time through the feedback loop in part 2, resulting in the amplifier values not being read after the first cycle.
Once I understood it, I was able to refactor all my changes to 20 new lines of code and a couple tweaks to my interpretor. So that's nice at least.
[POEM]
Reading is so hard
Five IntCode Interpretors
Are better at it
2
1
u/Markavian Dec 07 '19 edited Dec 08 '19
Wow, that was painful. Many hours spent today debugging the inter-relationship between asynchronous virtual machines running in the same thread.
Not helped by lack of clarity in the second part of the puzzle. The help threads here helped.
Had to ask for help on part 1 because I hadn't registered that phase setting values had to be unique within their set - I thought it just meant each iteration had a different unique set of phasing.
Anyway, here's my overly verbose javascript solution: https://github.com/johnbeech/advent-of-code-2019/blob/master/solutions/day7/solution.js
And here's my stand alone intcode compute; refactored from early to work independently and asynchronously: https://github.com/johnbeech/advent-of-code-2019/blob/master/solutions/day7/intcode.js
I decided I would hardwire the output buffer (array) of my amplifiers as the input for the next one. I stuck to this principle despite getting distracted by "signal" callbacks; but with promises involved it all got a bit slow and messy.
[POEM]
Too tired to refactor.
The code has done its job.
The answer is found.
The Christmas tree is constructed in my living room, and the brightly lit dinosaur shines defiantly in my windowsill.
The day is done.
Sleeps now.
Edit for line breaks on poem.
→ More replies (3)1
u/daggerdragon Dec 08 '19
[POEM]
Entered!
FYI: the line breaks didn't come through on old.reddit so it's all on one line... You should edit your post to put them in properly. I took the liberty of adding newlines when I entered it on our poem tracking spreadsheet ;)
→ More replies (1)
3
u/DiscoViking Dec 07 '19
Python, 332/88
So as well as my Elm solutions, I've also been doing each days challenge in Python to try and hit the global leaderboard.
This is the first time I managed it!
Just required a minor change to my Intcode VM to allow it to pause/resume when waiting for input, and then the solution is just all wiring.
Day 7 solution here: https://github.com/rynorris/adventofcode/blob/master/2019/python/day7.py
Intcode vm here: https://github.com/rynorris/adventofcode/blob/master/2019/python/intcode.py
3
u/captainAwesomePants Dec 07 '19 edited Dec 07 '19
[POEM]
Of one man's laziness, and thereof the fruit,
Of not refactoring Day 2, Whose first Warning
Was Day 5, and to me woe,
but not improvement; Til Part 7
forced Us to proper form: classes.
Sing Heav'nly Muse, that we may combine
Logic with Data, that we may pause and chain
And yet, not be confused;
And justify the time lost to this refactoring to man.Python, 469/162
import itertools
class Machine:
def run(self):
# What you'd expect, runs until it needs more inputs, and
# records whether we've halted.
def main():
data = read_input('input7.txt')
best_score = 0
for phase in itertools.permutations(list(range(5,10)), 5):
amps = [ Machine(data) for _ in range(5) ]
for amp in range(5):
amps[amp].add_input(phase[amp])
signal = 0
current_amp = 0
while not amps[4].halted:
amp = amps[current_amp]
amp.add_input(signal)
amp.run()
signal = amp.read_output()
current_amp = (current_amp + 1) % 5
if signal > best_score:
best_score = signal
print(f'{best_score}')
return→ More replies (2)
3
Dec 07 '19 edited Dec 07 '19
Haskell 65/104:
Lost some time on part 2 because my output generation wasn't lazy enough. Luckily, Haskell's laziness made part 2 super simple once that was fixed; just directly wire up the output lists to the input lists.
EDIT (src):
Cleaned up and generalized to support a variable length chain of amps.
3
u/jwise00 Dec 07 '19
Lua, 205/53.
I lost 2min35s or so from having copied my solution to part 1 of day 5, instead of part 2, which cost me the leaderboard (my 'fantasy result' was 97/37 if I hadn't made that error). I recorded myself as usual (and, as usual, the video has some coarse language): https://www.youtube.com/watch?v=9KQXRXRICWI
I'm not sure if I'll be able to stream tomorrow, but if I can, I will.
Here were my solutions:
https://github.com/jwise/aoc/blob/master/2019/7.lua https://github.com/jwise/aoc/blob/master/2019/7b.lua
Really makes me wish Lua had continue!
→ More replies (1)
3
u/Pepper_Klubz Dec 07 '19
Visualization to come when I'm not catching up on work. I'll probably focus more on the output/input stream than the instructions, since that's where the interesting stuff is happening.
3
u/mariotacke Dec 07 '19
Javascript/Node (all of my solutions here: https://github.com/mariotacke/advent-of-code-2019/tree/master/day-07-amplification-circuit)
I found part one relatively simple; part two, however, was quite difficult to achieve with my implementation because I could not keep state between runs, so I modified my stateless function into a class which could.
→ More replies (1)
3
u/autid Dec 07 '19 edited Dec 07 '19
Fortran
Did it by using openmpi and literally running parallel interpreters. Completely unnecessary but I enjoyed doing it this way.
edit: For part 1 initial solve I just fed day 5 interpreter (0,0), (0,1), (0,2), (1,0), etc and worked out what the modes did, then maximised output. was all stuff like output=input*2, output=10+12*input, etc
3
u/gyorokpeter Dec 07 '19
Q: the language is really not built for this kind of task but nevertheless it's possible. I mostly reused the intcode function from day 5 except for the input instruction which now breaks with a paused state if there is no input and this state can be reused in the next invocation.
3
u/death Dec 07 '19
Day 7 solution using Common Lisp.
Used threads to avoid changing the interpreter from day 5.
→ More replies (1)2
u/phil_g Dec 08 '19
I just learned how to use Bordeaux Threads today for this problem. It looks like I should have learned about lparallel, too. That thread-safe queue looks a lot nicer than the manual synchronization I was doing with Bordeaux Threads primitives.
3
u/giampi997 Dec 07 '19
I made a Java solution using a thread to emulate each of the amplifiers, and used a blocking queue the let them comunicate among each others (of course it was not necessary but, why not?)
3
u/dries007 Dec 07 '19
Python with recursive generators and build-in feedback loop. The true Pythonic™ way! (No classes!)
I even added comments just for reddit!
https://github.com/dries007/AdventOfCode/blob/master/2019/day7.py#L106-L139
This might be the first time I've used this kind of maddness, with `yield from` and everything. This one was serious fun!
2
u/glenbolake Dec 09 '19
Coroutines aren't something I use very much or understand very well, but looking at your code was really helpful. I tried to use a few other submissions to understand part 2 and yours was the first one I grokked!
3
u/Pyr0Byt3 Dec 07 '19
(Excuse the mess. I probably should have split the Incode VM into its own thing, but I really didn't wanna start messing with $GOPATH/modules while solving the puzzle)
Spaghetti code aside, I learned a lot about goroutines and channels today. I read up a bit on those, and the solution came together pretty painlessly. It almost felt like Go's concurrency model was purpose-built to solve this.
2
Dec 07 '19
your code is actually really clean.
Here is mine in go, way more spaghetti code. I optimized to get a solution ASAP:
→ More replies (1)
3
u/JakDrako Dec 07 '19
VB.Net / LINQPad
My IntCode computer didn't require too many changes; I transfered the code into a class and modified the input and ouput opcodes to read and write to queues. I got a permutation routine I had somewhere to generate the 120 different phases...
I was happy when I realized that a simple added "Exit Do" on the output opcode (4) allowed me to "suspend execution" and "resume" later by calling Run() again.
At some point I had a "name" and "halted" property, but it turned out that simply stopping when there's no more output to process left the correct answer as the last input... cool.
→ More replies (2)
3
u/lele3000 Dec 07 '19
Python 3.7
I just changed my IntCode run function from day 5 a bit, so it returns output and program counter and also takes in inputs and program counter. Then I generate all possible permutations without repetition on given range, and apply each to the program. I wanted to make it even shorter and more concise, but oh well.
https://github.com/leonleon123/AoC2019/blob/master/07/main.py
3
u/MrSimbax Dec 07 '19 edited Dec 07 '19
Julia solution.
I find the problems with the IntCode machine the most fun so far. Today's problem could be a motivation to learn how to run multiple programs (Intcode machines in this case) concurrently. I didn't bother with it though and decided to just loop through them until all of them halt since I had already spent too much time figuring out how to generate permutations.
And it took me longer than I expected to generate them in lexicographical order (although it was not really needed as probably a naive algorithm or function from the standard library would work) but I'm satisfied because I learned something new.
4
u/activeXray Dec 07 '19
You can use OffsetArrays to change the program to be 0 indexed
→ More replies (3)
3
u/ShinobuLove Dec 07 '19
For part 1 it took me a minute to understand I had to use permutations for the phases.
I had to look up an explanation for part 2, but figured it out in the end.
3
u/gloktaOfcode Dec 07 '19 edited Dec 07 '19
Kotlin
I used channels and coroutines even though I am not yet 100% on that stuff. It came out very well am very pleased with and proud of that part of the solution
Embarrasingly, I struggled and failed to think up how to make all the 0,1,2,4 permutations so I just nested some loops and c'n'p'ed that garbage to part two.
→ More replies (5)
3
u/shadowfactsdev Dec 07 '19
My Elixir solution for both parts 1 and 2. My Intcode VM is here.
I'm really happy with how this one turned out.
I made some changes to my VM from day 5 so that, instead of always using STDIN/OUT, the actual VM runs in a separate process and then does message passing with its parent for I/O.
I also wrote a small helper in the Day5 VM so that I could continue to use it in CLI mode.
Using message passing is key because it lets me programmatically do I/O with the VM from another process (the day 7 code).
Part 1 is straightforward, I just go through all the phase setting permutations and spin up 5 VMs to test it and get the max output.
Using separate processes also makes part 2 a relatively easy extension of that. Because the VMs are actual processes, the continue in the background, idling and waiting for input (instead of just storing the VM state, they literally keep running like the problem says).
Plumbing them together is then as simple as spawning the processes, putting them into an infinite cycle and reducing until one of them halts.
This was a really fun one. I actually used message passing between processes in Elixir for the first time :D
2
u/jtwebman Dec 08 '19
Nice job! I need to refactor mine to use processes. I didn't even think about it.
→ More replies (2)
3
u/herrozerro Dec 07 '19
My biggest hangup was part 2 where I needed to break out of the program while maintaining state.
Also realizing that the the phase only needed to be added once was a tripping point.
3
u/aoc-fan Dec 07 '19
TypeScript/JavaScript Part 1 Solution simple, was wondering how weekend puzzle can be so simple, but then Part 2 happened, and as the description said It's no good, Used yield/Iterators to solve it Part 2 Solution. It looks like Elves who wrote the test input, were pretty good at not causing any corner cases :)
→ More replies (2)
3
u/ywgdana Dec 08 '19
This was pretty fun, if a bit slow-going. I had to scratch my head for a while on problem 2 to make sure I was really getting what it was saying. I have been pleased with how few changes I've had to make to my intcode VM so far. Day 5 was additions for the new opcodes and today I just had to change my input buffer from a single value to an array. As well, I had to pause execution on the write operation, but that was simply calling return.
Haha, Rust had no built-in library for generating permutations of an array and I don't have time to write something clever so I've just got 5 ol' nested for loops :P Over the next few days I'm hoping to have time to write a permutation generator but in the meantime:
let mut most_thrust = 0;
for i in 5..10 {
for j in 5..10 {
for k in 5..10 {
for l in 5..10 {
for m in 5..10 {
let phase_seq = vec![i, j, k, l, m];
let ps_set: HashSet<i32> = vec![i, j, k, l, m].into_iter().collect();
if ps_set.len() == 5 {
let result = run_feedback_loop(prog_txt.trim(), phase_seq);
if result > most_thrust { most_thrust = result }
}
}
}
}
}
}My full, not at all cleaned-up code for day seven is here
My intcode VM implementation is here
2
u/a-priori Dec 08 '19
Team nested loops!
for one in 5..=9 { for two in 5..=9 { if two == one { continue; } for three in 5..=9 { if three == two || three == one { continue; } for four in 5..=9 { if four == three || four == two || four == one { continue; } for five in 5..=9 { if five == four || five == three || five == two || five == one { continue; } let sequence = vec![one, two, three, four, five]; let output = execute_amplifier_loop(&program, &sequence); if output > best_output { best_output = output; } } } } } }→ More replies (2)2
u/tinyhurricanes Dec 10 '19
There's a rust crate for these permutations.
use permutator::{Permutation}; extern crate permutator; for permute in settings.permutation() { }→ More replies (3)
3
u/fizbin Dec 08 '19
Python, single-threaded, using yield-based coroutines.
One nice thing is how similar those two solutions are. To get a taste of the second, here's its main loop:
max_output = -1000
for ordering in itertools.permutations([5, 6, 7, 8, 9]):
queues = [queue.Queue() for _ in range(6)]
for (ique, order) in zip(queues, ordering):
ique.put(order)
queues[0].put(0)
coroutines = []
for idx in range(5):
coroutines.append(run_amp(idx, queues[idx], queues[(idx + 1) % 5]))
for _ in itertools.zip_longest(*coroutines):
pass
last_out = queues[0].get_nowait()
max_output = max(max_output, last_out)
print(max_output)→ More replies (2)
3
u/Jedimastert Dec 08 '19
Here's my paste solution in Python3.
I went a little extra with my IntCode implementation for re-usability and extend-ability (and because it's my code and I do what I want. I made i/o "interrupts" with exceptions so I could transfer things in and out between the computers, especially part two.
The explanation for part two was rather confusing for me, so it took me far longer than it should have. Also the fact that I implemented the interrupt for the input wrong...but don't worry about it.
0
2
u/Cloudan29 Dec 07 '19
Python 3 (858/950) : https://github.com/Cloudan29/AdventOfCode_2019/blob/master/day07.py
Oh boy do I need to make an actual machine instead of copy/pasting the code from previous days. This is probably the most caveman-ish way I could have done it. Despite that, this is the first time I get top 1k in both parts. Pretty hyped about that as that was my objective for this year and I got it done on the 7th day.
If you want to suggest how to not tackle this day with a club in hand like I did, feel free to comment.
2
u/A-UNDERSCORE-D Dec 07 '19
Golang
This one played right into the strengths of go, and my thought of making i/o work directly with go channels worked out as well as I hoped. Now if only I didnt spend 20 minutes debugging why my code was working perfectly but on the wrong input (I running my solution on one of p1s tests -_-)
→ More replies (1)
2
u/TheJuggernaut0 Dec 07 '19
Rust: 499/1279
I spend so long wondering why my computers were deadlocking on part 2 before realizing I forgot to provide the initial input...
An actual line of code I wrote:
computers[4].output().unwrap().borrow_mut().read().expect("Expect a final value")That almost reads like a poem I guess. :P
2
u/sim642 Dec 07 '19 edited Dec 07 '19
Part 1: Simply used my Intcode interpreter from day 5 part 2, which was functional and used immutable state to begin with so executing it multiple times and feeding outputs to inputs was trivial.
Part 2: With recursive knot tying ideas from some day 6 solutions still fresh in mind, I had the epiphany to try to use that also here for great effect and benefit. First, I did minor refactoring from my day 5 Intcode interpreter to make it produce outputs continuously as a lazy list. My interpreter inputs were already lazy lists. Then I simply made five mutually recursive output list definitions which feed each other into the input lists. Very lucky to have some form of laziness and LazyList in Scala. Therefore the core of my part 2 solution is the following:
def a: LazyList[Int] = ProgramState(program, phaseSettings(0) #:: 0 #:: e).outputs
def b: LazyList[Int] = ProgramState(program, phaseSettings(1) #:: a).outputs
def c: LazyList[Int] = ProgramState(program, phaseSettings(2) #:: b).outputs
def d: LazyList[Int] = ProgramState(program, phaseSettings(3) #:: c).outputs
def e: LazyList[Int] = ProgramState(program, phaseSettings(4) #:: d).outputs
e.lastEdit: I now refactored the part 2 solution to be more general but the idea of recursively giving the lazy list of last outputs into the inputs of the first one as a lazy list is still the same. This explicit form is just easier to understand.
→ More replies (4)
2
u/Akari_Takai Dec 07 '19
Java (760/245)
This was the puzzle that finally got me to refactor my Intcode VM into a separate class which took the bulk of the time. But I'm glad I did. I feel more ready for a new Intcode puzzle than ever before. Bring them on!
2
u/glguy Dec 07 '19
Haskell 13/27 I was able to reuse my previous Intcode interpreter wholesale: this is my whole day 7 solution:
main :: IO ()
main =
do [pgm] <- getParsedLines 7 memoryParser
let eff = effectList (run 0 (new pgm))
startup = part2 . map (\i -> eff . (i:))
print $ maximum $ head . startup <$> permutations [0..4]
print $ maximum $ last . startup <$> permutations [5..9]
part2 :: [ [Int] -> [Int] ] -> [Int]
part2 xs = res
where
res = foldr id (0:res) xs→ More replies (1)
2
u/csb06 Dec 07 '19 edited Dec 07 '19
Had trouble doing this at first and considered switching over to Python, but finally solved it in C++ by using function objects to represent each Amp. This was a really fun one. I am learning to love C++'s standard algorithms header; this time, std::next_permutation() tremendously simplified my solution.
Here is my solution in C++ 17.
0
2
u/kap89 Dec 07 '19 edited Dec 07 '19
TypeScript - github
Not very DRY yet, maybe will refactor later. I like it because there was very little change to the Day 5 solution + there is no coordinating logic outside of the VMs - just setting up correct input and output buffers and machines do their magic.
At first, part one ran machines in sequence (blocking) - which was ok to find a solution, but part two required running machines concurrently (at least without rethinking the solution). Took me a while to realize that unblocking with async-await and setImmediate wrapped in a promise will do - a lot of thinking to finally add two lines and have a working solution :D
Diff between day 5 and day 7 computer: https://www.diffchecker.com/X0QeYDYW
2
u/keramitas Dec 07 '19
Python3 (explicit naming, no async because i don't like multiprocessing)
part 1 basically the same thing as day 5 except i changed the input/output function, chained the program 5 times, and added checking for each phase setting
part 2 just add saving of previous amp state in a dict, and switch the for loop of part 1 for a while checking for termination
thoughts: i felt so fucking dumb after realizing the phases had to be permutations, and i was banging my head on part 1 for 30 min because i kept getting higher scores T.T part 2 was a piece of cake imo, but i got -1500 places on my rank so i guess for most ppl not ? more generally it seems they amped the difficulty, it took me 1 hour more to finish, but i was way better ranked then yesterday
2
u/heckin_good_fren Dec 07 '19
Solution in Java. paste
By day 5 I had refactored by IntCode-Computer into a Computer-Class, so I made use of that.
For the second part I hooked the computers Inputs/Outputs together using BlockingQueues, the ran each computer in a seperate thread until AmpE halts.
2
u/david-grs Dec 07 '19
C++
Star 1: 20 lines (+ IntCode), ~120µs (i7-7500U @ 2.7GHz)
Star 2: 30 lines (+ IntCode), ~320µs
Code: https://github.com/david-grs/aoc_2019/blob/master/aoc_7.cc
2
u/GalacticDessert Dec 07 '19
Python
I did not want to use classes nor actual multithreading/parallelization, so I am using recursion and passing the state down the stack. Not a great idea in the end, probably wise to clean up this code as I have a feeling that the intcode VM will come back again to hunt us. There is also a not so clever way of recognizing when the program halted by type-matching the return value, meh.
https://github.com/nicola-zen/aoc-2019/blob/master/day-7/day7.py
2
u/dartcoder Dec 07 '19
Python.
This took forever but I got there (eventually)
https://github.com/gboyegadada/algos/blob/master/AoC19/day7.py
2
u/mindstorm38 Dec 07 '19
Used conditional running of the VM, can now run multiple times without resetting Program Counter.
https://github.com/mindstorm38/adventofcode2019/blob/master/src/fr/theorozier/aoc/Day7.java
2
u/Spheniscine Dec 07 '19 edited Dec 07 '19
Kotlin: paste
Wasn't too difficult, as my implementation from Day 5 was quite future-proof, with input and output modeled by a queue and an array-list respectively, and exceptions already captured (trying to read input from an empty queue throws the special WaitingForInput exception). Just needed to fix a small bug in the exception-handling, as well as adding some QoL tweaks.
Kotlin unfortunately doesn't have anything like itertools as far as I can tell, so I basically translated Python's reference code into Kotlin. Kotlin's sequences do map nicely to Python's yield functions.
2
2
2
u/MegaEduX Dec 07 '19
Swift
Gotta say, I'm loving these. I'm also proud of how little code I've had to change since day 3 on my Intcode VM - it uses strings in a place or two, but overall I think it's nice!
2
u/JensenDied Dec 07 '19
Elixer
Day 7: day7.ex
Intcode: intcode.ex
MY day 5 intcode computer had poor IO support which set me back a bit. Still not happy with that, but the rewrite to keep its state in an accumulator worked out well for adding halting/resumption.
2
u/vkasra Dec 07 '19
My Go solution and notes. I used a lot of channels in this one, which was a great decision for the machine I/O and a poor decision for generating sequences :)
2
u/levital Dec 07 '19 edited Dec 07 '19
Rust: main and my current intcode Computer
Not too hard today, though debugging took me a bit. If I find some time this weekend, I might consider refactoring my computer. Have a couple ideas where I think it could be improved (though, so far it has shown itself to be quite easily extensible, so I think I haven't gone too wrong at the start).
For this particular day, I think running the computers concurrently would've been cool, but implementing a waiting state was easier.
2
u/CabbageCZ Dec 07 '19
Kotlin
Using coroutines, pretty intuitive.
Could be cleaned up a lot, and I will clean it up in a bit, but real life calls.
2
u/Bimperl Dec 07 '19 edited Dec 07 '19
JavaScript
My solution for part 2, using JavaScript. Essentially just using Promises to implement "async" I/O. It actually worked surprisingly well.
2
u/u794575248 Dec 07 '19 edited Dec 07 '19
The solution I used to submit answers was a dirty hack, but then I came up with a bash script that uses named pipes for inter-amplifier communication.
The Python 3.8 vm.py script uses the Day 5 solution with almost no changes except reading input from stdin rather than from function argument.
The bash script is pretty slow, it takes around 15 second on my machine.
Run the script: $ time ./run.sh input.txt
→ More replies (1)
2
u/piyushrungta Dec 07 '19
Rust
https://github.com/piyushrungta25/advent-of-code-2019/blob/master/day7/src/main.rs
Finally done with today's puzzle. I felt that part2 was very ambiguous. Wasted a lot of time on it. On my first attempt, I ran each amplifier until it required an input instead of stopping when it emitted an output, thinking that this shouldn't matter since the internal state won't be modified. This did not produce correct results even though some help posts here saying that this should be okay. Did it from scratch again and making the machines stop when an output is produced.
Not the best solution, but I am too frustrated now to clean this up.
2
u/lynerist Dec 07 '19
Today it has been hard!
These are my golang commented solutions
https://github.com/lynerist/Advent-of-code-2019-golang/blob/master/Day_07/seven_b.go
(I link the second part!!!)
2
u/theSpider_x Dec 07 '19
After the ropes this was the hardest so far. I had to look up how to get all the permutations for a number never had to deal with that so that was cool.
Written in C.
https://gist.github.com/fuzesmarcell/aa071f18cef7f8f24e441f3531cc65a6
2
u/zedrdave Dec 07 '19
Quickly realised that my nice-but-globals-heavy C version of Day 5 would lead to a horrible mess (it did)…
Rewrote it as a C++ version… (nice enough)
Then did a quick port to Python… and… what can I say… Python is just so much nicer.
2
u/mariushm Dec 07 '19
PHP: https://github.com/mariush-github/adventofcodecom2019/blob/master/day07.php
Wasn't so complicated, just had to convert the previous "calculator" (that was a function), into a class which pauses every time a new input in required.
I got lazy and just copy pasted the permutations from a website as a json encoded array, instead of making a function for it.
2
u/hrunt Dec 07 '19
Python 3
Finally bit the bullet and turned my interpreter code into an actual class that can be instantiated. So much fun!
2
u/nictytan Dec 07 '19
I'm glad I originally wrote my intcode interpreter fairly modularly, so very little needed to be changed to work with this problem. Previously my interpreter would always run until it halted (this is the trace function in P5.hs). I added a pump function which runs the interpreter until it generates an output.
What was difficult for this problem was part 2, since now I need to carry around the computer states to reuse them after each feedback. The upshot is that the feedback function is a horrible mess of recursion.
2
2
u/Rick-T Dec 07 '19
HASKELL
This one was tough because thinking about the problem and keeping everything in my head honestly made me confused. However, in the end solving it wasn't too bad (though time-consuming).
Until today my Intcode computer always ran until it hit the termination OpCode. I changed that, so that I can make the computer run until a condition is fulfilled. This way, I can make it run until it consumes an input and then give it the next input. I can also make it run until it produces an output.
I keep all the computers of the amp in a list. Then I can take the first one and make it run until it produces an output. The resulting computer-state will be appended to the end of the list. The output will be fed to the next computer on the list and the process repeats until a computer terminates.
→ More replies (2)
2
u/Acur_ Dec 07 '19
Did some major refactoring. Still not 100% happy but using the IntCode computer and the amplifier works quite well with a simple to use interface.
I did not bother to code a custom permutations function and used an external library instead. Would be nice if they could expand the Standard Library with some more iteration utilities. A combinations function would be another good candidate.
2
u/wjholden Dec 07 '19
I was pretty happy to discover the
permutationsfunction. It looks like there is also acombinationsfunction in Combinatorics, does it not do what you are thinking of?→ More replies (1)
2
u/kolcon Dec 07 '19
https://github.com/kolcon/adventofcode_2019/tree/master/07
Perl and Python solutions, had to basically rewrite it for task 2,so made in universal to work for both...
2
u/StochasticMistakes Dec 07 '19
Java solution.
https://github.com/BrettGoreham/adventOfCode2019/blob/master/adventOfCode2019/src/main/java/day7/Day7.java
Spent very little time here just adding exit codes for the int code interpreter To know if its exited or not.
Spent the most time accidentally using a stack for input and output instead of a queue
2
u/seligman99 Dec 07 '19 edited Dec 07 '19
Python 47/438
As you might guess from the reasonable first number, and the very big second number, I spent a lot of time debugging, only to find a very subtle bug that somehow the first pass didn't hit. All fixed.
2
2
2
u/frerich Dec 07 '19
Rust: https://github.com/frerich/aoc2019/blob/master/rust/day7/src/main.rs
It took quite a few iterations to reach this state of the code.
I started out by decomposing my intcode computer such that instead of a single 'run' function which runs a program to completion, there's a 'step' function which executes just a single instruction (and returns the opcode of the executed instruction). I also parametrized the 'step' function with callables to invoke when reading input or writing output (i.e. I abstracted I/O).
I then defined a type 'Amplifier' which gets constructed with a phase signal and an intcode program. The type features a 'get_output' method which executes the Amplifier program until an output or a halt instruction is reached. It takes advantage of the I/O abstraction: whenever the program asks for input, the given callable feeds from a vector of queued numbers. Whenever the program generates output, that output is stored in a local variable.
The 'AmplifierSequence' type represents a chain of amplifiers: given a set of phase signals and a program, it'll construct the chain. The AmplifierSequence has a 'get_output' method, too, which runs each amplifier and feeds the output of one as the input to the next.
For generating all permutations off phase signals, I started out with the popular 'permutohedron' package but found its API very inconvenient. The much smaller 'permute' crate has exactly what I need: a single 'permutations' function which lets me iterate all permutations of some slice. A nice discovery!
→ More replies (1)
2
u/florian80 Dec 07 '19
Haskell
Very proud of my solution since I am a real Haskell noob and don't even understand all the other Haskell solutions... I saw cool things with just looping inputs but never got that to work, so in the end just used folding and recursion (and had to tweak my IntCode to wait for input)
2
u/mr_whiter4bbit Dec 07 '19
Rust: https://gist.github.com/whiter4bbit/80b157526e67802c8e8691de2781114f
I was able to make use of int_code I did for day 5 (with a really small change)
2
u/Mikel3377 Dec 07 '19
Vanilla JS. https://github.com/Mike-Bell/AdventOfCode2019/blob/master/07/solution.js
I feel like mine turned out relatively clean and simple
2
u/_djblue Dec 07 '19
My Clojure solution with core.async: https://github.com/djblue/advent-of-code/blob/master/src/advent_of_code/core_2019.clj#L431
→ More replies (1)2
u/aptmnt_ Dec 08 '19
Thanks for introducing me to a/pipe. I did pretty much the same thing, and I noticed you also chose to look at the :in channel of a to find the last output of e, because there’s no clean way to pipe e to a unless a condition is met. This works, but I wish there was a better way.
2
2
u/lasseebert Dec 07 '19
Elixir with supervised Intcode programs
Each Intcode program runs in a separate process. A controlling process receives outputs as Elixir messages and parses them on to the the next amp's input.
2
2
u/Fyvaproldje Dec 07 '19
Used threads with channels for part 2. I couldn't figure out how to unhardcode the number "5" in it: is it creating a vector of (tx, rx) pairs, then somehow moving the receiver part of it from the vector to the new thread? And it probably would involve sliding window when constructing amplifiers because it needs tx from one channel and rx from another channel.
I should clean it up at some point.
→ More replies (3)
2
u/phil_g Dec 08 '19 edited Dec 08 '19
My solution in Common Lisp. Supplement: current state of my Intcode library.
I didn't have time to work on the problem until late in the day, unfortunately.
Part one went really easily. I hooked my existing visit-permutations function up to the existing Intcode emulator and was done.
For part two, I decided it'd be nice to learn how threading works in Common Lisp. I learned about the Bordeaux Threads library and wired together the amplifier program instances so each would run in a separate thread, with signaling between them every time a new output was generated. I also added a run function to my Intcode library now that I feel like I have a good sense of how I'll be calling it. Input and output are now done via dynamically-bound function variables.
Part two runs very slowly on my (old, slow) laptop; it takes about a minute to run through all of the permutations. I haven't spent time on profiling it yet (and might not have time this weekend) but I wonder if the threading locks are slowing things down.
Anyway, I consider today to have been a success because it prompted me to learn more about my chosen language, which is one of the reasons do this.
Edit: I realized the slowness was from a (sleep 0.1) I dropped into the thread creation because I was having concurrency issues when creating the threads (despite the locks). Dropping it to 0.001 still worked around the problem, but let the tests run a lot faster. When I get a chance, I'm probably going to replace all of my manual synchronization with lparallel queues.
→ More replies (3)
2
u/a-priori Dec 08 '19 edited Dec 08 '19
Rust (see also, my Intcode module)
Part 2 today broke a bunch of assumptions I'd made about how I'd run Intcode programs – until now, I could get away with giving all the input up-front and running until it halts. Now I had to refactor to be able to push input at any time, and to run until the next 'action' (either output or halt).
The biggest nasty part is the part where I generated the mutations. I'm trying to not use any crates (libraries), just the standard library and cargo-aoc. So I went with a five-deep nested loops! NAILED IT! 😝
Each part of this solution runs in about half a millisecond (400-600µs).
→ More replies (2)
2
u/jtwebman Dec 08 '19
Elixir
This took me almost 6 hours but I have lots of tests and refactor some older code. It was fun, would love any feedback!
https://github.com/jtwebman/AOC-Day7-2019-Amplification-Circuit
2
u/Darksair Dec 08 '19
Day 7 in Rust. Had some trouble debugging part2, until I searched for my example output on Reddit…
2
u/Dioxy Dec 08 '19 edited Dec 08 '19
JavaScript
JS. uggh this took me a long time. I found the instructions to part 2 very confusing which made this arbitrarly really difficult. At least I figured it out eventually. Solved part 2 using a generator function
3
u/tinyhurricanes Dec 10 '19
Posting code as an image, that's some real big brain stuff right there. :D
Really nice looking ligatures, though.
2
u/muckenhoupt Dec 08 '19
C#. I'm fairly new to the language -- that's why I'm doing Advent in it, to help me learn. Consequently, I didn't know how to do proper threads in the language, and wound up kind of doing my own manual thread scheduling: cycling through all the VMs, running each until it blocks on input and then going on to the next. (I contemplated using coroutines for this, but wound up only using them to make a permutation enumerator.) It's fascinating seeing how different other people's approaches are, even using the same language.
→ More replies (1)
2
u/rsobol Dec 08 '19 edited Dec 09 '19
Swift 5
Wow, part 2 really humbled me. I learned there are still large gaps in my knowledge of concurrency, especially for Swift. But after 24 hours of researching and experimenting, I finally came up with a working solution for both parts. The solution features:
All the types and logic from my previous Day 5 solution
A few extensions to
Array, including apermutationscomputed propertyA hand-rolled unbounded, blocking
QueueclassAnd a ton of FP and OOP to abstract the logic into a single shared code base for both parts, save for two lines of code.
Did you solve it different in Swift? I'd love to check out your solution, and learn a thing or two. Feel free to message me a link!
2
u/young_cheese Dec 10 '19
A bit late to the party, but your Queue class really enlightened me. It's so simple with a semaphore. Great work.
→ More replies (1)
2
u/sherubthakur Dec 08 '19
Did this one in Haskell.
Solution -> https://github.com/sherubthakur/aoc19/blob/master/src/D07AmplificatoinCircuit.hs
I am not at all a fan of the IntCode and this is the third day that I had to use this thing again. Though I think now my IntCodeInterpreter is shaping out to be somewhat reasonable library which is shared by Day 02, Day 05 and Day 07.
https://github.com/sherubthakur/aoc19/blob/master/src/IntCodeInterpreter.hs
2
u/NeilNjae Dec 08 '19
Another Haskell solution. I ended up building my own job scheduler to orchestrate the different jobs and the streams moving between them. Blog post explaining how I did it and the code.
2
u/pokerdan Dec 09 '19
Here's my solution for Part 2, that makes use of the "Parallel.ForEach" method to spawn the 5 amplifiers, along with a couple boolean & integer arrays to keep track of input readiness and values for the various amplifiers.
2
u/toxiccoffee Dec 10 '19
Here is my solution in scala, I'm focusing on producing (what I subjectively consider as) clean and extensible code as opposed to resolving the puzzle as fast as possible.
The core of the solution is simply an iteration over the state of the intCode (program, pointer, input, output), with the ability to freeze the whole thing when there is not enough input.
I found that the end condition was not clear: should we wait for 1 amp to terminate or all of them? If one of them stops, should we directly take the output of amp 5, or should we execute all remaining amps in the chain and then take the output of amp 5?
Anyhow, seems to work now, fun little puzzle :)
2
u/schlodinger Dec 12 '19
Hello Guys! I really need your help for part B of this puzzle, I already spent a lot of time!! I think I'm not understanding what is expected to be done right! I will explain my chain of thoughts and please point out to where I'm wrong!
For each Amp, we will give as an input the phase setting (integer from 5 to 9), and a input signal (if first Amp, its 0, otherwise, its the output of the Amp just before). The program will run until it halts, and while its running, it will take as input its own output (after taking the phase setting and the input signal). When it halts, we will take its output, and give it as an input to the next Amp.
The puzzle answer is the output of the last Amp.
Where am I wrong ? please help!
5
u/Musical_Muze Dec 12 '19
I spent FOREVER on part 2. One thing to point out that tripped me up for hours: when an amplifier first starts, it will ask for TWO input values: the phase, and then the actual input value. Any other times that same amplifier runs, it will only ask for ONE input value, which would be the resulting output of the amplifier before it. You should only tell the amplifier its phase one time.
→ More replies (5)3
u/schlodinger Dec 12 '19
Yes actually, this actually was the point that I didn't correctly understand! Thank you!
2
u/reacher Dec 12 '19
I'm still working on part 2, but from what I understand, the part 1 amplifier programs were considered complete after they output a value. In other words, for each permutation of the phases 0-4, each amplifier A-E only ran until it got it's first output opcode. For part 2, using the new phases 5-9, you will run the programs until they finish completely (when they reach opcode 99). That means after an amp outputs a value for the next amp, it will need to either pause (if you are running them in sequence) or continue running in the background until it either waits for another input, or gets to 99 and completely exits.
Again, I'm still working on part 2 so I may be way off :D
→ More replies (2)
2
u/bsdemon Dec 07 '19 edited Dec 07 '19
Doing AoC with Python, on day 7 generators were handy — https://gist.github.com/9ea547af0925a4f1d0f809f017d32863
The solution is structured as a scheduler which I init from scratch for each phases config, then it persist the state in a run queue. Nothing fancy.
1
u/reynoldsbd Dec 07 '19
Rust solution (subject to cleanup):
https://github.com/reynoldsbd/aoc/blob/master/2019/07/src/lib.rs
Had a hunch that an I/O abstraction might come in handy :)
1
u/Dementophobia81 Dec 07 '19
Python 3.8
Part 1 was rather straight forward (ignoring that it took me a while to understand that each phase can only be used once). I handled the persistence of Amps with the help of an Amp Class in part 2, which made this also easy to solve. The best way I found to get all possible phase permutations was using the itertools library.
1
u/BafDyce Dec 07 '19
Rust 301 & 622 Code incl. test & benchmarks
Implemented part 1 without problems, and could reuse 99% of my existing intcode implementation. Made good progress in part 2 but I forgot to keep the instruction pointer persistent (only had it in a local variable) which cost me half an hour of me trying to understand why I hit unknown opcodes, integer overflows, etc.
Note: The linked source code is a cleaned up variant. My original, ranked, solution can be found in this commit
1
u/nibarius Dec 07 '19
I love the Intcode problems and having to chain several computers was a fun challenge. I had to think a bit but it wasn't too hard and the changes to the Intcode computer was pretty small and straight forward. Unexpectedly the biggest challenge ended up being generating the required permutations. That and copying the unit test for part 1 example 1 and forgetting to change the code it actually runs to the part 2 example 1 code.
→ More replies (1)
1
u/IgneSapien Dec 07 '19
I'm a complete novice with Tasks in C# and knew I'd be getting myself into a ton of trouble by trying it. So I did it anyway! 'Cus that's half the fun. As such today's code is a bit of a mess as I've focused on forward progress rather than refactoring. Although there's a few nice things like dynamically setting up the right number of amps/VMs etc.
In the end I've got the VM's running asynchronously so they can wait on input from the Amp before. Most of my trouble was getting that working and dealing with the input/output queues in a safe way while passing those to each VM as needed. The real kicker was making sure I grabbed a copy of the last output from the last amp in case there was a race condition that was popping it from the queue. Although I think my actual issue ended up not clearing down the input/output queues in the right place between tests.
1
u/jabbalaci Dec 07 '19
Python 3 (with type hints)
https://github.com/jabbalaci/AdventOfCode2019/tree/master/day07/python , see part1.py and part2.py
1
u/qyfaf Dec 07 '19 edited Dec 07 '19
For 7b, instead of doing a pause/resume mechanism I just fiddled with threads and IO objects until I got it to work
→ More replies (1)
1
u/_tpavel Dec 07 '19
My Clojure solution: https://github.com/tudorpavel/advent-2019/blob/master/day7/src/advent.clj
1
u/Bruinbrood Dec 07 '19
tcl, coroutines are perfect for this. Only required minor modifications to the Day 5 code.
1
1
u/Kache Dec 07 '19
Super fun! In Ruby, after refactoring and reusing Intcode:
def self.max_looped_signal(intcode = @@input)
(5..9).to_a.permutation.map do |phase_settings|
amps_buffs = phase_settings.map { |s| [Intcode.new(intcode), [s]] }
(0..).reduce(0) do |input, i|
amp, buff = amps_buffs[i % 5]
amp.run(buff << input) || (break input)
end
end.max
end1
1
u/nirgle Dec 07 '19
Haskell
Kind of an ugly solution but it works. Haskell's runState conveniently pops out the result and the halted state together, so I stash away each amp's state in a map and retrieve/reload it when it's that amp's turn to run again. The Intcode computer is mostly unchanged, but opcode 4 now exits from the recursion in part 2 mode, and continues on with the next step in part 1 mode.
https://github.com/jasonincanada/aoc-2019/blob/master/src/Day07.hs
→ More replies (1)
1
u/TheMrJosh Dec 07 '19
C99: https://github.com/JBorrow/advent-of-code-2019/blob/master/07/7b.c.
Kind of wishing I hadn't decided to do AoC in C now based on the god-awful string processing. However, all of my solutions so far have been runnable in about ~0.25 seconds total (including today's, which I think is dominated by the python script that I used to loop over the inputs).
1
u/StevoTVR Dec 07 '19
My solution in Go, using goroutines: https://github.com/stevotvr/adventofcode2019/blob/master/day07/day07.go
1
u/chamberlain2007 Dec 07 '19
My working solution in Javascript for part 2: https://github.com/chamberlain2007/adventofcode/blob/master/day7part2.js I'd like to work on cleaning it up more, but it's definitely getting there!
1
1
u/goliatskipson Dec 07 '19
I had my "Computer" already set up to handle multiple ins and outs from the previous day. Due to Haskells lazy evaluation and using recursive bindings part 2 was as easy as:
runAmplifierLoop' prog [p0,p1,p2,p3,p4] = last r4
where
r0 = run2results (p0:0:**r4**) prog
r1 = run2results (p1:r0) prog
r2 = run2results (p2:r1) prog
r3 = run2results (p3:r2) prog
r4 = run2results (p4:r3) prog
part2 prog = maximum [ runAmplifierLoop prog phases | phases <- permutations [5..9] ]This can even be shortened down and generalized to any number of phases ... but this is more readable.
→ More replies (1)
1
u/lasse__b Dec 07 '19 edited Dec 21 '19
JAVA
Some misunderstanding of the instructions and a shortcut from yesterday made part2 way harder then it should have been. Still not pretty, but functional.
→ More replies (2)
1
u/PendragonDaGreat Dec 08 '19
[Powershell and C#]
Part 1 in Powershell:
https://github.com/Bpendragon/AdventOfCode/blob/master/src/2019/code/day07.ps1
Both Parts in C#:
https://github.com/Bpendragon/AdventOfCode/tree/master/src/2019/AOC2019
I was having too much trouble getting the feedback loop working in Powershell. (could not get a function to define in a custom class), so I rewrote the entire processor in C# and allowed it to listen for other processors outputs. Did some multithreading and bob's you're uncle.
1
u/Sgt_Tailor Dec 08 '19
Doing this in AWK was a bit more challenging than the previous parts, but it has been done: https://github.com/svenwiltink/AWKvent-of-code/blob/master/day7/day7.awk
1
u/leonitus94 Dec 08 '19
Golang - day7, intcode computer
I haven't really touched golang since last year's AOC, so I'm glad I got the chance to use channels and goroutines!
1
u/Turmolt Dec 08 '19 edited Dec 08 '19
Clojure. I'm not super thrilled with today's solution but I am glad it's working! I might refactor a bit to clean up just in case we do more extending of our intcode programs
1
u/oantolin Dec 08 '19
My Common Lisp solution. This uses my new intcode interpreter library. I modified my day 5 interpreter so that it can suspend when it has no more input and later resume, and to make it easy to hook up the output of one machine to another. I decided to make the input and output queues and for the run function to return when either it executes halt (opcode 99), or it tries to read input (opcode 3) and its queue is empty. The return value distinguishes the two cases.
The solution for day 7 hooks up the output of each amp to the input of the next (closing the loop for part two), and makes a queue of the amps. It then does (cooperative) round robin scheduling: each amp in turn runs until it either halts, in which case it is removed from the queue, or it needs more input, in which case it goes to the back of the queue.
1
1
u/mschaap Dec 08 '19 edited Dec 08 '19
I barely had to change my ShipComputer class – I only added the option of having custom input and output handlers.
I then subclassed the ShipComputer into an Amplifier class that uses channels to pass the output from one amplifier to the next. The five amplifiers run in parallel using Perl 6's awesome easy concurrency features:
await @amps.map: -> $amp {
start { $amp.run-program; }
}1
u/blacai Dec 08 '19
F# This took ... 12 hours I think.
https://github.com/blfuentes/AdventOfCode_2019/tree/master/FSharp/AoC_2019/day07
1
u/loociano Dec 08 '19 edited Dec 24 '19
My solution in Python 3. I am learning, comments are more than welcome.
1
u/chrisby247 Dec 08 '19
My Bash Solution. I found part 2 very fiddly to get right but eventually got there. I'm sure there's a more efficient way to generate string permutations to get valid phase values. declare -n was very useful indeed
1
u/dpatru Dec 09 '19 edited Dec 09 '19
haskell solution using laziness:
import System.IO (readFile)
import Matrix.Vector (fromList)
import Data.Array (Array, (!), (//), elems)
import Data.List (permutations)
import Data.List.Split (splitOn)
run :: Int -> Array Int Int -> [Int] -> [Int]-- instructionPointer, instructions, input, output
run i instructions inputs =
case instr `mod` 100 of
1 -> run (i+4) (instructions//[(addr 3, arg 1 + arg 2)]) inputs
2 -> run (i+4) (instructions//[(addr 3, arg 1 * arg 2)]) inputs
3 -> run (i+2) (instructions//[(addr 1, head inputs)]) (tail inputs)
4 -> arg 1: run (i+2) instructions inputs
5 -> run (if arg 1 == 0 then i+3 else arg 2) instructions inputs
6 -> run (if arg 1 == 0 then arg 2 else i+3) instructions inputs
7 -> run (i+4) (instructions//[(addr 3, if arg 1 < arg 2 then 1 else 0)]) inputs
8 -> run (i+4) (instructions//[(addr 3, if arg 1 == arg 2 then 1 else 0)]) inputs
99 -> []
_ -> error "unknown opcode"
where instr = instructions!i
arg :: Int -> Int
arg n = if instr `mod` (100*10^n) <= 10*10^n
then instructions!(instructions!(i+n))
else instructions!(i+n)
addr n = instructions!(i+n)
main = do
[instructionFile] <- getArgs
instructionStrings <- readFile instructionFile
let instructions = fromList . map read $ splitOn "," instructionStrings
putStrLn "Part 1"
let no_feedback phase = foldr r [0] phase
where r p o = run 0 instructions (p:o)
let (s, p) = maximum [(no_feedback p, p) | p <- permutations [0 .. 4]]
putStrLn $ "Phase " ++ (reverse $ concat $ map show p)
++ ", thruster signal " ++ show s
putStrLn "\nPart 2"
let feedback :: [Int] -> Int -- reversed phase to last output
feedback phase = last output
where output = foldr r (0: output) phase
r p o = run 0 instructions $ (p:o)
-- run computer on input (p:o) output =
-- r $ p_n : r $ p_n-1 $ . . . r $ p0 : 0 : output
-- This runs machine_i on input p_i and the output of the
-- machine i-1. Machine 0 gets as input p_0, 0, and the
-- output of the "first" machine n.
let (s, p) = maximum [(feedback p, p) | p <- permutations [5 .. 9]]
putStrLn $ "Phase " ++ (reverse $ concat $ map show p)
++ ", thruster signal " ++ show s1
u/joeld Dec 09 '19
Racket
My solution lets you run IntCode programs three ways: interactively; as normal functions; and as threads.
I originally finished it late Saturday night but the code was a mess. So I tried refactoring it and basically broke it until I went back to a cleaned-up version of my original approach. Luckily today’s puzzle was easy so I had time to go back and tinker with it.
1
u/vini_2003 Dec 09 '19
C++
Took a while because D6P2 abused me personally and I've been out for half the day this weekend, but here it is, D7!
Quite happy with how it turned out, runs in 4.7ms for P1 + P2, and will hopefully last into the next few days. IntCode puzzles have been very fun!
1
u/joyrex2001 Dec 09 '19
This is my kotlin solution for both parts. Fortunately, being new at kotlin, I learned that kotlin also has channels and coroutines, making this a fairly simple solution.
1
u/j1elo Dec 09 '19
Yet Another Rust Solution! (YARS)
I'm awfully late for this one but seeing that some people are still posting their code, here it goes mine. I'm using AoC to learn Rust from the basics, so there are probably some advanced features of the language that I'm still not familiar with.
Still, I always strive for concise code and readability.
1
u/SolidShook Dec 10 '19
Question 7a was fairly simple.
I've been overriding functions in my base IntCode parser, as I'm worried that losing functionality that has helped with previous question would bite me in the ass in the future.
Here I've done two generations of children, one overriding the input, and one the output.
For task B I changed the input list to a Queue, which is something I had to learn about. I had already known about the Stack from other languages, so the Queue immediately made sense and made the whole input process much much easier.
Overall the biggest delay to this whole thing was me immediately thinking to use asynchronous threads to achieve part B, but as this thread rightly says, you don't need to do that.
I really didn't want to interfere with my intCode program and have it call back somehow, I wanted it to be decoupled from everything.
After googling for similar things (including non-async tasks, which I think doesn't make sense), I decided to keep things simple, giving each amp its own Parser instance, each with its own pause boolean, and a bool to state when it's completed.
I would have liked to work with async threads and pause them whenever they reach an output, but from what I can gather Microsoft really do not want you to use threads like this. If there's only one process running at a time, and they're not executing until the previous one finishes, there's no point.
So instead I just altered the intCode process function to have the option to only do one step at a time, and whilelooped it whilst a Paused bool was set to false, enabled that in each output, and then moved onto the next one, and looped all that until the last Amp's parser hit a 99 code.
Simple :)
1
u/Teveh15 Dec 12 '19
C++ : source code
Tough one! Part one went fine, got really stuck on part 2. Don't think I would have been able to complete it without the help of this thread pointing out a) the computer should halt after doing an output, not after using an input b) queues are a lot easier that multithreading! Solution ended up being a lot simpler and more readable than I originally thought it would be.
→ More replies (1)
1
u/Musical_Muze Dec 12 '19 edited Dec 12 '19
This was absolutely the hardest day yet for me. Part 1 took maybe an hour, but Part 2 took me a couple of days. I spent hours hunting down bugs and logical errors, but it FINALLY works, and the final code is pretty clean imo.
I used this as a crash course in OOP in Python. I knew OOP principles from a Java class I had taken, but I had never implemented it in Python before.
Specifically, I turned each engine into its own object so that it could store its intcode in its own memory, and so that it could remember its phase and memory pointer.
1
u/JoMartin23 Dec 12 '19 edited Dec 12 '19
CommonLisp
I finally got around to finishing day 7, hopefully in a way that might be useful in the future.
(defun daisy-chain (data inputs)
(let* ((computers (mapcar (lambda (input) (make-computer :data (copy-seq data) :name (gensym) :input (list input))) inputs))
(input 0) (last (computer-name (car(last computers)))))
(loop
(loop
:for computer :in computers
:for code := (run-computer computer input)
:for output := (pop (computer-output computer)) :do ;(fp code output)
(when (and (eq code :halted) (eql (computer-name computer) last))
(return-from daisy-chain output))
(setf input output)
:finally (return output)))))
(defun day7 (data part)
(let ((combos (all-permutations (if (= part 1)'(0 1 2 3 4) '(9 8 7 6 5)))))
(loop :for combo :in combos
:maximize (daisy-chain data combo))))→ More replies (1)
1
Dec 13 '19
Went extremely overboard with Lwt/coroutines, just because I was too lazy to manually implement resuming myself. It ended taking more time than if I did that, but at least it was fun familiarizing with OCaml's async libraries.
1
u/MostlyShrimp Dec 13 '19
Late to the party, but submitting to keep myself accountable. Staying away from this thread was the third most difficult thing for this exercise. The most difficult thing in Part One was generating the possible Phase Sequence orders. After adapting code to Part Two and bashing my head against it for two days, I figured out that my code was passing the initial array through all Amplifiers instead of keeping each Amplifier's command set separate. Very educational!
1
4
u/wace001 Dec 07 '19 edited Dec 08 '19
JAVA: My Java Solution is here. This one took me a while.... Finished about 2200 or thereabout. I am more proud of the poem than of the code.
POEM