zerosleeps

Since 2010

Advent of Code 2020 day 8

Thursday 10 December 2020

Advent of Code 2020 day 8. Happy with the logic, but not particularly happy with the implementation: lots of while loops and if statements that all look the same when you squint at the code.

Rather than reuse the same Console object for each iteration in part two and reset it’s state, I wish I’d created a new object for each iteration. But this works and I’m behind, so on to day 9.

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from pathlib import Path
import unittest

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

class Console():
    def __init__(self, raw_input):
        self.instructions = self.parse_raw_input(raw_input)
        self.accumulator = 0
        self.next_instruction = 0
        self.instruction_log = []
        self.mutate_line = -1

    @staticmethod
    def parse_raw_input(raw_input):
        return [
            (line.strip().split()[0], int(line.strip().split()[1]))
            for line
            in raw_input.strip().splitlines()
        ]

    def reset_state(self):
        self.accumulator = 0
        self.next_instruction = 0
        self.instruction_log = []

    def run(self):
        while self.next_instruction not in self.instruction_log:
            try:
                current_instruction = self.instructions[self.next_instruction]
            except IndexError:
                return (self.accumulator, 0)

            self.instruction_log.append(self.next_instruction)
            self.next_instruction += 1

            if current_instruction[0] == 'acc':
                self.accumulator += int(current_instruction[1])
            elif current_instruction[0] == 'jmp':
                self.next_instruction += (int(current_instruction[1]) - 1)
            elif current_instruction[0] == 'nop':
                pass

        return self.accumulator

    def mutate_input(self):

        last_line_mutated = self.mutate_line

        if last_line_mutated >= 0:
            # Revert previous mutation
            if self.instructions[last_line_mutated][0] == 'nop':
                self.instructions[last_line_mutated] = ('jmp', self.instructions[last_line_mutated][1])
            else:
                self.instructions[last_line_mutated] = ('nop', self.instructions[last_line_mutated][1])

            self.reset_state()

        self.mutate_line += 1

        while self.instructions[self.mutate_line][0] not in ['nop', 'jmp']:
            self.mutate_line += 1

        if self.instructions[self.mutate_line][0] == 'nop':
            self.instructions[self.mutate_line] = ('jmp', self.instructions[self.mutate_line][1])
        else:
            self.instructions[self.mutate_line] = ('nop', self.instructions[self.mutate_line][1])
        return True

def part_one(raw_input):
    return Console(raw_input).run()

def part_two(raw_input):
    c = Console(raw_input)
    while type(c.run()) != tuple:
        c.mutate_input()
    return c.accumulator

class TestExamples(unittest.TestCase):
    def setUp(self):
        self.example_input = """nop +0
            acc +1
            jmp +4
            acc +3
            jmp -3
            acc -99
            acc +1
            jmp -4
            acc +6"""

    def test_part_one(self):
        self.assertEqual(part_one(self.example_input), 5)

    def test_part_one(self):
        self.assertEqual(part_two(self.example_input), 8)

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

Advent of Code 2020 day 7

Wednesday 9 December 2020

Advent of Code 2020 day 7. I really struggled with this one. I never studied this sort of tree traversal stuff, and I’ve never had to do anything like it so it was all guess work. Pretty satisfying to finally figure it out though!

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
85
86
87
88
89
90
from pathlib import Path
import re
import unittest

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

def get_bag_from_input(input):
    return input.strip().split(' bags contain ')[0]

def get_contents_from_input(input):
    if re.search(r'no other bags', input):
        return {}
    else:
        return {
            ' '.join(bag.split()[1:-1]): int(bag.split()[0])
            for bag
            in input.strip().split(' bags contain ')[1].rstrip('.').split(', ')
        }

def parents_for_target(target, rules):
    return [bag for bag, contents in rules.items() if target in contents]

