zerosleeps

Since 2010

Advent of Code 2020 day 5

Saturday 5 December 2020

Back to Python today. I spent as long preparing the input as I did on anything else - for some reason I just can’t grok nested comprehensions in Python. Can write the equivalent nested loops no problem, but when it comes to re-factoring them…

Anyway here it is. Duplication in the row/column functions that could be better. And I’m sure there’s a cleverer way of grabbing multiple consecutive elements in an array for part two, like Ruby’s Enumerable#each_cons.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from pathlib import Path
import unittest

class BoardingPass():
    def __init__(self, input):
        self.input = input

    @property
    def row(self):
        candidates = list(range(128))
        for char in self.input[0:7]:
            if char == 'F':
                candidates = candidates[0:int(len(candidates) / 2)]
            else:
                candidates = candidates[int(len(candidates) / 2):]
        return candidates[0]

    @property
    def column(self):
        candidates = list(range(8))
        for char in self.input[-3:]:
            if char == 'L':
                candidates = candidates[0:int(len(candidates) / 2)]
            else:
                candidates = candidates[int(len(candidates) / 2):]
        return candidates[0]

    @property
    def seat_id(self):
        return ( self.row * 8 ) + self.column

def get_raw_input():
    return (Path(__file__).parent / 'day_05_input.txt').read_text()

def parse_raw_input(raw_input):
    return [ [ char for char in row.strip() ] for row in raw_input.strip().splitlines() ]

def part_one(raw_input):
    seat_ids = [ BoardingPass(parsed_input).seat_id for parsed_input in parse_raw_input(raw_input)]
    return max(seat_ids)

def part_two(raw_input):
    seat_ids = sorted(
        [ BoardingPass(parsed_input).seat_id for parsed_input in parse_raw_input(raw_input)]
    )

    for i, seat_id in enumerate(seat_ids):
        if seat_ids[i + 1] != seat_ids[i] + 1:
            return seat_ids[i] + 1

if __name__ == '__main__':
    print(part_one(get_raw_input()))
    print(part_two(get_raw_input()))

class TestPartOneExamples(unittest.TestCase):
    def test_example_one(self):
        bp = BoardingPass('FBFBBFFRLR')
        self.assertEqual(bp.row, 44)
        self.assertEqual(bp.column, 5)
        self.assertEqual(bp.seat_id, 357)

    def test_example_two(self):
        bp = BoardingPass('BFFFBBFRRR')
        self.assertEqual(bp.row, 70)
        self.assertEqual(bp.column, 7)
        self.assertEqual(bp.seat_id, 567)

    def test_example_three(self):
        bp = BoardingPass('FFFBBBFRRR')
        self.assertEqual(bp.row, 14)
        self.assertEqual(bp.column, 7)
        self.assertEqual(bp.seat_id, 119)

    def test_example_four(self):
        bp = BoardingPass('BBFFBBFRLL')
        self.assertEqual(bp.row, 102)
        self.assertEqual(bp.column, 4)
        self.assertEqual(bp.seat_id, 820)

Advent of Code 2020 day 4

Saturday 5 December 2020

My solution for Advent of Code 2020 day 4, this time in Ruby. I have a working Python solution as well, but it’s ugly: Ruby shines with chained methods and blocks.

I have a faint feeling that we’ll be revisiting this passport thing in future challenges…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Passport
  def initialize(attributes)
    @attributes = attributes
  end

  def self.parse_raw_input(raw_input)
    raw_input
      .strip
      .split($/ + $/) # Passports are separated by two newlines in batch file
      .map do |passport|
        passport
          .gsub($/, ' ') # Each passport may be split into multiple lines
      end
      .map do |passport|
        passport
          .split # Conveniently, String.split also strips white-space
          .to_h do |element|
            [
              element.split(':').first.to_sym,
              element.split(':').last
            ]
          end
      end
  end

  def all_fields_present?
    [:byr, :iyr, :eyr, :hgt, :hcl, :ecl, :pid].all? do |f|
      @attributes.has_key?(f)
    end
  end

  def all_fields_valid?
    return false unless @attributes[:byr].to_i.between?(1920, 2002)
    return false unless @attributes[:iyr].to_i.between?(2010, 2020)
    return false unless @attributes[:eyr].to_i.between?(2020, 2030)
    return false unless (
      @attributes.has_key?(:hgt) && (
        @attributes[:hgt][-2..] == 'cm' && @attributes[:hgt][0..-3].to_i.between?(150, 193) ||
        @attributes[:hgt][-2..] == 'in' && @attributes[:hgt][0..-3].to_i.between?(59, 76)
      )
    )
    return false unless @attributes[:hcl] =~ /^#[\da-f]{6}$/
    return false unless ['amb', 'blu', 'brn', 'gry', 'grn', 'hzl', 'oth'].count(@attributes[:ecl]) == 1
    return false unless @attributes[:pid] =~ /^\d{9}$/
    return true
  end

end

def part_one(raw_input)
  passports = Passport.parse_raw_input(raw_input).map do |parsed_input|
    Passport.new(parsed_input)
  end
  passports.filter { |p| p.all_fields_present? }.length
end

def part_two(raw_input)
  passports = Passport.parse_raw_input(raw_input).map do |parsed_input|
    Passport.new(parsed_input)
  end
  passports.filter { |p| p.all_fields_valid? }.length
end

puts "Part one: #{part_one(IO.read(File.join(__dir__, '../day_04_input.txt')))}"
puts "Part two: #{part_two(IO.read(File.join(__dir__, '../day_04_input.txt')))}"

Advent of Code 2020 day 3

Friday 4 December 2020

My Python solution for Advent of Code 2020 day 3. Nested lists and row/column coordinates always make my brain hurt.

