zerosleeps

Since 2010

Advent of Code 2020 day 14

Monday 14 December 2020

Advent of Code 2020 day 14. Great fun, which was a relief after my struggle with yesterday’s nonsense.

Took me a while to work out a nice way of building all the permutations for part two, but I settled on pushing the two permutations for each “bit” onto a stack and continually pulling them off the other end until no more with the mask were left.

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
def get_raw_input()
  IO.read(File.join(__dir__, '../day_14_input.txt'))
end

def parse_raw_input(raw_input)
    raw_input.strip.lines(chomp: true)
end

def apply_bitmask(input, mask)
  ( input | mask.tr('X', '0').to_i(2) ) & mask.tr('X', '1').to_i(2)
end

def parse_instruction(instruction)
  instruction.match(/^mem\[(?<location>\d+)\] = (?<value>\d+)$/).named_captures
end

def apply_bitmask_v2(input, mask)
  input = input.to_s(2).rjust(36, '0')
  mask.chars.each_with_index do |c,i|
    case c
    when '1'
      input[i] = '1'
    when 'X'
      input[i] = 'X'
    end
  end

  permutations = [input]
  while permutations.any? { |e| e.include?('X') }
    perm = permutations.shift
    permutations << perm.sub(/X/, '0')
    permutations << perm.sub(/X/, '1')
  end
  permutations
end

def run(parsed_input, version=1)
  memory = {}
  mask = ''
  parsed_input.each do |line|
    if line =~ /^mask = /
      mask = line.split.last
    else
      instruction = parse_instruction(line)
      if version == 1
        memory[instruction['location']] = apply_bitmask(instruction['value'].to_i, mask)
      else
        apply_bitmask_v2(instruction['location'].to_i, mask).each do |location|
          memory[location.to_i(2)] = instruction['value'].to_i
        end
      end
    end
  end
  memory.values.sum
end

puts "Part one: #{run(parse_raw_input(get_raw_input))}"
puts "Part two: #{run(parse_raw_input(get_raw_input), 2)}"

Advent of Code 2020 day 13

Monday 14 December 2020

Advent of Code 2020 day 13.

This was a struggle for me. Part one was easy enough (haven’t even bothered to include my code for that below), but I chipped away at part two for several hours before getting a solution.

The subreddit was full of people talking about Chinese Remainder Theorem which has a Wikipedia page that might as well be smeared across my wall in custard. The acronym “LCM” kept coming up as well, which I now know stands for “lowest common multiple”, and does a much better job of describing itself than the Chinese remainder theorem does.

Many sheets of paper later I realised how LCM could be used, basically to keep increasing the “period” whenever more than one of the buses were in sync.

No fun - all mathematics and pattern recognition. As a result the code you see below is crap because I can’t face looking at this puzzle any more now I have my answer.

As I type day 14’s puzzle has been out for 20 minutes as well, so I’m going to post this and see what the next one brings.

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
def low_com_mul(i)
    return i.reduce(1, :lcm)
end

buses = INPUT.strip.lines.last.split(',').map { |e| e == 'x' ? nil : e.to_i }
departures = Array.new(buses)

max_bus = buses.compact.max
max_bus_index = buses.index(max_bus)

period = max_bus
time = max_bus - max_bus_index
synced_buses = []

while departures.compact.any? { |e| e != 0 }
    if low_com_mul(synced_buses) > period
        period = low_com_mul(synced_buses)
        puts "Period changed to #{period}"
    end
    time += period
    synced_buses.clear
    departures = buses.each_with_index.map do |e, i|
        unless e == nil
            bus_offset = ((time + i) % e) # 0 if the bus is in the right place at the right time
            synced_buses << e if bus_offset == 0
            bus_offset
        end
    end
end
puts time

Advent of Code 2020 day 12

Saturday 12 December 2020

