beckel

5105977?s=460&v=4

wiedmann
GitHub: beckel

About me

Struggling with my name change - since changing your github user name breaks all links to the old repository, I decided not to do it and live in a world of confusion instead :-)

I am solving the puzzles in Python to refresh my programming skills and have some fun on the train rides to/from work. I’d like to use the chance to learn a new language (e.g., Go or Rust), but time is limited. Let’s see if I re-solve some of the older puzzles or if I postpone this step to next year’s AoC.

Day 00: python

Day 0 - Hello world in python

print("Hello World - Looking forward to a lot of cool puzzles")

Day 01: python

Day 1 - Solution in Python

Getting to know gitpod - should really start not pressing "CTRL+W anymore :-)

import math

def fuel_needed(mass):
    return math.floor(int(mass)/3 - 2)

def fuel_needed_recursive(mass):
    fuel_needed_i = fuel_needed(mass)
    if (fuel_needed_i <= 0):
        return 0
    return fuel_needed_i + fuel_needed_recursive(fuel_needed_i)

total_fuel = 0
total_fuel_recursive = 0

with open("input.txt", "r") as fp:
    for line in fp:
        total_fuel += fuel_needed(line)
        total_fuel_recursive += fuel_needed_recursive(line)

print("Total fuel: " + str(total_fuel))
print("Total fuel recursive: " + str(total_fuel_recursive))

Day 02: python

Day 2 - Solution in Python

Coding in the train :-) Need to learn some python test frameworks next time.

import computer

# Part 1
with open("input.txt", "r") as fd:
    line = fd.readline()
    code_initial = line.split(",")
    code_initial = [int(x) for x in code_initial]

    # restore gravity assist program
    code = code_initial.copy()
    code[1] = 12
    code[2] = 2

    computer.compute(code)
    print("Solution to part 1 - Output: " + str(code[0]))

    # Part 2
    range_noun = range(0, 100)
    range_verb = range(0, 100)
    desired_output = 19690720

    for noun in range_noun:
        for verb in range_verb:
            code = code_initial.copy()
            code[1] = noun
            code[2] = verb
            computer.compute(code)
            if code[0] == desired_output:
                print("Solution found - Noun: " + str(noun) + ", Verb: " + str(verb) + "; Solution: " + str(100*noun+verb))
logging = 0

def compute(code):
    i = 0
    while(True):
        if (logging):
            print(code)
        opcode = code[i]
        if (opcode == 99):
            return
        if (opcode == 1):
            code[code[i+3]] = code[code[i+1]] + code[code[i+2]]
            i = i + 4
        if (opcode == 2):
            code[code[i+3]] = code[code[i+1]] * code[code[i+2]]
            i = i + 4

Day 03: python

Day 3 - Solution in Python

numpy for better array handling!

Star 1: Performance issue: Instead of checking for intersections WHILE putting the cable on the board, I first put both cables on the board (in a big 2-dim array) and checked for intersections later on. Unfortunately, the covered area is bigger than expected (~8000x8000 fields), so checking 64M fields for intersections takes a few minutes. Star 2 requires refactoring such that intersections are computed (and returned) on the fly - should be a easy thing with the current architecture.

After refactoring, everything is quite quick now …​

import manhattan

# Part 1
with open("input.txt", "r") as fd:
    line = fd.readline()
    cable_1 = line.split(",")
    line = fd.readline()
    cable_2 = line.split(",")

    manhattan.compute(cable_1, cable_2)
import numpy as np
import math

debug = False

def compute(input_1, input_2):

    # convert steps into more computable form: [ [x1,y1], [x2,y2], ... ]
    steps_cable_1 = []
    steps_cable_2 = []
    extract_steps(input_1, steps_cable_1)
    extract_steps(input_2, steps_cable_2)

    # put cables on board and check for intersections
    board = np.zeros([100000, 100000], dtype=int)
    walk_over_board(board, steps_cable_1)
    intersections = walk_over_board_cable_2(board, steps_cable_2)

    # determine manhattan distance
    smallest_manhattan_distance = 100000000
    for intersection in intersections:
        distance = abs(intersection[0]) + abs(intersection[1])
        smallest_manhattan_distance = min(distance, smallest_manhattan_distance)
    print("Result: " + str(smallest_manhattan_distance))

    # Count steps to intersection
    steps_cable_1 = count_steps(steps_cable_1, intersections)
    steps_cable_2 = count_steps(steps_cable_2, intersections)

    # Get minimum number of steps
    min_steps = 10000000
    for i in range(0, len(steps_cable_1)):
        min_steps = min(min_steps, (steps_cable_1[i] + steps_cable_2[i]))

    print("Minimum steps for both cables:",min_steps)
    return [smallest_manhattan_distance, min_steps]


def extract_steps(steps_input, steps_output):
    for i in range(0, len(steps_input)):
        char_1 = steps_input[i][0]
        num_steps = int(steps_input[i][1:])
        if (char_1 == 'U'):
            [steps_output.append([0,1]) for x in range(0, num_steps)]
        if (char_1 == 'D'):
            [steps_output.append([0,-1]) for x in range(0, num_steps)]
        if (char_1 == 'L'):
            [steps_output.append([-1,0]) for x in range(0, num_steps)]
        if (char_1 == 'R'):
            [steps_output.append([1,0]) for x in range(0, num_steps)]

def walk_over_board(board, steps):
    x = 0
    y = 0
    for i in range(0, len(steps)):
        x += steps[i][0]
        y += steps[i][1]
        board[x,y] = 1

def walk_over_board_cable_2(board, steps):
    intersections = []
    x = 0
    y = 0
    for i in range(0, len(steps)):
        x += steps[i][0]
        y += steps[i][1]
        if board[x,y] == 1:
            intersections.append([x,y])
    if debug:
        print("Intersections:",intersections)
    return intersections

def count_steps(steps, intersections):
    result_num_steps = []
    for i in range(0, len(intersections)):
        x = 0
        y = 0
        num_steps = 0
        intersection = intersections[i]
        for j in range(0, len(steps)):
            x += steps[j][0]
            y += steps[j][1]
            num_steps += 1
            if (x == intersection[0] and y == intersection[1]):
                result_num_steps.append(num_steps)
                break
    return result_num_steps

Day 04: python

Day 4 - Solution in Python

Brute force is easy - "Non brute force" impossible?

def non_decreasing(d):
    for i in range(len(d)-1):
        if (d[i] > d[i+1]):
            return False
    return True

def contains_double(d):
    for i in range(len(d)-1):
        if (d[i] == d[i+1]):
            return True
    return False

def contains_double_no_larger_group(d):
    # could be generalized similarly - too lazy atm :)
    if d[0] == d[1] and d[1] != d[2] \
        or d[0] != d[1] and d[1] == d[2] and d[2] != d[3] \
        or d[1] != d[2] and d[2] == d[3] and d[3] != d[4] \
        or d[2] != d[3] and d[3] == d[4] and d[4] != d[5] \
        or d[3] != d[4] and d[4] == d[5]:
        return True
    return False

