【AoC】2022 Day7：パターンマッチングで解く

問題

PCの容量がパンパンなので、サイズが10000を超えるディレクトリを探してね！という問題です。

入力はこちらです。
cd, lsはLinuxなどで使うものと同じで、
dir hogeはhogeディレクトリがあることを指し、
1234 piyo.txtは容量が1234のファイルがあることを指します。

$ 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

https://adventofcode.com/2022/day/7

解答の方針

各ディレクトリがどれだけ容量を使っているのかそれぞれ求めれば良いです。

コマンドに応じて処理を行うため、Pythonのパターンマッチングを使って実装します。

解答

解答の全体はこちら

dict = defaultdict(int)
path = []  # 現在位置のパスを記録する

dictはkeyがパス、valueが容量です。
pathは["/", "a/", "b/", "c/"]のようにパスを記録していきます。

for line in lines:
    command = line.strip().split(" ")
    match command:
        case "$", "cd", "/": path = ["/"]
        case "$", "ls": continue
        case "dir", _: continue
        case "$", "cd", "..": path.pop()
        case "$", "cd", x: path.append(x + "/")
        case size, _: 
            # 親、親の親...のディレクトリまでサイズを足す
            for dir in itertools.accumulate(path):
                dict[dir] += int(size)

cdでディレクトリを移動したときにのみpathを変更します。

ファイルが見つかった場合、dictの対応する箇所に容量を足していきます。
例えばpath = ["/", "a/", "b/", "c/"]に容量300のファイルがある場合、
dictのキーが "/a/b/c/", "/a/b/", "/a/", "/"の要素にそれぞれ300を足しています。

itertoolsのaccumulate()で文字列の累積和を作ることで容量を足すべきパスを生成しています。

参考リンク

https://www.reddit.com/r/adventofcode/comments/zesk40/2022_day_7_solutions/
https://topaz.github.io/paste/#XQAAAQApAgAAAAAAAAAzHIoib6pXbueH4X9F244lVRDcOZab5q1+VXY/ex42qR7D+RJIsrl/Sxb6tPAL+4hwfHLYDcxAkOQUPDzJHt5E6HtsTuD7sQmi8zUjU23yXHSz2Ybz1Wg76Dml+yk2nSfpuHeVfYbBzOSzCq56Pqa2xKaoiZFw198LfErdujq9KpE+VyQQcqTb+3lhE6lB+md3/24UDyF9kQ7hNPzS3MMiOqXfViov9xImHF/cBQtDixb1urf0ihR2KbZi4sIlWsKr0bb1xtUxAP3NlxXAiq/OMZ0yHqyOrimJgFLHSn1lR9Gs1jLjZCGuSE5JTAqg6l18+0PmcudpJXsn21dPkc7Zqcm9JT6oQ9kl5C/HsOnhg0zfNdUV06YFakTcAq3/yygRiA==