https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 9> (spoilers) :thread:
# advent-of-code
a
j
Took a while to understand the memory encoding. I decided to use data classes to represent OccupiedBlock and FreeBlocks. For part 1 I used an array to store my memory blocks and then did the algorithm step by step, for part 2 I had the memory blocks in a list and moved the blocks in the list. https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day09.kt
b
for part1 i also created the memory layout in a list and just moved items around. for part2, i instead created a list of (id to length) and reordered those
m
I'm currently cleaning up because this has got to be the most ugly "initial" solution I made. part1 went blazingly somewhat smoothly, once I got the algorithm down part2 was a big struggle because I (once again) misread the input. Will edit this message later when I get something worth showing blob nervous
k
Took so much time on part 1 because of my data structure. And part 2 took much more because of a missing bounds check. But I feel pretty good about both solutions Also, today is definitely the most lines of code so far
b
part 1
d
That was painful
But I’m done
Will clean and post
I simulated the whole filesystem with a 
List<Int>
(of blocks) that just contained each file number of 
-1
for free space, in order to make part 2 tractable. Like:
Copy code
00...111...2...333.44.5555.6666.777.888899
With 
.
= 
-1
To start with part 1 I used forward/reverse iteration only, no mutations. In part 2, linear search for free space. Performs just fine.
Screenshot 2024-12-09 at 12.43.37 AM.png,Screenshot 2024-12-09 at 12.43.45 AM.png
n
Double plus ungood. But it compiles and gives the right answer. 400ms of pain intermixed with boredom. https://github.com/nbanman/pdx-puzzles/blob/main/kotlin/advent/src/main/kotlin/org/gristle/pdxpuzzles/advent/y2024/Y24D09.kt
ok, I halved the time with some rampant ugliness (not checking empty spaces once they are filled up).
m
First time I actually solved it directly when it came out at 6 in the morning. Finished part 2 reasonably quick after 28 minutes (global rank 565, my first time in the top 1000 🙂) Code is a giant ugly mess with several IntArrays and loops.
🥳 2
j
It’s good to read that a lot of us were struggling and have ugly solutions. It’s done but… don’t look yet 🙂
e
I didn't read the puzzle right, I started part 1 by trying to move whole files (like part 2). then when I got to part 2 I started with a more efficient packing algorithm before discovering that the one described in the text is just a single pass. and the traversal in reverse got me on both parts…
a
did anyone blow up blocks as a list? when I saw the input, I figured it was a trap that might prevent it from being stored in memory. so I used 
data class Block(val count: Int, val fileId: Int?)
with fileId being 
null
for the free spaces. so apart from checking for spaces and size, had to code in the math for big pieces being broken into smaller ones and then swapping and updating, etc.
so the 
12345
input would be parsed as only:
Copy code
[Block(count=1, fileId=0), Block(count=2, fileId=null), Block(count=3, fileId=1), Block(count=4, fileId=null), Block(count=5, fileId=2)]
and using the long version only for pretty printing while debugging:
Copy code
0..111....22222
also, I realise both parts defragging (I called it sorting) could be doing with indexing and not actually re-arranging
e
part 1 I used an 
IntArray
directly from the input: even indices are file ID * 2, odd indices are free spaces, values are sizes. then I mutate it throughout the solution, narrowing in from the left and right. part 2 I split the files from spaces and added another array for offsets. didn't expand anything into individual blocks or create any classes or objects
a
oh, so you just store it as 
[1, 2, 3, 4, 5]
? hmm, I definitely over-engineered it 🤦 finally have to do the same math with sizes, free/non-free etc. anyway; but with more data structures getting in the way 😕
r
My Part 1 just uses a 
List<Int?>
containing either the file id or null for a blank size and moves the last non-null value earlier while it can Part 2 was originally built on the same idea, but trying to keep track of the empty spaces got incredibly messy. I cleaned it up by making a data class to keep track of file attributes (id, size, start position) and started keep track of only the files. When I find a gap (by looking at the difference between the end and start positions of two consecutive files), I remove the file from the list, update its start position, and re-insert it in the correct place.
e
Unfortunately, due to work there is no time to clean it, especially the second part, it is a bit messy. https://github.com/bayesiano/advent-of-code-2024/blob/main/src/main/kotlin/Day9.kt
m
Refactored solution, part1 working naively on the raw list (kept the solution because it looks pretty and performs ok) while part2 uses a Map as underlying structure. Only 35 readable lines of code with no external references! https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2024/day09.kt
👍 1
n
I am struggling to understand the requirement when I reach file Id 150 and the file block is 5. do I fill it in as 15015? I guess rubber duck helps 😄 I was filling it with 5 times 150. Let me give it a go
m
^ Why would file id 150 be significant?
n
just an example anything over 10 is the same
m
^ Sure, but why five times?
^ I think you need to find a data structure where numbers >9 do not require more space than smaller numbers 🙂
n
let me extend the example in the test
Copy code
233313312141413140213
is going to
Copy code
00...111...2...333.44.5555.6666.777.888899.101
or
Copy code
00...111...2...333.44.5555.6666.777.888899.101010
m
^ What data structure other than text can you think of which might be better suited?
💡 1
n
I am not using text in my program I am running over the input from both sides and collecting the accumulation until both sides meet. I am just trying to understand the requirement and using the same illustration as in the description
Each file on disk also has an ID number based on the order of the files as they appear before they are rearranged
as per this line the id of the last 
3
is 10
I was doing the second variant but now I think I misunderstood and need to use the first variant
m
^ the point is that you cannot illustrate examples in ascii like they did if you use more than 10 files 🙂
e
⓪⓪。。。①①①。。。②。。。③③③。④④。⑤⑤⑤⑤。⑥⑥⑥⑥。⑦⑦⑦。⑧⑧⑧⑧⑨⑨。⑩⑩⑩
n
oooh, I think I get it now. let me give it a go
a
@Renette Ros your approach is what I first wanted to do but I thought wouldn't work due to memory/input size. guess I was being overly cautious (link for others)
👍 1
e
you can sum up your input to check for yourself but at 20000 characters long, it'll expand about 4.5x (100000) if the digit frequencies are distributed evenly or 9x (180000) in the worst case. which is big, but not "won't fit in memory" big
a
ah, good to know. thanks! I think Mr. Wastl has given me a Pavlovian response to "process this innocent text" questions 😛
j
Today was sooo much fun for me. I just needed to go with mutable data classes (which I dislike usually) to get to the sweet times.
Copy code
warming up for 5s
warmed up for 4.898349709s (136 times)
Parsing took 332.417us
Part 1 took 578.333us, result is 6378826667552
Part 2 took 39.445083ms, result is 6413328569890
Basically I'm chunking whole input into pairs "file,free", and then create sectors with a set size and a mutable list of chunks (files or their parts).
day9 JakubG.kt
n
@Michael Böiers @ephemient thanks for the tip, that was an easy fix to make it work )
p
b
finally cleaned up p2 as much as i probably will
guess i don't need the sort and can use 
.sumOf
instead of 
fold
j
Well, the test data are actually much funnier to do the visualizations! Go figure
Screen Recording 2024-12-09 at 19.07.04.mov
t
This has been my favorite puzzle so far. Instead of moving anything, I move right to left through the file chunks and figure out where I would move it and calculate the checksum of that block as if I had moved it. This works because all empty regions checksum to zero. So I can pretend to move somewhere and when I eventually scan the (now occupied) region it will net to zero. Same with space I vacate, it will be zero so I don't need to evaluate it. Part 2 finishes under 50ms. • Blog • Code
👍 1
n
Very nice! I had already cribbed the minHeap idea from someone else, but I appreciate the clever insight that we can add to checksum on the spot and then literally forget about it. Especially with all the ownership issues in my Rust solution it’s much easier to not have to move things around or modify state.
👍🏻 1
o
I used similar left to right approach for part one but could not figure out how to adapt it for part 2, so instead I calculated the checksum on the spot only when it cannot be moved else I move it and I know it cannot be moved later in the future since its already in the unmovable spot.
Copy code
import java.io.File
import java.util.LinkedList
import java.util.Stack

