zerosleeps

Since 2010

Advent of Code 2020 day 17

Friday 18 December 2020

Advent of Code 2020 day 17.

I spent ages trying to create a 3-dimension array for part 1 but gave up and went for a dictionary approach instead with nasty looking keys. Should have used tuples for the keys. It turns out that using a dict helped for part two anyway.

My solutions to the challenges are getting less-and-less production-quality as the days go on…

Here’s my solution for part two: part one was the same just without the ‘w’ dimension.

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
import re

class Cube4D(object):
    def __init__(self, raw_input):
        self.cube = {
            f'x{xi}y{yi}z0w0': x
            for yi, y in enumerate(raw_input.strip().splitlines())
            for xi, x in enumerate(y.strip())
        }

    def all_neighbours(self, c):
        x0, y0, z0, w0 = [int(i) for i in re.match(r'^x(-*\d+)y(-*\d+)z(-*\d+)w(-*\d+)$', c).groups()]
        return [
            self.cube.get(f'x{x}y{y}z{z}w{w}', '.')
            for w in range(w0-1, w0+2)
            for z in range(z0-1, z0+2)
            for y in range(y0-1, y0+2)
            for x in range(x0-1, x0+2)
            if (z, y, x, w) != (z0, y0, x0, w0)
        ]

    def count_active_neighbours(self, c):
        return len([ n for n in self.all_neighbours(c) if n == '#' ])

    def count_all_active(self):
        return len([ c for c in self.cube.values() if c == '#' ])

    def get_new_state(self, c):
        if self.cube.get(c, '.') == '#':
            if self.count_active_neighbours(c) in [2, 3]:
                return '#'
            else:
                return '.'
        elif self.cube.get(c, '.') == '.' and self.count_active_neighbours(c) == 3:
            return '#'
        else:
            return '.'

    def edges(self):
        xs = [ int(re.search(r'x(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        ys = [ int(re.search(r'y(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        zs = [ int(re.search(r'z(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        ws = [ int(re.search(r'w(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        return min(xs), max(xs), min(ys), max(ys), min(zs), max(zs), min(ws), max(ws)

    def cycle(self):
        new_cube = {}
        xmin, xmax, ymin, ymax, zmin, zmax, wmin, wmax = self.edges()

        for x in range(xmin-1, xmax+2):
            for y in range(ymin-1, ymax+2):
                for z in range(zmin-1, zmax+2):
                    for w in range(wmin-1, wmax+2):
                        new_cube[f'x{x}y{y}z{z}w{w}'] = self.get_new_state(f'x{x}y{y}z{z}w{w}')

        self.cube = new_cube

if __name__ == '__main__':
    c = Cube4D(INPUT)
    for _ in range(6):
        c.cycle()
    print(c.count_all_active())

Advent of Code 2020 day 16

Wednesday 16 December 2020

Advent of Code 2020 day 16. What an arse I made of this, but it was incredibly satisfying to complete! I submitted an answer for part two about 5 times before I managed to work out what the heck the question was asking me to multiply together. Just added to the fun of this one though.

Nested loops anyone?

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
from math import prod
from pathlib import Path
import unittest

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

def parse_rule_ranges(raw_range):
    return [[int(n) for n in r.split('-')] for r in raw_range.split(' or ')]

def parse_raw_input(raw_input):
    sections = raw_input.strip().split('\n\n')
    rules = {
        line.strip().split(': ')[0]: parse_rule_ranges(line.strip().split(': ')[1])
        for line
        in sections[0].splitlines()
    }
    my_ticket = [int(e) for e in sections[1].splitlines()[-1].strip().split(',')]
    nearby_tickets = [[int(e) for e in l.strip().split(',')] for l in sections[-1].splitlines()[1:]]
    return rules, my_ticket, nearby_tickets

def check_value_against_rules(rules, value):
    # Returns True if value passes any of the rules
    return any(
        [
            any(
                [value >= element[0] and value <= element[1] for element in rule]
            )
            for rule in rules.values()
        ]
    )

def part_one(raw_input):
    rules, my_ticket, nearby_tickets = parse_raw_input(raw_input)
    return sum(
        [
            value for ticket in nearby_tickets
            for value in ticket
            if not check_value_against_rules(rules, value)
        ]
    )

def part_two(raw_input):
    rules, my_ticket, nearby_tickets = parse_raw_input(raw_input)
    valid_tickets = [
        ticket for ticket in nearby_tickets
        if all([check_value_against_rules(rules, value) for value in ticket])
    ]

    field_position_candidates = {
        rule_name: list(range(len(my_ticket)))
        for rule_name in rules.keys()
    }

    for ticket in valid_tickets:
        for i, value in enumerate(ticket):
            for rule_name, rule_definition in rules.items():
                if all([value < element[0] or value > element[1] for element in rule_definition]):
                    # Value at position i is not a candidate for whatever rule we're looking at
                    # Remove i from posible positions for the rule
                    try:
                        field_position_candidates[rule_name].remove(i)
                    except ValueError:
                        # i presumably already removed by a previous rule
                        pass

    final_field_positions = {}
    while any([len(candidates) > 1 for candidates in field_position_candidates.values()]):
        for rule_name, candidate_positions in field_position_candidates.items():
            if len(candidate_positions) == 1:
                final_field_positions[rule_name] = candidate_positions[0]
                for remaining_candidate_positions in field_position_candidates.values():
                    if len(remaining_candidate_positions) > 1:
                        try:
                            remaining_candidate_positions.remove(candidate_positions[0])
                        except ValueError:
                            pass

    return prod([
        my_ticket[position]
        for field, position
        in final_field_positions.items()
        if field.startswith('departure')]
    )

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 15

Tuesday 15 December 2020

Advent of Code 2020 day 15. Part one was simple but too slow for part two, so part two uses dictionary lookups. Couldn’t see a way of doing this without storing the last two times each number had been seen.

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
def part_one(input, turns):
    memory = list(input)
    for turn in range(len(input), turns):
        if memory[-1] not in memory[0:-1]:
            memory.append(0)
        else:
            memory.append(
                (len(memory) + 1) - (len(memory) - list(reversed(memory[0:-1])).index(memory[-1]))
            )
    return memory[-1]

def part_two(input, turns):
    memory = {
        n: [t]
        for t, n
        in enumerate(INPUT)
    }

    last_number = input[-1]

    for turn in range(len(input), turns):
        if len(memory[last_number]) == 1:
            # Number not seen before
            this_number = 0
        else:
            this_number = memory[last_number][1] - memory[last_number][0]

        if this_number in memory:
            memory[this_number] = [memory[this_number][-1]] + [turn]
        else:
            memory[this_number] = [turn]

        last_number = this_number

    return last_number

if __name__ == '__main__':
    print(f'Part one: {part_one(INPUT, 2020)}')
    print(f'Part two: {part_two(INPUT, 30000000)}')

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