Advent of Code 2022: Day 7

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

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

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

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

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

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 он не заработает.

Первое решение — хорошо, у нас же тут «как бы файловая система» — так почему бы не сэмулировать её на файловой системе? Возможно, это сработало бы, если как следует поколдовать с 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#39; | \ 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]

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

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

#adventofcode #adventofcode2022

Advent of Code 2022: Day 7

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

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

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