First puzzle
As an electronic engineer, this puzzle is fascinating to me. A digital circuit needs to be simulated, and the puzzle solution is the value of one of the wires after everything is connected. This type of problems is very common while you are learning digital electronics. I encounter this again after so long, and the fact is that I have never tried to write code to do this. There was some software for simulating this or you need to do it yourself on a test. The puzzle input is the description of the circuit to be simulated. The circuit is described as a set of wires and gates connecting those wires. The values on the wires are represented as a 16-bit value. Here are the gates definitions:
- Value gate: This is just an assignment of a value to a gate. It is represented as VALUE -> GATE. Ex. 123 -> x
- AND gate: Bitwise AND operation between two wires or between a wire and a value GATE_A AND GATE_B -> GATE. Ex. x AND y -> z
- OR gate: Bitwise OR operation between two wires or between a wire and a value GATE_A OR GATE_B -> GATE. Ex. x OR y -> z
- Left-shift gate: Bitshift to the left by some bits count GATE_A LSHIFT BITS_COUNT -> GATE. Ex. x LSHIFT 2 -> y
- Right-shift: Bitshift to the right by some bits count GATE_A RSHIFT BITS_COUNT -> GATE. Ex. x RSHIFT 2 -> y
- Not gate: Bitwise inversion of the input gate bits NOT GATE_A -> GATE. Ex. NOT x -> y
The author provides a sample circuit to try your program. Very important because it is very easy to make a mistake:
Sample circuit:
- 123 -> x
- 456 -> y
- x AND y -> d
- x OR y -> e
- x LSHIFT 2 -> f
- y RSHIFT 2 -> g
- NOT x -> h
- NOT y -> i
Wire’s values:
- d: 72
- e: 507
- f: 492
- g: 114
- h: 65412
- i: 65079
- x: 123
- y: 456
We need to find the value of the wire “a” based on the puzzle input, but first, we need to parse and model the input to make our life easier. Using regular expressions, each gate connection is converted to a case class:
| trait WireOutput { | |
| def output: String | |
| } | |
| case class Not(input: String, output: String) extends WireOutput | |
| case class Value(input: Int, output: String) extends WireOutput | |
| case class Connection( input: String, output: String) extends WireOutput | |
| case class And(input1: String, input2: String, output: String) extends WireOutput | |
| case class AndWithValue(input1: Int, input2: String, output: String) extends WireOutput | |
| case class Or(input1: String, input2: String, output: String) extends WireOutput | |
| case class LShift(input: String, shift: Int, output: String) extends WireOutput | |
| case class RShift(input: String, shift: Int, output: String) extends WireOutput | |
| val notRx = """NOT ([a-z]+) -> ([a-z]+)""".r | |
| val valueRx = """([0-9]+) -> ([a-z]+)""".r | |
| val connectionRx = """([a-z]+) -> ([a-z]+)""".r | |
| val andRx = """([a-z]+) AND ([a-z]+) -> ([a-z]+)""".r | |
| val andWithValueRx = """([0-9]+) AND ([a-z]+) -> ([a-z]+)""".r | |
| val orRx = """([a-z]+) OR ([a-z]+) -> ([a-z]+)""".r | |
| val lShiftRx = """([a-z]+) LSHIFT ([0-9]+) -> ([a-z]+)""".r | |
| val rShiftRx = """([a-z]+) RSHIFT ([0-9]+) -> ([a-z]+)""".r | |
| def parseCircuit( raw:String ) : Array[WireOutput] = | |
| raw.split('\n').map { | |
| case notRx(i, o) => Not(i, o) | |
| case valueRx(i, o) => Value(i.toInt, o) | |
| case connectionRx(i, o) => Connection(i, o) | |
| case andRx(i1, i2, o) => And(i1, i2, o) | |
| case andWithValueRx(i1, i2, o) => AndWithValue(i1.toInt, i2, o) | |
| case orRx(i1, i2, o) => Or(i1, i2, o) | |
| case lShiftRx(i, shift, o) => LShift(i, shift.toInt, o) | |
| case rShiftRx(i, shift, o) => RShift(i, shift.toInt, o) | |
| } | |
| val circuit : Array[WireOutput] = parseCircuit(input) |
To calculate the final value of a wire, we can go backwards using recursion. Ex. Find the gate connected to the wire, then calculate the inputs and apply the gate operation:
| def WireValue( id: String, state: Map[String, Int] )( s: Array[WireOutput]) : (Int, Map[String,Int]) = { | |
| if ( state.contains(id) ) { | |
| (state(id), state ) | |
| } else { | |
| s find( _.output == id) match { | |
| case Some(Not(input, output) ) => { | |
| val (inputValue, otherState) = WireValue(input, state)(s) | |
| (~inputValue, otherState + ( output -> ~inputValue) ) | |
| } | |
| case Some(Value(input, output) ) => { | |
| ( input, state + ( output -> input ) ) | |
| } | |
| case Some(Connection(input, output) ) => { | |
| val (inputValue, otherState) = WireValue(input, state)(s) | |
| ( inputValue, otherState + ( output -> inputValue) ) | |
| } | |
| case Some(And(input1, input2, output) ) => { | |
| val ( input1Value, state1 ) = WireValue(input1, state )(s) | |
| val ( input2Value, state2 ) = WireValue(input2, state1 )(s) | |
| val outputValue = input1Value & input2Value | |
| ( outputValue, state2 + ( output -> outputValue )) | |
| } | |
| case Some(AndWithValue(input1, input2, output) ) => { | |
| val ( input2Value, state2 ) = WireValue(input2, state )(s) | |
| val outputValue = input1 & input2Value | |
| ( outputValue, state2 + ( output -> outputValue )) | |
| } | |
| case Some(Or(input1, input2, output) ) => { | |
| val ( input1Value, state1 ) = WireValue(input1, state )(s) | |
| val ( input2Value, state2 ) = WireValue(input2, state1 )(s) | |
| val outputValue = input1Value | input2Value | |
| ( outputValue, state2 + ( output -> outputValue )) | |
| } | |
| case Some(LShift(input1, shift, output) ) => { | |
| val ( input1Value, state1 ) = WireValue(input1, state )(s) | |
| val outputValue = input1Value << shift | |
| ( outputValue, state1 + ( output -> outputValue )) | |
| } | |
| case Some(RShift(input1, shift, output) ) => { | |
| val ( input1Value, state1 ) = WireValue(input1, state )(s) | |
| val outputValue = input1Value >> shift | |
| ( outputValue, state1 + ( output -> outputValue )) | |
| } | |
| case _ => (Int.MinValue, state) | |
| } | |
| } | |
| } | |
| val a = WireValue( "a", Map() )(circuit)._1 |
Second puzzle
For the second puzzle, we are asked to reset all the wired to zero, and to assign the first puzzle solution to the wire “b”. It can be done creating another circuit where there are no values assigned to any wire by filtering the first puzzle circuit eliminating all the Value case classes, and adding an assignment to the wire “b”. The puzzle solution continues to be the value of wire “a”:
| val newCircuitWithNoValues = circuit.filter{ | |
| case Value(_,_) => false | |
| case _ => true | |
| } | |
| val newCircuit = newCircuitWithNoValues :+ Value(a, "b") // a is first puzzle solution. | |
| val second_a = WireValue( "a", Map() )(newCircuit)._1 |
You can find this code along with my input and puzzle answers at here.