Machine simulations have come up before in Advent of Code and are fun to implement. This one is an interesting twist. As I read the description I thought we were going to have to decipher the opcodes, but fortunately part 1 is a bit simpler than that.
Parsing
Complex text structure again. You know what that means! A data model and a JParsec parser.
data classRegisters(valregs:IntArray)data classArguments(vala:Int,valb:Int,valc:Int)data classInstruction(valopcode:Int,valarguments:Arguments)data classSample(valbefore:Registers,valinstruction:Instruction,valafter:Registers)data classInput(valsamples:List<Sample>,valprogram:List<Instruction>)funparse(input:String):Input{valinteger:Parser<Int>=INTEGER.map(String::toInt)valregisters=integer.sepBy(string(", ")).between(string("["),string("]")).map(::Registers)valbefore=string("Before: ").next(registers)valafter=string("After: ").next(registers)valarguments=sequence(integer,WHITESPACES.next(integer),WHITESPACES.next(integer),::Arguments)valinstruction=sequence(integer,WHITESPACES.next(arguments),::Instruction)valsample=sequence(before,WHITESPACES.next(instruction),WHITESPACES.next(after),::Sample)valsamples=sample.sepBy(WHITESPACES)valprogram=instruction.sepBy(WHITESPACES)returnsequence(samples.followedBy(WHITESPACES),program,::Input).parse(input.trim())}
Machine simulation
At first I wrote all the instructions out as Kotlin functions but then decided it might be better to encode them as lambdas along with additional information such as the name. I wrote them as destructive in-place operations on a Registers since I have the feeling we're going to have to run the program at some point!
data classOperation(valname:String,valrun:(Registers,Arguments)->Unit)valoperations:List<Operation>=listOf(Operation("addr",{r,(a,b,c)->r[c]=r[a]+r[b]}),Operation("addi",{r,(a,b,c)->r[c]=r[a]+b}),Operation("mulr",{r,(a,b,c)->r[c]=r[a]*r[b]}),Operation("muli",{r,(a,b,c)->r[c]=r[a]*b}),Operation("banr",{r,(a,b,c)->r[c]=r[a]andr[b]}),Operation("bani",{r,(a,b,c)->r[c]=r[a]andb}),Operation("borr",{r,(a,b,c)->r[c]=r[a]orr[b]}),Operation("bori",{r,(a,b,c)->r[c]=r[a]orb}),Operation("setr",{r,(a,_,c)->r[c]=r[a]}),Operation("seti",{r,(a,_,c)->r[c]=a}),Operation("gtri",{r,(a,b,c)->r[c]=if(r[a]>b)1else0}),Operation("gtir",{r,(a,b,c)->r[c]=if(a>r[b])1else0}),Operation("gtrr",{r,(a,b,c)->r[c]=if(r[a]>r[b])1else0}),Operation("eqri",{r,(a,b,c)->r[c]=if(r[a]==b)1else0}),Operation("eqir",{r,(a,b,c)->r[c]=if(a==r[b])1else0}),Operation("eqrr",{r,(a,b,c)->r[c]=if(r[a]==r[b])1else0}))
Part 1
Since we need to run different instructions over the same input data we really need non-destructive versions of these operations. That's possible with a simple wrapper.
Now we really have to map opcodes to instructions! This is an extension of the part 1 puzzle where the samples are matches to opcodes. We have to deduce the unique mapping of opcodes to instructions however. My algorithm for this was:
For each sample and each operation
if the operation matches the sample output, add it to the possible set for that opcode
if the operation does not match the sample output, add it to the impossible set for that opcode
Each opcode's resolved set is its possible operations minus its impossible operations
While any opcode's resolved set is not a single operation
find all the opcodes which have resolved to a single operation
remove that operation from all other opcodes
In Kotlin:
funmatchOpcodes(input:Input):Map<Int,PureOperation>{data classMatch(valpossible:MutableSet<PureOperation>,valnotPossible:MutableSet<PureOperation>){valresolve:Set<PureOperation>get()=possible-notPossiblevalisResolved:Booleanget()=resolve.size==1overridefuntoString():String=resolve.toString()}valmatches=mutableMapOf<Int,Match>()(0..15).forEach{i->matches[i]=Match(mutableSetOf(),mutableSetOf())}input.samples.forEach{sample->pureOperations.forEach{op->valmatch=matches[sample.instruction.opcode]!!if(sample.matches(op))match.possible+=opelsematch.notPossible+=op}}while(matches.any{(_,m)->!m.isResolved}){matches.filter{(_,m)->m.isResolved}.forEach{(opcode,resolvedMatch)->matches.filter{(key,_)->key!=opcode}.forEach{(_,match:Match)->match.notPossible+=resolvedMatch.resolve}}}if(matches.any{e->!e.value.isResolved})throwIllegalStateException("failed to match all opcodes: $matches")returnmatches.mapValues{entry->entry.value.resolve.first()}}
Running the program is a simple fold over the registers. Turns out I didn't need my in-place destructive operations after all, so there's a possible refactor there.
Machine simulations have come up before in Advent of Code and are fun to implement. This one is an interesting twist. As I read the description I thought we were going to have to decipher the opcodes, but fortunately part 1 is a bit simpler than that.
Parsing
Complex text structure again. You know what that means! A data model and a JParsec parser.
Machine simulation
At first I wrote all the instructions out as Kotlin functions but then decided it might be better to encode them as lambdas along with additional information such as the name. I wrote them as destructive in-place operations on a
Registers
since I have the feeling we're going to have to run the program at some point!Part 1
Since we need to run different instructions over the same input data we really need non-destructive versions of these operations. That's possible with a simple wrapper.
Checking the number of operations which match a sample is easy;
And checking the number of samples which pass this test is similar:
Part 2
Now we really have to map opcodes to instructions! This is an extension of the part 1 puzzle where the samples are matches to opcodes. We have to deduce the unique mapping of opcodes to instructions however. My algorithm for this was:
In Kotlin:
Running the program is a simple fold over the registers. Turns out I didn't need my in-place destructive operations after all, so there's a possible refactor there.
Full code on github