You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
65 lines
1.4 KiB
65 lines
1.4 KiB
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__
|
|
2333133121414131402
|