1 files changed, 111 insertions, 0 deletions
diff --git a/2024/tcl/09.tcl b/2024/tcl/09.tcl
new file mode 100755
index 0000000..38a156c
--- /dev/null
+++ b/2024/tcl/09.tcl
@@ -0,0 +1,111 @@
+#!/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"