blob: 38a156c49b14772eeb835fc6ff1018c7eed7a2cb (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
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"
|