num_passwords = 0
num_passwords_no_larger_group = 0
for i in range(271973,785962):
    # create integer array from integer
    d = list(map(lambda x:int(x), list(str(i))))
    if (non_decreasing(d)):
        if (contains_double(d)):
            num_passwords += 1
        if (contains_double_no_larger_group(d)):
            num_passwords_no_larger_group += 1

print("Num passwords:",num_passwords)
print("Num passwords without larger group:",num_passwords_no_larger_group)

Day 05: python

Day 5 - Solution in Python

Switched to VS Code - good decision!

import computer

# Part 1
with open("input.txt", "r") as fd:
    line = fd.readline()
    code_initial = line.split(",")
    code_initial = [int(x) for x in code_initial]

    computer.compute(code_initial)
# add modes

logging = 1

def compute(code):
    i = 0
    while(True):
        [opcode, modes] = evaluate_instruction(code[i])
        if (opcode == 99):
            return
        if (opcode == 1):
            summand_1 = code[i+1] if len(modes) >= 1 and modes[0] == 1 else code[code[i+1]]
            summand_2 = code[i+2] if len(modes) >= 2 and modes[1] == 1 else code[code[i+2]]
            code[code[i+3]] = summand_1 + summand_2
            i += 4
        if (opcode == 2):
            factor_1 = code[i+1] if len(modes) >= 1 and modes[0] == 1 else code[code[i+1]]
            factor_2 = code[i+2] if len(modes) >= 2 and modes[1] == 1 else code[code[i+2]]
            code[code[i+3]] = factor_1 * factor_2
            i += 4
        if (opcode == 3):
            code[code[i+1]] = int(input("Provide input: "))
            i += 2
        if (opcode == 4):
            output = code[i+1] if len(modes) >= 1 and modes[0] == 1 else code[code[i+1]]
            print("Output:",str(output))
            i += 2
        if (opcode == 5):
            value = code[i+1] if len(modes) >= 1 and modes[0] == 1 else code[code[i+1]]
            jump_to = code[i+2] if len(modes) >= 2 and modes[1] == 1 else code[code[i+2]]
            if value != 0:
                i = jump_to
            else:
                i += 3
        if (opcode == 6):
            value = code[i+1] if len(modes) >= 1 and modes[0] == 1 else code[code[i+1]]
            jump_to = code[i+2] if len(modes) >= 2 and modes[1] == 1 else code[code[i+2]]
            if value == 0:
                i = jump_to
            else:
                i += 3
        if (opcode == 7):
            operand_1 = code[i+1] if len(modes) >= 1 and modes[0] == 1 else code[code[i+1]]
            operand_2 = code[i+2] if len(modes) >= 2 and modes[1] == 1 else code[code[i+2]]
            if operand_1 < operand_2:
                code[code[i+3]] = 1
            else:
                code[code[i+3]] = 0
            i += 4
        if (opcode == 8):
            operand_1 = code[i+1] if len(modes) >= 1 and modes[0] == 1 else code[code[i+1]]
            operand_2 = code[i+2] if len(modes) >= 2 and modes[1] == 1 else code[code[i+2]]
            if operand_1 == operand_2:
                code[code[i+3]] = 1
            else:
                code[code[i+3]] = 0
            i += 4

def evaluate_instruction(instruction):
    opcode_low = instruction % 10
    instruction = int(instruction / 10)
    opcode_high = instruction % 10
    opcode = opcode_high * 10 + opcode_low
    instruction = int(instruction / 10)

    modes = []
    while(instruction > 0):
        modes.append(instruction % 10)
        instruction = int(instruction / 10)

    return [opcode, modes]

Day 06: python

Day 6 - Solution in Python

Trying to submit results with almost no receiption in the train ;-) Quite a long distance to travel to Santa!

def get_depth(obj, orbit_mapping):
    if obj == "COM":
        return 0
    else:
        new_obj = orbit_mapping[obj]
        return 1 + get_depth(new_obj, orbit_mapping)


with open("./input.txt", "r") as fd:
    # store all orbit relations in ditionary
    orbit_mapping = {}
    for line in fd:
        left = line.strip().split(')')[0]
        right = line.strip().split(')')[1]
        orbit_mapping[right] = left

    # traverse and count links from each object to "COM"
    num = 0
    for obj in orbit_mapping:
        num += get_depth(obj, orbit_mapping)
    print("Number of direct and indirect orbits:",num)

    # Star 2: identify common objects which must NOT be travelled through
    you_object = "YOU"
    santa_object = "SAN"
    you_chain = []
    santa_chain = []
    while(you_object != "COM"):
        you_chain.append(orbit_mapping[you_object])
        you_object = orbit_mapping[you_object]
    while(santa_object != "COM"):
        santa_chain.append(orbit_mapping[santa_object])
        santa_object = orbit_mapping[santa_object]

    common_objects = set(you_chain) ^ set(santa_chain)
    print("Travel distance:",len(common_objects))

Day 07: python

Day 7 - Solution in Python

Refactored computer into an object oriented version (i.e., a class) such that it can maintain state of program/memory and the instruction pointer.

Now I know what "self hell" means in python ;-)

import amplifier_sequence
import itertools

with open("input.txt", "r") as fd:
    line = fd.readline()
    code = line.split(",")
    code = [int(x) for x in code]

    max_output = 0
    # Part 1
    for permutation in list(itertools.permutations(range(5))):
        output = amplifier_sequence.run_standalone(code, permutation)
        max_output = max(output, max_output)
    print("Max output (standalone):",max_output)

    max_output = 0
    # Part 2
    for permutation in list(itertools.permutations(range(5, 10))):
        output = amplifier_sequence.run_feedback(code, permutation)
        max_output = max(output, max_output)
    print("Max output (feedback):",max_output)
from computer import Computer

def run_standalone(program, phase_configuration):
    in_val = 0
    for i in phase_configuration:
        amplifier = Computer(program.copy(), [i, in_val])
        amplifier.run()
        out_val = amplifier.get_last_output()
        in_val = out_val

    return out_val

def run_feedback(program, phase_configuration):

    in_val = 0
    num_amplifiers = len(phase_configuration)

    # initialize amplifiers
    amplifiers = []
    for i in phase_configuration:
        amplifiers.append(Computer(program.copy(), [i]))

    # start first amplifier
    amplifiers[0].provide_input(in_val)

    # run amplifier and connect output to next amplifier (if not halted)
    i = 0
    while(True):
        amplifiers[i].run()
        output = amplifiers[i].get_last_output()
        i = (i+1) % num_amplifiers
        if (amplifiers[i].has_terminated() == False):
            amplifiers[i].provide_input(output)
        else:
            return output
debug = 0

class Computer:

    def __init__(self, code, program_input):
        self.code = code
        self.ptr = 0 # ptr: instruction pointer
        self.program_output = []
        self.program_input = program_input
        self.state = "RUNNING"

    def run(self):
        while(True):
            [opcode, modes] = evaluate_instruction(self.code[self.ptr])
            if (opcode == 99):
                self.state = "TERMINATED"
                return
            if (opcode == 1):
                summand_1 = self.code[self.ptr+1] if len(modes) >= 1 and modes[0] == 1 else self.code[self.code[self.ptr+1]]
                summand_2 = self.code[self.ptr+2] if len(modes) >= 2 and modes[1] == 1 else self.code[self.code[self.ptr+2]]
                self.code[self.code[self.ptr+3]] = summand_1 + summand_2
                self.ptr += 4
            if (opcode == 2):
                factor_1 = self.code[self.ptr+1] if len(modes) >= 1 and modes[0] == 1 else self.code[self.code[self.ptr+1]]
                factor_2 = self.code[self.ptr+2] if len(modes) >= 2 and modes[1] == 1 else self.code[self.code[self.ptr+2]]
                self.code[self.code[self.ptr+3]] = factor_1 * factor_2
                self.ptr += 4
            if (opcode == 3):
                if (len(self.program_input) == 0):
                    return # wait for input
                self.code[self.code[self.ptr+1]] = self.program_input.pop(0)
                self.ptr += 2
            if (opcode == 4):
                output = self.code[self.ptr+1] if len(modes) >= 1 and modes[0] == 1 else self.code[self.code[self.ptr+1]]
                if (debug):
                    print("Output:",str(output))
                self.program_output.append(output)
                self.ptr += 2
            if (opcode == 5):
                value = self.code[self.ptr+1] if len(modes) >= 1 and modes[0] == 1 else self.code[self.code[self.ptr+1]]
                jump_to = self.code[self.ptr+2] if len(modes) >= 2 and modes[1] == 1 else self.code[self.code[self.ptr+2]]
                if value != 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            if (opcode == 6):
                value = self.code[self.ptr+1] if len(modes) >= 1 and modes[0] == 1 else self.code[self.code[self.ptr+1]]
                jump_to = self.code[self.ptr+2] if len(modes) >= 2 and modes[1] == 1 else self.code[self.code[self.ptr+2]]
                if value == 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            if (opcode == 7):
                operand_1 = self.code[self.ptr+1] if len(modes) >= 1 and modes[0] == 1 else self.code[self.code[self.ptr+1]]
                operand_2 = self.code[self.ptr+2] if len(modes) >= 2 and modes[1] == 1 else self.code[self.code[self.ptr+2]]
                if operand_1 < operand_2:
                    self.code[self.code[self.ptr+3]] = 1
                else:
                    self.code[self.code[self.ptr+3]] = 0
                self.ptr += 4
            if (opcode == 8):
                operand_1 = self.code[self.ptr+1] if len(modes) >= 1 and modes[0] == 1 else self.code[self.code[self.ptr+1]]
                operand_2 = self.code[self.ptr+2] if len(modes) >= 2 and modes[1] == 1 else self.code[self.code[self.ptr+2]]
                if operand_1 == operand_2:
                    self.code[self.code[self.ptr+3]] = 1
                else:
                    self.code[self.code[self.ptr+3]] = 0
                self.ptr += 4

    def get_last_output(self):
        return self.program_output[len(self.program_output)-1]

    def provide_input(self, i):
        self.program_input.append(i)

    def has_terminated(self):
        return True if self.state == "TERMINATED" else False

def evaluate_instruction(instruction):
    opcode_low = instruction % 10
    instruction = int(instruction / 10)
    opcode_high = instruction % 10
    opcode = opcode_high * 10 + opcode_low
    instruction = int(instruction / 10)

    modes = []
    while(instruction > 0):
        modes.append(instruction % 10)
        instruction = int(instruction / 10)

    return [opcode, modes]

Day 08: python

Day 8 - Solution in Python

Cool puzzle - needed to glitch the eyes a bit to be able to read the code though :)

import numpy as np

def render(image_display):
    for i in range(image_display.shape[0]):
        for j in range(image_display.shape[1]):
            if image_display[i,j] == 0:
                print(' ', end = '')
            else:
                print('█', end = '')
        print()

x = 25
y = 6
with open("input.txt") as fd:
    line = fd.readline()
    digits = [int(x) for x in line]
    z = len(digits) // x // y
    image = np.zeros([x,y,z],dtype=np.int64)

    for i in range(z):
        for j in range(y):
            image[:,j,i] = digits[i*x*y + j*x : i*x*y + (j+1)*x]

    # identify layer with least 0s
    test = image == 0
    zeros_on_layers = np.sum(test, axis=(0,1))
    z_min_zeros = np.argmin(zeros_on_layers)

    # Star 1: No. 1s * no. 2s on layer with least 0s
    num_one_digits = np.sum(image[:,:,z_min_zeros] == 1)
    num_two_digits = np.sum(image[:,:,z_min_zeros] == 2)
    print("Result Star 1:",num_one_digits*num_two_digits)

    # print the image (Star 2)
    image_display = np.zeros([x,y],dtype=np.int64)
    for i in range(x):
        for j in range(y):
            color_array = image[i,j,:]
            for color in color_array:
                if color == 0:
                    break
                if color == 1:
                    image_display[i,j] = 1
                    break
                else:
                    continue

    image_display = np.transpose(image_display)
    render(image_display)

Day 09: python

Day 9 - Solution in Python

Refactored computer into an object oriented version (i.e., a class) such that it can maintain state of program/memory and the instruction pointer.

Now I know what "self hell" means in python ;-)

import amplifier_sequence
from computer import Computer

with open("input.txt", "r") as fd:
    line = fd.readline()
    code = line.split(",")
    code = [int(x) for x in code]

    computer = Computer(code, [1])
    computer.run()
    result = computer.get_whole_output()
    print("State: " + str(computer.get_state()))
    print("Output Star 1: " + str(result))

    computer = Computer(code, [2])
    computer.run()
    result = computer.get_whole_output()
    print("State: " + str(computer.get_state()))
    print("Output Star 2: " + str(result))
from computer import Computer

def run_standalone(program, phase_configuration):
    in_val = 0
    for i in phase_configuration:
        amplifier = Computer(program.copy(), [i, in_val])
        amplifier.run()
        out_val = amplifier.get_last_output()
        in_val = out_val

    return out_val

def run_feedback(program, phase_configuration):

    in_val = 0
    num_amplifiers = len(phase_configuration)

    # initialize amplifiers
    amplifiers = []
    for i in phase_configuration:
        amplifiers.append(Computer(program.copy(), [i]))

    # start first amplifier
    amplifiers[0].provide_input(in_val)

    # run amplifier and connect output to next amplifier (if not halted)
    i = 0
    while(True):
        amplifiers[i].run()
        output = amplifiers[i].get_last_output()
        i = (i+1) % num_amplifiers
        if (amplifiers[i].has_terminated() == False):
            amplifiers[i].provide_input(output)
        else:
            return output
debug = 0