def number_of_children(bag, all_rules):
    count = 0
    if len(all_rules[bag]) > 0:
        for b, q in all_rules[bag].items():
            count += ( q * number_of_children(b, all_rules))
    return count + 1 # Plus one to account for current bag as well

def part_one(raw_input):
    rules = {
        get_bag_from_input(line):get_contents_from_input(line)
        for line
        in raw_input.strip().splitlines()
    }

    candidates = set(parents_for_target('shiny gold', rules))

    growth = True
    while growth:
        new_candidates = { b for c in candidates for b in parents_for_target(c, rules) }
        if new_candidates <= candidates:
            growth = False
        candidates.update(new_candidates)

    return len(candidates)

def part_two(raw_input):
    all_rules = {
        get_bag_from_input(line):get_contents_from_input(line)
        for line
        in raw_input.strip().splitlines()
    }

    return number_of_children('shiny gold',all_rules) - 1

class TestExamples(unittest.TestCase):
    def setUp(self):
        self.example_input = """light red bags contain 1 bright white bag, 2 muted yellow bags.
            dark orange bags contain 3 bright white bags, 4 muted yellow bags.
            bright white bags contain 1 shiny gold bag.
            muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
            shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
            dark olive bags contain 3 faded blue bags, 4 dotted black bags.
            vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
            faded blue bags contain no other bags.
            dotted black bags contain no other bags.
        """

    def test_part_one(self):
        self.assertEqual(part_one(self.example_input), 4)

    def test_part_two_example_one(self):
        self.assertEqual(part_two(self.example_input), 32)

    def test_part_two_example_two(self):
        example_input = """shiny gold bags contain 2 dark red bags.
            dark red bags contain 2 dark orange bags.
            dark orange bags contain 2 dark yellow bags.
            dark yellow bags contain 2 dark green bags.
            dark green bags contain 2 dark blue bags.
            dark blue bags contain 2 dark violet bags.
            dark violet bags contain no other bags.
        """
        self.assertEqual(part_two(example_input), 126)

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

Advent of Code 2020 day 6

Sunday 6 December 2020

My Python solution for Advent of Code 2020 day 6. My initial working version was much more verbose than the copy below, but the tools used were the same - set and collections.Counter.

Very happy with my decision back during day 3 to split up puzzle input retrieval from parsing - it’s made testing the puzzle examples using the same code paths as testing my actual input much easier, which in turn makes me more likely to actually write those tests.

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
85
from collections import Counter
from pathlib import Path
import unittest

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

def parse_raw_input(raw_input):
    return [
            [
                [ char for char in person.strip() ]
            for person in group.splitlines() ]
        for group in raw_input.strip().split('\n\n')
    ]

class Group():
    def __init__(self, input):
        self.people = [person for person in input]

    @property
    def flattened_questions(self):
        return [question for person in self.people for question in person]

    @property
    def unique_questions(self):
        return set(self.flattened_questions)

    @property
    def questions_answered_by_all(self):
        counter = Counter(self.flattened_questions)
        return [question for question, count in counter.items() if count == len(self.people)]

def part_one(parsed_input):
    return sum([len(Group(group).unique_questions) for group in parsed_input])

def part_two(parsed_input):
    return sum([len(Group(group).questions_answered_by_all) for group in parsed_input])

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

class TestPartOneExamples(unittest.TestCase):
    def test_example_one(self):
        example = """abcx
            abcy
            abcz"""
        self.assertEqual(part_one(parse_raw_input(example)), 6)

    def test_example_two(self):
        example = """abc

            a
            b
            c

            ab
            ac

            a
            a
            a
            a

            b"""
        self.assertEqual(part_one(parse_raw_input(example)), 11)

class TestPartTwoExample(unittest.TestCase):
    def test_example(self):
        example = """abc

            a
            b
            c

            ab
            ac

            a
            a
            a
            a

            b"""
        self.assertEqual(part_two(parse_raw_input(example)), 6)

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')))}"