aoc2022_7.go

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
}