class Computer:

    def __init__(self, code, program_input):
        self.code = [ 0 if x >= len(code) else code[x] for x in range(100000) ]
        self.ptr = 0 # ptr: instruction pointer
        self.program_output = []
        self.program_input = program_input
        self.state = "INITIALIZED"
        self.relative_base = 0

    def run(self):
        while(True):
            self.state = "RUNNING"
            [opcode, modes] = evaluate_instruction(self.code[self.ptr])
            if (opcode == 99):
                self.state = "TERMINATED"
                return
            elif (opcode == 1):
                modes.extend([0 for _ in range(3-len(modes))])
                summand_1 = self.read(1, modes[0])
                summand_2 = self.read(2, modes[1])
                self.write(3, modes[2], summand_1 + summand_2)
                self.ptr += 4
            elif (opcode == 2):
                modes.extend([0 for _ in range(3-len(modes))])
                factor_1 = self.read(1, modes[0])
                factor_2 = self.read(2, modes[1])
                self.write(3, modes[2], factor_1 * factor_2)
                self.ptr += 4
            elif (opcode == 3):
                modes.extend([0 for _ in range(1-len(modes))])
                if (len(self.program_input) == 0):
                    self.state = "WAITING_FOR_INPUT"
                    return # wait for input
                self.write(1, modes[0], self.program_input.pop(0))
                self.ptr += 2
            elif (opcode == 4):
                modes.extend([0 for _ in range(1-len(modes))])
                assert(len(modes) >= 1)
                output = self.read(1, modes[0])
                if (debug):
                    print("Output:",str(output))
                self.program_output.append(output)
                self.ptr += 2
            elif (opcode == 5):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value != 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 6):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value == 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 7):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 < operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 8):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 == operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 9):
                modes.extend([0 for _ in range(1-len(modes))])
                offset_change = self.read(1, modes[0])
                self.relative_base += offset_change
                self.ptr += 2
            else:
                print(self.program_output)
                raise Exception("Unknown opcode: " + str(opcode))

    def read(self, offset, mode):
        if mode == 0:
            return self.code[self.code[self.ptr+offset]]
        elif mode == 1:
            return self.code[self.ptr+offset]
        elif mode == 2:
            return self.code[self.relative_base + self.code[self.ptr + offset]]

    def write(self, offset, mode, value):
        if mode == 0:
            self.code[self.code[self.ptr+offset]] = value
        elif mode == 1:
            self.code[self.ptr+offset] = value
        elif mode == 2:
            self.code[self.relative_base + self.code[self.ptr + offset]] = value

    def get_last_output(self):
        return self.program_output[len(self.program_output)-1]

    def get_whole_output(self):
        return self.program_output

    def provide_input(self, i):
        self.program_input.append(i)

    def has_terminated(self):
        return True if self.state == "TERMINATED" else False

    def get_state(self):
        return self.state

def evaluate_instruction(instruction):
    opcode_low = instruction % 10
    instruction = int(instruction / 10)
    opcode_high = instruction % 10
    opcode = opcode_high * 10 + opcode_low
    instruction = int(instruction / 10)

    modes = []
    while(instruction > 0):
        modes.append(instruction % 10)
        instruction = int(instruction / 10)

    return [opcode, modes]

Day 10: python

Day 10 - Solution in Python

Good chance to get the old school trigonometry skills back on track.

import numpy as np
import math
from collections import defaultdict

debug = False
field = []
with open("input.txt") as fd:
    # read input
    for line in fd:
        field.append(list(map(lambda x: 1 if x == '#' else 0, line.strip())))
    x = np.asarray(field,dtype=np.int64)
    x = np.transpose(x)

    # count visible asteroids
    max_visible_asteroids = { 'x': 0, 'y': 0, 'num': 0, 'directions': defaultdict(list) }
    it = np.nditer(x, flags=['multi_index'])
    while not it.finished:
        directions = defaultdict(list)
        i = it.multi_index[0]
        j = it.multi_index[1]
        if debug:
            print("Checking field",i,",",j)

        # do not proceed if there is no astroid
        if x[i,j] == 0:
            it.iternext()
            continue

        # identify visible targets
        it_target = np.nditer(x, flags=['multi_index'])
        while not it_target.finished:
            i_target = it_target.multi_index[0]
            j_target = it_target.multi_index[1]

            # continue if target is no asteroid
            if x[i_target,j_target] == 0:
                it_target.iternext()
                continue

            # continue if target is same field
            if (i == i_target) and (j == j_target):
                it_target.iternext()
                continue

            # store direction and distance
            dir = np.arctan2(i_target-i, j_target-j)
            distance = math.sqrt((j_target-j)**2 + (i_target-i)**2)
            directions[dir].append({'x': i_target, 'y': j_target, 'distance': distance})

            it_target.iternext()

        visible_asteroids_from_here = len(directions.keys())
        if visible_asteroids_from_here > max_visible_asteroids['num']:
            max_visible_asteroids['num'] = visible_asteroids_from_here
            max_visible_asteroids['x'] = i
            max_visible_asteroids['y'] = j
            max_visible_asteroids['directions'] = directions

        it.iternext()

    print("Part 1: Max. visible asteroids:",max_visible_asteroids['num']," - from (",max_visible_asteroids['x'],",",max_visible_asteroids['y'],")")

    # Star 2: Shoot asteroids with laster
    dir_from_base = max_visible_asteroids['directions']
    hit_number = 0
    while (len(dir_from_base) > 0):
        for direction in sorted(dir_from_base.keys(), reverse=True):
            asteroids_in_line = dir_from_base[direction]
            list.sort(asteroids_in_line, key=lambda x:x['distance'])
            closest = asteroids_in_line.pop(0)
            if not asteroids_in_line:
                del dir_from_base[direction]
            hit_number += 1
            print("Hit no.",hit_number,": Asteroid at",closest['x'],closest['y'])

Day 11: python

Day 11 - Solution in Python

Glad we got yet another Intcode puzzle - this time no changes to the computer were needed except for a helper function that returns the last two outputs instead of returning the whole output at once.

import math
from painting_robot import paint

with open("input.txt", "r") as fd:
    line = fd.readline()
    code = line.split(",")
    code = [int(x) for x in code]

    [black, white] = paint(code, 0)
    print("Star 1 - Painted panels:",len(black)+len(white))

    [black, white] = paint(code.copy(), 1)
    print("Star 2 - Painted panels:",len(black)+len(white))

    # print picture
    min_y = 10000
    max_y = -10000
    min_x = 10000
    max_x = -10000
    for pos in black:
        min_y = min(min_y, pos[1])
        max_y = max(max_y, pos[1])
        min_x = min(min_x, pos[0])
        max_x = max(max_x, pos[0])
    for pos in white:
        min_y = min(min_y, pos[1])
        max_y = max(max_y, pos[1])
        min_x = min(min_x, pos[0])
        max_x = max(max_x, pos[0])

    for i in reversed(range(min_y,max_y+1)):
        for j in range(min_x+1,max_x-1):
            if [j,i] in black:
                print(' ', end = '')
            else:
                print('█', end = '')
        print()
