https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 7> :thread:
# advent-of-code
a
d
Nothing like a little recursion to warm up the brain cells!
j
OH BOY THAT WAS FUN!!!
m
Nice! When I saw the input I dreaded an interpreter building task, luckily it wasn’t 😉
d
same - I was ready but then I was like -- oh this is actually pretty cool!
j
Yeah! I was dreading the parsing at first. But it was ok.
d
my favorite is 
when
...
"ls" -> { /* no op */}
j
No recursion on my side, just input.lineSequence.fold(“/”) {…}
d
I'm looking forward to seeing your functional way
m
Lost some time trying to use fold() … then went the old imperative way. No functions, just loops and whens 🙂
d
(I wish I could think in functional)
j
Need to cleanup and then I’ll post 🙂
j
I lost a ton of time wondering why 10_000 wasn't working...
m
@David Whittaker I think the human brain is not meant to think in functional. We think in imperative, which is also why the Python hackers are so damn fast. We’re great at using many heavy-lifting functional constructs like windowed(), but we’re not so great at folding and reducing unless the use-case is almost trivial.
m
My solution
m
Anyways, here’s my naive approach:
Copy code
package aoc2022

fun main() = day07(String(System.`in`.readAllBytes())).forEach(::println)

private fun day07(input: String): List<Any?> {
    val currentPath = mutableListOf<String>()
    val sizes = mutableMapOf<String, Long>()
    var used = 0L
    for (line in input.lines()) {
        if (line.startsWith("$ cd ")) with(currentPath) {
            when (val to = line.substringAfterLast(" ")) {
                ".." -> removeLast()
                "/" -> clear()
                else -> add(to)
            }
        }
        else {
            val size = line.split(" ").first().toIntOrNull() ?: continue
            var dir = "/"
            for (e in currentPath) {
                if (!dir.endsWith("/")) dir += "/"
                dir += e
                sizes.compute(dir) { _, prev -> (prev ?: 0L) + size }
            }
            used += size
        }
    }

    val total = 70000000L
    val needed = 30000000L
    val free = total - used
    val toFree = needed - free

    return with(sizes.values) {
        listOf(filter { it <= 100000 }.sum(), filter { it >= toFree }.min())
    }
}
d
Version 1
no recursion
m
I found that you don't need to track files: just increase the "files size" of the current directory when encountering a file.
d
except in size by lazy
good point
however that helped me figure out some parsing errors
m
Yeah I started with a 
sealed class Node
with 
Directory
and 
File
subclasses, then realized 
File
is not needed.
d
I also started out with sealed class INode and they realized it would be easier to keep separate file and dir lists anyway
s
That was fun indeed!
Copy code
class Directory(val parent: Directory?) {
    var totalSize: Int = 0
    val childDirs: MutableMap<String, Directory> = mutableMapOf()

    fun find(predicate: (Directory) -> Boolean): List<Directory> = buildList {
        if (predicate(this@Directory)) {
            add(this@Directory)
        }
        addAll(childDirs.values.flatMap { dir -> dir.find(predicate) })
    }

    fun updateTotalSizes(): Int {
        totalSize += childDirs.values.sumOf { it.updateTotalSizes() }
        return totalSize
    }
}

fun buildGraph(input: List<String>) = Directory(null).apply {
    var current: Directory = this
    input.forEach { line ->
        current = when {
            line == "$ cd /" -> this
            line == "$ ls" -> current
            line == "$ cd .." -> current.parent!!
            line.startsWith("$ cd ") -> current.childDirs[line.substringAfter("$ cd ")]!!
            line.startsWith("dir ") -> current.apply {
                childDirs[line.substringAfter("dir ")] = Directory(current)
            }

            line[0].isDigit() -> current.apply { totalSize += line.split(" ")[0].toInt() }
            else -> throw RuntimeException("Can't parse: $line")
        }
    }
    updateTotalSizes()
}

fun part1(input: List<String>): Int = buildGraph(input)
    .find { it.totalSize <= 100000 }
    .sumOf { it.totalSize }

fun part2(input: List<String>): Int {
    val root = buildGraph(input)
    val excess = 30000000 - (70000000 - root.totalSize)
    return root.find { it.totalSize >= excess }
        .minBy { it.totalSize }
        .totalSize
}
d
I see... y'all tracked the total size as files were added.
d
yeah also tracked all dirs in a flat list
m
Cleaned version: What I found is that you can ignore 
dir
. Every directory is only entered once, so you can create them as you enter. Can also just drop the first line 
cd /
.
j
ok so here’s my parsing:
Copy code
sealed interface TreeNode {
    val size: Int
    val content: List<TreeNode>
}

