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