Hi,
Someone please help me understand part 2 of day 7
I am trying to get the answer given in first example of part two.
The input is
3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5
For sequence 9,8,7,6,5
First input I gave was 9 as phase setting
Then gave 0 at the second occurrence of opcode 3
The program proceeds but it encounters opcode 5 at position 23 and resets my address pointer to 6. At 6 again the opcode is 3. Now here I give 8(next phase setting) or previous output value? Also in this way my program is not reaching 99 and it kept running until i killed it.
Hello...
Believe it or not, I'm still not getting how Part 2 works... I like the way you spelled things out in your post per the sample data. Enter 9, then enter 0, etc. Can you do something similar with the understanding you've gained here? I would truly appreciate it. Thanks.
In part 1, a sequence of 2 amps (A0,A1) will operate like so:
A0-Start
A0-asks for phase number (0)
A0-asks for input (0)
A0-outputs oa1
A0-ends
A1-starts
A1-asks for a phase number (1)
A1 asks for input (oa1)
A1 outputs oa2 <—answer
A1 ends
Part 2 is... complicated to diagram, but I will try (again with two amps, A5 and A6)
A5
A6
Start
Start
input read: phase (5)
input read: phase (6)
input read from init: 0
input needed
output o1a5
input needed
input read from A5: o1a5
output o1a6
input read from A6: o1a6
input needed
output o2a6
end
input read from A5: o2a6
output o2a6 (answer)
end
Obviously the prompt uses 5 amps, and your input code produces a larger number of outputs per amp than my example. But I think this is the minimal state diagram possible that shows off the difference.
Thanks for replying... I'm a new programmer, and I'm not sure why, but things still aren't making sense. Let me tell you what I'm doing. First of all, Part 1 works fine for me. This is what I do for Part 2 (sample 1).
Sample one is:
Max thruster signal 139629729 (from phase setting sequence 9,8,7,6,5):
3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5
So...
I start the program, I guess it would be on Amp A. It asks for input, and I give it 9 (from the phase setting sequence above). Then it asks for a second input, and I give it 0 (from the instructions in Part 2). At that point I get an output of 5 and the program stops... Here I have a few questions... 1) should the program have stopped? 2) When I start up the program on Amp B do I start with fresh data (above), or do I use the updated data (I'm using a hash table).
So, then, I guess I start Amp B; it asks for an input. I give it 8, the second number in the phase setting sequence. It asks for another input, and I give it a 5 (from the output above). At that point the program stops and outputs 14. So, at this point I have two amps that have already stopped. This goes on until I get to the fifth amp and I get an output there. But, Amp A has already stopped (it stopped right away). So, what do I do with the output I just got from the fifth amp? It's not the solution; it's a low number.
Hopefully, some of this makes sense. If I can't get the sample to work, I don't know how I'm going to get the puzzle data to work. Any replies would be very welcome.
I did it all in sync, runs well enough nonetheless.
(load-file"intcode.clj")(nsDay07(:requireintcode)(:import(clojure.langPersistentQueue))); Returns a sequence of all possible permutations for a given collection.(defnpermutations[coll](lazy-seq(if(seq(restcoll))(applyconcat(for[elementcoll](map#(conselement%)(permutations(remove#{element}coll)))))[coll]))); Creates a sequence of the initial amp states, initialised with the Amp Controller Software memory and one of the given settings(defnprepare-amps[acssettings](map(partialintcode/initial-stateacs)settings)); Continues processing an amp state by removing its interrupted state and adding the given input(defncontinue[inputamp-state](intcode/process(->amp-state(dissoc:interrupted)(update:inputs#(conj%input))))); Returns true if all of the given states are terminated(defnall-terminated?[states](not-any?(complementidentity)(map:terminatedstates))); Runs a feedback loop given the Amp Controller Software and settings.; It loops until all amp states are terminated, which means that it can be used for both parts.(defnfeedback-loop[acssettings](loop[amp-states(reduceconjPersistentQueue/EMPTY(prepare-ampsacssettings))input0](if(all-terminated?amp-states)input(let[processed(continueinput(firstamp-states))](recur(conj(popamp-states)processed)(last(:outputsprocessed))))))); Finds the largest output signal possible given an acs and the possible phase settings.(defnlargest-output-signal[acspossible-settings](applymax(for[settings(permutationspossible-settings)](feedback-loopacssettings))))(definput(intcode/parse-intcodes(slurp(first*command-line-args*))))(println"Highest output signal:"(largest-output-signalinput(range5)))(println"Highest output signal (with feedback loop settings):"(largest-output-signalinput(range510)))
Well, today was definitely fun. Continuing in Python from previous days, part one was fairly easy as the modifications to my existing Intcode computer were minimal and the task itself was fairly straight-forward, but part two was interesting.
For part two, I chose to rewrite my whole Intcode computer in dart, as that is the language I am most familiar with, and I'm happy I did so. I then gave each amplifier a StreamController as its output and the BroadcastStream of the previous amplifier's StreamController as its input and had them listen to each other in async. Probably not the easiest way to do it, but very fun and interesting to write.
Here's the code for part 2:
import'dart:async';import'dart:io';import'dart:math'asmath;import'./tools/intcode_computer.dart';import'./tools/permutations.dart';//! Part 1 of day 7 is in day_7.pyvoidmain()async{varinput=(awaitFile('inputs/day_7.txt').readAsString()).split(',').map((a)=>int.parse(a)).toList();run(input);}voidrun(input)async{varpermutations=findAllPermutations('56789');intmax;for(varpermutationinpermutations){varout=awaitrunCycle(input,permutation);max=math.max(max??0,out);}print(max);}Future<int>runCycle(input,Stringpermutation)async{varcontrollers=List.generate(5,(_)=>StreamController());/// Creating a list of the broadcast streams of the controllers so that I can subscribe to them from herevarstreams=List.generate(5,(i)=>controllers[i].stream.asBroadcastStream(),);/// Create a list of intcode computers - the amplifiersvarcomps=List.generate(5,(i)=>IntcodeComputer(List.from(input),/// Giving each computer the broadcast stream at its index as the input stream and the controller/// of an index one higher as the output stream, which means the computer will output to the next/// computer's input stream. The last computer outputs to the first computer's streaminputStream:streams[i],outputStream:controllers[i+1<5?i+1:0]),);varsplit=permutation.trim().split('');/// Add the phase setting of the computer to that computer's input stream as the first inputfor(inti=0;i<5;i++){controllers[i].sink.add(int.parse(split[i]));}/// Provide the first computer with the input signal 0controllers[0].sink.add(0);/// Keep track of every input to the first computer (ie every output of the last computer). The/// last value this will have will be the last value of the operationintlast;streams.first.listen((output)=>last=output);/// Run all computers, but keep a reference of the last computer run so that we can wait until it/// finishes before closing the stream controllers and returning the last valuefor(inti=0;i<comps.length-1;i++)comps[i].run();varrun4=comps[4].run();awaitrun4;/// Close all stream controllers to prevent memory leaksfor(varcontrollerincontrollers)controller.close();returnlast;}
I decided to go with javascript and use generators so I could easily suspend the amplifier program between inputs
constINSTRUCTIONS={ADD:1,MULT:2,INPUT:3,OUTPUT:4,JUMP_IF_TRUE:5,JUMP_IF_FALSE:6,LESS_THAN:7,EQUALS:8,HALT:99}functionrunProgram(instructions){instructions=instructions.slice()returnfunction*amplifier(){letlastOutput=nullfor(leti=0;i<instructions.length;++i){constinstruction=instructions[i]constparsed=String(instruction).padStart(5,'0').split('')constvalueMode=(value,mode='0')=>mode==='0'?instructions[value]:valueconstopCode=Number(parsed.slice(3).join(''))constmodes=parsed.slice(0,3)switch(opCode){caseINSTRUCTIONS.ADD:{constx=valueMode(instructions[++i],modes[2])consty=valueMode(instructions[++i],modes[1])instructions[instructions[++i]]=x+ybreak}caseINSTRUCTIONS.MULT:{constx=valueMode(instructions[++i],modes[2])consty=valueMode(instructions[++i],modes[1])instructions[instructions[++i]]=x*ybreak}caseINSTRUCTIONS.INPUT:{instructions[instructions[++i]]=yield{type:'INPUT'}break}caseINSTRUCTIONS.OUTPUT:{lastOutput=valueMode(instructions[++i],modes[2])yield{type:'OUTPUT',value:lastOutput}break}caseINSTRUCTIONS.JUMP_IF_TRUE:{constcompare=valueMode(instructions[++i],modes[2])constjumpTo=valueMode(instructions[++i],modes[1])-1if(compare!=0){i=jumpTo}break}caseINSTRUCTIONS.JUMP_IF_FALSE:{constcompare=valueMode(instructions[++i],modes[2])constjumpTo=valueMode(instructions[++i],modes[1])-1if(compare==0){i=jumpTo}break}caseINSTRUCTIONS.LESS_THAN:{constx=valueMode(instructions[++i],modes[2])consty=valueMode(instructions[++i],modes[1])instructions[instructions[++i]]=x<y?1:0break}caseINSTRUCTIONS.EQUALS:{constx=valueMode(instructions[++i],modes[2])consty=valueMode(instructions[++i],modes[1])instructions[instructions[++i]]=x===y?1:0break}caseINSTRUCTIONS.HALT:returnlastOutput}}}}constpermutations=inputArr=>{letresult=[]constpermute=(arr,m=[])=>{if(arr.length===0){result.push(m)}else{for(leti=0;i<arr.length;i++){letcurr=arr.slice()letnext=curr.splice(i,1)permute(curr.slice(),m.concat(next))}}}permute(inputArr)returnresult}functionpart1(instructions){constallInputs=permutations([0,1,2,3,4])constresults=allInputs.map(inputs=>{constamplifiers=inputs.map((input,i)=>{constamplifier=runProgram(instructions)()amplifier.next()// set phaseconststate=amplifier.next(input)constname=String.fromCharCode(i+65)return{amplifier,state,name}})letpower=0for(constampofamplifiers){const{amplifier}=ampconstout=amplifier.next(power)power=out.value.value}returnpower})returnresults.reduce((p,v)=>Math.max(p,v),0)}functionpart2(instructions){constallInputs=permutations([9,8,7,6,5])constresults=allInputs.map(inputs=>{constamplifiers=inputs.map((input,i)=>{constamplifier=runProgram(instructions)()amplifier.next()// set phaseconststate=amplifier.next(input)constname=String.fromCharCode(i+65)return{amplifier,state,name}})letpower=0while(amplifiers[amplifiers.length-1].state.done===false){for(constampofamplifiers){const{amplifier}=ampconstout=amplifier.next(power)// continue to next inputamp.state=amplifier.next()power=out.done?out.value:out.value.value}}returnpower})returnresults.reduce((p,v)=>Math.max(p,v),0)}if(process.argv[1]===__filename){constinput=require('fs').readFileSync(0).toString()constinstructions=input.split(',').map(Number)constp1Max=part1(instructions)console.log(p1Max)constp2Max=part2(instructions)console.log(p2Max)}
Anyway... JavaScript. It has this nice generator thing that I basically never used professionally and very rarely by myself, and here I am using them twice here. But you know, they're quite good for stateful machines. (Which is also why I rarely use them - like many others, I prefer stateless approaches.)
This is the solution for the second part, as the first can run the first (except for the phase settings, where I just add 5 to the permutation's elements - see at the end).
Many parts are the same of day 5 of course. Sorry for the repetition.
constparameterCount={1:3,2:3,3:1,4:1,5:2,6:2,7:3,8:3,99:0};constcodes=input.split(',').map(Number);// As amplifiers are now stateful machines, we'll sort out to generators again.// A copy of the memory and the input stack is given.function*createProgramInstance(localCodes,...stack){letinstructionPointer=0;function*getInstructions(){while(instructionPointer<localCodes.length){constinstruction=localCodes[instructionPointer];constopcode=instruction%100;constmodes=Array.from({length:3},(_,index)=>Math.floor(instruction/10**(index+2)%10));constparamCount=parameterCount[opcode];constparams=localCodes.slice(instructionPointer+1,instructionPointer+paramCount+1);instructionPointer+=paramCount+1;yield{opcode,modes,params};}}functiongetValue(index,mode){returnmode===0?localCodes[index]:index;}functionexecute({opcode,modes,params}){switch(opcode){case1:localCodes[params[2]]=getValue(params[0],modes[0])+getValue(params[1],modes[1]);break;case2:constresult=getValue(params[0],modes[0])*getValue(params[1],modes[1]);localCodes[params[2]]=result;break;case3:localCodes[params[0]]=stack.shift();break;case4:returngetValue(params[0],modes[0]);case5:if(getValue(params[0],modes[0])){instructionPointer=getValue(params[1],modes[1]);}break;case6:if(getValue(params[0],modes[0])===0){instructionPointer=getValue(params[1],modes[1]);}break;case7:localCodes[params[2]]=+(getValue(params[0],modes[0])<getValue(params[1],modes[1]));break;case8:localCodes[params[2]]=+(getValue(params[0],modes[0])===getValue(params[1],modes[1]));break;}}for(constinstructionofgetInstructions()){if(instruction.opcode===99){return;}constoutput=execute(instruction);if(typeofoutput==='number'){// In order to resume execution, we get a new input (passed with .next())stack.push(yieldoutput);}}}// Given a number, returns the corresponding permutation of 0-length.// Can surely be improved, but it's definitely not the bottleneck.functiongetPermutation(length,index){constitems=Array.from({length},(_,i)=>i);letfactorial=1;returnitems.reduce((permutation,num)=>{constitemIdx=Math.floor(index/factorial)%(num+1);factorial*=num+1;permutation.splice(itemIdx,0,num);returnpermutation;},[]);}functioncreateAmplifier(phaseSetting,initialInput){constampCodes=[...codes];returncreateProgramInstance(ampCodes,phaseSetting,initialInput);}constAMPS=5;// Basically, AMPS!letpermutationCount=1;for(leti=1;i<=AMPS;i++){permutationCount*=i;}functionrunPermutation(permutation){letpreviousOutput=0;constamplifiers=[];letcounter=0;while(true){constindex=counter%AMPS;if(amplifiers.length-1<index){amplifiers.push(createAmplifier(permutation[index],previousOutput));}constamplifier=amplifiers[index];const{value}=amplifier.next(previousOutput);if(typeofvalue==='number'){previousOutput=value;}else{returnpreviousOutput;}counter++;}}constresults=[];for(leti=0;i<permutationCount;i++){constpermutation=getPermutation(AMPS,i).map(num=>num+5);constresult=runPermutation(permutation);results.push(result);}console.log(Math.max(...results));
Horray, finally got part 2 solved!! happy dance Took FOREVER but I finally got it working. This will be the part 2 solution in JavaScript (part 1 was very similar, just slightly more simplified and didn't involve the objects I created for each amp).
// Shout out to MikeTheReader & Morganamilo for the help with part 2 of this one!// Memory - initial puzzle input, a list of integersconstinput=[3,8,1001,8,10.....3,9,1002,9,99];// copy of initial input, so we can reset properlyletinputCopy=[...input];// opcode 1 - get values at position 1&2 right after code, add together, store in position 3functionopcode1(a,b,c,p,dir){letvalA=ptest(p[0],a,dir);letvalB=ptest(p[1],b,dir);dir[c]=valA+valB;// console.log(`op1: ${valA} + ${valB} = ${valA + valB}`)}// opcode 2 - get values at position 1&2 right after code, multiply, store in position 3functionopcode2(a,b,c,p,dir){letvalA=ptest(p[0],a,dir);letvalB=ptest(p[1],b,dir);dir[c]=valA*valB;// console.log(`op2: ${valA} * ${valB} = ${valA * valB}`)}// opcode 3 - takes an input and stores in position 1functionopcode3(iv,s,dir){dir[s]=iv;// console.log(`op3: putting ${iv} into spot ${s}`)}// opcode 4 - outputs value at position 1functionopcode4(s,p,dir){letval=ptest(p[0],s,dir);// console.log(`op4: outputting ${val}`)returnval;}// opcode 5 - if position 1 != 0, changes i to position 2; otherwise, does nothingfunctionopcode5(a,b,inp,p,dir){letvalA=ptest(p[0],a,dir);letvalB=ptest(p[1],b,dir);if(valA!==0){inp=valB;}// console.log(`op5: inst. pointer is now ${inp}`);returninp;}// opcode 6 - if position 1 == 0, changes i to position 2; otherwise, does nothingfunctionopcode6(a,b,inp,p,dir){letvalA=ptest(p[0],a,dir);letvalB=ptest(p[1],b,dir);if(valA===0){inp=valB;}// console.log(`op6: inst. pointer is now ${inp}`);returninp;}// opcode 7 - if position 1 < position 2, position 3 is set to 1; otherwise, it's set to 0functionopcode7(a,b,c,p,dir){letvalA=ptest(p[0],a,dir);letvalB=ptest(p[1],b,dir);if(valA<valB){dir[c]=1;}else{dir[c]=0;}// console.log(`op7: comparing if ${valA} is < ${valB}`);}// opcode 8 - if position 1 == position 2, position 3 is set to 1; otherwise, it's set to 0functionopcode8(a,b,c,p,dir){letvalA=ptest(p[0],a,dir);letvalB=ptest(p[1],b,dir);if(valA==valB){dir[c]=1;}else{dir[c]=0;}// console.log(`op8: comparing if ${valA} equals ${valB}`);}// allows parameter modes - checks for 0 or 1, decides if returning actual number called or position of number in inputfunctionptest(param,checkval,dir){if(param==0||!param){returndir[checkval];}elseif(param==1){returncheckval;}}// opcode 99 - stop program// run through memory input, following instructions until 99 is hitfunctionrunProgram(amp){for(leti=amp.pointer;i<inputCopy.length;i++){if(amp.directions[i]===99){if(amp.haltCalled){returnamp.output;}amp.haltCalled=true;haltsCalled++;amp.pointer=i;returnamp.output;}letinstruct=amp.directions[i].toString();letopval=parseInt(instruct.slice(-2),10);letparams=instruct.slice(0,-2).split('').reverse();letione=amp.directions[i+1];letitwo=amp.directions[i+2];letithree=amp.directions[i+3];switch(opval){case01:opcode1(ione,itwo,ithree,params,amp.directions);i+=3;break;case02:opcode2(ione,itwo,ithree,params,amp.directions);i+=3;break;case03:if(amp.requestedInputs===0){opcode3(amp.inputPhase,ione,amp.directions);i++;amp.requestedInputs++;break;}elseif(amp.requestedInputs===1){opcode3(amp.inputInit,ione,amp.directions);i++;amp.requestedInputs++;break;}else{opcode3(amp.inputSig,ione,amp.directions);i++;break;}case04:letres=opcode4(ione,params,amp.directions);amp.output=res;i++;amp.pointer=i+1;returnamp.output;break;case05:letcheckt=opcode5(ione,itwo,i,params,amp.directions);if(i!=checkt){i=checkt-1;}else{i+=2;}break;case06:letcheckf=opcode6(ione,itwo,i,params,amp.directions);if(i!=checkf){i=checkf-1;}else{i+=2;}break;case07:opcode7(ione,itwo,ithree,params,amp.directions);i+=3;break;case08:opcode8(ione,itwo,ithree,params,amp.directions);i+=3;break;}}}letmaxSignal=0;// Didn't feel like creating this, so found a method here: https://stackoverflow.com/a/20871714constpermutator=(inputArr)=>{letresult=[];constpermute=(arr,m=[])=>{if(arr.length===0){result.push(m)}else{for(leti=0;i<arr.length;i++){letcurr=arr.slice();letnext=curr.splice(i,1);permute(curr.slice(),m.concat(next))}}}permute(inputArr);returnresult;}letphaseSettingOptions=[0,1,2,3,4];letphaseSettingOptions2=[5,6,7,8,9];letphaseSettings=permutator(phaseSettingOptions);letphaseSettings2=permutator(phaseSettingOptions2);// phase 2 settingsletamps=[{'name':'a','pointer':0,'inputPhase':0,'inputInit':0,'inputSig':0,'requestedInputs':0,'output':0,'haltCalled':false,'directions':[...input]},{'name':'b','pointer':0,'inputPhase':0,'inputInit':0,'inputSig':0,'requestedInputs':0,'output':0,'haltCalled':false,'directions':[...input]},{'name':'c','pointer':0,'inputPhase':0,'inputInit':0,'inputSig':0,'requestedInputs':0,'output':0,'haltCalled':false,'directions':[...input]},{'name':'d','pointer':0,'inputPhase':0,'inputInit':0,'inputSig':0,'requestedInputs':0,'output':0,'haltCalled':false,'directions':[...input]},{'name':'e','pointer':0,'inputPhase':0,'inputInit':0,'inputSig':0,'requestedInputs':0,'output':0,'haltCalled':false,'directions':[...input]},];lethaltsCalled=0;functionrunAmp(phase,init,sig,amp){amp.inputPhase=phase;amp.inputInit=init;amp.inputSig=sig;letnextInput=runProgram(amp);returnnextInput;}functionrunCycle(phase){for(letj=0;j<amps.length;j++){letprevious=j-1;if(previous<0){previous=4;}if(amps[j].pointer===0){amps[j].inputInit=runAmp(phase[j],amps[previous].output,0,amps[j]);}else{amps[j].inputSig=runAmp(phase[j],amps[j].inputInit,amps[previous].output,amps[j]);}}}functionresetValues(){for(leta=0;a<amps.length;a++){letthisAmp=amps[a];thisAmp.pointer=0;thisAmp.inputPhase=0;thisAmp.inputInit=0;thisAmp.inputSig=0;thisAmp.requestedInputs=0;thisAmp.output=0;thisAmp.haltCalled=false;thisAmp.directions=[...input];}};for(leti=0;i<phaseSettings2.length;i++){letphaseOrder=phaseSettings2[i];haltsCalled=0;resetValues();do(runCycle(phaseOrder));while(haltsCalled!==5);if(maxSignal===0){maxSignal=amps[4].output;}elseif(amps[4].output>maxSignal){maxSignal=amps[4].output;console.log(`best phase: ${phaseOrder}`);}}console.log(`Max signal: ${maxSignal}`);
Here's my part 2 solution in #haskell. I ended up needing to do some substantial refactoring from my previous solution that I'd used for day 5 as well as part 1. My original version attempting to go for performance by using mutable vectors to store the program state, ostensibly allowing for more performant seeks and writes to the program state. I started to extend this approach using IORefs to program state and some other clever trickery. Although I managed to get constant memory utilization, the performance was so bad the program never actually finished running.
After profiling didn't help enough, and I verified that there was nothing unsound about my algorithm, I decided to start from the ground up with the simplest solution and went back to a pure implementation using record updates to manage all of the changes to start, and manually sending IO between the amplifiers. Once again proving that when it comes to optimization I'm never as clever as I think I am, the compiler did it's job and took my naive implementation and gave me a version that finished in a couple hundred milliseconds.
My new version needs some refactoring still, both for readability and ergonomics during future challenges, but here is the version left on my disk from when I finally finished up at 5am:
Here's my solution to part 1 minus the obscene overhaul to Day05. I spent too long futzing because my refactor wasn't as friendly as I had hoped, and there was a terrible bug in my permutation generator.
Well that was fun! My decision on day 2 to do the machine simulator in C continues to be both an advantage and a disadvantage. I'm enjoying flitting between the low-level pointer hacking and the high-level Prolog and Haskell solutions on other days.
Generating the permutations of the phase signals was the hardest bit today. The principle is a simple one - lock some digits, generate the permutations of the remaining, and recurse - but the details and corner cases in recursive C were a bit tricky.
I'm a Staff Software Engineer at Cisco. I specialize in Python and Go, building functional, practical, and maintainable web systems leveraging Kubernetes and the cloud. Blog opinions are my own.
Playing some Sunday night catch-up. My previous architecting bit me in the butt today. Had to re-think my "stdin/stdout" concepts. Converted them to vector buffers (should probably have used queues, but too lazy). Worked out pretty well. The key for me was adding in a new opcode (98, so far unused) to signify a halt waiting for input rather than a full program halt (99). Here's my (part 2) solution in Rust:
/// Day 7: Amplification Circuit/// /// Use the Intcode Interpreter to AMPLIFY POWER!usestd::fs;useitertools::Itertools;usecrate::intcode::IntcodeInterpreter;/// Parses the input. Expects a single line of integers separated by/// commasfnparse_input()->Vec<isize>{lettext:String=fs::read_to_string("data/day7.txt").unwrap();letcleaned=text.trim();cleaned.split(",").map(|c|c.parse().unwrap()).collect()}pubfnrun(){letnumbers=parse_input();letmutmax_output=0;forcombin(5..=9).permutations(5){letmuta=IntcodeInterpreter::new(numbers.clone());letmutb=IntcodeInterpreter::new(numbers.clone());letmutc=IntcodeInterpreter::new(numbers.clone());letmutd=IntcodeInterpreter::new(numbers.clone());letmute=IntcodeInterpreter::new(numbers.clone());a.push_input(comb[0]);b.push_input(comb[1]);c.push_input(comb[2]);d.push_input(comb[3]);e.push_input(comb[4]);letmuta_input=0;letmutout;loop{a.push_input(a_input);a.run();b.push_input(a.shift_output());b.run();c.push_input(b.shift_output());c.run();d.push_input(c.shift_output());d.run();e.push_input(d.shift_output());e.run();out=e.shift_output();ife.current_instruction()==99{break;}a_input=out;}println!("Got {}",out);ifout>max_output{max_output=out;}}println!("Max output is: {}",max_output);}
And, my Intcode Interpreter, for reference. I completed day 7 and 9 back to back, so there's some day 9 stuff in here that won't apply to this problem:
usestd::io;usestd::collections::HashMap;/// An Intcode Interpreter is a simple virtual machine that uses opcodes/// to modify its internal memorypubstructIntcodeInterpreter{memory:HashMap<usize,isize>,in_buffer:Vec<isize>,out_buffer:Vec<isize>,ip:usize,relative_base:isize,}implIntcodeInterpreter{pubfnnew(numbers:Vec<isize>)->Self{letmutmemory:HashMap<usize,isize>=HashMap::new();for(ind,num)innumbers.iter().enumerate(){memory.insert(ind,*num);}Self{memory,in_buffer:Vec::new(),out_buffer:Vec::new(),ip:0,relative_base:0,}}/// Sets a memory address to a valuepubfnset(&mutself,position:usize,value:isize){self.memory.insert(position,value);}/// Reads from a memory addresspubfnget(&mutself,position:usize)->isize{*self.memory.entry(position).or_default()}/// Shows the memory for debuggingpubfnprint(&self){println!("{:?}",self.memory);}/// Get the current instructionpubfncurrent_instruction(&mutself)->isize{self.get(self.ip)%100}/// Add a value to the input queuepubfnpush_input(&mutself,value:isize){self.in_buffer.push(value);ifself.current_instruction()==98{self.memory.insert(self.ip,self.memory[&self.ip]-95);// Return the instruction to// a 3 while maintaining// argtype values}}pubfncount_output(&self)->usize{self.out_buffer.len()}/// Pop a value off the output queuepubfnshift_output(&mutself)->isize{ifself.out_buffer.is_empty(){panic!("Shift from empty out buffer!");}self.out_buffer.remove(0)}/// Runs the program in memory until the stopcode (99) is reached/// /// All new ops should have their own method./// They take no rust args, but read in args as needed and/// shift the instruction pointer when they're done./// Steps should be the number of args used + 1 for the opcodepubfnrun(&mutself){loop{matchself.current_instruction(){1=>self.op1(),2=>self.op2(),3=>self.op3(),4=>self.op4(),5=>self.op5(),6=>self.op6(),7=>self.op7(),8=>self.op8(),9=>self.op9(),98=>return,// Halt until receiving input99=>return,// End of program_=>panic!("Unrecognized opcode {}.",self.get(self.ip)),};}}/// Reads a number from STDINfnread_stdin()->isize{letmutbuffer=String::new();io::stdin().read_line(&mutbuffer).expect("STDIN read failed.");buffer.trim().parse::<isize>().unwrap()}/// Write a number to STDOUTfnwrite_stdout(number:isize){println!("{}",number);}/// Process the parameter mode and provide the value given/// as a parameterfnarg(&mutself,offset:usize)->isize{letnew_index=self.ip+offset;letmode=(self.memory[&self.ip]/10isize.pow(1+offsetasu32))%10;ifmode==2{letaddr=self.relative_base+self.memory[&new_index];letval=self.get(addrasusize);self.get(addrasusize)}elseifmode==1{self.memory[&new_index]}elseifmode==0{self.get(self.memory[&new_index]asusize)}else{panic!("Unknown parameter mode {}",mode);}}/// Returns the address to write output tofnoutput_address(&self,offset:usize)->usize{letmode=(self.memory[&self.ip]/10isize.pow(1+offsetasu32))%10;letnew_index=self.ip+offset;ifmode==0{self.memory[&new_index]asusize}elseifmode==2{(self.relative_base+self.memory[&new_index])asusize}else{panic!("Output address with weird mode");}}/// Steps the IP forward "count" steps, wrapping if neededfnstep(&mutself,count:usize){self.ip=(self.ip+count)%self.memory.len();}/// Causes the interpreter to block until receiving inputfnhalt_on_input(&mutself){// Update the last two digits from 03 to 98, but maintain// the argtype valuesself.memory.insert(self.ip,self.memory[&self.ip]+95);}/// Add [1] + [2], store in [3]fnop1(&mutself){letin1=self.arg(1);letin2=self.arg(2);letout=self.output_address(3);self.set(out,in1+in2);self.step(4);}/// Mult [1] * [2], store in [3]fnop2(&mutself){letin1=self.arg(1);letin2=self.arg(2);letout=self.output_address(3);self.set(out,in1*in2);self.step(4);}/// Read one value from STDIN and store it in [1]fnop3(&mutself){letout=self.output_address(1);letval:isize;ifself.in_buffer.is_empty(){self.halt_on_input();return;}else{val=self.in_buffer.remove(0);}self.set(out,val);self.step(2);}/// Read [1] and send it to STDOUTfnop4(&mutself){letarg=self.arg(1);self.out_buffer.push(arg);self.step(2);}/// If [1] != 0, set IP -> [2], else nothingfnop5(&mutself){ifself.arg(1)!=0{self.ip=self.arg(2)asusize;}else{self.step(3);}}/// if [1] == 0, set IP -> [2], else nothingfnop6(&mutself){ifself.arg(1)==0{self.ip=self.arg(2)asusize;}else{self.step(3);}}/// if [1] < [2], set [3] to 1, else 0fnop7(&mutself){letout=self.output_address(3);ifself.arg(1)<self.arg(2){self.set(out,1);}else{self.set(out,0);}self.step(4);}/// if [1] == [2], set [3] to 1, else 0fnop8(&mutself){letout=self.output_address(3);ifself.arg(1)==self.arg(2){self.set(out,1);}else{self.set(out,0);}self.step(4);}/// Shift relative base by [1]fnop9(&mutself){self.relative_base+=self.arg(1);self.step(2);}}
Hi,
Someone please help me understand part 2 of day 7
I am trying to get the answer given in first example of part two.
The input is
3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5
For sequence 9,8,7,6,5
First input I gave was 9 as phase setting
Then gave 0 at the second occurrence of opcode 3
The program proceeds but it encounters opcode 5 at position 23 and resets my address pointer to 6. At 6 again the opcode is 3. Now here I give 8(next phase setting) or previous output value? Also in this way my program is not reaching 99 and it kept running until i killed it.
Roughly I think:
So... when the first amp gets to its third or later input, it needs to wait until it receives an output from the last amp.
Once all amps reach 99, the answer is the last outputted value from the last amp.
Got the output. Its 3:30 AM and I can finally sleep now.
Hello...
Believe it or not, I'm still not getting how Part 2 works... I like the way you spelled things out in your post per the sample data. Enter 9, then enter 0, etc. Can you do something similar with the understanding you've gained here? I would truly appreciate it. Thanks.
My attempt:
In part 1, a sequence of 2 amps (A0,A1) will operate like so:
Part 2 is... complicated to diagram, but I will try (again with two amps, A5 and A6)
Obviously the prompt uses 5 amps, and your input code produces a larger number of outputs per amp than my example. But I think this is the minimal state diagram possible that shows off the difference.
Please feel free to ask clarifying questions!
Thanks for replying... I'm a new programmer, and I'm not sure why, but things still aren't making sense. Let me tell you what I'm doing. First of all, Part 1 works fine for me. This is what I do for Part 2 (sample 1).
Sample one is:
Max thruster signal 139629729 (from phase setting sequence 9,8,7,6,5):
3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5
So...
I start the program, I guess it would be on Amp A. It asks for input, and I give it 9 (from the phase setting sequence above). Then it asks for a second input, and I give it 0 (from the instructions in Part 2). At that point I get an output of 5 and the program stops... Here I have a few questions... 1) should the program have stopped? 2) When I start up the program on Amp B do I start with fresh data (above), or do I use the updated data (I'm using a hash table).
So, then, I guess I start Amp B; it asks for an input. I give it 8, the second number in the phase setting sequence. It asks for another input, and I give it a 5 (from the output above). At that point the program stops and outputs 14. So, at this point I have two amps that have already stopped. This goes on until I get to the fifth amp and I get an output there. But, Amp A has already stopped (it stopped right away). So, what do I do with the output I just got from the fifth amp? It's not the solution; it's a low number.
Hopefully, some of this makes sense. If I can't get the sample to work, I don't know how I'm going to get the puzzle data to work. Any replies would be very welcome.
I did it all in sync, runs well enough nonetheless.
And here's the ever growing intcode computer: github.com/jkoenig134/AdventOfCode...
Well, today was definitely fun. Continuing in Python from previous days, part one was fairly easy as the modifications to my existing Intcode computer were minimal and the task itself was fairly straight-forward, but part two was interesting.
For part two, I chose to rewrite my whole Intcode computer in dart, as that is the language I am most familiar with, and I'm happy I did so. I then gave each amplifier a StreamController as its output and the BroadcastStream of the previous amplifier's StreamController as its input and had them listen to each other in async. Probably not the easiest way to do it, but very fun and interesting to write.
Here's the code for part 2:
And the code for my dart Intcode Computer: gist.github.com/jakcharvat/818c477...
Day 7 with swift
I decided to go with javascript and use generators so I could easily suspend the amplifier program between inputs
Yoooo and I thought day 5 was annoying 😫
Anyway... JavaScript. It has this nice generator thing that I basically never used professionally and very rarely by myself, and here I am using them twice here. But you know, they're quite good for stateful machines. (Which is also why I rarely use them - like many others, I prefer stateless approaches.)
This is the solution for the second part, as the first can run the first (except for the phase settings, where I just add 5 to the permutation's elements - see at the end).
Many parts are the same of day 5 of course. Sorry for the repetition.
See text, input and first part on my repo.
Part one was a piece of cake imo. Part two was a lot tougher.
Horray, finally got part 2 solved!! happy dance Took FOREVER but I finally got it working. This will be the part 2 solution in JavaScript (part 1 was very similar, just slightly more simplified and didn't involve the objects I created for each amp).
Here's my part 2 solution in #haskell. I ended up needing to do some substantial refactoring from my previous solution that I'd used for day 5 as well as part 1. My original version attempting to go for performance by using mutable vectors to store the program state, ostensibly allowing for more performant seeks and writes to the program state. I started to extend this approach using IORefs to program state and some other clever trickery. Although I managed to get constant memory utilization, the performance was so bad the program never actually finished running.
After profiling didn't help enough, and I verified that there was nothing unsound about my algorithm, I decided to start from the ground up with the simplest solution and went back to a pure implementation using record updates to manage all of the changes to start, and manually sending IO between the amplifiers. Once again proving that when it comes to optimization I'm never as clever as I think I am, the compiler did it's job and took my naive implementation and gave me a version that finished in a couple hundred milliseconds.
My new version needs some refactoring still, both for readability and ergonomics during future challenges, but here is the version left on my disk from when I finally finished up at 5am:
Here's my solution to part 1 minus the obscene overhaul to Day05. I spent too long futzing because my refactor wasn't as friendly as I had hoped, and there was a terrible bug in my permutation generator.
I'm now mulling whether I want to go full Coroutines for part 2...
Part 1: oh gods, so many for loops
(using basically the same intcode processor from day 5, except output is put into a variable instead of output to the console)
FINALLY got part 2 done. Had to mess around so much:
For some reason I can't get this to work with part 1, but I'm done worrying about it. 😠
Well that was fun! My decision on day 2 to do the machine simulator in C continues to be both an advantage and a disadvantage. I'm enjoying flitting between the low-level pointer hacking and the high-level Prolog and Haskell solutions on other days.
Generating the permutations of the phase signals was the hardest bit today. The principle is a simple one - lock some digits, generate the permutations of the remaining, and recurse - but the details and corner cases in recursive C were a bit tricky.
Today's code runs both parts in 14 milliseconds!
Code at github.com/neilgall/adventofcode20...
Hey Jon, I was curious so I counted the languages used on day 6 for you 🤗
JavaScript × 4
Python × 2
Clojure × 1
Elixir × 1
Java × 1
Kotlin × 1
PHP × 1
Prolog × 1
Swift × 1
Awesome! Thanks! (Runs off to paste it in before I head to bed.)
Playing some Sunday night catch-up. My previous architecting bit me in the butt today. Had to re-think my "stdin/stdout" concepts. Converted them to vector buffers (should probably have used queues, but too lazy). Worked out pretty well. The key for me was adding in a new opcode (98, so far unused) to signify a halt waiting for input rather than a full program halt (99). Here's my (part 2) solution in Rust:
And, my Intcode Interpreter, for reference. I completed day 7 and 9 back to back, so there's some day 9 stuff in here that won't apply to this problem:
That was hard, but here is my javascript walkthrough