Advent of Code 2020 day 12. This one was really good fun - my favourite yet. Of course, as soon as I’d finished cleaning up I had a look at some of the solutions other folks had come up, and immediately felt a bit dumb. Seems I overcooked the rotation thing with all that trigonometry. Sod ‘em: I’m still very pleased with the structure and readability of my solution!

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
from math import radians, sin, cos
from pathlib import Path

class Point:
    FACINGS = ('north', 'east', 'south', 'west')

    # +-------> +x
    # |
    # |
    # |
    # +y

    def move(self, direction, distance):
        if direction == 'north':
            self.coordinates[1] -= distance
        elif direction == 'south':
            self.coordinates[1] += distance
        elif direction == 'east':
            self.coordinates[0] += distance
        elif direction == 'west':
            self.coordinates[0] -= distance

    def run_instruction(self, instruction):
        value = int(instruction[1:])

        if instruction[0] == 'N':
            self.move('north', value)
        elif instruction[0] == 'S':
            self.move('south', value)
        elif instruction[0] == 'E':
            self.move('east', value)
        elif instruction[0] == 'W':
            self.move('west', value)
        elif instruction[0] == 'L':
            self.rotate(-value)
        elif instruction[0] == 'R':
            self.rotate(value)
        elif instruction[0] == 'F':
            self.move(self.facing, value)

    def normalise_rotation(self, degrees):
        if degrees < 0:
            return degrees + 360
        else:
            return degrees

    def manhattan_distance(self):
        return sum([abs(c) for c in self.coordinates])

class Ship(Point):
    def __init__(self, version=1):
        self.coordinates = [0, 0]
        self.facing = 'east'

    def rotate(self, degrees):
        self.facing = self.FACINGS[(self.FACINGS.index(self.facing) +
                      int(self.normalise_rotation(degrees)/90))%4]

class Waypoint(Point):
    def __init__(self):
        self.coordinates = [10,-1]
        self.ship = Ship()

    def rotate(self, degrees):
        r = radians(self.normalise_rotation(degrees))

        self.coordinates = [
            round(cos(r) * (self.coordinates[0] - self.ship.coordinates[0]) -
                  sin(r) * (self.coordinates[1] - self.ship.coordinates[1]) +
                  self.ship.coordinates[0]),
            round(sin(r) * (self.coordinates[0] - self.ship.coordinates[0]) +
                  cos(r) * (self.coordinates[1] - self.ship.coordinates[1]) +
                  self.ship.coordinates[1])
        ]

    def distance_from_ship(self):
        return [
            self.coordinates[0] - self.ship.coordinates[0],
            self.coordinates[1] - self.ship.coordinates[1]
        ]

    def run_instruction(self, instruction):
        if instruction[0] == 'F':
            for _ in range(int(instruction[1:])):
                # Store waypoint's current distance from ship
                distance = self.distance_from_ship()
                # Move ship to waypoint
                self.ship.coordinates = self.coordinates
                # Move waypoint to new relative distance
                self.coordinates = [
                    self.ship.coordinates[0] + distance[0],
                    self.ship.coordinates[1] + distance[1]
                ]
        else:
            super().run_instruction(instruction)

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

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

def part_one(input):
    ship = Ship()
    for instruction in input:
        ship.run_instruction(instruction)
    return ship.manhattan_distance()

def part_two(input):
    waypoint = Waypoint()
    for instruction in input:
        waypoint.run_instruction(instruction)
    return waypoint.ship.manhattan_distance()

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

Advent of Code 2020 day 11

Friday 11 December 2020

Advent of Code 2020 day 11. Again this is a slightly sanitised version of the code used to submit my answers, but there’s a still a lot of duplication.

The trickiest and messiest part of this was dealing with negative list indexes for seats right at the edge of the grid. I briefly considered adding a gutter to the grid but that would only have caused a different assortment of edge cases.

Used pytest for this one as well. Nicer output than unittest, but for dead-simple cases like this I don’t see much difference.

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
101
102
103
104
105
106
import pytest
from pathlib import Path