I took a gamble for part one and decided not to build the repeating pattern when needed, instead using the mod/wraparound approach. Got lucky that part two didn’t build on this component of the puzzle!

Grid could do with a little love, e.g. why does it have an ‘x’ getter but not a ‘y’ getter?

Ooh one other change I made is to the way I parse the puzzle input. In past years (and in this years previous challenges) I’ve usually had a get_input function that reads the input file and parses it. That has meant that my unit tests - with their hardcoded “example” inputs - have had to use pre-parsed inputs (or I’ve had to parse the example inputs manually before sticking it in the unit test).

I changed that today so that the Grid objects themselves parse raw input, and I can therefore feed them either text files or sample strings, which in turn means the parsing itself is now getting tested. Much better - will continue doing that.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
from math import prod
from pathlib import Path
import unittest

def get_input():
    return (Path(__file__).parent / 'day_03_input.txt').read_text()

class Grid():
    def __init__(self, input):
        self.grid = self.parse_input(input)
        self.position = {'x': 0, 'y': 0}

    @classmethod
    def parse_input(self, input):
        return [ [ char for char in line.strip() ] for line in input.splitlines() ]

    @property
    def grid_height(self):
        return len(self.grid)

    @property
    def grid_width(self):
        """Return width of slope

        Assumes all rows have the same width
        """
        return len(self.grid[0])

    @property
    def x(self):
        """Return effective x position

        Accounts for arboreal genetics and biome stability
        """
        return self.position['x'] % self.grid_width

    def past_bottom(self):
        if self.position['y'] > ( self.grid_height - 1 ):
            return True
        else:
            return False

    def slope(self, delta_x, delta_y):
        obstacles = []
        while not self.past_bottom():
            obstacles.append(self.grid[self.position['y']][self.x])
            self.position['y'] += delta_y
            self.position['x'] += delta_x
        return obstacles

def part_one(input):
    return Grid(input).slope(3,1).count('#')

def part_two(input):
    slope_results = []
    slopes_to_check = [[1,1],[3,1],[5,1],[7,1],[1,2]]
    for slope in slopes_to_check:
        grid = Grid(input)
        slope_results.append(grid.slope(slope[0], slope[1]).count('#'))
    return prod(slope_results)

class TestExamples(unittest.TestCase):
    def setUp(self):
        self.example_grid = """..##.......
            #...#...#..
            .#....#..#.
            ..#.#...#.#
            .#...##..#.
            ..#.##.....
            .#.#.#....#
            .#........#
            #.##...#...
            #...##....#
            .#..#...#.#"""

    def test_part_one(self):
        self.assertEqual(part_one(self.example_grid), 7)

    def test_part_two(self):
        self.assertEqual(part_two(self.example_grid), 336)

if __name__ == '__main__':
    print(f'Part one: {part_one(get_input())}')
    print(f'Part two: {part_two(get_input())}')

Advent of Code 2020 day 2

Wednesday 2 December 2020

My Python solution for Advent of Code 2020 day 2. Taking the object-orientated path when I tackled part one didn’t really buy me much for part two, but I stand by my decision!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from pathlib import Path
import re
import unittest

def get_input():
    input_file = Path(__file__).parent / 'day_02_input.txt'

    with open(input_file) as file:
        return [line.strip() for line in file.readlines()]

class Password():
    def __init__(self, input):
        match = re.match('^(\d+)-(\d+) (\w): (\w+)$', input)
        self.min = int(match[1])
        self.max = int(match[2])
        self.letter = match[3]
        self.password = match[4]

    def valid_password(self):
        c = self.password.count(self.letter)
        if c >= self.min and c <= self.max:
            return True
        else:
            return False

    def new_valid_password(self):
        if (self.password[self.min - 1] == self.letter) ^ (self.password[self.max - 1] == self.letter):
            return True
        else:
            return False

class TestExamples(unittest.TestCase):
    def setUp(self):
        example_list = """1-3 a: abcde
                   1-3 b: cdefg
                   2-9 c: ccccccccc"""
        self.passwords = [Password(p.strip()) for p in example_list.splitlines()]

    def test_part_one(self):
        self.assertEqual(len([p for p in self.passwords if p.valid_password()]), 2)

    def test_part_two(self):
        self.assertEqual(len([p for p in self.passwords if p.new_valid_password()]), 1)

if __name__ == '__main__':
    passwords = [Password(p) for p in get_input()]
    print(f'Part one: {len([p for p in passwords if p.valid_password()])}')
    print(f'Part two: {len([p for p in passwords if p.new_valid_password()])}')

Advent of Code 2020 day 1

Wednesday 2 December 2020

My Python solution for Advent of Code 2020 day 1. I’ve cleaned this up a wee bit since submitting my answers, but the essence of it hasn’t changed. I did use itertools.permutations at first, which happened to work because the loop bails out as soon as it finds a solution, but I changed it to itertools.combinations for readability.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from pathlib import Path
from itertools import combinations
from math import prod
import unittest

def get_input():
    input_file = Path(__file__).parent / 'day_01_input.txt'

    with open(input_file) as file:
        return [int(line.strip()) for line in file.readlines()]

def run(input, length):
    for p in combinations(input, length):
        if sum(p) == 2020:
            return(prod(p))

class TestExamples(unittest.TestCase):
    def setUp(self):
        self.input = [1721,979,366,299,675,1456]

    def test_part_one(self):
        self.assertEqual(run(self.input, 2), 514579)

    def test_part_two(self):
        self.assertEqual(run(self.input, 3), 241861950)

if __name__ == '__main__':
    print(f'Part one: {run(get_input(), 2)}')
    print(f'Part two: {run(get_input(), 3)}')