Created
December 7, 2022 06:09
-
-
Save shoenig/e9c1a2697109c08ca7af79e9ca66375f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"bufio" | |
"fmt" | |
"os" | |
"sort" | |
"strconv" | |
"strings" | |
) | |
type node struct { | |
name string | |
size int | |
parent *node | |
entries map[string]*node | |
} | |
func (n *node) add(child *node) { | |
if n.entries == nil { | |
n.entries = make(map[string]*node) | |
} | |
child.parent = n | |
n.entries[child.name] = child | |
n.update(child.size) | |
} | |
func (n *node) update(size int) { | |
n.size += size | |
if n.name != "/" { | |
n.parent.update(size) | |
} | |
} | |
func main() { | |
r, err := os.Open(os.Args[1]) | |
check(err) | |
script := make([]string, 0, 1024) | |
scanner := bufio.NewScanner(r) | |
for scanner.Scan() { | |
line := scanner.Text() | |
line = strings.TrimSpace(line) | |
if line == "" { | |
continue | |
} | |
script = append(script, line) | |
} | |
root := &node{ | |
name: "/", | |
entries: make(map[string]*node), | |
} | |
root.parent = root | |
run(root, script) | |
candidates := make([]int, 0, 100) | |
inspect(root, "", root.size, &candidates) | |
fmt.Println("total used", root.size) | |
fmt.Println("candidates", candidates) | |
sort.Ints(candidates) | |
fmt.Println("smallest", candidates[0]) | |
} | |
const ( | |
modeInst = iota | |
modeData | |
) | |
const capacity = 70000000 | |
const needs = 30000000 | |
func inspect(fs *node, ident string, used int, small *[]int) { | |
if len(fs.entries) != 0 { | |
// fmt.Println("dir", fs.name, "size", fs.size) | |
if capacity-(used-fs.size) > needs { | |
fmt.Println("candidate", fs.name, fs.size) | |
*small = append(*small, fs.size) | |
} | |
for _, entry := range fs.entries { | |
inspect(entry, ident+" ", used, small) | |
} | |
} | |
} | |
func run(fs *node, script []string) { | |
mode := modeInst | |
for i := 1; i < len(script); i++ { | |
line := script[i] | |
// fmt.Println("line", line, "mode", mode) | |
switch { | |
case line == "$ ls": | |
mode = modeData | |
case strings.HasPrefix(line, "$ cd"): | |
mode = modeInst | |
tokens := strings.Fields(line) | |
target := tokens[2] | |
if target == ".." { | |
fs = fs.parent | |
fmt.Println("cd into ..", fs.parent.name) | |
} else { | |
fs = fs.entries[target] | |
fmt.Println("cd into", target) | |
} | |
case mode == modeData: | |
tokens := strings.Fields(line) | |
name := tokens[1] | |
if tokens[0] == "dir" { | |
dir := &node{name: name} | |
fs.add(dir) | |
} else { | |
size := ToInt(tokens[0]) | |
f := &node{name: name, size: size} | |
fs.add(f) | |
} | |
} | |
} | |
} | |
func check(err error) { | |
if err != nil { | |
fmt.Println("err", err) | |
os.Exit(1) | |
} | |
} | |
func ToInt(s string) int { | |
i, err := strconv.Atoi(s) | |
check(err) | |
return i | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment