zerosleeps

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

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

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

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

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