So, we're going to work with Intcodes every other day? 😩
The worst part is that, since we're reserving two digit for the opcodes, I expect we're going to work with them again in the future (even though it says "You now have a complete Intcode computer.")
Moreover, the problem forgot to mention that when we write back to the memory, it could be done in relative mode too and not just position mode. Thanks 🤦♂️
But anyway... JavaScript with generators blah blah. I lost quite some time trying to understand why my solution didn't work... Until I realized I was passing the input values incorrectly 😵 I have none but myself to blame there...
Only new thing: the use of JavaScript's BigInt. Hooray for ES2020!
Solution for both parts:
constparameterCount={1:3,2:3,3:1,4:1,5:2,6:2,7:3,8:3,9:1,99:0};constcodes=input.split(',').map(BigInt);function*createProgramInstance(localCodes,...stack){letinstructionPointer=0;letrelativeBase=0;function*getInstructions(){while(instructionPointer<localCodes.length){constinstruction=Number(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};}}functionexecute({opcode,modes,params}){functiongetAddress(index){return(modes[index]===2?relativeBase:0)+Number(params[index]);}functiongetValue(index){constvalue=modes[index]===1?params[index]:localCodes[getAddress(index)];returntypeofvalue==='bigint'?value:0n;}switch(opcode){case1:localCodes[getAddress(2)]=getValue(0)+getValue(1);break;case2:localCodes[getAddress(2)]=getValue(0)*getValue(1);break;case3:localCodes[getAddress(0)]=stack.shift();break;case4:returngetValue(0);case5:if(getValue(0)){instructionPointer=Number(getValue(1));}break;case6:if(getValue(0)===0n){instructionPointer=Number(getValue(1));}break;case7:localCodes[getAddress(2)]=BigInt(getValue(0)<getValue(1));break;case8:localCodes[getAddress(2)]=BigInt(getValue(0)===getValue(1));break;case9:relativeBase+=Number(getValue(0));break;}}for(constinstructionofgetInstructions()){if(instruction.opcode===99){return;}constoutput=execute(instruction);if(typeofoutput==='bigint'){yieldoutput;}}}for(constpartof[1n,2n]){constprogram=createProgramInstance(codes,part);console.log(`# Part ${part}`);for(constvalueofprogram){console.log(String(value));}}
Running times:
~2.5 ms
~370 ms
Hardware: MacBook Pro mid-2015
As usual, my text and input can be found on my repo.
BTW, I'm dead last in the leaderboards among those who completed all 9 days 😂 Jon, you're ahead of me without today!
Well, let's hope we won't have to implement more! 😄
After all we already have basic arithmetic, I/O, conditional jumps, comparisons and pointer manipulation... What else do we need for a basic processor?
Today's addition was simple enough. For safe access to "not yet allocated" memory, I created 2 new helper functions:
; Reads a value from memory(defnread-mem[process-stateaddress](let[mem(:memoryprocess-state)](if(>=address(countmem))0(memaddress)))); Writes a value to memory and returns the new process state(defnwrite-mem[process-stateaddressvalue](let[mem(:memoryprocess-state)](if(>=address(countmem))(assocprocess-state:memory(conj(intomem(repeat(-address(countmem))0))value))(assoc-inprocess-state[:memoryaddress]value))))
And after changing the instruction type from int to long (which is the default number type in clojure anyway), I could just add the new stuff to my existing framework:
; new parameter mode function(fn[process-stateaddress](+(read-memprocess-stateaddress)(:rel-baseprocess-state))); new opcode(defrel-base-offset-opcode{:operator(fn[process-stateoffset-pointer](->process-state(update:rel-base+(read-memprocess-stateoffset-pointer))(update:pointer+2))):params1})
I've been sending input and read output "manually", but it worked well enough for day 7. Interestingly, I learned something about ruby today: arrays are essentially unbounded! so i didn't have worry about the memory issue, I could just read/write to where in the array I wanted and if the array was too short, I'd just read out a nil instead of getting some form of IndexOutOfBoundsError or something.
I made this comment somewhere else in the thread, but the fact that opcode 09 could also work in relative mode, (and that we could write to addresses in relative mode as well) threw me off, I spent way too long trying to track that bug down.
classIntCodedefinitialize(instructions)@instructions=instructions@ptr=0@in_buff=[]@out_buff=[]@rel_base=0@blocked=falseenddefsend_input(thing)@in_buff.push(thing)enddefread_output()return@out_buff.shift()enddefinspect()puts@instructions.to_sputs@out_buff.to_senddefisBlocked()return@blockedenddefread_mem(idx)ifidx<0puts"wat: negative index"endval=@instructions[idx]ifval==nil@instructions[idx]=0return0elsereturnvalendenddefwrite_mem(idx)enddefrun()@blocked=falsewhile@ptr<@instructions.lengthdo# puts @ptr, @instructions.to_sbase_op=read_mem(@ptr)# puts base_opop=base_op%100# get last 2 digitsflags=base_op/100# top n digitsarg1=read_value(@instructions,@ptr+1,flags%10)ifop==1flags=flags/10arg2=read_value(@instructions,@ptr+2,flags%10)flags=flags/10arg3=read_value(@instructions,@ptr+3,flags%10)r=read_mem(arg1)+read_mem(arg2)@instructions[arg3]=r@ptr+=4elsifop==2flags=flags/10arg2=read_value(@instructions,@ptr+2,flags%10)flags=flags/10arg3=read_value(@instructions,@ptr+3,flags%10)r=read_mem(arg1)*read_mem(arg2)@instructions[arg3]=r@ptr+=4elsifop==3if@in_buff.empty?# puts "waiting for input"@blocked=truereturnfalseendinput=@in_buff.shift()# puts "got input #{input}, putting in location #{arg1}"@instructions[arg1]=input.to_i@ptr+=2elsifop==4output=read_mem(arg1)@out_buff.push(output)# puts "output: #{output}"@ptr+=2elsifop==5flags=flags/10arg2=read_value(@instructions,@ptr+2,flags%10)ifread_mem(arg1)!=0@ptr=read_mem(arg2)else@ptr+=3endelsifop==6flags=flags/10arg2=read_value(@instructions,@ptr+2,flags%10)ifread_mem(arg1)==0@ptr=read_mem(arg2)else@ptr+=3endelsifop==7flags=flags/10arg2=read_value(@instructions,@ptr+2,flags%10)flags=flags/10arg3=read_value(@instructions,@ptr+3,flags%10)ifread_mem(arg1)<read_mem(arg2)@instructions[arg3]=1else@instructions[arg3]=0end@ptr+=4elsifop==8flags=flags/10arg2=read_value(@instructions,@ptr+2,flags%10)flags=flags/10arg3=read_value(@instructions,@ptr+3,flags%10)ifread_mem(arg1)==read_mem(arg2)@instructions[arg3]=1else@instructions[arg3]=0end@ptr+=4elsifop==9@rel_base+=read_mem(arg1)# puts "updated relative base to #{@rel_base}"@ptr+=2elsifop==99# puts "halting!"breakelseputs"wat"return@instructionsendendreturn@instructionsenddefread_value(instructions,arg,flag)ifflag==1returnargelsifflag==2v=read_mem(arg)+@rel_basereturnvelsereturnread_mem(arg)endendendif__FILE__==$0instructions=[]File.open(ARGV[0],"r")do|file_handle|file_handle.each_linedo|line|instructions=line.split(",").map{|n|n.to_i}breakendendvm=IntCode.new(instructions)vm.send_input(2)vm.run()putsvm.read_output()end
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.
Had a rough time hunting down some issues that caused all of the available test cases to pass but failed my puzzle input. Turns out I should have been using "x % 10" to get the one's digit, not "x % 3" like I had.
Also, I feel like the specification for how opcode 3 (read input) works with this new relative parameter mode wasn't made super clear. But it worked out in the end. Here's my rust solution:
/// Day 9: Sensor Boost/// /// Boost sensors with relative Intcode parameters.usestd::fs;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/day9.txt").unwrap();letcleaned=text.trim();cleaned.split(",").map(|c|c.parse().unwrap()).collect()}pubfnrun(){letnumbers=parse_input();letmuta=IntcodeInterpreter::new(numbers);a.push_input(2);a.run();println!("Result: {}",a.shift_output());}
And my Intcode Interpreter:
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);}}
My big deal was making the Intcode computer fully backwards compatible with Day 5 and 7 as well as making it run for Day 9. (I haven't tried it with Day 2, though for some reason there's a part of my brain that thinks that is perhaps irreconcilable with that day).
I felt like the directions to this one were incredibly unclear. Should the program be able to write in the original instruction space or not? "Memory beyond the initial program starts with the value 0 and can be read or written like any other memory. (It is invalid to try to access memory at a negative address, though.)" What does "beyond" mean here? How do you differentiate between "beyond" memory and "any other memory," particularly if you can't "access memory at a negative space"? It was also unclear that the "beyond" memory was actually initialized with zeros. (I originally assumed that the program wouldn't attempt to access uninitialized space, but that ended up being proved wrong almost immediately.)
Still, this implementation served me pretty well:
fromenumimportEnumclassOperation(Enum):ADDITION=1MULTIPLICATION=2INPUT=3OUTPUT=4JUMP_IF_TRUE=5JUMP_IF_FALSE=6LESS_THAN=7EQUALS=8RELATIVE_BASE=9TERMINATION=99classMode(Enum):POSITION=0IMMEDIATE=1RELATIVE=2classInstruction:def__init__(self,opcode):# instruction: 1 is add, 2 is multiply, 3 is input, 4 is output, 99 is end
self.operation=Operation(_get_nth_digit(1,opcode)*10+_get_nth_digit(0,opcode))# mode: 0 is indirect, 1 is immediate
self.modes=list(map(Mode,[_get_nth_digit(2,opcode),_get_nth_digit(3,opcode),_get_nth_digit(4,opcode)]))def__str__(self):return"{}, {}".format(repr(self.operation),self.modes)classProgramState:def__init__(self,ops,output=None,address=0,memory={},rel_base=0,done=False):self.ops=ops# the instruction set
self.output=output# any previous output
self.address=address# index of next instruction to execute
self.memory=memory# the memory heap
self.rel_base=rel_base# the relative base from which to calculate relative addresses
self.done=done# flag to indicate whether this program has hit opcode 99
def__repr__(self):return"Last Output: {}, Rel Base: {}. Op Address: {}".format(self.output,self.rel_base,self.address)defrun(state,inp):return_run(state.ops,inp,state.address,state.output,state.memory,state.rel_base)def_run(ops,input,starting_addr,last_output,memory,rel_base):# start at the front of the inputs
input_idx=0# no output yet
output=last_output# assign to i for brevity
i=starting_addrwhileops[i]!=99:instruction=Instruction(ops[i])ifinstruction.operationisOperation.ADDITION:first=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)second=_get_resolved_arg(instruction,ops,memory,rel_base,i,2)destination=_get_resolved_position(instruction,ops,rel_base,i,3)_write(first+second,destination,ops,memory)i+=4elifinstruction.operationisOperation.MULTIPLICATION:first=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)second=_get_resolved_arg(instruction,ops,memory,rel_base,i,2)destination=_get_resolved_position(instruction,ops,rel_base,i,3)_write(first*second,destination,ops,memory)i+=4elifinstruction.operationisOperation.INPUT:destination=_get_resolved_position(instruction,ops,rel_base,i,1)_write(int(input[input_idx]),destination,ops,memory)input_idx+=1i+=2elifinstruction.operationisOperation.OUTPUT:output=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)i+=2returnProgramState(ops,output,i,memory,rel_base,False)elifinstruction.operationisOperation.JUMP_IF_TRUE:first=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)second=_get_resolved_arg(instruction,ops,memory,rel_base,i,2)iffirst!=0:i=secondelse:i+=3elifinstruction.operationisOperation.JUMP_IF_FALSE:first=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)second=_get_resolved_arg(instruction,ops,memory,rel_base,i,2)iffirst==0:i=secondelse:i+=3elifinstruction.operationisOperation.LESS_THAN:first=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)second=_get_resolved_arg(instruction,ops,memory,rel_base,i,2)destination=_get_resolved_position(instruction,ops,rel_base,i,3)_write(1iffirst<secondelse0,destination,ops,memory)i+=4elifinstruction.operationisOperation.EQUALS:first=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)second=_get_resolved_arg(instruction,ops,memory,rel_base,i,2)destination=_get_resolved_position(instruction,ops,rel_base,i,3)_write(1iffirst==secondelse0,destination,ops,memory)i+=4elifinstruction.operationisOperation.RELATIVE_BASE:rel_offset=_get_resolved_arg(instruction,ops,memory,rel_base,i,1)rel_base+=rel_offseti+=2returnProgramState(ops,output,i,{},rel_base,True)# Returns the number at the given position (0 being the rightmost)
def_get_nth_digit(n,number):returnnumber//10**n%10def_get_resolved_arg(instruction,ops,memory,rel_base,address,arg):# ops[i+1] if instruction.modes[0] is Mode.IMMEDIATE else ops[ops[i+1]]
mode=instruction.modes[arg-1]ifmodeisMode.IMMEDIATE:returnops[address+arg]final_addr=ops[address+arg]# Here, mode is POSITION or RELATIVE
# if RELATIVE add the relative base
ifmodeisMode.RELATIVE:final_addr+=rel_basereturnops[final_addr]iffinal_addr<len(ops)elsememory.get(final_addr,0)def_get_resolved_position(instruction,ops,rel_base,address,arg):# ops[i+1] if instruction.modes[0] is Mode.IMMEDIATE else ops[ops[i+1]]
mode=instruction.modes[arg-1]ifmodeisMode.POSITION:returnops[address+arg]elifmodeisMode.RELATIVE:returnops[address+arg]+rel_baseelse:print("Bonkers! Unhandled case")def_write(value,destination,ops,memory):ifdestination<len(ops):ops[destination]=valueelse:memory[destination]=value
And the driver program for Day 9:
fromintcodeimportProgramStatefromintcodeimportrunwithopen('day09.txt')asf:# split line into operation list
opsAsStrings=f.read().split(",")# turn them all into integers
ops=list(map(int,opsAsStrings))defboost(ops,inp):outputs=[]state=run(ProgramState(ops),[inp])whilenotstate.done:print(state.output)outputs.append(state.output)state=run(state,[])print(state.memory)returnoutputs# Part One
print("Part One: %s"%boost(ops,1))print("Part Two: %s"%boost(ops,2))
Well that was tough! The new requirements revealed a few deficiencies with my IntCode emulator. My addressing modes were a mess for writes, but somehow made it this far anyway. The need to expand the memory on demand meant a substantial refactor. I also had to use a nonstandard (but widely supported) __int128 data type to support the big numbers required.
Printing large numbers is also lacking support in the C standard library. I had to cut a couple of corners...
char*print_opcode(opcoden){staticcharstr[50];if(n==0)return"0";else{char*s=str+sizeof(str)-1;intnegative=0;opcodex=n;if(x<0){negative=1;x=-x;// eek, minimum negative value edge case}for(*--s='\0';x!=0&&s!=str;x/=10){*--s='0'+(x%10);}if(negative)*--s='-';returns;// eek, not thread safe}}
As part of my debugging I had it trace the execution using made-up assembly language:
Part 1
0000 1102 mul 34463338,34463338
0004 1007 lt 1187721666102244,34463338
0008 1005 jnz 0,53
0011 1101 add 0,3
0015 109 base 988
0017 209 base 3
0019 9 base 3
0021 209 base 3
0023 209 base 3
0025 203 in 1
0027 1008 eq 1,1
0031 1005 jnz 1,65
0065 1102 mul 32,1
0069 1101 add 0,500
0073 1101 add 0,636
0077 1102 mul 36,1
0081 1101 add 0,29
0085 1102 mul 864,1
0089 1102 mul 21,1
One advantage of using C is speed though. We were warned it might take time to run but the tests and both parts of my implementation run in 84 milliseconds!
Full code here. I've enjoyed my return to C programming but I'm quietly hoping for something using a high-level language tomorrow!
woof, here's my new Kotlin intcode parser, as the day's specific code is now as simple as loading the file, splitting it, and running it.
Key rewrite pieces:
More monads.
Redid my janky parameter reader.
Switched from arrays to maps. (GIGANTIC SPEEDUP)
Kotlin data classes come with a copy function! Using constructors to manually do the same thing was the final and most pernicious bug. USE THE copy FUNCTION WHEN PRESERVING IMMUTABILITY!
packageintcodeimportarrow.core.*sealedclassMode{funassignable(first:Long,offset:Long)=when(this){isImmediate->throwError("Cannot assign to immediate value")isPosition->firstisRelative->(offset+first)}funvalueOf(first:Long,code:Map<Long,Long>,relativeBase:Long)=when(this){isImmediate->first.some()isPosition->code[first].toOption()isRelative->code[relativeBase+first].toOption()}.getOrElse{0L}objectImmediate:Mode()objectPosition:Mode()objectRelative:Mode()}data classCurrentState(valpointer:Option<Long>=0L.some(),valinputs:MutableList<Long>=mutableListOf(),valoutput:Option<Long>=Option.empty(),valrelativeBase:Long=0)operatorfunCurrentState.plus(n:Int)=copy(pointer=pointer.map{it+n})operatorfunCurrentState.plus(n:Long)=copy(pointer=pointer.map{it+n})funPair<Long,Mode>.index(state:CurrentState)=second.assignable(first,state.relativeBase)funPair<Long,Mode>.value(code:Map<Long,Long>,state:CurrentState)=second.valueOf(first,code,state.relativeBase)sealedclassInstruction{abstractvalopcodes:Intabstractfunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>openfunfindInputs(code:MutableMap<Long,Long>,state:CurrentState):Either<String,List<Pair<Long,Mode>>>=state.pointer.fold({emptyList<Pair<Long,Mode>>().right()},{pointer->(pointer+1..pointer+3).map{code[it]?:0}.zip(extractParameterType(pointer,code)).fold(listOf<Pair<Long,Mode>>().right()){a:Either<String,List<Pair<Long,Mode>>>,b->a.flatMap{acc->b.second.fold({"Pointer $pointer: Problem parsing input ${b.first}: $it".left()},{(acc+(b.firsttoit)).right()})}}})privatefunextractParameterType(pointer:Long,code:MutableMap<Long,Long>)="%010d".format((code[pointer]?:0)/100).takeLast(opcodes).reversed().map{when(it){'0'->Mode.Position.right()'1'->Mode.Immediate.right()'2'->Mode.Relative.right()else->"Bad mode $it".left()}}sealedclassThreeParameterInstruction:Instruction(){overridevalopcodes:Int=3classAdd:ThreeParameterInstruction(){overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>{code[params[2].index(state)]=params[0].value(code,state)+params[1].value(code,state)return(state+4).right()}}classMultiply:ThreeParameterInstruction(){overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>{code[params[2].index(state)]=params[0].value(code,state)*params[1].value(code,state)return(state+4).right()}}classLessThan:ThreeParameterInstruction(){overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>{code[params[2].index(state)]=when{params[0].value(code,state)<params[1].value(code,state)->1Lelse->0L}return(state+4).right()}}classEqual:ThreeParameterInstruction(){overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>{code[params[2].index(state)]=when{params[0].value(code,state)==params[1].value(code,state)->1else->0L}return(state+4).right()}}}sealedclassTwoParameterInstruction:Instruction(){overridevalopcodes:Int=2classJumpIfTrue:TwoParameterInstruction(){overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>{returnwhen(params[0].value(code,state)){0L->state+3else->state.copy(pointer=params[1].value(code,state).some())}.right()}}classJumpIfFalse:TwoParameterInstruction(){overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>=when(params[0].value(code,state)){0L->state.copy(pointer=params[1].value(code,state).some())else->state+3}.right()}}classSetFromInput(privatevalinputOption:Option<Long>):Instruction(){overridevalopcodes:Int=1overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState)=inputOption.fold({state},{input->code[params[0].index(state)]=inputstate.copy(pointer=state.pointer.map{it+2})}).right()}classOutput:Instruction(){overridevalopcodes:Int=1overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>{println("OUTPUT: ${params[0].value(code, state)}")returnstate.copy(pointer=state.pointer.map{it+2},output=params[0].value(code,state).some()).right()}}classModifyRelativeBase:Instruction(){overridevalopcodes:Int=1overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>{returnstate.copy(pointer=state.pointer.map{it+2},relativeBase=state.relativeBase+params[0].value(code,state)).right()}}objectEnd:Instruction(){overridevalopcodes:Int=0overridefunexecute(code:MutableMap<Long,Long>,params:List<Pair<Long,Mode>>,state:CurrentState):Either<String,CurrentState>=state.copy(pointer=Option.empty()).right()}}funparseInstruction(instruction:Long,input:MutableList<Long>):Either<String,Pair<Instruction,MutableList<Long>>>=when(instruction%100){1L->(Instruction.ThreeParameterInstruction.Add()toinput).right()2L->(Instruction.ThreeParameterInstruction.Multiply()toinput).right()3L->(Instruction.SetFromInput(input.firstOrNone())toinput.drop(1).toMutableList()).right()4L->(Instruction.Output()toinput).right()5L->(Instruction.TwoParameterInstruction.JumpIfTrue()toinput).right()6L->(Instruction.TwoParameterInstruction.JumpIfFalse()toinput).right()7L->(Instruction.ThreeParameterInstruction.LessThan()toinput).right()8L->(Instruction.ThreeParameterInstruction.Equal()toinput).right()9L->(Instruction.ModifyRelativeBase()toinput).right()99L->(Instruction.Endtoinput).right()else->"Problem parsing instruction $instruction".left()}funhandleCodePoint(code:MutableMap<Long,Long>,eitherState:Either<String,CurrentState>):Either<String,CurrentState>=eitherState.flatMap{state->state.pointer.fold({"Program has stopped.".left()},{pointer->code[pointer].rightIfNotNull{"Code point $pointer undefined."}.flatMap{codeValue->parseInstruction(codeValue,state.inputs).flatMap{(instr,inp)->instr.findInputs(code,state).flatMap{params->instr.execute(code,params,state.copy(pointer=pointer.some(),inputs=inp))}}}})}funstep(code:MutableMap<Long,Long>,state:CurrentState):Either<String,Long>{returnstep(code,state.right())}tailrecfunstep(code:MutableMap<Long,Long>,state:Either<String,CurrentState>):Either<String,Long>=when(state){isEither.Left<String>->"Error: ${state.a}".left()isEither.Right<CurrentState>->{when(state.b.pointer){isNone->state.b.output.fold({"No output".left()},{it.right()})isSome<Long>->step(code,handleCodePoint(code,state))}}}
I really enjoy these IntCode challenges, especially when you have a problem in your code and find that the program from the problem statement is showing you where it's wrong 🤩
OH MY GOD! Again opcode computer. I tried many time but couldn't create the perfect computer (with swift). Might take a break and come back with FRESH, from Scratch opcode computer and post it later.
So, we're going to work with Intcodes every other day? 😩
The worst part is that, since we're reserving two digit for the opcodes, I expect we're going to work with them again in the future (even though it says "You now have a complete Intcode computer.")
Moreover, the problem forgot to mention that when we write back to the memory, it could be done in relative mode too and not just position mode. Thanks 🤦♂️
But anyway... JavaScript with generators blah blah. I lost quite some time trying to understand why my solution didn't work... Until I realized I was passing the input values incorrectly 😵 I have none but myself to blame there...
Only new thing: the use of JavaScript's
BigInt. Hooray for ES2020!Solution for both parts:
Running times:
Hardware: MacBook Pro mid-2015
As usual, my text and input can be found on my repo.
BTW, I'm dead last in the leaderboards among those who completed all 9 days 😂 Jon, you're ahead of me without today!
this burned me, i sat there for 30 minutes trying to figure out what i was doing wrong
I believe the two digits are just there because of opcode 99 :)
And that would make ten opcodes so far, right.
Well, let's hope we won't have to implement more! 😄
After all we already have basic arithmetic, I/O, conditional jumps, comparisons and pointer manipulation... What else do we need for a basic processor?
We're in uncharted waters! I think this is first year we've had so much refactoring/reuse work to do. (Definitely the earliest)
It's been pretty frustrating going, but getting things to work has been satisfying as heck.
JS Solution w/ generators again
I like being able to "plug in" the IO implementation at runtime with the yields, it's almost like algebraic effects in JS
Dope! Ive started doing this but it was taking me too long, checkout my solutions at github.com/LeonFedotov/advent-of-code
Hi, a (very wordy) Python solution using a generator function.
Getting output is done by running:
then...
Part 1
or Part 2:
"""
Hi,
now i am learning python
i also wrote a program in very basic
but i did not get the answer
can u give me any hint
"""
import numpy as np
f = open("input9","r") # file opening
code = f.read() + ',0' * 1000 # for reading files with commas(,) as list
nList = code.split(',')
f.close() # file closing
print(nList)
for i in range(0, len(nList)): # converting elements of List(strings) into integers
nList[i] = int(nList[i])
print(len(nList))
def get_digit(number, n):
return number // 10**n % 10
def intcode(nList,in1):
List = nList.copy()
for i,each in enumerate(nList):
List[i] = int(each)
i = 0
rb = 0
boost_program = intcode(nList,1)
print(boost_program)
print(intcode(boost_program,1))[1]
I'll be posting my other attempts to: github.com/devChad/advent_of_code
Today's addition was simple enough. For safe access to "not yet allocated" memory, I created 2 new helper functions:
And after changing the instruction type from int to long (which is the default number type in clojure anyway), I could just add the new stuff to my existing framework:
As always, here's the whole code: github.com/jkoenig134/AdventOfCode...
I've been sending input and read output "manually", but it worked well enough for day 7. Interestingly, I learned something about ruby today: arrays are essentially unbounded! so i didn't have worry about the memory issue, I could just read/write to where in the array I wanted and if the array was too short, I'd just read out a
nilinstead of getting some form ofIndexOutOfBoundsErroror something.I made this comment somewhere else in the thread, but the fact that opcode
09could also work in relative mode, (and that we could write to addresses in relative mode as well) threw me off, I spent way too long trying to track that bug down.Had a rough time hunting down some issues that caused all of the available test cases to pass but failed my puzzle input. Turns out I should have been using "x % 10" to get the one's digit, not "x % 3" like I had.
Also, I feel like the specification for how opcode 3 (read input) works with this new relative parameter mode wasn't made super clear. But it worked out in the end. Here's my rust solution:
And my Intcode Interpreter:
My big deal was making the Intcode computer fully backwards compatible with Day 5 and 7 as well as making it run for Day 9. (I haven't tried it with Day 2, though for some reason there's a part of my brain that thinks that is perhaps irreconcilable with that day).
I felt like the directions to this one were incredibly unclear. Should the program be able to write in the original instruction space or not? "Memory beyond the initial program starts with the value 0 and can be read or written like any other memory. (It is invalid to try to access memory at a negative address, though.)" What does "beyond" mean here? How do you differentiate between "beyond" memory and "any other memory," particularly if you can't "access memory at a negative space"? It was also unclear that the "beyond" memory was actually initialized with zeros. (I originally assumed that the program wouldn't attempt to access uninitialized space, but that ended up being proved wrong almost immediately.)
Still, this implementation served me pretty well:
And the driver program for Day 9:
Well that was tough! The new requirements revealed a few deficiencies with my IntCode emulator. My addressing modes were a mess for writes, but somehow made it this far anyway. The need to expand the memory on demand meant a substantial refactor. I also had to use a nonstandard (but widely supported)
__int128data type to support the big numbers required.Printing large numbers is also lacking support in the C standard library. I had to cut a couple of corners...
As part of my debugging I had it trace the execution using made-up assembly language:
One advantage of using C is speed though. We were warned it might take time to run but the tests and both parts of my implementation run in 84 milliseconds!
Full code here. I've enjoyed my return to C programming but I'm quietly hoping for something using a high-level language tomorrow!
woof, here's my new Kotlin intcode parser, as the day's specific code is now as simple as loading the file, splitting it, and running it.
Key rewrite pieces:
copyFUNCTION WHEN PRESERVING IMMUTABILITY!I was unpleasantly tired yesterday so failed to complete in time, leaving me behind on day 10, too. But at least I got day 9 done.
There's a lot of code, so I've left it in a gist:
I really enjoy these IntCode challenges, especially when you have a problem in your code and find that the program from the problem statement is showing you where it's wrong 🤩
Hi 😙
My solutions are here: github.com/LeonFedotov/advent-of-code
OH MY GOD! Again opcode computer. I tried many time but couldn't create the perfect computer (with swift). Might take a break and come back with FRESH, from Scratch opcode computer and post it later.
It took some time but finally solved with Swift.
Code can be found here: github.com/rizwankce/AdventOfCode/...