Advent of Code 2019 Day 7 (simple emulator, opcode processing)

Question

Since couple of days ago I started to learn python by doing AoC 2019. I would like to share with you my solution to day7 (Amplification Circuit) part 1 and part 2.

Challenge summary:

--- Day 7: Amplification Circuit ---

==================== Part 1 ====================

There are five amplifiers connected in series; each one receives an input signal and produces an output signal. They are connected such that the first amplifier's output leads to the second amplifier's input, the second amplifier's output leads to the third amplifier's input, and so on. The first amplifier's input value is 0, and the last amplifier's output leads to your ship's thrusters.

    O-------O  O-------O  O-------O  O-------O  O-------O
0 ->| Amp A |->| Amp B |->| Amp C |->| Amp D |->| Amp E |-> (to thrusters)
    O-------O  O-------O  O-------O  O-------O  O-------O

The Elves have sent you some Amplifier Controller Software (your puzzle input), a program that should run on your existing Intcode computer. Each amplifier will need to run a copy of the program.

For example, suppose you want to try the phase setting sequence 3,1,2,4,0, which would mean setting amplifier A to phase setting 3, amplifier B to setting 1, C to 2, D to 4, and E to 0. Then, you could determine the output signal that gets sent from amplifier E to the thrusters with the following steps:

Start the copy of the amplifier controller software that will run on amplifier A. At its first input instruction, provide it the amplifier's phase setting, 3. At its second input instruction, provide it the input signal, 0. After some calculations, it will use an output instruction to indicate the amplifier's output signal. Start the software for amplifier B. Provide it the phase setting (1) and then whatever output signal was produced from amplifier A. It will then produce a new output signal destined for amplifier C. Start the software for amplifier C, provide the phase setting (2) and the value from amplifier B, then collect its output signal. Run amplifier D's software, provide the phase setting (4) and input value, and collect its output signal. Run amplifier E's software, provide the phase setting (0) and input value, and collect its output signal. The final output signal from amplifier E would be sent to the thrusters. However, this phase setting sequence may not have been the best one; another sequence might have sent a higher signal to the thrusters.

Here are some example programs:

Max thruster signal 43210 (from phase setting sequence 4,3,2,1,0):

3,15,3,16,1002,16,10,16,1,16,15,15,4,15,99,0,0

Max thruster signal 54321 (from phase setting sequence 0,1,2,3,4):

3,23,3,24,1002,24,10,24,1002,23,-1,23, 101,5,23,23,1,24,23,23,4,23,99,0,0

Max thruster signal 65210 (from phase setting sequence 1,0,4,3,2):

3,31,3,32,1002,32,10,32,1001,31,-2,31,1007,31,0,33, 1002,33,7,33,1,33,31,31,1,32,31,31,4,31,99,0,0,0

Try every combination of phase settings on the amplifiers. What is the highest signal that can be sent to the thrusters?

==================== Part 2 ====================

      O-------O  O-------O  O-------O  O-------O  O-------O
0 -+->| Amp A |->| Amp B |->| Amp C |->| Amp D |->| Amp E |-.
   |  O-------O  O-------O  O-------O  O-------O  O-------O |
   |                                                        |
   '--------------------------------------------------------+
                                                            |
                                                            v
                                                     (to thrusters)

Most of the amplifiers are connected as they were before; amplifier A's output is connected to amplifier B's input, and so on. However, the output from amplifier E is now connected into amplifier A's input. This creates the feedback loop: the signal will be sent through the amplifiers many times.

In feedback loop mode, the amplifiers need totally different phase settings: integers from 5 to 9, again each used exactly once. These settings will cause the Amplifier Controller Software to repeatedly take input and produce output many times before halting. Provide each amplifier its phase setting at its first input instruction; all further input/output instructions are for signals.

Don't restart the Amplifier Controller Software on any amplifier during this process. Each one should continue receiving and sending signals until it halts.

All signals sent or received in this process will be between pairs of amplifiers except the very first signal and the very last signal. To start the process, a 0 signal is sent to amplifier A's input exactly once.

