AOC第7天 - 设备上没有空间-DEV365 开发者社区

设备上没有剩余空间

Question
这是一个有趣的一天！我们终于有些具有挑战性。

试图更新该设备时，我们从精灵那里得到了一个设备，我们收到一个错误，通知我们设备上的内存不足

$ system-update --please --pretty-please-with-sugar-on-top
Error: No space left on the device

为了确定发生了什么，我们开始探索设备文件系统并记录输出（我们的拼图输入）
例如

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

表示以下结构

- / (dir)
  - a (dir)
    - e (dir)
      - i (file, size=584)
    - f (file, size=29116)
    - g (file, size=2557)
    - h.lst (file, size=62596)
  - b.txt (file, size=14848514)
  - c.dat (file, size=8504156)
  - d (dir)
    - j (file, size=4060174)
    - d.log (file, size=8033020)
    - d.ext (file, size=5626152)
    - k (file, size=7214296)

当我第一次解决它时，我会在所有命令上进行迭代，并且没有创建任何结构，并且只需跟踪当前的dir，并一旦完成它，就会更新其父级的大小。
我考虑过在这篇文章中尝试一些更有趣的东西，让我们从输入中创建一个文件系统表示形式，然后以后使用它来回答今天的难题

首先，我们需要理解输入的每一行，因为我们将创建一个令牌器！
我们的令牌

// token/token.go
package token

type TokenType string

const (
    Cd   TokenType = "Cd"
    Ls   TokenType = "Ls"
    File TokenType = "File"
    Dir  TokenType = "Dir"
)

type Token struct {
    Type    TokenType
    Literal string
}

我们有4种类型的令牌，每种类型的输出线。
此外，我们还将原始数据保存在literal中，以便以后使用它。

现在让我们写下令牌机，其责任是获取我们的输入并将其转换为有意义的令牌列表

// token/tokenizer.go
package token

import "strings"

func newToken(tokenType TokenType, literal string) Token {
    return Token{
        Type:    tokenType,
        Literal: literal,
    }
}

func Tokenize(raw string) []Token {
    lines := strings.Split(string(raw), "\n")
    tokens := []Token{}
    for _, l := range lines {
        parts := strings.Split(l, " ")
                // process commands
        if parts[0] == "$" {
            if parts[1] == "ls" {
                tokens = append(tokens, newToken(Ls, l))
            } else {
                tokens = append(tokens, newToken(Cd, l))
            }
                // process ls output
        } else {
            if parts[0] == "dir" {
                tokens = append(tokens, newToken(Dir, l))
            } else {
                tokens = append(tokens, newToken(File, l))
            }
        }
    }
    return tokens
}

创建一个结构来表示我们的文件系统

type FileSystem struct {
    root *FileSystemNode
}

type FileSystemNode struct {
    Size   int
    Parent *FileSystemNode
    Token  token.Token
    Name   string
    Dirs   map[string]*FileSystemNode
}

现在到了有趣的部分，越过我们的令牌并根据该构建类似的树结构

func newFileSystemNode(name string, token token.Token, parent *FileSystemNode) *FileSystemNode {
    return &FileSystemNode{Name: name, Parent: parent, Token: token, Dirs: map[string]*FileSystemNode{}}
}

func NewFileSystem(tokens []token.Token) *FileSystem {
    root := newFileSystemNode("/", token.Token{Type: token.Dir, Literal: "/"}, nil)
    fileSystem := &FileSystem{root}
    current := root
    for _, t := range tokens {
        switch t.Type {
        case token.File:
            current.Size += CreateFileNode(t.Literal).Size
        case token.Dir:
            node := CreateDirNode(t.Literal)
            current.Dirs[node.Name] = newFileSystemNode(node.Name, t, current)
        case token.Ls:
            continue
        case token.Cd:
            cdNode := CreateCdNode(t.Literal)
            if cdNode.To == ".." {
                current.Parent.Size += current.Size
                current = current.Parent
            } else {
                _, ok := current.Dirs[cdNode.To]
                if ok {
                    current = current.Dirs[cdNode.To]
                }
            }
        default:
            fmt.Println("Unexpected token!", t)
        }

    }

    // In case we are not ending at the root node
    for current != root {
        current.Parent.Size += current.Size
        current = current.Parent
    }

    return fileSystem
}

