disk_map = DATA.read.chars.each_slice(2)
  .flat_map.with_index {|(a,b),i|
    [ Array.new(a.to_i, i), Array.new(b.to_i, nil) ]
  }.reject(&:empty?)

# while (prev, free = disk_map.each_cons(2).find { _2.include?(nil) })
#   tail = disk_map.last
#   until free.empty? || tail.empty?
#     prev << tail.shift
#     free.pop
#   end
#
#   while disk_map.last.all?(&:nil?)
#     disk_map.pop
#   end
# end

# pp disk_map.flatten.compact.each.with_index.sum { _1 * _2 }

Block = Struct.new(:id, :size, :prev, :next) do
  def each(dir: :next, stop: nil)
    return enum_for(__method__, dir:, stop:) unless block_given?

    cur = self
    while cur != stop
      yield cur
      cur = cur.send(dir)
    end
  end

  def inspect
    "<Block id=#{id} size=#{size} prev=#{prev&.id} next=#{self.next&.id}>"
  end

  def to_s
    (id || ?.).to_s * size
  end
end

blocks = disk_map.map { Block.new(_1[0], _1.size) }
  .each_cons(2) { _1.next = _2; _2.prev = _1 }

head = blocks.first

blocks.last.each(dir: :prev).reject { _1.id.nil? }.each do |file|
  free = head.each(stop: file)
    .select { _1.id.nil? }
    .find { _1.size >= file.size }
  next if free.nil?

  free.id, file.id = file.id, free.id

  if free.size > file.size
    c = Block.new(nil, free.size - file.size, free, free.next)
    free.size = file.size
    free.next = c
    c.next.prev = c
  end
end

pp head.each.flat_map { Array.new(_1.size, _1.id) }.each.with_index.sum { _1.to_i * _2 }

__END__