Home Notes Advent of code 2019 solutions

Advent Of Code 2019 Solutions

Python solutions to the daily coding puzzles, explained.

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.

I first participated in Advent of Code in 2018. I enjoyed working on the challenges and I learned a lot. The goal of the advent of code is to try to get on the leaderboard which is the fastest people to complete the problem when it is released at midnight.

Last year my goal was to complete all the problems. This year I will focus on writing clean code and writing more about my experience.

Each code snippet is complete, runnable program. I have included my input for each day. While you are in the directory for the day (ex. /Day-01) you can run the code line this

$ python solution.py input.txt

You can also find all of these solutions on Github: lazydancer/Advent-of-Code-2019

Table of Contents

Day 1: The Tyranny of the Rocket Equation

For Part 1, we simply need to divide each module weight by 3 and substact 2. The only thing in my code that is unusally is the ‘//’ which is an integer divide. It acts as a round down function.

For Part 2, we need to account for the extra weight of the fuel. This is done with a while loop where it looks for values which would add more fuel. When the fuel get less than 8.9999… the result will be 0.

import fileinput

def part_1():
	module_weights = map(int, fileinput.input())
	fuel_calc = lambda x: x // 3 - 2

	return sum(map(fuel_calc, module_weights))	

def part_2():
	module_weights = map(int, fileinput.input())

	return sum(map(calculate_fuel, module_weights))

def calculate_fuel(module_weight):
	total_fuel = 0
	w = module_weight

	while w >= 9:
		w = w // 3 - 2
		total_fuel += w

	return total_fuel


print('The solution to part 1 is', part_1()) # 3188480
print('The solution to part 2 is', part_2()) # 4779847

The tyranny of the rocket equation relates to the ideal rocket equation. Which is interesting to derive. We have the follow the rule of conservation of momentum where the momentum in a closed system needs to remain constant.

All this simplifies to…

mdv = v_exhaust * dm

This makes sense the change in the momentum of the ship is the change in mass of the ship times the exhaust speed

Rearranging and integrating both sides with respect to time and knowing 1/x integrates to ln(x) and ln(a) - ln(b) = ln(a/b). Finds the ideal rocket equation.

v_final - v_inital = v-exhaust * ln(m_inital / m_final)

Day 2: 1202 Program Alarm

For part 1, we need a run program which would set the pointer every 4 numbers. This is done with a simple for loop but not robust if another size of jump is needed.

For part 2, we iterate over the program to find when a result is a desired number. The inputs are changed till the result is given. With only 100 possible values for the two. Leads to only 10,000 combinations and since order matters we look at the permutations using the builtin itertools module.

import fileinput
from itertools import permutations
import copy

def main():
    int_program = load_program()
    print('The solution to part 1 is', run_program(int_program, 12, 2)) # 4930687
    print('The solution to part 2 is', find_inputs(int_program, 19690720)) # 5335


def load_program():
    int_program = fileinput.input()[0]
    int_program = int_program.split(',')     
    int_program = list(map(int, int_program))
    return int_program


def find_inputs(int_program, value):
    for noun, verb in permutations(range(100), 2):
        if run_program(int_program, noun, verb) == value:
            return 100 * noun + verb


def run_program(input_int_program, noun, verb):
    int_program = copy.copy(input_int_program)

    int_program[1] = noun
    int_program[2] = verb

    for i in range(0, len(int_program), 4):
        if isComplete(int_program, i):
            break

        int_program = run_opcode(int_program, i)

    return int_program[0]


def run_opcode(int_program, i):
    opcode = int_program[i]
    first = int_program[i+1]
    second = int_program[i+2]
    result = int_program[i+3]

    if opcode == 1:
        int_program[result] = int_program[first] + int_program[second]
    elif opcode == 2:
        int_program[result] = int_program[first] * int_program[second]
    else:
        raise Error()

    return int_program


def isComplete(int_program, i):
    return int_program[i] == 99


main()

Day 3: Crossed Wires

This one was done in Rust

For Part 1, we can find the path in which each wire takes, creating a vector of locations. Finding where the two wires interset is looking at where both wire end at a location. We can use a set data type to find the union, in this case a HashSet finding an intersection.

For Part 2, we look for the shortest manhattan distance along the path of the wires.