data class FileNode(override val size: Int) : TreeNode {
    override val content: List<TreeNode> get() = emptyList()
}

data class DirNode(override val content: MutableList<TreeNode> = mutableListOf()) : TreeNode {
    override val size: Int get() = content.sumOf { it.size }
}

private fun parse(input: String): Collection<DirNode> {
    val filesystem = mutableMapOf("/" to DirNode())

    input.lineSequence().filterNot(String::isBlank)
        .fold("/") { cwd, command ->
            if (command.startsWith("$ cd ")) {
                cwd.pathResolve(command.substringAfter("$ cd "))
            } else {
                if (command.startsWith("dir ")) {
                    val dirNode = DirNode()
                    filesystem[cwd.pathResolve(command.substringAfter("dir "))] = dirNode
                    filesystem[cwd]!!.content += dirNode
                } else if (command.first().isDigit()) {
                    filesystem[cwd]!!.content += FileNode(command.substringBefore(" ").toInt())
                } else require(command == "$ ls") { "WTF `$command`" }
                cwd
            }
        }
    return filesystem.values
}
As you can see, it’s not completely functional, as the 
.fold()
lambda updates 
tree
that is defined outside of the closure. but otherwise, I’m pretty content with that.
d
good thing they didn’t 
ls
the same dir more than once… didn’t guard against that lol
m
That would catch sooo many people off guard (certainly me).
d
There was also no inner cd / thankfully
j
Oh man I'm so bad with graph stuff
b
I tried to be defensive in case they did something like that, but still ended up with an edgecase where I was replacing directories 😞
t
Am I going too heavy with sealed classes 🤔
k
It took me quite some time to get the correct answer for the part1. The test input worked, but the real input didn't.... Finally, I found the cause... I put the dir sizes in a Map..(instead of a list) and use the dir-name as the key... And.... in the input file, there are sub-dirs with the same name.... 💢
g
Wow today was a challenge. Here is my solution, with recursion but without building a tree
SolutionDay7.cpp
m
test code worked. actual input caused a stackoverflowexception .. any ideas ?
g
@Monster Brain hard to say but maybe check the condition which trigger leaving the method in recursion and why it is not met
m
Today I had bad luck on the debugging side, the test input worked, but somehow not on the real file, cue the debugging that took way too long so no leaderboard spot for me.
Copy code
object Day7 : Challenge() {
    private val root = Directory().also { root ->
        input.lineSequence()
            .map { it.split(" ") + "" } // Why no destructuring to nullable?
            .fold(root) { directory, (a, b, c) ->
                when {
                    a == "$" && b == "cd" && c == "/" -> root
                    a == "$" && b == "cd" && c == ".." -> directory.parent!!
                    a == "$" && b == "cd" -> directory.directories.getValue(c)
                    a == "$" && b == "ls" -> directory
                    a == "dir" -> directory.apply { directories[b] = Directory(directory) }
                    else -> directory.apply { updateDirectory(a.toInt()) }
                }
            }
    }
    override fun part1() = root.getAllDirectorySizes()
        .filter { it <= 100000 }
        .sum()

    override fun part2() = root.getAllDirectorySizes()
        .filter { it >= root.fileSize - 40000000 }
        .minOrNull()
}