import math
from computer import Computer

def paint(program, initial_color):

    computer = Computer(program, [initial_color])

    black = []
    white = []
    position = [0,0]
    direction = 90

    while(True):

        computer.run()
        [color, turn] = computer.get_last_output_values(2)

        # paint black (0) or white (1)
        if color == 0:
            if position not in black: black.append(position)
            if position in white: white.remove(position)
        if color == 1:
            if position not in white: white.append(position)
            if position in black: black.remove(position)

        # turn left (0) or right (1)
        if turn == 0:
            direction = (direction + 90) % 360
        elif turn == 1:
            direction = (direction - 90) % 360

        # step forward
        new_x = position[0] + int(math.cos(math.radians(direction)))
        new_y = position[1] + int(math.sin(math.radians(direction)))
        position = [new_x, new_y]

        if computer.get_state() == "TERMINATED":
            break
        elif computer.get_state() == "WAITING_FOR_INPUT":
            current_color = 1 if position in white else 0
            computer.provide_input(current_color)

    return [black, white]
debug = 0

class Computer:

    def __init__(self, code, program_input):
        self.code = [ 0 if x >= len(code) else code[x] for x in range(100000) ]
        self.ptr = 0 # ptr: instruction pointer
        self.program_output = []
        self.program_input = program_input
        self.state = "INITIALIZED"
        self.relative_base = 0

    def run(self):
        while(True):
            self.state = "RUNNING"
            [opcode, modes] = evaluate_instruction(self.code[self.ptr])
            if (opcode == 99):
                self.state = "TERMINATED"
                return
            elif (opcode == 1):
                modes.extend([0 for _ in range(3-len(modes))])
                summand_1 = self.read(1, modes[0])
                summand_2 = self.read(2, modes[1])
                self.write(3, modes[2], summand_1 + summand_2)
                self.ptr += 4
            elif (opcode == 2):
                modes.extend([0 for _ in range(3-len(modes))])
                factor_1 = self.read(1, modes[0])
                factor_2 = self.read(2, modes[1])
                self.write(3, modes[2], factor_1 * factor_2)
                self.ptr += 4
            elif (opcode == 3):
                modes.extend([0 for _ in range(1-len(modes))])
                if (len(self.program_input) == 0):
                    self.state = "WAITING_FOR_INPUT"
                    return # wait for input
                self.write(1, modes[0], self.program_input.pop(0))
                self.ptr += 2
            elif (opcode == 4):
                modes.extend([0 for _ in range(1-len(modes))])
                assert(len(modes) >= 1)
                output = self.read(1, modes[0])
                if (debug):
                    print("Output:",str(output))
                self.program_output.append(output)
                self.ptr += 2
            elif (opcode == 5):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value != 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 6):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value == 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 7):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 < operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 8):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 == operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 9):
                modes.extend([0 for _ in range(1-len(modes))])
                offset_change = self.read(1, modes[0])
                self.relative_base += offset_change
                self.ptr += 2
            else:
                print(self.program_output)
                raise Exception("Unknown opcode: " + str(opcode))

    def read(self, offset, mode):
        if mode == 0:
            return self.code[self.code[self.ptr+offset]]
        elif mode == 1:
            return self.code[self.ptr+offset]
        elif mode == 2:
            return self.code[self.relative_base + self.code[self.ptr + offset]]

    def write(self, offset, mode, value):
        if mode == 0:
            self.code[self.code[self.ptr+offset]] = value
        elif mode == 1:
            self.code[self.ptr+offset] = value
        elif mode == 2:
            self.code[self.relative_base + self.code[self.ptr + offset]] = value

    def get_last_output(self):
        return self.program_output[len(self.program_output)-1]

    def get_last_output_values(self, number):
        num_items = len(self.program_output)
        return self.program_output[num_items-number:num_items]

    def get_whole_output(self):
        return self.program_output

    def provide_input(self, i):
        self.program_input.append(i)

    def has_terminated(self):
        return True if self.state == "TERMINATED" else False

    def get_state(self):
        return self.state

def evaluate_instruction(instruction):
    opcode_low = instruction % 10
    instruction = int(instruction / 10)
    opcode_high = instruction % 10
    opcode = opcode_high * 10 + opcode_low
    instruction = int(instruction / 10)

    modes = []
    while(instruction > 0):
        modes.append(instruction % 10)
        instruction = int(instruction / 10)

    return [opcode, modes]

Day 12: python

Day 11 - Solution in Python

Cool puzzle! Made a small conceptual mistake in part 2 that made the solution ages to compute. Gladly (and with some help) I could fix it. Waiting wouldn’t have been a lot of fun …​

import copy
import math
import numpy as np

moons = []
# test 1: "test-1.txt" / 10
# test 2: "test-2.txt" / 100
# real: "input.txt" / 1000
max_steps = 1000
with open("input.txt") as fd:
    for line in fd:
        line = line.strip()
        line = line[1:-1]
        moons.append([int(x[2:]) for x in line.split(', ')])

num_moons = len(moons)
init_position = copy.deepcopy(moons)
velocity = np.zeros([num_moons,3], dtype=np.int64)

steps = 0
roundtrip = list([0, 0, 0])
while(True):

    steps += 1

    # get position change
    move = np.zeros([num_moons,3], dtype=np.int64)
    for i in range(0, num_moons):
        for j in range(0, num_moons):
            for dim in range(0,3):
                if moons[i][dim] < moons[j][dim]:
                    move[i][dim] += 1
                elif moons[i][dim] > moons[j][dim]:
                    move[i][dim] -= 1

    # adapt velocity and position
    for i in range(0, num_moons):
        for dim in range(0,3):
            velocity[i][dim] += move[i][dim]
            moons[i][dim] += velocity[i][dim]

    # check if position has been seen before
    for dim in range(0,3):
        if roundtrip[dim] == 0:
            found_repeat = 0
            for i in range(0,num_moons):
                if velocity[i][dim] == 0 and moons[i][dim] == init_position[i][dim]:
                    found_repeat += 1
            if found_repeat == num_moons:
                roundtrip[dim] = steps
                print("-----------")
                print("All mooons return to origin of dimension",dim)
                print("after",steps,"steps.")
                print("Round trip vector:",roundtrip)
                print("-----------")

    # all roundtrips found?
    if steps > max_steps and 0 not in roundtrip:
        break

    # compute energy (don't do after max_steps steps)
    if steps <= max_steps:
        energy = 0
        for i in range(0, num_moons):
            sum_kinetic = 0
            sum_potential = 0
            for dim in range(0,3):
                sum_kinetic += abs(velocity[i][dim])
                sum_potential += abs(moons[i][dim])
            energy += sum_kinetic * sum_potential

    if steps == max_steps:
        print("Energy",energy,"after step",steps)