我们迭代令牌并根据我们获得的令牌类型执行一些操作。

文件令牌：将文件大小添加到当前DIR
dir令牌：在当前的dir中创建一个新目录，并根据令牌字面（dir name）命名
ls token：我们不在乎它，只是继续我们的循环
CD令牌：
- “ ..”字面：我们将current更改为current.parent，并将当前dir的大小添加到父母
- 否则，我们在使用ls之前已经看到了一些DIR，我们将当前的dir更改为current.Dirs[dirName]

type CdNode struct {
    To string
}

func CreateCdNode(str string) CdNode {
    parts := strings.Split(str, " ")
    return CdNode{
        To: parts[2],
    }
}

在功能末尾，我们回到了根目录，并将每个目录大小添加到其父级，这是因为我们的输出不包含..命令回到顶部。

现在，我们已经拨入了文件系统创建过程，我们可以开始实现第一部分解决方案

第1部分

我们的任务是查找所有目录，大小<= 100,000
为此，我们需要有一种方法来浏览文件系统结构中的每个目录。让我们添加方法来支持该能力

func (tree *FileSystem) Walk(visitor func(t *FileSystemNode)) {
    tree.root.Walk(visitor)
}


func (node *FileSystemNode) Walk(visitor func(t *FileSystemNode)) {
    visitor(node)
    for _, t := range node.Dirs {
        t.Walk(visitor)
    }
}

文件系统和filesystemnode获取Walk方法

我们传递了将在文件系统中的每个节点上调用的函数。
使用上述方法，我们的解决方案现在像
一样简单

func Part1(raw string) int {
    fs := parse(raw)
    sum := 0
    fs.Walk(func(node *fileSystem.FileSystemNode) {
        if node.Size <= 100000 {
            sum += t.Size
        }
    })

    return sum
}

第2部分

在第2部分中，我们的任务是将可用空间的数量增加到至少3,000,000，我们还知道设备上的总内存为7,000,000
我们需要找到可以删除的最小目录，以增加免费内存量> = 3,000,000

在我们的示例中，我们有以下选项：

删除目录E，将未使用的空间增加584。
删除目录A，该目录将增加未使用的空间94853。
删除目录D，它将增加未使用的空间24933642。
DELETE DIRECTORY /，它将将未使用的空间增加48381165。< /li>

目录e和a都太小；删除它们不会释放足够的空间。但是，Directories d和/都足够大！在这些之间，选择最小的：d，将未使用的空间增加到24933642。

解决第2部分的逻辑也很简单，但我们确实需要揭露我们的fileSystem的大小

func (tree *FileSystem) Size() int {
    return tree.root.Size
}

第2部分解决方案

func Part2(raw string) int {
    fs := parse(raw)

    const OS_MEM = 70000000
    const THRESHOLD = 30000000

    unusedSpace := OS_MEM - fs.Size()
    min := OS_MEM
    fs.Walk(func(node *fileSystem.FileSystemNode) {
        if unusedSpace+node.Size > THRESHOLD {
            if min > node.Size {
                min = node.Size
            }
        }
    })

    return min
}

对于每个目录，我们通过删除它是否有足够的免费内存unusedSpace+t.Size > THRESHOLD进行检查，以查看它是否小于当前最小目录。

pheww ...就是第7天！
我知道这种方法对于AOC问题有点太结构了，最初，我在不构建整个结构，令牌等的情况下解决了它...
为了这篇博客文章，我想我会让事情变得更加结构化和有趣

您可以找到完整的代码here
感谢您的阅读！