Eventually, the software on the amplifiers will halt after they have processed the final loop. When this happens, the last output signal from amplifier E is sent to the thrusters. Your job is to find the largest output signal that can be sent to the thrusters using the new phase settings and feedback loop arrangement.

Try every combination of the new phase settings on the amplifier feedback loop. What is the highest signal that can be sent to the thrusters?

==================== Here is my solution ====================

I found it quite clever that I actually connected this amplifiers in such cascade manner in code. What do you think?

#!/usr/bin/env python3

import sys
import itertools
from queue import Queue

class amplifier(object):

    code = None

    def __init__(self, phase_input):
        self.pc = 0
        self.halted = False
        self.other_amplifier = None
        self.inputs = Queue()
        self.add_input(phase_input)
        self.outputs = []

    def set_other_amplifier(self, other_amplifier):
        self.other_amplifier = other_amplifier

    def has_other_amplifier(self):
        return self.other_amplifier is not None

    def add_input(self, _input):
        self.inputs.put(_input)

    def get_input(self):
        return self.inputs.get()

    def has_input(self):
        return not self.inputs.empty()

    def add_output(self, _output):
        if self.has_other_amplifier() and not self.other_amplifier.halted:
            self.other_amplifier.add_input(_output)
        else:
            self.outputs.append(_output)

    def run_program(self):
        ncp = amplifier.code.copy()
        i = self.pc
        while i < len(ncp):
            op = ncp[i]
            if op == 1:
                ncp[ncp[i+3]] = ncp[ncp[i+1]] + ncp[ncp[i+2]]
                i += 4
            elif op == 2:
                ncp[ncp[i+3]] = ncp[ncp[i+1]] * ncp[ncp[i+2]]
                i += 4
            elif op == 3:
                if self.has_input():
                    inp = self.get_input()
                    ncp[ncp[i+1]] = inp
                    i += 2
                else:
                    self.pc = i
                    if self.has_other_amplifier() and not self.other_amplifier.halted:
                        self.other_amplifier.run_program()
                    return
            elif op == 4:
                self.add_output(ncp[ncp[i+1]])
                i += 2
            elif op == 104:
                self.add_output(ncp[i+1])
                i += 2
            elif op == 5: # jump-if-true
                if ncp[ncp[i+1]] != 0:
                    i = ncp[ncp[i+2]]
                else:
                    i += 3
            elif op == 105:
                if ncp[i+1] != 0:
                    i = ncp[ncp[i+2]]
                else:
                    i += 3
            elif op == 1005:
                if ncp[ncp[i+1]] != 0:
                    i = ncp[i+2]
                else:
                    i += 3
            elif op == 1105:
                if ncp[i+1] != 0:
                    i = ncp[i+2]
                else:
                    i += 3
            elif op == 6: # jump-if-false
                if ncp[ncp[i+1]] == 0:
                    i = ncp[ncp[i+2]]
                else:
                    i += 3
            elif op == 106:
                if ncp[i+1] == 0:
                    i = ncp[ncp[i+2]]
                else:
                    i += 3
            elif op == 1006:
                if ncp[ncp[i+1]] == 0:
                    i = ncp[i+2]
                else:
                    i += 3
            elif op == 1106:
                if ncp[i+1] == 0:
                    i = ncp[i+2]
                else:
                    i += 3
            elif op == 7: # less than
                if ncp[ncp[i+1]] < ncp[ncp[i+2]]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 107:
                if ncp[i+1] < ncp[ncp[i+2]]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 1007:
                if ncp[ncp[i+1]] < ncp[i+2]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 1107:
                if ncp[i+1] < ncp[i+2]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 8: # equals 
                if ncp[ncp[i+1]] == ncp[ncp[i+2]]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 108:
                if ncp[i+1] == ncp[ncp[i+2]]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 1008:
                if ncp[ncp[i+1]] == ncp[i+2]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 1108:
                if ncp[i+1] == ncp[i+2]:
                    ncp[ncp[i+3]] = 1
                else:
                    ncp[ncp[i+3]] = 0
                i += 4
            elif op == 101: # addition
                ncp[ncp[i+3]] = ncp[i+1] + ncp[ncp[i+2]]
                i += 4
            elif op == 1001:
                ncp[ncp[i+3]] = ncp[ncp[i+1]] + ncp[i+2]
                i += 4
            elif op == 1101:
                ncp[ncp[i+3]] = ncp[i+1] + ncp[i+2]
                i += 4
            elif op == 102: # multiplication
                ncp[ncp[i+3]] = ncp[i+1] * ncp[ncp[i+2]]
                i += 4
            elif op == 1002:
                ncp[ncp[i+3]] = ncp[ncp[i+1]] * ncp[i+2]
                i += 4
            elif op == 1102:
                ncp[ncp[i+3]] = ncp[i+1] * ncp[i+2]
                i += 4
            elif op == 99:
                i = len(ncp)
            else:
                print(op, "opcode not supported")
                i += 1
        self.halted = True
        if self.has_other_amplifier() and not self.other_amplifier.halted:
            self.other_amplifier.run_program()

