Advent of Code 2016 - Day 10

Useful Links

Concepts and Packages Demonstrated

Problem Intro
Part 1
Part 2
Results

Problem Intro

We have a factory of bots that are sorting microchips. Each bot has a number, and can hold up to two microchips. When a bot has two microchips, it follows a pre-programmed instruction to give its low-value chip to one destination and its high-value chip to another. These destinations can be other bots or output bins.

The instructions are of two types:

value A goes to bot B: This instruction gives microchip with value A to bot B.
bot A gives low to (bot|output) B and high to (bot|output) C: This instruction tells bot A what to do when it has two chips.

Here is an example of the input data:

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

Part 1

What is the number of the bot that is responsible for comparing value-61 microchips with value-17 microchips?

This problem requires us to simulate the process of the bots sorting the chips. We need to keep track of which chips each bot has, and process the instructions in the correct order. An instruction for a bot to give away its chips can only be executed when that bot has two chips.

My strategy is as follows:

Create a Bot class: This class will represent a bot. It will have methods to add a chip, check if it’s full, and get its low and high value chips. It will also have a method to check if it is currently comparing two specific chip values.
Parse the instructions: Use regular expressions to parse the two types of instructions.
Process instructions in a loop: Continuously loop through the instructions. In each iteration, try to execute as many instructions as possible. An instruction is removed from the list once it has been successfully executed. The loop continues until no instructions are left.

Solution Code

import logging
import os
import time
import re

SCRIPT_DIR = os.path.dirname(__file__)
INPUT_FILE = "input/input.txt"

value_pattern = re.compile(r"value (\d+) goes to bot (\d+)")
bot_gives_pattern = re.compile(r"bot (\d+) gives low to (output|bot) (\d+) and high to (output|bot) (\d+)")

CHECK_VALS = [61, 17]

class Bot:
    """ A bot picks up microchips from inputs, or from other bots.
    When a bot has two microchips, it is able to give those microchips to other bots, or to outputs. 
    External rules tell Bots what to do. """ 
    
    MAX_VALUES = 2
    
    def __init__(self, num:int) -> None:
        self._num = num
        self._values = []
    
    def add_value(self, value:int) -> None:
        if self.is_full():
            raise ValueError("This bot is full.")
        
        self._values.append(value)
        
    def is_full(self) -> bool:
        if len(self._values) == Bot.MAX_VALUES:
            return True
        
        return False

    def pop_low(self) -> int:
        ret_val = min(self._values)
        self._values.remove(ret_val)
        return ret_val
    
    def pop_high(self) -> int:
        ret_val = max(self._values)
        self._values.remove(ret_val)
        return ret_val
            
    def compares(self, values:list) -> bool:
        return set(self._values) == set(values)
    
    def __repr__(self):
        return f"Bot {self.num}: Values={sorted(self._values)}"

def main():
    logging.basicConfig(level=logging.INFO, format="%(asctime)s:%(levelname)s:\t%(message)s")
        
    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        all_instructions = f.read().splitlines()
    
    bots = {}
    outputs = {}
    
    while all_instructions:
        remove_list = []
        for instr in all_instructions:
            if (match := value_pattern.match(instr)):
                value, bot_num = [int(x) for x in match.groups()]
                bot = make_or_get_bot(bots, bot_num)
                
                if not bot.is_full():
                    bot.add_value(value)
                    remove_list.append(instr)
                continue
            
            if (match := bot_gives_pattern.match(instr)):
                bot_num, low_type, low_num, high_type, high_num = match.groups()
                bot_num, low_num, high_num = map(int, [bot_num, low_num, high_num])

                src_bot = make_or_get_bot(bots, bot_num)

                if src_bot.is_full():
                    if src_bot.compares(CHECK_VALS):
                        logging.info(f"Part 1: {src_bot} compares {CHECK_VALS}")
                    
                    # Check if target bots have space
                    can_give = True
                    if low_type == "bot" and make_or_get_bot(bots, low_num).is_full():
                        can_give = False
                    if high_type == "bot" and make_or_get_bot(bots, high_num).is_full():
                        can_give = False

                    if can_give:
                        if low_type == "bot":
                            make_or_get_bot(bots, low_num).add_value(src_bot.pop_low())
                        else:
                            outputs[low_num] = src_bot.pop_low()
                        
                        if high_type == "bot":
                            make_or_get_bot(bots, high_num).add_value(src_bot.pop_high())
                        else:
                            outputs[high_num] = src_bot.pop_high()
                            
                        remove_list.append(instr)
                continue
               
        all_instructions = list(filter(lambda element: element not in remove_list, all_instructions))

def make_or_get_bot(bots: dict[int, Bot], bot_num: int):
    if bot_num not in bots:
        bots[bot_num] = Bot(bot_num)
    return bots[bot_num]

if __name__ == "__main__":
    main()

Explanation

The Bot class is a simple container for the chips, with methods to manage its state.
The main loop continues as long as there are instructions to process. Inside the loop, we iterate through the current list of instructions.
For value... instructions, we add the chip to the bot if it’s not full. If successful, the instruction is marked for removal.
For bot...gives... instructions, we first check if the source bot is full. If it is, we then check if the destination bots (if any) have space. If everything is in order, we perform the transfer and mark the instruction for removal.
After each pass through the instructions, we remove the ones that have been successfully executed. This process repeats until all instructions are gone.

Part 2

What do you get if you multiply together the values in output bins 0, 1, and 2?

This part is straightforward. Since we are already tracking the values that go into the output bins, we just need to multiply the values in bins 0, 1, and 2 after all instructions have been processed.

Solution Code - Part 2

    # Part 2
    prod = outputs[0] * outputs[1] * outputs [2]
    logging.info(f"Part 2: Product of outputs 0, 1, and 2 = {prod}")

Results

Part 1: Bot 93 compares [17, 61]
Part 2: Product of outputs 0, 1, and 2 = 47101
Execution time: 0.0056 seconds

‹›

Learning Python with Advent of Code Walkthroughs