result = np.lcm(np.lcm(roundtrip[0], roundtrip[1]), roundtrip[2])
print("History repeats itself after",result,"iterations")

Day 13: python

Day 13 - Solution in Python

That was fun! I was tempted to do a manual version (instead of an "AI") as well but retrieving console input while the program is running turned out to be too tedious.

import numpy as np
from computer import Computer
import time

def is_x(i):
    return i % 3 == 0

def is_y(i):
    return (i+2) % 3 == 0

def is_tile(i):
    return (i+1) % 3 == 0

def icon(tile_id):
    if tile_id == 0:
        return ' ' # empty space
    elif tile_id == 1:
        return '█' # wall
    elif tile_id == 2:
        return '▒' # block
    elif tile_id == 3:
        return '▂' # paddle
    elif tile_id == 4:
        return '•' # ball

def print_lines(n, x_dim, char):
    for _ in range(n):
        for _ in range(x_dim):
            print(char, end='')
        print()

def render(board, score):
    x_dim = board.shape[0]
    y_dim = board.shape[1]
    print_lines(8, x_dim, ' ')
    for y in range(y_dim):
        for x in range(x_dim):
            print(icon(board[x][y]), end='')
        print()
    print_lines(1, x_dim, '-')
    print("Score:",score)
    print_lines(1, x_dim, '-')

with open("input.txt") as fd:
    line = fd.readline().strip()
    code = line.split(',')
    code = [int(x) for x in code]
    computer = Computer(code, [])
    computer.run()

    # Star 1: block tiles
    output = computer.get_whole_output()
    num_block_tiles = 0
    for i in range(0, len(output)):
        if is_tile(i):
            if output[i] == 2:
                num_block_tiles += 1
    print("Star 1: There are",num_block_tiles,"block tiles on the board.")

    # Set program to "free" mode
    code[0] = 2

    # Set joystick to "center"
    joystick = 1

    computer = Computer(code, [])
    i = 0
    score = 0
    x_dim = 41
    y_dim = 25
    board = np.zeros([x_dim, y_dim])
    while(computer.get_state() != "TERMINATED"):
        computer.run()
        output = computer.get_whole_output()
        while (i < len(output)):
            if (output[i] == -1 and output[i+1] == 0):
                score = output[i+2]
            else:
                tile_id = output[i+2]
                board[output[i]][output[i+1]] = tile_id
                if tile_id == 4:
                    ball_x = output[i]
                elif tile_id == 3:
                    paddle_x = output[i]
            i += 3
        render(board, score)

        # adjust joystick
        if paddle_x > ball_x:
            joystick = -1
        elif paddle_x < ball_x:
            joystick = 1
        else:
            joystick = 0
        computer.provide_input(joystick)
        time.sleep(0.1)

    print("Final score:",score)

Day 14: python

Day 14 - Solution in Python

For star 2: Used a "manual" binary search due to late night programming lazyness ;-)

import numpy as np
import math

def get_ore(amount_needed, chemical, reactions, spare_parts):

    if chemical == "ORE":
        return amount_needed

    amount_produced = int(reactions[chemical][0])
    amount_reactions_needed = math.ceil(amount_needed / amount_produced)
    ueberschuss = amount_reactions_needed * amount_produced - amount_needed
    if ueberschuss > 0:
        if not chemical in spare_parts:
            spare_parts[chemical] = 0
        spare_parts[chemical] += ueberschuss
    input_required = reactions[chemical][1:]

    ore_needed = 0
    for input_reaction in input_required:
        in_amount = amount_reactions_needed * int(input_reaction.split(" ")[0])
        in_chemical = input_reaction.split(" ")[1]
        if in_chemical in spare_parts:
            if spare_parts[in_chemical] >= in_amount:
                spare_parts[in_chemical] -= in_amount
                continue
            else:
                in_amount -= spare_parts[in_chemical]
                spare_parts[in_chemical] = 0

        ore_needed += get_ore(in_amount, in_chemical, reactions, spare_parts)

    return ore_needed


with open("input.txt") as fd:
    reactions = dict()
    for line in fd:
        reaction_output = line.strip().split(" => ")[1]
        reaction_input = line.strip().split(" => ")[0].strip().split(", ")
        tmp = [int(reaction_output.split(" ")[0])]
        tmp.extend(reaction_input)
        reactions[reaction_output.split(" ")[1]] = tmp

    spare_parts = dict()
    ore = get_ore(1, "FUEL", reactions, spare_parts)

    print("Star 1:",ore)
    print("Star 2: Maximum 11788286 fuel can be produced (manual binary search :-)")
    # ore = get_ore(11788286, "FUEL", reactions, spare_parts)

Day 15: python

Day 15 - Solution in Python

Learned a lot (refreshed BFS, collections.deque, and usage of tuples)

from labyrinth import start_labyrinth

fd = open("input.txt")
line = fd.readline().strip()
code = [int(x) for x in line.split(',')]

start_labyrinth(code)
import copy
from computer import Computer
import math
from collections import deque

def opposite(i):
    return (i + 1) % 4 + 1

def start_labyrinth(code):

    directions = { 1: (0,1), 2: (0,-1), 3:(-1,0), 4:(1,0) }
    state = { (0, 0): (0, Computer(code, []), 0) } # field, computer, steps
    queue = deque([(0,0)])
    results = []

    # bfs
    while(queue):
        if not queue:
            0+1# DONE - not sure what to do

        current_pos = queue.popleft()
        _, computer, steps = state[current_pos]
        for direction, move in directions.items():
            new_pos = (current_pos[0] + move[0], current_pos[1] + move[1])
            if new_pos in state:
                continue
            comp = computer.copy()#copy.deepcopy(computer)
            comp.provide_input(direction)
            comp.run()
            result = comp.get_last_output()
            state[new_pos] = (result, comp, steps+1)
            if result == 1:
                queue.append(new_pos)
            if result == 2:
                results.append((new_pos, steps+1))
    min_steps = 10000
    for r in results:
        min_steps = min(min_steps, r[1])
    print("Star 1:",min_steps,"steps.")

    with_oxygen = {results[0][0]: 0}
    bfs = deque([results[0][0]])
    while bfs:
        current_pos = bfs.popleft()
        for direction, move in directions.items():
            new_pos = (current_pos[0] + move[0], current_pos[1] + move[1])
            if new_pos in with_oxygen:
                continue
            if new_pos in state and state[new_pos][0] == 1:
                with_oxygen[new_pos] = with_oxygen[current_pos] + 1
                bfs.append(new_pos)
    print(max(with_oxygen.values()))





    # return_steps = 100000000

    # # mark field as visited
    # visited.append(position)

    # # check each direction
    # direction_next_step = []

    # for i in directions:

    #     # don't move back
    #     if i == opposite(in_dir):
    #         continue

    #     # run computer (but not every time ...)
    #     computer_copy = copy.deepcopy(computer)
    #     computer_copy.provide_input(i)
    #     computer_copy.run()
    #     result = computer_copy.get_last_output()

    #     if result == 0:
    #         0+1 # do nothing

    #     elif result == 1:
    #         direction_next_step.append(i)

    #     elif result == 2:
    #         return num_steps + 1

    # for i in direction_next_step:

    #     # increase counter by one
    #     new_pos = move(position, i)
    #     if new_pos not in visited:
    #         steps = walk(copy.deepcopy(computer), num_steps+1, i, new_pos, visited)
    #         return_steps = min(steps, return_steps)
    #         assert(computer.get_last_output() == 1)

    # return return_steps
