[SPOILER ALERT] Advent of Code: Day 7 solutions

[Stephan van Hulst]

package nl.nibsi.aoc.y22.d07;

import java.io.*;
import java.util.*;

public final class FileSystem {

  private final Directory root;

  private FileSystem(Directory root) {
    this.root = root;
  }

  public Directory root() {
    return root;
  }

  public void printTo(PrintWriter printer) {
    root.visitBy(new FileSystemVisitor() {
      @Override
      public void visitDirectory(Directory directory) {
        printIndentation(directory.depth());
        printer.printf("- %s (dir)%n", directory.name());
      }

      @Override
      public void visitFile(File file) {
        printIndentation(file.depth());
        printer.printf("- %s (file, size=%d)%n", file.name(), file.calculateSize());
      }

      private void printIndentation(int depth) {
        for (var i = 0; i < depth; i++) {
          printer.print("  ");
        }
      }
    });
  }

  public static FileSystem inferFromCommands(Scanner scanner) {
    var root = Directory.createRoot();
    var currentDirectory = root;

    while (scanner.hasNext()) {
      scanner.next("[$]");

      var command = scanner.next("cd|ls");

      currentDirectory = switch (command) {
        case "cd" -> cd(currentDirectory, scanner);
        case "ls" -> ls(currentDirectory, scanner);
        default   -> throw new AssertionError();
      };
    }

    return new FileSystem(root);
  }

  private static Directory cd(Directory currentDirectory, Scanner scanner) {
    var destination = scanner.next();

    return switch (destination) {
      case "/"  -> currentDirectory.root();
      case ".." -> currentDirectory.parent().get();
      default   -> currentDirectory.subdirectory(destination).get();
    };
  }

  private static Directory ls(Directory currentDirectory, Scanner scanner) {
    while (scanner.hasNext("dir") || scanner.hasNextLong()) {
      if (scanner.hasNext("dir")) {
        scanner.next();
        var name = scanner.next();
        currentDirectory.addDirectory(name);
      }

      else {
        var size = scanner.nextLong();
        var name = scanner.next();
        currentDirectory.addFile(name, size);
      }
    }

    return currentDirectory;
  }
}

package nl.nibsi.aoc.y22;

import java.io.*;
import java.nio.charset.*;
import java.util.*;
import java.util.function.*;

import nl.nibsi.aoc.y22.d07.Directory;
import nl.nibsi.aoc.y22.d07.FileSystem;
import nl.nibsi.aoc.y22.d07.FileSystemVisitorAdapter;

final class Day07 {

  public static void main(String... args) throws IOException {
    FileSystem fileSystem;

    try (
      var stream = Day07.class.getResourceAsStream("day07.txt");
      var scanner = new Scanner(stream, StandardCharsets.UTF_8);
    ) {
      fileSystem = FileSystem.inferFromCommands(scanner);
    }

    var printer = new PrintWriter(System.out, true);

    fileSystem.printTo(printer);

    solvePart1(fileSystem, printer);
    solvePart2(fileSystem, printer);
  }

  private static void solvePart1(FileSystem fileSystem, PrintWriter printer) {
    var directories = findDirectories(fileSystem, directory -> directory.calculateSize() <= 100000L);

    var totalSize = directories.stream().mapToLong(Directory::calculateSize).sum();

    printer.println(totalSize);
  }

  private static void solvePart2(FileSystem fileSystem, PrintWriter printer) {
    var   usedSpaceSize = fileSystem.root().calculateSize();
    var unusedSpaceSize = 70000000L -   usedSpaceSize;
    var spaceToFreeSize = 30000000L - unusedSpaceSize;

    var directories = findDirectories(fileSystem, directory -> directory.calculateSize() >= spaceToFreeSize);

    directories.stream().mapToLong(Directory::calculateSize).min().ifPresent(printer::println);
  }

  private static List<Directory> findDirectories(FileSystem fileSystem, Predicate<Directory> predicate) {
    List<Directory> directories = new ArrayList<>();

    fileSystem.root().visitBy(new FileSystemVisitorAdapter() {
      @Override
      public void visitDirectory(Directory directory) {
        if (predicate.test(directory)) {
          directories.add(directory);
        }
      }
    });

    return directories;
  }
}

[Mike Simmons]

Here's my Kotlin version:

package year2022.day07

import year2022.util.Lines
import java.io.File

fun main() {
//    val file = File("src/year2022/day07/sample1.txt")
    val file = File("src/year2022/day07/input.txt")
    val lines = Lines.from(file)

    println("\nPart 1:")

    assert(lines[0] == "cd /")

    val baseDir = DirTreeBuilder(lines.takeLast(lines.size - 1)).root
    val result1 = baseDir.all()
        .filter { it is Directory && it.size() <= 100000}
        .sumOf { it.size() }
    println("result1=$result1")

    println("\nPart 2:")
    val sizeToDelete = baseDir.size() - 40_000_000
    val result2 = baseDir.all()
        .filter { it is Directory && it.size() >= sizeToDelete }
        .map { it.size() }.min()
    println("result2=$result2")
}

class DirTreeBuilder(lines: List<String>) {
    val root = Directory("/", null)
    var current = root

    init {
        lines.forEach { line ->
            val words = line.split(" ")
            when (words[0]) {
                "$" -> if (words[1] == "cd") current =
                    if (words[2] == "..") current.parent!!
                    else current.subdirectory(words[2])
                "dir" -> Directory(words[1], current)
                else -> File(words[1], current, words[0].toLong())
            }
        }
    }
}