def get_signal(permutation_iter):
    a = amplifier(next(permutation_iter))
    a.add_input(0)

    b = amplifier(next(permutation_iter))
    c = amplifier(next(permutation_iter))
    d = amplifier(next(permutation_iter))
    e = amplifier(next(permutation_iter))

    a.set_other_amplifier(b)
    b.set_other_amplifier(c)
    c.set_other_amplifier(d)
    d.set_other_amplifier(e)
    e.set_other_amplifier(a)

    a.run_program()

    return e.outputs

def solve(permutation_base):
    permutations = itertools.permutations(permutation_base)
    max_signal = None
    max_signal_phase_seq = None
    for p in permutations:
        signal = get_signal(iter(p))
        if not max_signal or signal > max_signal:
            max_signal = signal
            max_signal_phase_seq = p
    print(max_signal_phase_seq, '->', max_signal)

if __name__ == "__main__":
    with open("input") as f:
            amplifier.code = list(map(lambda x: int(x), f.readline().split(',')))
    solve([0, 1, 2, 3, 4]) # part1
    solve([5, 6, 7, 8, 9]) # part2

Answer 1

Style

• Use CamalCase for class names, like class Amplifier.
• No need to explicitly extends object.
• When encountering unsupported opcode, raise an exception to kill the program immediately instead of printing an error message. It helps you discover bugs earlier. This is known as "fail fast".
• get_signal() should accept an Iterable instead of an Iterator. You can do a lot of magic with Iterables, like this:

def get_signal(permutation_iter):
    # Transform list of integer into list of amplifiers and unpack them.
    a, b, c, d, e = map(amplifier, permutation_iter)
    a.add_input(0)

    a.set_other_amplifier(b)
    b.set_other_amplifier(c)
    c.set_other_amplifier(d)
    d.set_other_amplifier(e)
    e.set_other_amplifier(a)

    a.run_program()

    return e.outputs

It also makes the iter() call in solve() unnecessary.

• The main job of solve() is getting the maximum from a list of permutations, using get_signal() as key. Python already has max() function for this, but we need to extract the permutation itself as well. So we can write our own argmax() function to simplify this. Note that the code is a lot cleaner without for loop.

def argmax(iterable, key=None):
    arg = max((item for item in iterable), key=key)
    value = key(arg) if key else arg
    return arg, value

def solve(permutation_base):
    permutations = itertools.permutations(permutation_base)
    max_signal_phase_seq, max_signal = argmax(permutations, key=get_signal)
    print(max_signal_phase_seq, "->", max_signal)

Structure

• Pull out the intcode computer into its own function or class, which will ease code reuse(You'll need the intcode computer in multiple challenges of AoC later).
• Don't "hard wire" parameter modes into opcode. Parse parameter modes independently of actual operations. For example, opcode 102, 1002, and 1102 should trigger the same function(multiplication), only passing different parameters.(Spoiler: You'll need to add another parameter mode later)