Advent of Code 2024 day009.rb

day009.rb

require_relative "main"

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

  s = INPUT.strip

  expand = ->(s) { s.chars.each_with_object([]).with_index { |(c, a), i| c.to_i.times { a.push(i.even? ? i / 2 : nil) } } }

  checksum = ->(a) { a.each_with_index.sum { _2 * _1.to_i } }

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

  condense1 = ->(a) do
    i = 0
    j = a.length - 1
    while i < j - 2
      i += 1 until a[i].nil?
      j -= 1 while a[j].nil?
      a[i], a[j] = a[j], a[i]
    end
    a
  end

  answer1 = checksum.call(condense1.call(expand.call(s)))

  pp answer1

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

  condense2 = ->(a) do
    voids = Hash.new { |h, k| h[k] = [] }
    i = 0
    while i < a.length
      i += 1 while !a[i].nil? && i < a.length
      ii = i
      ii += 1 while a[ii].nil? && ii < a.length

      voids[ii - i].push(i) if ii > i

      i = ii
    end

    j = a.length - 1
    while j >= 0
      j -= 1 while a[j].nil? && j >= 0
      jj = j
      jj -= 1 while a[jj] == a[j] && jj >= 0

      dj = j - jj

      if dj > 0 && (d = voids.keys.filter { |k| k >= dj && voids[k].any? { _1 < jj } }.min { voids[_1][0] <=> voids[_2][0] })
        i = voids[d].shift
        while j > jj
          a[i], a[j] = a[j], a[i]
          i += 1
          j -= 1
        end
        voids[d - dj].unshift(i).sort! if d > dj
      end

      j = jj
    end

    a
  end

  answer2 = checksum.call(condense2.call(expand.call(s)))

  pp answer2
end