use std::env;
use std::fs;
use std::collections::HashSet;

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    let input = fs::read_to_string(filename)
         .expect("Something went wrong reading the file");
    let mut lines = input.lines();

    let steps_0 = parse_line(lines.next().unwrap());
    let steps_1 = parse_line(lines.next().unwrap());

    let positions_0: HashSet<_> = steps_0.iter().cloned().collect();
    let positions_1: HashSet<_> = steps_1.iter().cloned().collect();
    let collisions = positions_0.intersection(&positions_1);
    let closest_collision = collisions.clone().map(|x| x.0.abs() + x.1.abs()).min();
    println!("Part One: {:?}", closest_collision.unwrap());

    let quickest_collision = collisions.map(|pos| steps_0.iter().position(|x| x == pos).unwrap() + steps_1.iter().position(|x| x == pos).unwrap() + 2).min();
    println!("Part Two: {:?}", quickest_collision.unwrap());
}

fn parse_step(step: &str) -> impl Iterator<Item = (isize, isize)> {
    let mut chars = step.chars();

    let coord = match chars.next() {
        Some('U') => (0, -1),
        Some('D') => (0,  1),
        Some('L') => (-1, 0),
        Some('R') => (1, 0),
        _         => (0, 0)
    };

    let dist: usize = chars.collect::<String>().parse().unwrap();
    
    std::iter::repeat(coord).take(dist)
}

fn parse_line(line: &str) -> Vec<(isize, isize)> {
    line.split(",").flat_map(parse_step).scan((0,0), |pos, step| {
        pos.0 += step.0;
        pos.1 += step.1;
        Some(pos.clone())
    }).collect()
}

Day 4: Secure Container

Part 1, we can find adjancent cells by taking a copy, shifting it by one and comparing against the original.

Part 2, we can use a BTreeMap and count all of the numbers given finding if any are equal to 2.

use std::collections::btree_map::BTreeMap;

fn only_doubles(x: u32) -> bool {
    let mut count = BTreeMap::new();

    for c in x.to_string().chars() {
        *count.entry(c).or_insert(0) += 1
    }

    count.iter().map(|(ch, count)| count).any(|x| (*x == 2))
}

fn adjancent_chars(x: u32) -> bool {
    let x = x.to_string();
    let chars_a: Vec<_> = x.chars().collect();
    let chars_b = &chars_a.clone()[1..];

    chars_a.iter().zip(chars_b.iter()).map(|(a, b)| a == b).any(|x| x)
}

fn always_increase(x: u32) -> bool {
    let x = x.to_string();
    let chars_a: Vec<_> = x.chars().map(|x| x.to_digit(10).unwrap()).collect();
    let chars_b = &chars_a.clone()[1..];

    chars_a.iter().zip(chars_b.iter()).map(|(a, b)| a <= b).all(|x| x)
}

fn main() {

    let mut part_1_count = 0;
    for i in 387638..919123 {
        if adjancent_chars(i) && always_increase(i) {
            part_1_count += 1;
        }
    }

    println!("{:?}", part_1_count); //466

    let mut part_2_count = 0;
    for i in 387638..919123 {
        if adjancent_chars(i) && always_increase(i) && only_doubles(i) {
            part_2_count += 1;
            println!("{:?}: {:?}", part_2_count, i);
        }
    }

    println!("{:?}", part_2_count); //292

}

Day 5: Sunny with a Chance of Asteroids

Back to python

Part 1, Using the old code from day 2, we had to introduce a new functions like input and ouput. The INPUT variable I made a global constant

Part 2, even more functions were added and we needed to separate the pointer from the for loop and introduced more functions

import fileinput
from itertools import permutations
import copy

INPUT = 1

def main():
    int_program = load_program()
    INPUT = 1
    print('The solution to part 1 is', run_program(int_program)) # 4930687
    INPUT = 5
    print('The solution to part 2 is', run_program(int_program)) # 5335


def load_program():
    int_program = fileinput.input()[0]
    int_program = int_program.split(',')     
    int_program = list(map(int, int_program))
    return int_program

def run_program(input_int_program):
    int_program = copy.copy(input_int_program)

    pointer = 0
    while int_program[pointer] != 99:

        old_pointer = copy.copy(pointer)

        (int_program, pointer) = run_opcode(int_program, pointer)

        if old_pointer == pointer:
            if int_program[pointer] % 10 in [1, 2, 7, 8]:
                pointer += 4
            elif int_program[pointer] % 10 in [5, 6]:
                pointer += 3
            elif int_program[pointer] % 10 in [3, 4]:
                pointer += 2


    return int_program[0]