debug = 0

class Computer:

    def __init__(self, code, program_input):
        self.code = [ 0 if x >= len(code) else code[x] for x in range(5000) ]
        self.ptr = 0 # ptr: instruction pointer
        self.program_output = []
        self.program_input = program_input
        self.state = "INITIALIZED"
        self.relative_base = 0

    def run(self):
        while(True):
            self.state = "RUNNING"
            [opcode, modes] = evaluate_instruction(self.code[self.ptr])
            if (opcode == 99):
                self.state = "TERMINATED"
                return
            elif (opcode == 1):
                modes.extend([0 for _ in range(3-len(modes))])
                summand_1 = self.read(1, modes[0])
                summand_2 = self.read(2, modes[1])
                self.write(3, modes[2], summand_1 + summand_2)
                self.ptr += 4
            elif (opcode == 2):
                modes.extend([0 for _ in range(3-len(modes))])
                factor_1 = self.read(1, modes[0])
                factor_2 = self.read(2, modes[1])
                self.write(3, modes[2], factor_1 * factor_2)
                self.ptr += 4
            elif (opcode == 3):
                modes.extend([0 for _ in range(1-len(modes))])
                if (len(self.program_input) == 0):
                    self.state = "WAITING_FOR_INPUT"
                    return # wait for input
                self.write(1, modes[0], self.program_input.pop(0))
                self.ptr += 2
            elif (opcode == 4):
                modes.extend([0 for _ in range(1-len(modes))])
                assert(len(modes) >= 1)
                output = self.read(1, modes[0])
                if (debug):
                    print("Output:",str(output))
                self.program_output.append(output)
                self.ptr += 2
            elif (opcode == 5):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value != 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 6):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value == 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 7):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 < operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 8):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 == operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 9):
                modes.extend([0 for _ in range(1-len(modes))])
                offset_change = self.read(1, modes[0])
                self.relative_base += offset_change
                self.ptr += 2
            else:
                print(self.program_output)
                raise Exception("Unknown opcode: " + str(opcode))

    def read(self, offset, mode):
        if mode == 0:
            return self.code[self.code[self.ptr+offset]]
        elif mode == 1:
            return self.code[self.ptr+offset]
        elif mode == 2:
            return self.code[self.relative_base + self.code[self.ptr + offset]]

    def write(self, offset, mode, value):
        if mode == 0:
            self.code[self.code[self.ptr+offset]] = value
        elif mode == 1:
            self.code[self.ptr+offset] = value
        elif mode == 2:
            self.code[self.relative_base + self.code[self.ptr + offset]] = value

    def get_last_output(self):
        return self.program_output[len(self.program_output)-1]

    def get_last_output_values(self, number):
        num_items = len(self.program_output)
        return self.program_output[num_items-number:num_items]

    def get_whole_output(self):
        return self.program_output

    def provide_input(self, i):
        self.program_input.append(i)

    def has_terminated(self):
        return True if self.state == "TERMINATED" else False

    def get_state(self):
        return self.state

    def set_relative_base(self, rel_base):
        self.relative_base = rel_base

    def set_state(self, state):
        self.state = state

    def set_ptr(self, ptr):
        self.ptr = ptr

    def set_program_output(self, output):
        self.program_output = output

    def copy(self):
        c = Computer(self.code, self.program_input.copy())
        c.set_relative_base = self.relative_base
        c.state = self.state
        c.ptr = self.ptr
        c.program_output = self.program_output.copy()
        return c

def evaluate_instruction(instruction):
    opcode_low = instruction % 10
    instruction = int(instruction / 10)
    opcode_high = instruction % 10
    opcode = opcode_high * 10 + opcode_low
    instruction = int(instruction / 10)

    modes = []
    while(instruction > 0):
        modes.append(instruction % 10)
        instruction = int(instruction / 10)

    return [opcode, modes]

Day 16: python

Day 16 - Solution in Python

That was fun - looks quite arbitrary for a FFT :) Part 2: Not sure why it only works for input.txt and one of the tests - maybe a minor offset problem - well, works for the input and hence contributed to rescuing Santa …​

import math
import sys
import numpy as np

def fft(output_list, num_phases):
    pattern = (0, 1, 0, -1)
    for phase in range(num_phases):
        print("Phase",phase)
        input_list = output_list
        output_list = ''
        for i in range(len(input_list)):
            current_pattern = [x for x in pattern for _ in range(i+1)]
            sum_of_phase = 0
            for j in range(len(input_list)):
                val = input_list[j]
                index = (j+1) % len(current_pattern)
                multiplier = current_pattern[index]
                sum_of_phase += int(val) * multiplier
            output_list += str(sum_of_phase)[len(str(sum_of_phase))-1]
    return output_list[0:8]

if __name__ == "__main__":
    input = "59712692690937920492680390886862131901538154314496197364022235676243731306353384700179627460533651346711155314756853419495734284609894966089975988246871687322567664499495407183657735571812115059436153203283165299263503632551949744441033411147947509168375383038493461562836199103303184064429083384309509676574941283043596285161244885454471652448757914444304449337194545948341288172476145567753415508006250059581738670546703862905469451368454757707996318377494042589908611965335468490525108524655606907405249860972187568380476703577532080056382150009356406585677577958020969940093556279280232948278128818920216728406595068868046480073694516140765535007"
    # input = "03036732577212944063491565474664"
    # input = "02935109699940807407585447034323"
    # input = "03081770884921959731165446850517"
    # result = fft(input, 100)
    # print("Star 1:",result)

    # Star 2
    # input: 650 characters long

    # COMP RESULT
    def compute_output(list_a, list_b):
        val = 0
        for idx in reversed(range(len(list_a))):
            val += list_a[idx]
            list_b[idx] = val % 10
        list_a[idx:len(list_a)] = list_b[idx:len(list_b)].copy()
        return list_a

    input_list = [int(x) for x in list(input)]
    offset = int(input[0:7])
    total_size = len(input_list) * 10001
    assert(offset > (total_size / 2))

    # create long input list
    offset_in_input_list = offset % len(input_list)
    input_list_long = input_list[offset_in_input_list:].copy()
    num_lists_at_the_end = math.floor((len(input_list)*10000 - (offset+1)) / len(input_list))
    for i in range(num_lists_at_the_end):
        input_list_long.extend(input_list.copy())

    # Phase 1-100:
    tmp_input_list = np.zeros(len(input_list_long), dtype=np.int16)#list_a.copy()
    for i in range(100):
        print("Phase",i)
        input_list_long = compute_output(input_list_long, tmp_input_list)
        print(input_list_long[0:8])