class Directory(
    val parent: Directory? = null,
    val directories: MutableMap<String, Directory> = mutableMapOf(),
    var fileSize: Long = 0
) {
    fun getAllDirectorySizes(): Sequence<Long> = sequenceOf(fileSize) +
        directories.values.flatMap(Directory::getAllDirectorySizes)

    fun updateDirectory(sizeOfFile: Int) {
        fileSize += sizeOfFile
        parent?.updateDirectory(sizeOfFile)
    }
}
n
@Monster Brain If you use a class that stores nodes, anything to do with toString() or hashCode() or a val with a getter function can cause SOE because the information is not found in the class itself but with the nodes it's attached to.
j
I had a bit of luck in that my solution for Part 1 was immediately reusable for part 2. My Directory class has a method
Copy code
fun searchDirectories(selector: (Directory) -> Boolean): List<Directory> {
    val result = mutableListOf<Directory>()
    if (selector(this)) result.add(this)
    result.addAll(items.values.filterIsInstance<Directory>().flatMap { it.searchDirectories(selector) })
    return result
}
Solution for part 1 is then `
Copy code
root.searchDirectories { it.size <= 100000  }.sumOf { it.size }
and for part 2
Copy code
root.searchDirectories { it.size >= toDelete }.minBy { it.size }
c
using totalSize by lazy { stuff } is easy in-built memoization for the tree parsing + recursion
r
I'm another one that's here discovering that the input was a lot less problematic than it could have been, and my robust solution was totally unnecessary 🤦‍♂️
p
Today I needed a lot more time for solving comparing to the last days: https://github.com/PoisonedYouth/advent-of-code-kotlin-2022/blob/main/src/day07/Day07.kt
m
Refactored solution:
Copy code
package aoc2022

fun main() = day07(String(System.`in`.readAllBytes())).forEach(::println)

private fun day07(input: String): List<Any?> {
    var dir = listOf<String>()
    val sizes = mutableMapOf<List<String>, Int>()
    var used = 0

    fun List<String>.cd(dir: String) = when (dir) {
        ".." -> subList(0, size - 1)
        "/" -> listOf()
        else -> plus(dir)
    }

    fun List<String>.addSize(size: Int) = indices.map { subList(0, it + 1) }.forEach { path ->
        sizes[path] = (sizes[path] ?: 0) + size
    }

    for (line in input.lines()) when {
        line.startsWith("$ cd ") -> dir = <http://dir.cd|dir.cd>(line.substringAfterLast(" "))
        else -> line.split(" ").first().toIntOrNull()?.also(dir::addSize)?.also { used += it }
    }

    return with(sizes.values) {
        listOf(filter { it <= 100_000 }.sum(), filter { it >= used - 40_000_000 }.min())
    }
}
h
Reading all of your solutions (and looking at the clock), I think I may have been overthinking it with mine: https://github.com/haraldsperre/advent-of-code-2022/blob/main/src/Day07.kt
m
@rkechols Yes, one of the lessons for me from this season is to look closely at the input to make sure not to over-engineer the solution. Today I immediately thought “tree!“. Luckily, after another minute of reading I abandoned it and went with “map”. 🙂
d
My solution can be summarized by this function:
Copy code
private fun <T> recursiveVisit(
        dir: Directory,
        filter: (Directory) -> Boolean,
        defaultValue: T,
        combinator: (T, T) -> T, operation: (Directory) -> T
    ): T {
        var result = if (filter.invoke(dir)) operation.invoke(dir) else defaultValue
        dir.subdirectories.forEach { subdir ->
            result = combinator.invoke(result, recursiveVisit(subdir, filter, defaultValue, combinator, operation))
        }
        return result
    }
It's like a recursive fold so you can call it (in my case) with:
Copy code
recursiveVisit(root, { dir -> dir.getTotalSize() < 100000L }, 0L, { left, right -> left + right }) {
            it.getTotalSize()
        }
For part 1 and for part 2:
Copy code
recursiveVisit(root, { dir ->
            dir.getTotalSize() >= spaceToFree
        }, Long.MAX_VALUE, { left, right -> minOf(left, right) }) {
            it.getTotalSize()
        }
e
I flip-flopped on whether to use 
"/a/b/c"
paths or strip the leading `/`; in the end I decided it was easier to store paths as 
"a/b/c"
, since this meant that finding the parent directory could simply be 
.substringBeforeLast('/', "")
r
luckily I was not the only one encountering a StackOverflowError today 😬 anyway, proud to have a solution supporting multiple 
cd /
commands and 
ls
commands in the same directory, even though that was apparently not needed, robustness FTW! metal
d
I don't even support a single 
cd /
😄
I just skipped it because it was at the beginning of the file 😛
e
I completely ignore 
$ ls
and 
dir
, so if a file shows up multiple times I'll count it multiple times
m
I support multiple 
cd /
, directory names etc. 😇😅
e
actually I completely ignore the filenames too
but multiple 
/
or doing 
cd ..
while at 
/
works in mine
m
Files are just sizes in this puzzle
d
Yeah they ended up being irrelevant
r
yeah given the input, a lot of shortcuts were apparently possible, but I was programming defensively, unneeded in this case but still proud of it 😛
z
Honestly surprised that nobody showed this solution yet… I’ve just used 
java.io.File
and its great Kotlin extensions, and actually created all the files 🙃 https://github.com/zsmb13/advent-of-code-2022/blob/main/src/Day07.kt (Yes I did check beforehand that it would be some reasonable size (~40MB), though the second part ended up ensuring that it’s all quite reasonably sized)
d
I just started out by building a model which I thought was at least accurate enough to work with with sealed interfaces 🙂
m
doing 
cd ..
while at 
/
would break my solution, which makes kind of sense. For AoC we build solutions that expect well-formed input.
d
If that would have been a requirement, they would have mentioned it 🙂
r
@zsmb you like to live dangerously 😄
e
in real life, 
cd ..
at 
/
is totally fine though
but yeah we didn't have to handle it 🙂
d
Yes, you can go indefinitely, like 
cd /../../../../../
m
Well, they didn’t specify that in the requirements 😉
d
Luckily for us they didn't 🙂
m
Fixed 🙂
Copy code
fun List<String>.cd(dir: String) = when (dir) {
    ".." -> if (isEmpty()) this else subList(0, size - 1)
    "/" -> listOf()
    else -> plus(dir)
}
r
Today was fun - I formed a 
tree
out of it and performed 
dfs
e
@Michael Böiers just for clarity I'd probably write
Copy code
".." -> dropLast(1)
"/" -> emptyList()
but it's really the same
a
I implemented solution passing test data in 10mins and haven’t fixed it on real data up to now 😄
d
I realized that I don't really need my 
Directory
data class with its subdirectories and files lists, you only need the files with their full paths, kind of like how zip files and git work and then you could always derive the directories from their paths
m
@ephemient Yes, that communicates the intent much better.
x
anyone else had to override the 
toString()
because of a stackoverflow?
r
Yes, i had override it.
m
^ data classes are over-used 😉
It would be cool if in Kotlin all classes that are compatible could automatically get the 
copy
method - not just the data classes.
A good use case for that are database entities. They have a lot of attributes, and if you model the entities as immutable (which I like to do), you really need to define them as data classes just to get the copy method. But since database tables can have cyclical references, you then need to remember to override hashcode, equals and toString to get back to default behavior. That kind of sucks, when all I ever needed was the damn copy method!
d
Yeah, the annoying and useful thing about copy is that it has the same parameters as your constructor (so you can copy with modified fields) so that's why (I think) it works for data classes because Kotlin needs the language construct as a trigger to generate the correct method. Maybe you could create an annotation or KSP processor which can generate this as well? For instance say you had
Copy code
@Copyable
class Foo(val s: String)
And it would generate an extension function 
fun Foo.copy(s: String) = Foo(s = s)
m
@Davio Let’s continue that discussion here: https://kotlinlang.slack.com/archives/C0B9K7EP2/p1670403430892679
r
j
Hi, today I implemented a 
FsNode
class (with map of children as property) and I'm trying to add a 
find
function to it accepting a predicate that runs BFS and returns all nested child nodes matching the predicate. I managed to do it in a way that it returns a 
List
however, I'd like to change it to a 
Sequence
so that it is lazily evaluated (and I practice how to use sequences/yield). My current code starts like
Copy code
fun find(predicate: Predicate<FsNode>): List<FsNode> {
    val toExplore = mutableListOf(this)
and I tried changing it to
Copy code
fun find(predicate: Predicate<FsNode>): Sequence<FsNode> = sequence {
    val toExplore = mutableListOf(this)
The problem is that 
this
now refers to 
SequenceScope
not to the encapsulating class. Can someone please advise how to access 
FsNode.this
inside the sequence code or how to generate this as a sequence properly?
d
You can use this@something right?
j
Yes that's the syntax part I was missing 🙂 Thanks
j
• is it overcomplicated? YES ✅ • does it unnecessary copy large collections of data just to stay in immutable world? YES ✅ but: • does it stay away from global state and refrain from modifying variables outside 
.fold()
closure? YES ✅ • does it use bisect to find the best candidate in second part? ALSO YES✅ (talking about optimization priorities here xd)
m
Finally did it. Stackoverflow error occured since many sub dir having same name and child calling parent .. my bad !!
f
x
went overboard with dsls. Not sure if that makes this more or less readable 🤷
j
Looks nice. Just if you're optimizing the 
.minBy { it.size }.size
can be simplified to 
.minOf { it.size }
p
After messing up by first writing a parser for the wrong input format (in my blurry-eyed state this morning I thought the visualised filesystem was the input) I settled on this:
m
I did that once, since then I always open my real input to see how it looks before starting.
p
I skipped the 
dir
and 
ls
commands completely
r
Kotlin rewrite of betavero’s solution in Noulith: https://github.com/betaveros/advent-of-code-2022/blob/main/p7.noul
p
A little tidy-up. No need to `removeFirst()`/`addFirst()` when you can just 
acc[0] += n
on an 
ArrayDeque
🙂
m
@Rafal Bednarczuk Nice, so I learned something new about Kotlin today (
partialWindows
) 🙂
w
My solution is more verbose, but it handles a lot more general cases that don't actually appear in the input like 
..
Within a bigger path, revisiting directories, etc https://github.com/wakingrufus/advent-of-code-2022/blob/main/src/main/kotlin/com/github/wakingrufus/aoc/day7/Day7.kt
l
Highlights of my solution include iterating the tree as a 
Sequence
, 
.fold
and unnecessary regexes. I like regexes. Not purely functional though
day07.cpp
n
It's a little late to start on a big theme like 2019's IntCode, but I wonder if we'll be building out a fleshed-out shell over the course of multiple problems.
o
a
• my initial solution used paths as a list of strings which were keys in the dictionary. that made it easy to do 
currDir = currDir + nextDir
or 
currDir = currDir.dropLast(1)
◦ along with a dataclass for subdirs and files. also had global mutable state etc. which felt quite disgusting • removed all that and put path as string with "/a/b.txt" etc. each pointing to just the size; or 0 for dirs. • I didn't want to just ignoring dirs in the listing ◦ but before seeing part 2, it's unclear how much we'd need to refactor and retro-refactoring based on part 2's requirements and what is finally not needed at all feels a bit like cheating • (I noticed that there's no 'cd /' anywhere except at the top) https://github.com/aneroid/advent-of-code-2022-kotlin/blob/main/src/Day07.kt
f
might regret not building the file structure at a later date, but i mapped the input once (using an outer 
Stack
to know which directory I was in at any given time) to Dirs and Files, including their paths. noticed every directory was only 
cd-ed
to once. then I could calculate sizes by just filtering for data. made 
Node
Dir
and 
File
classes mostly just to have a conceptual image of the data. https://github.com/fmmr/advent/blob/master/src/main/kotlin/no/rodland/advent_2022/Day07.kt
t
Late again today due to Wednesdays being one of my busier mornings at work. But I had fun. Once I realized that I don’t really care about files (just their total size) everything became easier. • Blog • Code
p
You're really fast, writing code and also that fantastic blog
t
Thank you! Glad you enjoy it.
p
I write my own one, but your is a lot more detailed and feels like a story.
t
@zsmb I’m so glad you implemented this. I considered it for the briefest of moments and decided it was too crazy but I regretted it up until I saw you do it. Yours is my favorite solution of the day. 🙂
a
Hello! I am late to the party today, I was having too much fun with today's problem and really got carried away with my solution. Spent nearly the entire day on it. I went with a FileSystem solution and then applied operations on top of it. Would really love some feedback on it from the amazing folks here. https://github.com/Akhunzaada/advent-of-code-2022/blob/main/src/Day07.kt
@todd.ginsberg @ephemient @Fredrik Rødland @Davio @zsmb @Paul Woitaschek @Michael Böiers @Marcin Wisniowski @phldavies @Grzegorz Aniol
l
mostly a mess, but i'm mostly here to show off the `toString` implementation that formats it as a (sort of) nice tree, which i spent way too long on 🙂
j
https://github.com/jbotuck/aoc2022/blob/main/src/Day07.kt I took care to handle the case of a user cd ing into a directory that was never output from ls
k
My solution is with Tree of sealed classes. Every time I add a file I recalculate the sizes of the directories up to the root. This happens quickly and everything is calculated constantly. No recursion required. It could be written more qualitatively, but I didn't have the strength for it. https://github.com/karloti/advent-of-code-2022-kotlin/blob/main/src/Day07.kt
p
For the truly inefficient - use Jimfs as a virtual filesystem, populate and traverse.
p
That's lame. What about creating the files for real instead? 🧌
p
I honestly wanted to but wanted to use the FileStore.usableSpace value, and couldn't create a filesystem with the right space and blocksize to make it work nicely.
l
Out of curiosity, I went back to todays puzzle to try "outsourcing" the tree to the actual file system. This is probably one of the stupidest ways to solve the puzzle but (much to my surprise) it actually worked and using the 
kotlin.io.path
package is quite convenient! 😅 https://github.com/TheMrMilchmann/AdventOfCode2022/blob/master/src/main/kotlin/days/Day07Silly.kt
f
I'm still a bit surprised how many actually parses the structure to an actual tree-structure with pointers to children and parents and calls getSize() recursively etc, when it's actually quite easy to get alle the data parseable in a one dimensional structure which is easy to filter/sum pretty easy of course I'll regret saying this on Day17
w
Lol I did consider that
I was referring to the actual file solution. But the reason I did the tree structure was I usually try to optimize for readability and staying close to the problem description helps with that
d
The tree structure is much easier to debug and understand IMO. Here’s my code transformed to a flat map with precomputed sizes. Was a lot harder to get working correctly.
It is 6 lines shorter and doesn’t use any custom classes
Compare with
I also didn't know where part 2 was going to go
e
33 Views
Open in Slack
PreviousNext
Powered by