Advent of Code 2024 day018.rb

day018.rb

require_relative "main"

module Day018
  INPUT = File.read("INPUT.txt")
  SIDE = 71
  LIMIT = 1024

  CORRUPT = "#"
  SAFE = "."

  grid = Grid.new(SIDE, SIDE, SAFE)
  points = INPUT.split("\n").map { |line| V[*line.scan(/\d+/).map(&:to_i)] }

  ORIGIN = V[0, 0]
  DESTINATION = V[SIDE - 1, SIDE - 1]

  ##########
  # Part 1 #
  ##########

  points[0...LIMIT].each { |v| grid.set_value(v, CORRUPT) }

  visited = {}
  parents = {}
  q = [ORIGIN]
  while q.count > 0
    c = q.shift
    if c == DESTINATION
      answer1 = 0

      loop do
        c = parents[c]
        break if c.nil?
        answer1 += 1
      end

      pp answer1
      break
    end
    visited[c] = true
    grid.four(c).filter { |n| !visited[n] && grid.get_value(n) != CORRUPT }.each do |n|
      parents[n] = c
      q.push(n) unless q.include?(n)
    end
  end

  ##########
  # Part 2 #
  ##########

  points[LIMIT..].each do |v|
    grid.set_value(v, CORRUPT)

    ns = grid.eight(v)
    if ns.count == 8
      corrupt_ns = ns.filter { |n| grid.get_value(n) == CORRUPT }
      potentially_blocked = if corrupt_ns.count == 2
        (corrupt_ns[0] - corrupt_ns[1]).major_abs > 1
      else
        corrupt_ns.count > 2
      end
    else
      potentially_blocked = grid.get_values(ns).any?(CORRUPT)
    end

    if potentially_blocked
      visited = {}
      q = [ORIGIN]
      reached = false
      while q.count > 0
        c = q.shift
        break if (reached = c == DESTINATION)
        visited[c] = true
        grid.four(c).filter { |n| !visited[n] && grid.get_value(n) != CORRUPT }.each do |n|
          q.push(n) unless q.include?(n)
        end
      end

      unless reached
        answer2 = v.to_a.join(",")

        pp answer2
        break
      end
    end
  end
end