from solution import fft
import pytest

#result = fft("12345678", 4)
#assert(result == "01029498")

result = fft("80871224585914546619083218645595", 100)
assert(result == "24176176")

result = fft("19617804207202209144916044189917", 100)
assert(result == "73745418")

result = fft("69317163492948606335995924319873", 100)
assert(result == "52432133")

Day 17: python

Day 17 - Solution in Python

Did part 2 manually - like everybody on reddit ;-)

from scaffold import get_intersection, cleanup

fd = open("input.txt")
line = fd.readline().strip()
code = [int(x) for x in line.split(',')]

get_intersection(code.copy())
cleanup(code.copy())
from computer import Computer
from collections import defaultdict

def get_intersection(code):
    computer = Computer(code, [])
    computer.run()

    x = 0
    y = 0
    sum_alignment = 0
    items = defaultdict(list)
    for ascii_item in computer.get_whole_output():
        if ascii_item == 10:
            y += 1
            print()
        else:
            x += 1
            items[y].append(ascii_item)
            print(chr(ascii_item), end='')

    # check for intersections
    sum_alignment = 0
    num_intersections = 0
    for x in range(len(items[0])):
        for y in range(len(items.keys())):
            if x > 0 and x < len(items[0])-1:
                if y > 0 and y < len(items.keys())-1:
                    if chr(items[y][x]) == '#' and chr(items[y-1][x]) == '#' and chr(items[y+1][x]) == '#' and chr(items[y][x-1]) == '#' and chr(items[y][x+1]) == '#':
                        num_intersections += 1
                        sum_alignment += x*y
    print("Star 1: Sum of alignment:",sum_alignment)

def cleanup(code):

    code[0] = 2
    input_main_routine = "A,A,B,B,C,B,C,B,C,A"
    input_function_a = "L,10,L,10,R,6"
    input_function_b = "R,12,L,12,L,12"
    input_function_c = "L,6,L,10,R,12,R,12"

    input_vector = [ord(x) for x in list(input_main_routine)]
    input_vector.append(10)
    input_vector.extend([ord(x) for x in list(input_function_a)])
    input_vector.append(10)
    input_vector.extend([ord(x) for x in list(input_function_b)])
    input_vector.append(10)
    input_vector.extend([ord(x) for x in list(input_function_c)])
    input_vector.append(10)
    input_vector.extend([ord('n'), 10])

    computer = Computer(code, input_vector)
    computer.run()
    print("Star 2 result:",computer.get_last_output())
debug = 0

class Computer:

    def __init__(self, code, program_input):
        self.code = [ 0 if x >= len(code) else code[x] for x in range(5000) ]
        self.ptr = 0 # ptr: instruction pointer
        self.program_output = []
        self.program_input = program_input
        self.state = "INITIALIZED"
        self.relative_base = 0

    def run(self):
        while(True):
            self.state = "RUNNING"
            [opcode, modes] = evaluate_instruction(self.code[self.ptr])
            if (opcode == 99):
                self.state = "TERMINATED"
                return
            elif (opcode == 1):
                modes.extend([0 for _ in range(3-len(modes))])
                summand_1 = self.read(1, modes[0])
                summand_2 = self.read(2, modes[1])
                self.write(3, modes[2], summand_1 + summand_2)
                self.ptr += 4
            elif (opcode == 2):
                modes.extend([0 for _ in range(3-len(modes))])
                factor_1 = self.read(1, modes[0])
                factor_2 = self.read(2, modes[1])
                self.write(3, modes[2], factor_1 * factor_2)
                self.ptr += 4
            elif (opcode == 3):
                modes.extend([0 for _ in range(1-len(modes))])
                if (len(self.program_input) == 0):
                    self.state = "WAITING_FOR_INPUT"
                    return # wait for input
                self.write(1, modes[0], self.program_input.pop(0))
                self.ptr += 2
            elif (opcode == 4):
                modes.extend([0 for _ in range(1-len(modes))])
                assert(len(modes) >= 1)
                output = self.read(1, modes[0])
                if (debug):
                    print("Output:",str(output))
                self.program_output.append(output)
                self.ptr += 2
            elif (opcode == 5):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value != 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 6):
                modes.extend([0 for _ in range(2-len(modes))])
                value = self.read(1, modes[0])
                jump_to = self.read(2, modes[1])
                if value == 0:
                    self.ptr = jump_to
                else:
                    self.ptr += 3
            elif (opcode == 7):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 < operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 8):
                modes.extend([0 for _ in range(3-len(modes))])
                operand_1 = self.read(1, modes[0])
                operand_2 = self.read(2, modes[1])
                if operand_1 == operand_2:
                    self.write(3, modes[2], 1)
                else:
                    self.write(3, modes[2], 0)
                self.ptr += 4
            elif (opcode == 9):
                modes.extend([0 for _ in range(1-len(modes))])
                offset_change = self.read(1, modes[0])
                self.relative_base += offset_change
                self.ptr += 2
            else:
                print(self.program_output)
                raise Exception("Unknown opcode: " + str(opcode))

    def read(self, offset, mode):
        if mode == 0:
            return self.code[self.code[self.ptr+offset]]
        elif mode == 1:
            return self.code[self.ptr+offset]
        elif mode == 2:
            return self.code[self.relative_base + self.code[self.ptr + offset]]

    def write(self, offset, mode, value):
        if mode == 0:
            self.code[self.code[self.ptr+offset]] = value
        elif mode == 1:
            self.code[self.ptr+offset] = value
        elif mode == 2:
            self.code[self.relative_base + self.code[self.ptr + offset]] = value

    def get_last_output(self):
        return self.program_output[len(self.program_output)-1]

    def get_last_output_values(self, number):
        num_items = len(self.program_output)
        return self.program_output[num_items-number:num_items]

    def get_whole_output(self):
        return self.program_output

    def provide_input(self, i):
        self.program_input.append(i)

    def has_terminated(self):
        return True if self.state == "TERMINATED" else False

    def get_state(self):
        return self.state

    def set_relative_base(self, rel_base):
        self.relative_base = rel_base

    def set_state(self, state):
        self.state = state

    def set_ptr(self, ptr):
        self.ptr = ptr

    def set_program_output(self, output):
        self.program_output = output

    def copy(self):
        c = Computer(self.code, self.program_input.copy())
        c.set_relative_base = self.relative_base
        c.state = self.state
        c.ptr = self.ptr
        c.program_output = self.program_output.copy()
        return c

def evaluate_instruction(instruction):
    opcode_low = instruction % 10
    instruction = int(instruction / 10)
    opcode_high = instruction % 10
    opcode = opcode_high * 10 + opcode_low
    instruction = int(instruction / 10)

    modes = []
    while(instruction > 0):
        modes.append(instruction % 10)
        instruction = int(instruction / 10)

    return [opcode, modes]