Day 10: Balance Bots

In [1]:

    

with open("input/day10.txt", "r") as f:
    inputLines = tuple(line.strip() for line in f)


    

In [2]:

    

import collections
import enum
import functools
import operator
import re


    

In [3]:

    

# Bots give their chips either to another bot or to an output
ReceiverType = enum.Enum("Receiver", "BOT OUTPUT")


    

In [4]:

    

# Parse the receiver part of an instruction
def parseReceiver(receiver):
    match = re.fullmatch(r"(bot|output) ([0-9]+)", receiver)
    assert match is not None
    receiverTypeStr, indexStr = match.groups()
    return ReceiverType[receiverTypeStr.upper()], int(indexStr)

assert parseReceiver("output 42") == (ReceiverType.OUTPUT, 42)
assert parseReceiver("bot 13") == (ReceiverType.BOT, 13)


    

In [5]:

    

# Parse all instructions, and return
# * a dict that holds the initial chips for each bot,
# * a dict that maps bot indices to the receivers of the low and high chips if the respective bot has
#   two chips.
def parseInstructions(instructions):
    initialState = collections.defaultdict(set)
    lowHighReceivers = {}
    
    for instruction in instructions:
        # Try to interpret the line as a bot initialization instruction
        initMatch = re.fullmatch(r"value ([0-9]+) goes to bot ([0-9]+)", instruction)
        
        if initMatch is not None:
            value, bot = map(int, initMatch.groups())
            initialState[bot].add(value)
        else:
            # No initialization instruction 
            # -> it is an instruction for handling the low/high microchips of a bot
            lowHighMatch = re.fullmatch(
                r"bot ([0-9]+) gives low to (.*) and high to (.*)", instruction)
            assert lowHighMatch is not None
            
            botStr, low, high = lowHighMatch.groups()
            bot = int(botStr)
            assert bot not in lowHighReceivers
            lowHighReceivers[bot] = tuple(map(parseReceiver, (low, high)))

    return initialState, lowHighReceivers


    

In [6]:

    

class BotSimulator:
    
    def __init__(self, instructions):
        self.state, self.lowHighReceivers = parseInstructions(instructions)
        self.outputs = collections.defaultdict(list)

        # Verify that no bot has more than two chips
        assert all(len(chips) <= 2 for bot, chips in self.state.items())

        # Active bots are those that have two chips and will give them away
        self.activeBots = collections.deque(
            bot for bot, chips in self.state.items() if len(chips) == 2)
        
    def isActive(self):
        """Returns true if there are still bots which have two chips."""
        return len(self.activeBots) > 0
    
    def nextStep(self):
        """Returns 
        * the next bot which will give its chips away, and
        * a set which contains the values of these chips."""
        if self.isActive():
            bot = self.activeBots[0]
            values = self.state[bot]
            return bot, values
    
    def executeStep(self):
        """Makes the first active bot give away its chips."""
        assert len(self.activeBots) > 0
        bot = self.activeBots.popleft()
        sortedValues = sorted(self.state[bot])
        assert len(sortedValues) == 2
        self.state[bot].clear()
    
        for value, (receiverType, receiverIndex) in zip(sortedValues, self.lowHighReceivers[bot]):
            if receiverType is ReceiverType.OUTPUT:
                self.outputs[receiverIndex].append(value)
            else:
                assert receiverType is ReceiverType.BOT
                self.state[receiverIndex].add(value)
                if len(self.state[receiverIndex]) == 2:
                    self.activeBots.append(receiverIndex)
        
    def run(self):
        """Calls executeStep repeatedly until no bot has more than one chip."""
        while self.isActive():
            self.executeStep()


    

In [7]:

    

def findBotForValues(instructions, values):
    simulator = BotSimulator(instructions)
    values = set(values)
    
    while simulator.isActive():
        nextBot, nextValues = simulator.nextStep()
        if nextValues == values:
            return nextBot
        simulator.executeStep()


    

In [8]:

    

# Verify that we get the correct result for the test instructions
testInstructions = """value 5 goes to bot 2
bot 2 gives low to bot 1 and high to bot 0
value 3 goes to bot 1
bot 1 gives low to output 1 and high to bot 0
bot 0 gives low to output 2 and high to output 0
value 2 goes to bot 2""".split("\n")

assert findBotForValues(testInstructions, (5, 2)) == 2


    

In [9]:

    

findBotForValues(inputLines, (61, 17))


    

    
Out[9]:





118

In [10]:

    

def productOutputs012(instructions):
    simulator = BotSimulator(instructions)
    simulator.run()
    return functools.reduce(operator.mul, (simulator.outputs[i][0] for i in range(3)), 1)


    

In [11]:

    

productOutputs012(inputLines)


    

    
Out[11]:





143153