def run_opcode(int_program, pointer):
    opcode = int_program[pointer]

    first = int_program[pointer+1] 
    second = int_program[pointer+2]
    third = int_program[pointer+3]

    first_parameter_mode = int((opcode % 1000 - opcode % 100) / 100) 
    second_parameter_mode = int((opcode % 10000 - opcode % 1000) / 1000)

    if(first_parameter_mode == 0):
        a = int_program[first]
    else:
        a = first

    if(second_parameter_mode == 0):
        b = int_program[second]
    else:
        b = second

    if opcode % 10 == 1:
        int_program[third] = a + b

    elif opcode % 10 == 2:
        int_program[third] = a * b

    elif opcode % 10 == 3:
        int_program[first] = INPUT 

    elif opcode % 10 == 4:
        print("TEST diagnotic program output:", int_program[first])

    elif opcode % 10 == 5:
        if a != 0:
            pointer = b

    elif opcode % 10 == 6:
        if a == 0:
            pointer = b 

    elif opcode % 10 == 7:
        if a < b:
            int_program[third] = 1
        else:
            int_program[third] = 0

    elif opcode % 10 == 8:
        if a == b:
            int_program[third] = 1
        else:
            int_program[third] = 0
    else:
        raise Error()

    return (int_program, pointer)

main()

Day 6: Universal Orbit Map

For part 1, we can set up a map which looks at what planet it orbits. For each planet going down the chain to the base. Finding the base is done by taking the differnce between two sets. The ‘guide’ is a hashmap for really quick lookup values

For part 2, we can find the path of YOU and SAN back to the base element and the paths will be common until a divergent step. Add up the remain elements that aren’t common to find the paths between them.

import fileinput

input = fileinput.input()
input = [line.strip().split(')') for line in input]

# hash guide from planet to lower orbit 
guide = {line[1]: line[0] for line in input}

# should be only one planet that doesn't have a guide value
(base,) = set(guide.values()) - set(guide.keys())

count = 0
for planet in guide:
    while planet != base:
        planet = guide[planet]
        count += 1


print('The solution to part 1 is:', count) # 162816


# Find the descent patterns of YOU and SAN
# Match the first common element
# Add up the above to find the transfer distance - 2
you_path = []
planet = 'YOU'
while planet != base:
    planet = guide[planet]
    you_path.append(planet)
you_path.reverse()

san_path = []
planet = 'SAN'
while planet != base:
    planet = guide[planet]
    san_path.append(planet)
san_path.reverse()

diverge_step = 0
for step in range(len(san_path)):
    if san_path[step] != you_path[step]:
        diverge_step = step - 1
        break;


steps_you = len(you_path) - diverge_step 
steps_san = len(san_path) - diverge_step

result = steps_san + steps_you - 2

print('The solution to part 2 is:', result)

Day 7: Amplification Circuit

For part 1, we can use the itertools library and use the permutations function to get the result of the max

For part 2, I didn’t get it done in the time I had. I think you need to keep the state of the program. I will come back to this, I will try to create a stateful ampifier class

import fileinput
from itertools import permutations

def main():
    program = fileinput.input()
    program = [int(i) for i in program[0].split(',')]

    highest = 0
    for phase_settings in permutations(range(0,5), 5):
        output = 0
        for phase in phase_settings:
            output = next(intcode_run(program, [phase, output]))
        
        highest = output if output > highest else highest

    print("The solution to part 1 is", highest)


def intcode_run(program, inputs):
    inputs = inputs[::-1]
    param = {}
    ptr = 0   
    skip = (4,4,2,2,3,3,4,4)

    while program[ptr] is not 99:
        opcode = program[ptr] % 10
        for i in range(1,4): 
            param[i] = ptr + i if program[ptr]//int('100'.ljust(i+2, '0')) % 10 else program[ptr + i]
        if opcode is 1: 
            program[param[3]] = program[param[1]] + program[param[2]]
        elif opcode is 2: 
            program[param[3]] = program[param[1]] * program[param[2]]
        elif opcode is 3: 
            program[param[1]] = int(inputs.pop())
        elif opcode is 4: 
            yield program[param[1]]
        elif opcode is 5 and program[param[1]] or opcode is 6 and not program[param[1]]: 
            ptr = program[param[2]] - 3
        elif opcode is 7: 
            program[param[3]] = 1 if program[param[1]] < program[param[2]] else 0
        elif opcode is 8: 
            program[param[3]] = 1 if program[param[1]] == program[param[2]] else 0
        ptr += skip[opcode-1]

main()

Day 8: Space Image Format

For part 1, we can split the transmission into different chunks and count the layer with the fews 0 by using the min and count function

For part 2, we just send to a function which returns 1 or 0 the first layer it sees them

import fileinput

WIDTH = 25
HEIGHT = 6

transmission = fileinput.input()[0].strip()

