Мои взаимоотношения с этой загадкой можно описать примерно такой фразой (по мотивам анекдотов):

– Дерево – подумал Штирлиц
– Дерево – поняло дерево

Всё началось с того, что мне совершенно не хотелось строить это дерево (забегая вперёд – всё же пришлось).

После пары неудачных попыток (о которых ниже) – решил хранить эту псевдо-ФС в избыточном виде – получились этакие “мангровые заросли”.

Директории, помимо вложенности в свои родительские каталоги, дублируются на корневом уровне. Таким образом получается без лишних усилий посчитать результат по условиям загадки.

record File(String name, long size, List<File> files) {}
static Map<String, File> flattenFs = new HashMap<>();

static void day7(String puzzleInputUri) throws IOException, InterruptedException {
    List<String[]> commands = client.send(
            request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()
        ).body()
        .skip(1)
        .filter(line -> !line.equals("$ ls"))
        .map(line -> line.replace("$ ", ""))
        .map(line -> line.split(" "))
        .toList();

    String currentDirKey = "/";
    flattenFs.put(currentDirKey, new File("/", 0L, new ArrayList<>()));
    for (var commandLine : commands) {
        String command = commandLine[0];
        String arg = commandLine[1];
        if ("dir".equals(command)) {
            String newDirKey = currentDirKey + "/" + arg;
            flattenFs.putIfAbsent(newDirKey, new File(newDirKey, 0L, new ArrayList<>()));
            flattenFs.get(currentDirKey).files().add(flattenFs.get(newDirKey));
        } else if ("cd".equals(command)) {
            if ("..".equals(arg)) {
                String parentDir = currentDirKey.substring(0, currentDirKey.lastIndexOf("/"));
                currentDirKey = flattenFs.keySet().stream()
                    .filter(dir -> dir.equals(parentDir))
                    .findAny().orElseThrow();
            } else {
                currentDirKey += "/" + arg;
            }
        } else {
            flattenFs.get(currentDirKey).files().add(new File(arg, Long.parseLong(command), new ArrayList<>()));
        }
    }

    long resultPartOne = flattenFs.values().stream()
        .mapToLong(dir -> getTotalSize(dir, 0L))
        .filter(size -> size <= 100_000L)
        .sum();
    System.out.println(resultPartOne);

    long usedSpace = getTotalSize(flattenFs.get("/"), 0L);
    long freeSpace = 70_000_000L - usedSpace;
    long needForUpdateSpace = 30_000_000L - freeSpace;
    long resultPartTwo = flattenFs.values().stream()
        .mapToLong(dir -> getTotalSize(dir, 0L))
        .filter(size -> size >= needForUpdateSpace)
        .min()
        .orElseThrow();
    System.out.println(resultPartTwo);
}

static long getTotalSize(File dir, long totalSize) {
    List<File> files = dir.files();
    for (File file : files) {
        totalSize += file.size() > 0L
            ? file.size()
            : getTotalSize(flattenFs.get(file.name()), 0L);
    }
    return totalSize;
}

Этот пример запускал на Java 17, на традиционно используемой в прошлых задачах одиннадцатой версии Java он не заработает.

Исходные данные: https://adventofcode.com/2022/day/7/input

Неудачные попытки седьмого дня

Мы сделали ФС в твоей ФС

Первое решение – хорошо, у нас же тут “как бы файловая система” – так почему бы не сэмулировать её на файловой системе? Возможно, это сработало бы, если как следует поколдовать с find. А может – и нет.

Так или иначе, ФС создавалась (всегда успешно – на тестовом пример и не всегда – на реальном)

curl -s --request GET \
  --url https://adventofcode.com/2022/day/7/input \
  -b session=secret \
| sed -n '2,$p' | sed 's/$ //' | grep -v 'ls$' | \
perl -lne '
@comm;
%log = $_ =~ /^(\w+)\s(.+)$/;
while (($k, $v) = each %log) {
    if ($k eq "dir") {push (@comm, "mkdir $v")}
    elsif ($k =~ /\d+/) {push (@comm, "fallocate -l $k $v")}
    elsif ($k eq "cd") {push (@comm, "$k $v")}
}
print join (" && ", @comm);
' \
| tail -n 1 | sh

И на тестовом же примере получался прекрасный и верный ответ с помощью

find . -type f -exec du -ab -t -100000 {} + | cut -f 1 | awk '{s+=$1} END {print s}'

Увы, заставить это сработать на реальных данных мне не удалось.

За деревьями леса не видно

Вторая попытка – ладно, придётся всё же создать дерево. Максимально простой узел в виде:

class TreeNode {
    public String name;
    public TreeNode parent;
    public Map<String, TreeNode> childs = new HashMap<>();
    public long size;

    public TreeNode(String name, TreeNode parent, long size) {
        this.name = name;
        this.parent = parent;
        this.size = size;
    }
}

И не менее простое заполнение дерева этим узлами:

TreeNode root = new TreeNode("/", null, 0L);
TreeNode current = root;
for (var commandLine : commands) {
    String command = commandLine[0];
    String arg = commandLine[1];
    if ("dir".equals(command)) {
        current.childs.putIfAbsent(arg, new TreeNode(arg, current, 0L));
    } else if ("cd".equals(command)) {
        if ("..".equals(arg)) current = current.parent;
        else current = current.childs.get(arg);
    } else {current.size += Long.parseLong(command);}
}

Отличное получилось дерево! Оно красиво распечатывалось в правильном виде

/[23352670]
├── a[94269]
│   └── e[584]
└── d[24933642]

и замечательно считало результат на тестовом примере! Жаль только, что на рабочих данных это дерево безбожно врало 🙂 Либо я окончательно разучился в рекурсию…

В общем, безуспешно повозившись с деревьями некоторое время, я понял, что лес – это нечто большее, чем одни лишь деревья, и в итоге пришел к решению, описанному в начале заметки.