Advent of Code 2024 day016.rb

day016.rb

require_relative "main"

module Day016
  INPUT = File.read("INPUT.txt")

  grid = INPUT.to_grid

  CHAR_START = "S"
  CHAR_END = "E"
  EAST = V[1, 0]
  EMPTY = "."
  WALL = "#"

  V_START = grid.find(CHAR_START)
  V_END = grid.find(CHAR_END)

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

  visited = Hash.new { |h, k| h[k] = false }
  scores = Hash.new { |h, k| h[k] = Float::INFINITY }

  q = [[V_START, EAST]]
  scores[V_START] = 0
  while q.count > 0
    v, d = q.shift

    resort = false
    grid.four(v).filter { |n| !visited[n] && [EMPTY, CHAR_END].include?(grid.get_value(n)) }.each do |n|
      inc = (n - v == d) ? 1 : 1001
      if scores[v] + inc <= scores[n]
        scores[n] = scores[v] + inc
        resort = true
        q.push([n, n - v])
      end
    end

    q.sort! { |a, b| scores[a.first] <=> scores[b.first] } if resort
    visited[v] = true
  end

  answer1 = scores[V_END]

  pp answer1

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

  paths = []
  dfs = ->(v, d, visited, score) do
    return if score + scores[v] > answer1

    paths.push(visited) if v == V_START

    grid.four(v).filter { |n| !visited.include?(n) && [EMPTY, CHAR_START].include?(grid.get_value(n)) }.each do |n|
      inc = (d.nil? || n - v == d) ? 1 : 1001
      dfs.call(n, n - v, visited + [v], score + inc)
    end
  end

  dfs.call(V_END, nil, [V_END], 0)

  answer2 = paths.flatten.uniq.count + 1

  pp answer2
end