def directions():
    return [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]

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

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

def get_adjacent(grid, seat, position):
    if (y := seat[0]+position[0]) < 0:
        return None
    if (x := seat[1]+position[1]) < 0:
        return None
    try:
        return grid[y][x]
    except IndexError:
        return None

def get_visible(grid, seat, direction):
    y = seat[0]+direction[0]
    x = seat[1]+direction[1]

    try:
        while y >= 0 and x >= 0 and grid[y][x] == '.':
            y += direction[0]
            x += direction[1]
        if y >= 0 and x >= 0:
            return grid[y][x]
        else:
            return None
    except IndexError:
        return None

def count_all_occupied_adjacent(grid, seat):
    return len(
        [
            result for result
            in (get_adjacent(grid, seat, position_to_check) for position_to_check in directions())
            if result == '#'
        ]
    )

def count_all_occupied_visible(grid, seat):
    return len(
        [
            result for result
            in (get_visible(grid, seat, direction_to_check) for direction_to_check in directions())
            if result == '#'
        ]
    )

def count_all_occupied(grid):
    return len([seat for row in grid for seat in row if seat == '#'])

def tick(grid, method, trigger):
    new_grid = [[seat for seat in row] for row in grid]
    last_count = 0
    iterations = 0

    while last_count != count_all_occupied(new_grid) or last_count == 0:
        last_count = count_all_occupied(grid)

        for y, row in enumerate(grid):
            for x, seat in enumerate(row):
                current_seat = grid[y][x]
                if method == 'visible':
                    count_of_occupied = count_all_occupied_visible(grid, [y, x])
                else:
                    count_of_occupied = count_all_occupied_adjacent(grid, [y, x])

                if current_seat == 'L' and count_of_occupied == 0:
                    new_grid[y][x] = '#'
                elif current_seat == '#' and count_of_occupied >= trigger:
                    new_grid[y][x] = 'L'

        grid = [[seat for seat in row] for row in new_grid]

    return last_count

class TestExamples():
    @pytest.fixture
    def example_input(self):
        return """L.LL.LL.LL
            LLLLLLL.LL
            L.L.L..L..
            LLLL.LL.LL
            L.LL.LL.LL
            L.LLLLL.LL
            ..L.L.....
            LLLLLLLLLL
            L.LLLLLL.L
            L.LLLLL.LL"""

    def test_part_one_example(self, example_input):
        assert tick(parse_raw_input(example_input), 'adjacent', 4) == 37

    def test_part_two_example(self, example_input):
        assert tick(parse_raw_input(example_input), 'visible', 5) == 26

if __name__ == '__main__':
    print(tick(parse_raw_input(get_raw_input()), 'adjacent', 4))
    print(tick(parse_raw_input(get_raw_input()), 'visible', 5))

Advent of Code 2020 day 10 part 2

Friday 11 December 2020

Advent of Code 2020 day 10 part two. Not in the mood for this one. My solution has been stolen from /u/ald_loop’s incredibly thorough and generous explanation.

No amount of stepping through this line-by-line in a debugger has lifted the brain-fog. Obviously the code is programming-101 stuff, it’s simply that I’m unable to link the logic to the problem and the solution.

I’ll revisit this in the future, but for now I’m just going to let it go.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def part_two(parsed_input):
    # Add charging outlet and device to list of adapters
    parsed_input += [0, max(parsed_input)+3]
    parsed_input = sorted(parsed_input)

    dp = [0]*len(parsed_input)
    # There's only one path to the charging outlet
    dp[0] = 1
    for i in range(1, len(parsed_input)):
        sm = 0
        for j in range(1,4): # 1, 2, 3
            if i-j < 0:
                # Skip out-of-range checks at the start of the process
                continue
            if parsed_input[i]-parsed_input[i-j] <= 3:
                # Candidate adapter
                sm += dp[i-j]
        dp[i] = sm
    return dp[-1]