def chunks(l, n):
    for i in range(0, len(l), n):
        yield l[i:i+n]

layers = chunks(transmission, WIDTH * HEIGHT)

fewest_zeros, _ = min([(l, l.count("0")) for l in layers], key=lambda x: x[1])

print('The solution to part 1 is:', fewest_zeros.count('1') * fewest_zeros.count('2'))

def get_color(layers, i):
    for l in layers:
        if l[i] == '1':
            return '1'
        if l[i] == '0':
            return '0'

layers = list(chunks(transmission, WIDTH * HEIGHT))

img = []
for i in range(WIDTH * HEIGHT):
    color = get_color(layers, i)
    img.append(color)
    
for r in range(HEIGHT):
    print(''.join(img[r * WIDTH:(r + 1) * WIDTH]).replace('0', ' ').replace('1', 'x'))

Day 9: Sensor Boost

After debugging for a while, I have left this one where it is. I hope to come back to this challenge

import fileinput

def main():
    program = fileinput.input()
    program = [int(i) for i in program[0].split(',')]
    for output in intcode_run(program, []):
        print(output)


def intcode_run(program, inputs):
    inputs = inputs[::-1]
    param = {}
    ptr = 0   
    rb = 0

    while program[ptr] is not 99:
        opcode = program[ptr] % 10


        for i in range(1,4): 
            if program[ptr] // int(10**(i+1)) % 10  == 0:
                param[i] = program[ptr + i]
            if program[ptr] // int(10**(i+1)) % 10  == 1:
                param[i] = ptr + i
            if program[ptr] // int(10**(i+1)) % 10  == 2:
                param[i] = rb + program[ptr + i]


        if opcode is 1: 
            program[param[3]] = program[param[1]] + program[param[2]]
            ptr += 4
        elif opcode is 2: 
            program[param[3]] = program[param[1]] * program[param[2]]
            ptr += 4
        elif opcode is 3: 
            program[param[1]] = int(inputs.pop())
            ptr += 2
        elif opcode is 4: 
            yield program[param[1]]
            ptr += 2
        elif opcode is 5 and program[param[1]] or opcode is 6 and not program[param[1]]: 
            ptr = program[param[2]] - 3
            ptr += 3
        elif opcode is 6:
            raise "Number 6"
        elif opcode is 7: 
            program[param[3]] = 1 if program[param[1]] < program[param[2]] else 0
            ptr += 4
        elif opcode is 8: 
            program[param[3]] = 1 if program[param[1]] == program[param[2]] else 0
            ptr += 4
        elif opcode is 9:
            rb = program[param[1]]
            ptr += 2

main()

Day 10: Monitoring Station

For part one I selected an asteroid to check if it had the most lines of sight by creating an expanding box from the asteroid and using any asteroids as casting shadows on the ones behind it

import fileinput
import copy
import math

def main():
    asteroids = set()
    for y, line in enumerate(fileinput.input()):
        line = line.strip()
        for x, char in enumerate(line):
            if char == '#':
                asteroids.add((x, y))

    solution = max([visible_asteroids(ast, asteroids) for ast in asteroids])
    print("The solution to part 1 is", solution)


def visible_asteroids(ast, asteroids):
    local_asteroids = copy.copy(asteroids)
    space_width = max(asteroids)[0] * 2

    top_lefts = [(ast[0]-x, ast[1]-x) for x in range(space_width)]
    
    for i, tl in enumerate(top_lefts):
        width = i*2+1
    
        casts_shade = local_asteroids.intersection(ring(tl, width))

        for cs in casts_shade:
            shaded = shade_mapping(ast, cs, space_width)
            local_asteroids -= shaded


    return len(local_asteroids)



def shade_mapping(c, b, width):
    x_offset = b[0] - c[0]
    y_offset = b[1] - c[1]
    
    gcd = math.gcd(x_offset, y_offset)

    if gcd != 0:
        x_offset = int(x_offset / gcd)
        y_offset = int(y_offset / gcd)

    shaded = set()
    for i in range(1, width):
        shaded.add((b[0] + x_offset * i, b[1] + y_offset * i))

    return shaded


def ring(tl_loc, width):
    x, y = tl_loc

    result = set()

    for i in range(width):
        result.add((tl_loc[0] + i, tl_loc[1]))
    for i in range(1, width):
        result.add((tl_loc[0] + width-1, tl_loc[1] + i))
    for i in range(1, width):
        result.add((tl_loc[0] + width-1 - i, tl_loc[1] +  width-1))
    for i in range(1, width-1):
        result.add((tl_loc[0], tl_loc[1] + width-1 - i))

    return result

main()