fun main() {
    val input = File("/Users/oogbe/IdeaProjects/AdventOfCodeSolutions/solutions/src/2024/input.txt").readText()
    println(input.map { it.digitToInt().toLong() }.sum())
    var abs = 0
    val diskInputs = input.mapIndexed { index, c ->
        val x = if (index % 2 == 0) FileBlock(index / 2, c.digitToInt(), abs) else FreeSpace(c.digitToInt(), abs)
        abs += c.digitToInt()
        x
    }
    val deque = LinkedList<DiskInput>().also { it.addAll(diskInputs) }
    var result = 0L
    while (deque.isNotEmpty()) {
        val back = deque.pollLast()
        if (back is FreeSpace) continue
        val diskBlock = back as FileBlock
        val temp = Stack<DiskInput>()
        var found = false
        while (deque.isNotEmpty()) {
            val front = deque.pollFirst()
            if (front is FreeSpace && front.frequency >= diskBlock.frequency) {
                if (front.frequency > diskBlock.frequency) {
                    deque.addFirst(
                        FreeSpace(
                            front.frequency - diskBlock.frequency,
                            front.absIndex + diskBlock.frequency
                        )
                    )
                }
                deque.addFirst(FileBlock(back.id, back.frequency, front.absIndex))
                found = true
                break
            } else {
                temp.push(front)
            }
        }
        while (temp.isNotEmpty()) {
            deque.addFirst(temp.pop())
        }
        if(!found) {
            (diskBlock.absIndex until (diskBlock.absIndex + diskBlock.frequency)).forEach {
                result += it * diskBlock.id
            }
        }
    }
    println(result)

}