abstract class Node(val name: String, val parent: Directory?) {
    init {
        if (parent?.contents?.get(name) == null)
            parent?.add(this)
    }
    abstract fun size(): Long
    abstract fun all(): Sequence<Node>
}

class Directory(name: String, parent: Directory?) : Node(name, parent) {

    val contents = mutableMapOf<String,Node>()
    fun add(node: Node) { contents[node.name] = node }
    override fun size() = contents.values.map { it.size() }.sum()

    fun subdirectory(name: String): Directory =
        (contents[name] ?: Directory(name, this)) as Directory

    override fun all(): Sequence<Node> = contents.values.asSequence().flatMap { it.all() } + this
    override fun toString(): String = "${parent ?: ""}/$name"
}

class File(name: String, parent: Directory?, val size: Long) : Node(name, parent) {
    override fun size() = this.size
    override fun all(): Sequence<Node> = sequenceOf(this)
    override fun toString(): String = "File(name=$name,parent=$parent,size=$size)"
}

[Junilu Lacar]

Been on vacation in South Texas for a couple of weeks, just got back to the AoC2022. Been refactoring my solution framework and puzzling over how to use higher order functions to solve Day 7.

Here's what I ended up with after multiple refactorings (Kotlin):

class Day7  (
    private val fileName: String,
    private val expected1: Int,
    private val expected2: Int) : Solution {

    override val name: String get() = "Day 7 ($fileName)"
    private val root = parse(InputReader(fileName).lines())

    override fun part1() = Result(expected1, smallDirectories().sumOf { it.size() })

    private fun smallDirectories() = findDirs { it.size() <= 100_000 }

    override fun part2() = Result(expected2, smallestDirectoryToDelete().size())

    private fun smallestDirectoryToDelete(): FileAoC7 {
        val spaceNeeded = spaceNeeded(root.size())
        return findDirs { it.size() >= spaceNeeded }.minByOrNull { it.size() }!!
    }

    private fun spaceNeeded(used: Int) = 30_000_000 - (70_000_000 - used)

    private fun parse(input: List<String>): FileAoC7 {
        val root = FileAoC7("/")
        var currentDir = root
        val dirStack: Stack<FileAoC7> = Stack()

        fun dirName(line: String) = line.split(" ")[1]

        fun toFile(line: String) = line.split(" ").let { FileAoC7(it[1], it[0].toInt()) }

        fun toDir(line: String) = FileAoC7(dirName(line))

        fun upDir() = if (dirStack.isNotEmpty()) dirStack.pop() else dirStack.push(root).let { root }

        fun chdir(line: String) = dirStack.push(currentDir).let {
            currentDir.contents.first { it.name == dirName(line.substring(2)) }
        }

        input.forEach { line ->
            when {
                line.startsWith("$ cd /") -> dirStack.push(root)
                line.startsWith("$ cd ..") -> currentDir = upDir()
                line.startsWith("$ cd ") -> currentDir = chdir(line)
                line.startsWith("dir ") -> currentDir.contents.add(toDir(line.trim()))
                line.first().isDigit() -> currentDir.contents.add(toFile(line.trim()))
            }
        }

        return root
    }

    private fun findDirs(predicate: (FileAoC7) -> Boolean): List<FileAoC7> {
        val dirs: MutableList<FileAoC7> = mutableListOf()
        root.walkDirectories { if (predicate.invoke(it)) dirs.add(it) }
        return dirs
    }
}

data class FileAoC7 (val name: String, val bytes: Int, val isDirectory: Boolean = false) {
    constructor(name: String) : this(name,0, true) {}

    val contents: MutableList<FileAoC7> = mutableListOf()
    fun size(): Int = if (isDirectory) contents.sumOf { it.size() } else bytes

    fun walkDirectories(action: (FileAoC7) -> Unit) {
        if (!isDirectory) return
        action.invoke(this)
        contents.filter { it.isDirectory }.forEach { it.walkDirectories(action) }
    }
}

[Junilu Lacar]

Here's another way to write the findDirs function in Kotlin, using the also scope function:
   private fun findDirs(predicate: (FileAoC7) -> Boolean): List<FileAoC7> {        val dirs: MutableList<FileAoC7> = mutableListOf()        root.walkDirectories { if (predicate.invoke(it)) dirs.add(it) }        return dirs    }
   private fun findDirs(predicate: (FileAoC7) -> Boolean): List<FileAoC7> = mutableListOf<FileAoC7>()        .also { matches -> root.walkDirectories { if (predicate.invoke(it)) matches.add(it) } }
Doing it this way, you don't have to create a local variable to collect matches to the given predicate. The also() scope function returns whatever value it was invoked on hence, calling also() on a new instance will return that new instance after the also block is executed.

[Junilu Lacar]

Another refactoring that uses another scope function, let(), to tighten up the code.

This
   private fun smallestDirectoryToDelete(): FileAoC7 {        val spaceNeeded = spaceNeeded(root.size())        return findDirs { it.size() >= spaceNeeded }.minByOrNull { it.size() }!!    }
can be written as
   private fun smallestDirectoryToDelete() = spaceNeeded().let { minSize ->        findDirs { it.size() >= minSize }.minByOrNull { it.size() }!! }    private fun spaceNeeded() = 30_000_000 - (70_000_000 - root.size())