Advent Of Code 2021 Day 11, 12, 13

advent_of_code_2021.rb

# frozen_string_literal: true

# https://adventofcode.com/2021
module AdvantOfCode2021
  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 11 ======

  def intialize_octopus_matrix
    parse_reading(11).map do |line|
      line.split('').map(&:to_i)
    end
  end

  def increment_octopus_matrix(matrix)
    matrix.map do |row|
      row.map do |number|
        number + 1
      end
    end
  end

  def reset_flashed_octopus_matrix(matrix)
    matrix.map do |row|
      row.map do |number|
        number > 9 ? 0 : number
      end
    end
  end

  def increment_neighbors(matrix, x, y)
    new_flashes = []

    if x > 0
      matrix[x - 1][y] += 1
      new_flashes << [x - 1, y] if matrix[x - 1][y] > 9
    end

    if x < matrix[0].length - 1
      matrix[x + 1][y] += 1
      new_flashes << [x + 1, y] if matrix[x + 1][y] > 9
    end

    if y > 0
      matrix[x][y - 1] += 1
      new_flashes << [x, y - 1] if matrix[x][y - 1] > 9
    end

    if y < matrix.length - 1
      matrix[x][y + 1] += 1
      new_flashes << [x, y + 1] if matrix[x][y + 1] > 9
    end

    if x > 0 && y > 0
      matrix[x - 1][y - 1] += 1
      new_flashes << [x - 1, y - 1] if matrix[x - 1][y - 1] > 9
    end

    if x < matrix[0].length - 1 && y < matrix.length - 1
      matrix[x + 1][y + 1] += 1
      new_flashes << [x + 1, y + 1] if matrix[x + 1][y + 1] > 9
    end

    if x > 0 && y < matrix.length - 1
      matrix[x - 1][y + 1] += 1
      new_flashes << [x - 1, y + 1] if matrix[x - 1][y + 1] > 9
    end

    if x < matrix[0].length - 1 && y > 0
      matrix[x + 1][y - 1] += 1
      new_flashes << [x + 1, y - 1] if matrix[x + 1][y - 1] > 9
    end

    new_flashes
  end

  def count_flashes_in_octopus_matrix(matrix)
    queue = []
    flashed = []

    # Find starting points
    matrix.each_with_index do |row, x|
      row.each_with_index do |number, y|
        if number > 9
          queue << [x, y]
          flashed << [x, y]
        end
      end
    end

    until queue.empty?
      x, y = queue.shift
      # Push into flashed after we dequeue
      new_flashes = increment_neighbors(matrix, x, y)

      queue.concat(new_flashes - flashed)
      flashed.concat(new_flashes - flashed)
    end

    flashes = matrix.flatten.count { |number| number > 9 }

    [matrix, flashes]
  end

  def day_11(steps: 100)
    matrix = intialize_octopus_matrix
    first_synchro = nil
    total_flashes = 0
    step = 1

    until first_synchro || (steps.present? && step > steps)
      # print_matrix(matrix, step)
      matrix = increment_octopus_matrix(matrix)
      matrix, flashes = count_flashes_in_octopus_matrix(matrix)
      matrix = reset_flashed_octopus_matrix(matrix)
      puts "Flashes for step #{ step }: #{ flashes }"
      first_synchro = step if flashes == 100

      total_flashes += flashes
      step += 1
    end

    print_matrix(matrix, 'Final')
    puts "Flashes after #{ steps }: #{ total_flashes }"
    puts "First synchro on step #{ first_synchro }"
  end

  def print_matrix(matrix, step)
    puts "============ #{ step }"
    matrix.each do |row|
      puts row.join(' ')
    end
  end

  #
  # ====== Day 12 ======
  #

  def generate_graph
    graph = {}
    parse_reading(12).each do |line|
      start, finish = line.split('-')
      graph[start] ||= []
      graph[finish] ||= []
      graph[start] << finish
      graph[finish] << start
    end
    graph
  end

  def is_small?(node)
    # 'start' and 'end' are included in 'small'
    node =~ /^[a-z]+$/
  end

  def count_no_revisit_paths_dfs(graph, node, stack, visited)
    return 1 if node == 'end'

    next_nodes = graph[node] - visited

    return 0 if next_nodes.empty?

    next_nodes.sum do |next_node|
      new_visited = is_small?(node) ? visited + [node] : visited
      count_no_revisit_paths_dfs(
        graph,
        next_node,
        stack + [next_node],
        new_visited,
      )
    end
  end

  def is_path_invalid?(node, path)
    # 'end' is checked at start of recursion
    return true if node == 'start' && path.include?('start')

    node_visits = (path + [node]).group_by { |n| n }
    distinct_small_visit_count =
      node_visits.count { |k, v| is_small?(k) && v.size > 1 }
    max_small_visit_count =
      node_visits.count { |k, v| is_small?(k) && v.size > 2 }

    distinct_small_visit_count > 1 || max_small_visit_count > 0
  end

  # Count paths with 1 revisit to small node
  def count_revisit_paths_dfs(graph, node, stack, visited)
    return 1 if node == 'end'

    next_nodes = graph[node]
    return 0 if is_path_invalid?(node, visited)

    next_nodes.sum do |next_node|
      count_revisit_paths_dfs(
        graph,
        next_node,
        stack + [next_node],
        visited + [node],
      )
    end
  end

  def day_12
    graph = generate_graph
    p1_paths = count_no_revisit_paths_dfs(graph, 'start', [], [])
    p2_paths = count_revisit_paths_dfs(graph, 'start', [], [])
    puts "0 Small Revisit Paths count = #{ p1_paths }"
    puts "1 Small Revisit Paths count = #{ p2_paths }"

    graph
  end

  #
  # ====== Day 13 ======
  #

  def generate_matrix(coords)
    max_x = 0
    max_y = 0

    coords.each do |x, y|
      max_x = x if x > max_x
      max_y = y if y > max_y
    end

    matrix = Array.new(max_y + 1) { Array.new(max_x + 1) { 0 } }
    coords.each do |x, y|
      matrix[y][x] = 1
    end

    matrix
  end

  # Values are always half folds, technically idx not needed
  def fold_matrix(matrix, fold)
    fold_axis, fold_idx = fold

    if fold_axis == 'x'
      fold_left(matrix, fold_idx)
    else
      fold_up(matrix, fold_idx)
    end
  end

  def fold_up(matrix, idx)
    new_x = matrix.first.length
    new_y = idx

    new_matrix = Array.new(new_y) { Array.new(new_x) { 0 } }
    new_matrix.each_with_index do |row, y|
      row.each_with_index do |_, x|
        fold_y_idx = y + (idx - y) * 2
        new_matrix[y][x] = [matrix[y][x], matrix[fold_y_idx][x]].max
      end
    end

    new_matrix
  end

  def fold_left(matrix, idx)
    new_x = idx
    new_y = matrix.length

    puts "fold left on #{idx} makes #{ new_x } x #{ new_y }"
    new_matrix = Array.new(new_y) { Array.new(new_x) { 0 } }
    new_matrix.each_with_index do |row, y|
      row.each_with_index do |_, x|
        fold_x_idx = x + (idx - x) * 2
        new_matrix[y][x] = [matrix[y][x], matrix[y][fold_x_idx]].max
      end
    end

    new_matrix
  end

  def count_dots(matrix)
    matrix.flatten.count { |dot| dot == 1 }
  end

  def day_13
    instructions, readings = parse_reading(13).partition do |line|
      line.include?('fold along')
    end
    coords =
      readings.map { |reading| reading.split(',').map(&:to_i) }.reject(&:blank?)
    folds = instructions.map do |instruction|
      axis, idx = instruction.gsub('fold along ', '').split('=')
      [axis, idx.to_i]
    end

    matrix = generate_matrix(coords)
    puts "Count Initial #{ count_dots(matrix) }"
    step_1 = fold_matrix(matrix, folds.first)
    puts "Count after step 1 #{ count_dots(step_1) }"
    code_matrix = folds.reduce(matrix) do |matrix, fold|
      fold_matrix(matrix, fold)
    end
    print_matrix(code_matrix, 'Code.txt')
    code_matrix
  end

  def print_matrix(matrix, to_file)
    File.open(to_file, 'w') do |f|
      matrix.each do |row|
        f.puts row.map { |el| el == 0 ? '.' : '#' }.join(' ')
      end
    end
  end
end