sealed interface DiskInput {
    val frequency: Int
    val absIndex: Int
}

data class FileBlock(val id: Int, override val frequency: Int, override val absIndex: Int) : DiskInput
data class FreeSpace(override val frequency: Int, override val absIndex: Int) : DiskInput
I remember in C# their linkedlist has a method for inserting a new node in front of another node. woulda helped in this case.
r
I spent enough time on part 2 - figuring out, what's wrong with my logic. Had to rewrite it again, taking different classes (Space and File) into consideration - making it much easier to code and debug. https://github.com/ritesh-singh/aoc-2024/blob/main/src/day09/Day09_2.kt
m
I’m still working on my visualisations for all the 2024 puzzles, and today I tackled day 9
advent of code intensifies 6
❤️ 1
j
nice. what tech are you using for rendering?
m
I’m using Jetpack Compose Multiplatform and ViewModels, with a touch of shaders to mimic the retro CRT effect.
I saw your visualisation for day 16 and it was really cool kodee happy! Which tech stack did you use?
❤️ 1
j
It’s just java.awt.* 😁
🙌 1
t
@Manel Martos what kind of Shaders do you use? Are AGSL Shaders work on Compose Desktop?
m
@Tobias Wohlfarth Yep! Since we have Compose Multiplatform, we can use AGSL when targeting any platform: Android, iOS, Web, or Desktop. I wrote an article describing how to do that in a seamless way. https://medium.com/@mmartosdev/pushing-the-boundaries-of-compose-multiplatform-with-agsl-shaders-d6d47380ba8a
🙌 1
e
can't get past the paywall but "any platform" as long as it doesn't include older devices :p
t
Can't read it too, but yes really cool. Looking at your Photo-FX Demo App this seem relativly easy to implement.
37 Views
Open in Slack
PreviousNext
Powered by