#!/bin/env tclsh

source lib.tcl
setup 9 data

puts {Part 1: Compacted Filesystem Checksum}

## PARSE
set disk {}
set steps 0
for {set i 0} {$i < [string length $input]} {incr i} {
  set chunk [
    if {$i % 2 == 0} {
      expr {$i / 2}
    } else {
      incr steps [string index $input $i]
      expr {"."}
    }]
  append disk [string repeat "$chunk " [string index $input $i]]
}

## COMPACT
set free_idx -1
for {set i 0} {$i < $steps} {incr i} {
  set fid [lindex $disk end-$i]
  if {$fid == "."} continue

  set free_idx [lsearch -start $free_idx+1 -exact $disk .]

  lset disk end-$i .
  lset disk $free_idx $fid
}

set disk [lrange $disk 0 end-$steps]

## CHECKSUM
set checksum 0
for {set i 0} {$i < [llength $disk]} {incr i} {
  incr checksum [expr {[lindex $disk $i] * $i}]
}

puts "Checksum: $checksum"

puts ""
puts {Part 2: Unfragmented Compacted Filesystem Checksum}

## PARSE
set disk {}
set steps 0
for {set i 0} {$i < [string length $input]} {incr i} {
  if {[string index $input $i] == 0} continue
  lappend disk [list [expr {$i % 2 == 0 ? $i / 2 : "."}] [string index $input $i]]
}

## COMPACT
set free_idx -1
set max_fid [llength $disk]
for {set i [expr {[llength $disk] - 1}]} {$i >= 0} {incr i -1} {
  lassign [lindex $disk $i] fid flen
  if {$fid == "."} continue
  if {$fid >= $max_fid} continue
  set max_fid $fid

#  puts "fid: $fid"


  set free_idx [lsearch -start $free_idx -index 0 -exact $disk .]

  # find large enough free space or bail
  set usable_free_idx $free_idx
#  puts "first free_idx: [lindex $disk $usable_free_idx 1] // $flen"
  while {[lindex $disk $usable_free_idx 1] < $flen} {
#    puts "in this loop"
    set usable_free_idx [lsearch -start $usable_free_idx+1 -index 0 -exact $disk .]
    if {$usable_free_idx == -1} break
  }
#  puts "free_idx: $usable_free_idx // $i"
  if {$usable_free_idx == -1 || $usable_free_idx > $i} continue

  set free_len [lindex $disk $usable_free_idx 1]
#  puts "free_len: $free_len // $flen"
  if {$free_len == $flen} {
    lset disk $usable_free_idx [list $fid $flen]
  } else {
    set disk [lreplace $disk $usable_free_idx $usable_free_idx \
                      [list $fid $flen] \
                      [list . [expr {$free_len - $flen}]]]
    incr i
  }

  # this can create sequences like {20 1} {. 4} {. 5} {. 3} {22 6} but it won't matter
  lset disk $i [list . $flen]
}

## CHECKSUM
set checksum 0
set idx 0
foreach chunk $disk {
  lassign $chunk fid flen
  if {$fid == "."} {
    incr idx $flen
    continue
  }

  set extent [expr {$idx + $flen}]
  for {} {$idx < $extent} {incr idx} {
    incr checksum [expr {$idx * $fid}]
  }
}

puts "Checksum: $checksum"