Advent Of Code Day 1-10, no edits

advent_of_code_2021.rb

# https://adventofcode.com/2021
module AdventOfCode2021
  URL = 'https://adventofcode.com/2021/day/%d/input'
  COOKIE = 'NOPE'

  def parse_reading(day)
    day_url = URL % day
    HTTParty.get(day_url, headers: { 'Cookie' => COOKIE }).body.split("\n")
  end

  #
  # ====== DAY 1 ======
  #
  def increases(arr)
    total = 0
    arr ||= parse_reading(1).map(&:to_i)

    arr.each_with_index do |i, idx|
      total += 1 if idx > 0 && arr[idx - 1] < i
    end

    total
  end

  def increases_2
    total = 0
    arr = parse_reading(1).map(&:to_i)

    arr2 = parse_reading.map.with_index do |i, idx|
      i + arr[idx + 1] + arr[idx + 2] if idx < arr.size - 2
    end

    increases(arr2.compact)
  end

  #
  # ====== DAY 2 ======
  #
  def position
    arr = parse_reading(2)
    horizontal = 0
    depth = 0

    arr.each do |element|
      direction, distance = element.split(' ')
      if direction == 'forward'
        horizontal += distance.to_i
      elsif direction == 'down'
        depth += distance.to_i
      elsif direction == 'up'
        depth -= distance.to_i
      end
    end

    horizontal * depth
  end

  def position_2
    arr = parse_reading(2)
    horizontal = 0
    aim = 0
    depth = 0

    arr.each do |element|
      direction, distance_str = element.split(' ')
      distance = distance_str.to_i
      if direction == 'forward'
        horizontal += distance
        depth += aim * distance
      elsif direction == 'down'
        aim += distance
      elsif direction == 'up'
        aim -= distance
      end
    end

    horizontal * depth
  end

  #
  # ====== DAY 3 ======
  #
  def gamma(bitcount)
    binary_gamma = bitcount.values.map { |v| v['0'] > v['1'] ? '0' : '1' }.join
    binary_gamma.to_i(2)
  end

  def episilon(bitcount)
    binary_episilon = bitcount.values.map { |v| v['0'] < v['1'] ? '0' : '1' }.join
    binary_episilon.to_i(2)
  end

  def power
    arr = parse_reading(3)
    len = arr.first.length
    bitcount = len.times.map { |i| [i, { '0' => 0, '1' => 0 }] }.to_h
    arr.each do |element|
      element.split('').each_with_index do |bit, idx|
        bitcount[idx][bit] += 1
      end
    end

    gamma(bitcount) * episilon(bitcount)
  end

  def bitcount(arr, idx)
    bitcount = { '0' => 0, '1' => 0 }
    arr.each { |element| bitcount[element[idx]] += 1 }
    bitcount
  end

  def oxygen(arr)
    idx = 0
    while arr.length > 1
      bitcount = bitcount(arr, idx)
      filter_bit = bitcount['0'] > bitcount['1'] ? '0' : '1'
      arr.select! { |e| e[idx] == filter_bit }
      idx += 1
    end

    arr.first.to_i(2)
  end

  def co2(arr)
    idx = 0
    while arr.length > 1
      bitcount = bitcount(arr, idx)
      filter_bit = bitcount['0'] <= bitcount['1'] ? '0' : '1'
      arr.select! { |e| e[idx] == filter_bit }
      idx += 1
    end

    arr.first.to_i(2)
  end

  def life_support
    arr = parse_reading(3)
    oxygen(arr.dup) * co2(arr.dup)
  end

  #
  # ====== DAY 4 ======
  #

  def mark_board(board, number)
    board.each_with_index do |row, y|
      row.each_with_index do |cell, x|
        board[y][x][:marked] = true if cell[:value] == number
      end
    end
  end

  def check_board(board)
    winning_row = board.find { |row| check_row(row) }
    return true if winning_row.present?

    0..4.times do |idx|
      row = board.map { |row| row[idx] }
      return true if check_row(row)
    end

    false
  end

  def check_row(row)
    row.select { |cell| cell[:marked] }.length == 5
  end

  def get_board_score(board, number)
    board.flatten.reject { |c| c[:marked] }.inject(0) do |sum, cell|
      sum + cell[:value].to_i
    end * number.to_i
  end

  def get_boards(input)
    boards = []
    input.reject(&:blank?).each_slice(5).map do |rows|
      board = []
      rows.map do |row|
        board << row.strip.split(/\s+/).map do |cell|
          { value: cell, marked: false }
        end
      end

      boards << board
    end

    boards
  end

  def play_bingo
    input = parse_reading(4)
    picked_numbers = input.shift.split(',')
    boards = get_boards(input)

    picked_numbers.each do |number|
      puts "number #{ number }"
      boards.each do |board|
        mark_board(board, number)
        if check_board(board)
          puts 'Found winning row!'
          return get_board_score(board, number)
        end
      end
    end
  end

  def play_bingo_last
    input = parse_reading(4)
    picked_numbers = input.shift.split(',')
    boards = get_boards(input)

    picked_numbers.each do |number|
      puts "number #{ number }"
      boards.each { |board| mark_board(board, number) }
      finished = boards.select { |board| check_board(board) }
      boards -= finished

      if boards.empty?
        puts 'Found last board!'
        return get_board_score(finished.first, number)
      end
    end
  end

  #
  # ====== DAY 5 ======
  #

  def find_min_grid(readings)
    max_x = 20
    max_y = 10
    readings.each do |start, finish|
      max_x = [max_x, start[0], finish[0]].max
      max_y = [max_y, start[1], finish[1]].max
    end

    puts "Creating min grid of #{ max_x + 1 } x #{ max_y + 1 }"
    Array.new(max_y + 1) { Array.new(max_x + 1) { 0 } }
  end

  def find_intersections
    readings = parse_reading(5).map do |line|
      coord1, coord2 = line.split(' -> ')
      [coord1.split(',').map(&:to_i), coord2.split(',').map(&:to_i)]
    end

    grid = find_min_grid(readings)

    readings.each do |start, finish|
      # Assume only horizontal or vertical lines
      if start[0] == finish[0]
        puts "vertical #{ start[0] } from #{ start[1] } to #{ finish[1] }"
        min = [start[1], finish[1]].min
        max = [start[1], finish[1]].max
        min.upto(max) { |y| grid[y][start[0]] += 1 }
      elsif start[1] == finish[1]
        puts "horizontal #{ start[1] } from #{ start[0] } to #{ finish[0] }"
        min = [start[0], finish[0]].min
        max = [start[0], finish[0]].max
        min.upto(max) { |x| grid[start[1]][x] += 1 }
      else
        puts "diagonal #{ start } to #{ finish }"
        # Only perfect diagonals
        length = (start[0] - finish[0]).abs + 1
        x_step = start[0] > finish[0] ? -1 : 1
        y_step = start[1] > finish[1] ? -1 : 1
        length.times do |i|
          puts "step #{ start[0] + i * x_step }, #{ start[1] + i * y_step }"
          grid[start[1] + i * y_step][start[0] + i * x_step] += 1
        end
      end
    end

    print_grid(grid, to_file: 'grid.txt')
    grid.map { |row| row.select { |cell| cell > 1 }.length }.sum
  end

  def print_grid(grid, to_file: nil)
    if to_file
      File.open(to_file, 'w') do |f|
        f << grid.map do |row|
          row.map { |i| i == 0 ? '.' : i }.join('')
        end.join("\n")
      end
    else
      grid.each { |row| puts row.join('') }
    end
  end

  #
  # ====== DAY 6 ======
  #

  def count_day(fishes)
    new_fishes = fishes[0]
    fishes[0] = fishes[1]
    fishes[1] = fishes[2]
    fishes[2] = fishes[3]
    fishes[3] = fishes[4]
    fishes[4] = fishes[5]
    fishes[5] = fishes[6]
    fishes[6] = fishes[7] + new_fishes
    fishes[7] = fishes[8]
    fishes[8] = new_fishes

    fishes
  end

  def count_lantern_fish(days)
    fishes = 0.upto(8).map { |day| [day, 0] }.to_h
    parse_reading(6)[0].split(',').each do |fish|
      fishes[fish.to_i] += 1
    end

    print_fishes(fishes)
    1.upto(days) do |day|
      fishes = count_day(fishes)
      puts "Day #{ day }"
      print_fishes(fishes)
    end

    puts "Final fish count after #{ days }: #{ fishes.values.sum }"
  end

  def print_fishes(fishes)
    puts(
      fishes.map do |day, fish_count|
        "#{ day }:#{ format('% 2d', fish_count) }"
      end.join(' '),
    )
  end

  #
  # ====== DAY 7 ======
  #

  def generate_position_matrix(crabs)
    matrix = {}
    crabs.each do |crab|
      matrix[crab] ||= 0
      matrix[crab] += 1
    end

    matrix
  end

  def generate_distance_matrix(position_matrix)
    matrix = {}

    Array(0..position_matrix.keys.max).each do |location|
      matrix[location] = {}
      position_matrix.keys.each do |other_crab|
        other_count = position_matrix[other_crab]
        # For them to move here
        matrix[location][other_crab] = other_count * (location - other_crab).abs
      end
    end

    matrix
  end

  def generate_distance_matrix_p2(position_matrix)
    matrix = {}

    Array(0..position_matrix.keys.max).each do |location|
      matrix[location] = {}
      position_matrix.keys.each do |other_crab|
        other_count = position_matrix[other_crab]
        # For them to move here
        distance = (location - other_crab).abs
        matrix[location][other_crab] = other_count * Array(1..distance).sum
      end
    end

    matrix
  end

  def find_min_position
    crabs = parse_reading(7)[0].split(',').map(&:to_i)
    # crabs = '16,1,2,0,4,2,7,1,2,14'.split(',').map(&:to_i)
    position_matrix = generate_position_matrix(crabs)
    distance_matrix = generate_distance_matrix_p2(position_matrix)

    soln = distance_matrix.map { |crab, matrix| [crab, matrix.values.sum] }.to_h
    min_value = soln.values.min
    min_crab = soln.index(min_value)

    puts "#{ min_crab } #{ min_value }"
    puts "others: #{ soln.keys.select { |k| soln[k] == min_value }.join(',') }"
  end

  #
  # ====== DAY 8 ======
  #

  # Note:
  #  aaaa   0000
  # b    c 1    2
  # b    c 1    2
  #  dddd   3333
  # e    f 4    5
  # e    f 4    5
  #  gggg   6666
  # test with 'abcdefg'
  def num_from_key(key, output)
    if match_key(key, output, 2, 5) # cf
      1
    elsif match_key(key, output, 0, 2, 3, 4, 6) # acdeg
      2
    elsif match_key(key, output, 0, 2, 3, 5, 6) # acdfg
      3
    elsif match_key(key, output, 1, 2, 3, 5) # bcdf
      4
    elsif match_key(key, output, 0, 1, 3, 5, 6) # abdfg
      5
    elsif match_key(key, output, 0, 1, 3, 4, 5, 6) # abdefg
      6
    elsif match_key(key, output, 0, 2, 5) # acf
      7
    elsif match_key(key, output, 0, 1, 2, 3, 4, 5, 6) # abcdefg
      8
    elsif match_key(key, output, 0, 1, 2, 3, 5, 6) # abcdfg
      9
    elsif match_key(key, output, 0, 1, 2, 4, 5, 6) # abcefg
      0
    else
      puts "Key #{ key } is invalid for #{ output }"
    end
  end

  def match_key(key, output, *indices)
    output.chars.sort == indices.map { |idx| key[idx] }.sort
  end

  def find_key_from_inputs(inputs)
    key = {
      0 => '',
      1 => '',
      2 => '',
      3 => '',
      4 => '',
      5 => '',
      6 => '',
    }

    # Find 1
    one = inputs.find { |input| input.length == 2 }.chars
    # Find 4
    four = inputs.find { |input| input.length == 4 }.chars
    # Find 7
    seven = inputs.find { |input| input.length == 3 }.chars
    # Find 8
    eight = inputs.find { |input| input.length == 7 }.chars

    # Find 6, 9, 0
    six_nine_zero = inputs.select { |input| input.length == 6 }.map(&:chars)

    # Find 2, 3, 5
    two_three_five = inputs.select { |input| input.length == 5 }.map(&:chars)

    eight_sub_charsix = six_nine_zero.flat_map { |option| eight - option }

    # Solve seven - one => 'a'
    key[0] = seven - one

    # Solve missing_c6 - four => 'e'
    key[4] = eight_sub_charsix - four

    # Solve missing_c6 - key[4] - seven = 'd'
    key[3] = eight_sub_charsix - key[4] - seven

    # Solve missing_c6 - key[4] - key[3] = 'c'
    key[2] = eight_sub_charsix - key[4] - key[3]

    four_sub_charfive = two_three_five.map { |option| four - option }

    key[1] =
      four_sub_charfive
      .map { |option| option - key[2] }
      .reject(&:empty?)
      .find { |option| option.length == 1 }

    four_sub_two = four_sub_charfive.find { |option| option.length == 2 }

    key[5] = four_sub_two - key[1]

    key[6] = 'abcdefg'.chars - key.values.flatten

    key.values.flatten
  end

  def solve_seven_seg
    puzzles = parse_reading(8).map do |line|
      inputs, outputs = line.split(' | ')
      [inputs.split(' '), outputs.split(' ')]
    end

    solns = puzzles.map do |inputs, outputs|
      key = find_key_from_inputs(inputs)
      outputs.map { |output| num_from_key(key, output) }
    end
    part_one = solns.flatten.select { |i| [1, 4, 7, 8].include?(i) }.length
    puts "1,4,7,8 count = #{ part_one }"
    total = solns.map { |s| s.join('') }.map(&:to_i).sum
    puts "Total = #{ total }"
  end

  #
  # ====== DAY 9 ======
  #
  def find_neighbors(map, x, y)
    neighbors = []
    neighbors << [x - 1, y] if x > 0
    neighbors << [x + 1, y] if x < map.length - 1
    neighbors << [x, y - 1] if y > 0
    neighbors << [x, y + 1] if y < map[0].length - 1
    neighbors
  end

  def find_basin_size(map, x, y)
    queue = [[x, y]]
    visited = []

    until queue.empty?
      cur = queue.shift

      neighbors = find_neighbors(map, *cur)
      neighbors_sans_nine = neighbors.reject { |x, y| map[y][x] == 9 }
      unvisited_neighbours = neighbors_sans_nine - visited - queue
      visited << cur
      queue.concat(unvisited_neighbours)
    end

    visited.size
  end

  def parse_map
    map = parse_reading(9).map do |line|
      line.split('').map(&:to_i)
    end
  end

  def is_location_local_low(map, x, y)
    local = map[y][x]
    above = y > 0 ? map[y - 1][x] : 9
    below = y + 1 < map.size ? map[y + 1][x] : 9
    left = x > 0 ? map[y][x - 1] : 9
    right = x + 1 < map[y].size ? map[y][x + 1] : 9

    local < above && local < below && local < left && local < right
  end

  def find_local_lows
    lows = []
    map = parse_map
    map.each_with_index do |row, y|
      row.each_with_index do |_cell, x|
        lows << [x, y] if is_location_local_low(map, x, y)
      end
    end

    p1_score = lows.sum { |x, y| map[y][x] + 1 }
    basin_sizes = lows.map { |x, y| find_basin_size(map, x, y) }.sort.reverse
    p2_score = basin_sizes[0] * basin_sizes[1] * basin_sizes[2]
    [p1_score, p2_score]
  end

  def print_basin_map(map, to_file)
    nine_map = map.map { |row| row.map { |cell| [cell - 8, 0].max } }
    File.open(to_file, 'w') do |f|
      f << nine_map.map { |row| row.join('') }.join("\n")
    end
  end

  #
  # ====== DAY 10 ======
  #
  PAIRS = {
    ')' => '(',
    ']' => '[',
    '}' => '{',
    '>' => '<',
  }

  SCORE = {
    ')' => 3,
    ']' => 57,
    '}' => 1197,
    '>' => 25137,
  }

  SCORE_2 = {
    ')' => 1,
    ']' => 2,
    '}' => 3,
    '>' => 4,
  }

  def calculate_completion_score(corrections)
    corrections.map do |correction|
      correction.inject(0) do |score, char|
        (score * 5) + SCORE_2[PAIRS.index(char)]
      end
    end
  end

  def auto_complete_line(line)
    stack = []

    line.chars.each_with_index do |char, idx|
      if [')', ']', '}', '>'].include?(char)
        open_char = PAIRS[char]
        if stack.empty? || stack.last != open_char
          raise "AUTO COMPLETE FOUND ILLEGAL LINE"
        else
          stack.pop
        end
      else
        stack.push(char)
      end
    end

    stack.reverse
  end

  def find_illegal_char(line)
    stack = []

    line.chars.each_with_index do |char, idx|
      if [')', ']', '}', '>'].include?(char)
        open_char = PAIRS[char]
        if stack.empty? || stack.last != open_char
          puts "ILLEGAL #{ line } found #{ char } at #{ idx }"
          return char
        else
          stack.pop
        end
      else
        stack.push(char)
      end
    end

    nil
  end

  def parse_lines
    lines = parse_reading(10)
    score = 0
    corrections = []

    lines.each do |line|
      illegal_char = find_illegal_char(line)
      if illegal_char.present?
        score += SCORE[illegal_char]
      else
        corrections << auto_complete_line(line)
      end
    end
    completion_scores = calculate_completion_score(corrections)

    puts "Score = #{ score }"
    puts "Completion = #{ completion_scores.sort[completion_scores.size/2] }"
  end
end