<Advent of Code 2024 day 15> (spoilers) :thread:

# advent-of-code

[Advent of Code 2023 day 15]

Advent of Code 2024 day 15 (spoilers) 🧵

[Marcin Wisniowski]

Part 2

[Marcin Wisniowski]

Pretty fun puzzle today

[Jonathan Kolberg]

Was fun, for part 2 I abstracted the boxes away and computed all boxes that have to be moved in one step and moved them at once:
https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day15.kt

[Michael de Kaste]

Very fun puzzle, I always do well on these

Day 15 Michael.cpp

[Jonathan Kolberg]

Was glad to be able to use a tailrecursive function today to compute all the boxes that should be moved and move them in the end.

[Michael de Kaste]

The little robot is doing its best ☺️

[Dan Fingal-Surma]

Not bad. For part 2 you need to model the force more precisely vs part 1 or E/W motion

[Dan Fingal-Surma]

My code is garbo

[Jonathan Kolberg]

Dan it helps to compute all the boxes, that would be moved and move them in one step. To be fair for part 2 I modeled boxes as a data class BigBox and had a SimpleBox in a sealed hierachy.

[Dan Fingal-Surma]

https://github.com/dfings/advent-of-code/blob/main/src/2024/problem_15.main.kts

[Dan Fingal-Surma]

I’ll clean it up and post a screenshot later

[Dan Fingal-Surma]

I calculate points of force one line at a time until you hit a wall or empty space and update intermediate sets of what to remove and add for the next state

[Dan Fingal-Surma]

tldr yes I move them in one step. My Warehouse is immutable

[Dan Fingal-Surma]

I needed to implement a print for the warehouse to get N/S working correctly

[Dan Fingal-Surma]

I should probably model boxes as Pair<Point, Point>, might reduce LOC

[Dan Fingal-Surma]

Alright I’m pretty happy with it

[Dan Fingal-Surma]

Part 1

[Dan Fingal-Surma]

Part 2

[Dan Fingal-Surma]

Parsing and solving

[phldavies]

I had so many issues with my approach as I for some brain-addled reason was trying to keep the part2 widened boxes as a Set<Point(x,y)> but I got there in the end...

year 2024 day 15 warmup (30 iterations) took 9.441068167s
year 2024 day 15 part 1
	 Default took 36.804841ms 👑: 1421727
year 2024 day 15 part 2
	 Default took 275.489666ms 👑: 1463160

Day15.kt

[Max Thiele]

Kept a set of single-point per box for part 2. It became quite messy but after some cleanup I'm fine with it

https://github.com/fabmax/aoc-kt/blob/main/src/y2024/day15/Day15.kt

[Jakub Gwóźdź]

To be honest, I was hoping for something more interesting for visualization today, but anyway. Here we go:
At least "real" times more interesting: both parts around 50-60ms. Would be even faster if I skipped generating statuses for animations 🙂

Screen Recording 2024-12-15 at 13.42.07.mov

[kingsley]

Spent way too much time debugging all sorts of corner cases and my solution is super messy, even after rewriting with maps

[David]

Can anyone send me their steps from the larger example in part two? I jut can't figure out where the bug in my program is. It solves the small example perfectly and I couldn't find a step in the larger one that's wrong (I checked like 100 steps or so).

[Jakub Gwóźdź]

@David my animation two comments above is just that, but you’ll have to play/pause it

[David]

@Jakub Gwóźdź Thanks! Do you know how many steps you do per second? It is still quite hard do find the step where your algorithm is different from mine without knowing the iteration number in the animation.

[Jakub Gwóźdź]

@David

Untitled.txt

[David]

Awesome, thank you so much! I was able to find the problem and solve part two 🙂

[roman.belov]

Having some fun using Kotlin Notebook for today's task, along with Kandy, Multik and awesome Advent of Code adapter! Will you accept the challenge and continue the notebook with animations for part 2?

day15.mov

[Michael de Kaste]

I've rewritten my 'check next possible set of points` function and I just noticed how much I don't want to lose context receivers sad panda great case for the guards to shine again though!

context(MutableMap<Point, Char>)
fun Set<Point>.nextSet(dir: Point): Set<Point>? = map(dir::plus).flatMapTo(mutableSetOf()) { destination ->
    when (get(destination)) {
        null -> emptyList()
        '#' -> return null
        '[' if dir in setOf(NORTH, SOUTH) -> listOf(destination, destination + EAST)
        ']' if dir in setOf(NORTH, SOUTH) -> listOf(destination, destination + WEST)
        else -> listOf(destination)
    }
}

[Dan Fingal-Surma]

@David, for me the keys bugs were (a) not properly transferring force via box parts not directly N/S of the points being pushed, (b) transferring force via empy space

[Luan Tran]

I blundered so hard today trying to find out a way to fix all of the bugs for part 2. In the end I basically copied the solution on the top of this thread. That one feel so elegant and easy to understand.

[David]

Yeah, I struggled quite a bit as well. But once I felt I was close, I couldn't stop 😄

[Kai Yuan]

My part2 solution works for the test input, The step result after each move is correct too (thanks for the step results above). However, it doesn't give the correct result for the real input.. It's really hard to find the bug... 😵‍💫 💢

[Dan Fingal-Surma]

The test input is lacking some cases. Those cases don't show up into far in to the real input.

[Dan Fingal-Surma]

For example, try this test case:
Before

######################
##                  ##
##    [][]          ##
##   [][][]  []     ##
##    [] [] [][]    ##
##     []  []       ##
##      [][]        ##
##       []         ##
##        @         ##
######################

Move north
After should be

######################
##    [][]          ##
##   [][]    []     ##
##    [] [] []      ##
##     [][][] []    ##
##      [][]        ##
##       []         ##
##        @         ##
##                  ##  
######################

Then start inserting walls in various blank spots that are in the way and make sure nothing moves

[nerses]

@Kai Yuan this one helped me to figure out what's wrong in my code

#########
##..O...#
#...O...#
#..O....#
#.OO....#
#..O.OO.#
#.OO....#
#.#OOO..#
##OOO...#
#O.OO.#.#
#...OO..#
#..O..#.#
#...OO..#
#...@...#
#########

<^<<^><^^>vvvv>>^

[Dan Fingal-Surma]

eyeballing it looks like that sets up a similar case

[nerses]

ah yes similar case to your's, just an input you can feed in directly 😄

[Kai Yuan]

Thanks a lot @Dan Fingal-Surma, I imported your input, and it turned out the "move-up" didn't work correctly: (somehow a box at the top was missing....)

#..................#
#....[][]..........#
#...[][][]..[].....#
#....[].[].[][]....#
#.....[]..[].......#
#......[][]........#
#.......[].........#
#........@.........#

[after 1 : Up] 
#......[]..........#
#...[][]....[].....#
#....[].[].[]......#
#.....[][][].[]....#
#......[][]........#
#.......[].........#
#........@.........#
#..................#

@nerses thank you too! 👍
Now at least I know where to look at.

[Kai Yuan]

Bug fixed!!! a distinct() call was missing.... 💢
I got the 2nd 🌟 after fixing it. Thank you guys..
what a Sunday night!

[Paul Woitaschek]

🤯
For some reason it took forever to find a solution.
1. Check recursively if we can push
2. While checking, also collect the points we want to push
3. Then push them all together
https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day15.kt

[Paul Woitaschek]

push.png

[Neil Banman]

Ugh, that was every bit as fiddly and buggy as I thought it would be. Now I'm a day behind.

[Ozioma Ogbe]

import utils.Point
import java.io.File

fun main() {
    val (input, directions) =
        File("input.txt").readText().split("\n\n")
            .let {
                it[0].let {
                    it.replace("#", "##").replace(".", "..").replace("@", "@.").replace("O", "[]")
                }.split("\n").toMutableList().map { it.toMutableList() }.toMutableList() to it[1].split("\n")
                    .joinToString("")
            }
    val directionMap = mapOf(
        '^' to Point(-1, 0),
        'v' to Point(1, 0),
        '<' to Point(0, -1),
        '>' to Point(0, 1),
    )
    var robotPosition = input.mapIndexed { x, chars ->
        chars.mapIndexed { y, c ->
            if (c == '@') x to y
            else null
        }
    }.flatten().filterNotNull().map { Point(it.first, it.second) }.single()

    directions.forEach {
        val direction = directionMap[it]!!
        val nextPosition = robotPosition.copy(x = robotPosition.x + direction.x, y = robotPosition.y + direction.y)
        val inputCopy = input.map { it.map { it }.toMutableList() }.toMutableList()

        val result = if (direction.x != 0 && input.getOrNull(nextPosition.x)?.getOrNull(nextPosition.y)
                .let { it == ']' || it == '[' }
        ) {
            input.getOrNull(nextPosition.x)!!.getOrNull(nextPosition.y)!!.let {
                (if (it == '[') proceed(nextPosition.copy(y = nextPosition.y + 1), input, direction)
                else proceed(nextPosition.copy(y = nextPosition.y - 1), input, direction)) && proceed(
                    nextPosition, input, direction
                )
            }
        } else {
            proceed(nextPosition, input, direction)
        }
        if (result) {
            input[robotPosition.x][robotPosition.y] = '.'
            robotPosition = nextPosition
            input[robotPosition.x][robotPosition.y] = '@'
        } else {
            inputCopy.forEachIndexed { x, chars -> chars.forEachIndexed { y, c -> input[x][y] = c } }
        }
    }

    input.mapIndexed { x, chars ->
        chars.mapIndexed { y, c ->
            if (c == '[') (100 * x + y).toLong() else 0L
        }.sum()
    }.sum().also(::println)

}

fun proceed(
    currentPosition: Point,
    input: MutableList<MutableList<Char>>,
    direction: Point
): Boolean {
    val nextPosition = currentPosition.copy(
        x = currentPosition.x + direction.x,
        y = currentPosition.y + direction.y
    )
    return when (input[currentPosition.x][currentPosition.y]) {
        '#' -> false

        '[', ']' -> {
            (if (direction.x != 0 && input.getOrNull(nextPosition.x)?.getOrNull(nextPosition.y)
                    .let { it == ']' || it == '[' }
            ) {
                input.getOrNull(nextPosition.x)!!.getOrNull(nextPosition.y)!!.let {
                    (if (it == '[') proceed(nextPosition.copy(y = nextPosition.y + 1), input, direction)
                    else proceed(nextPosition.copy(y = nextPosition.y - 1), input, direction)) && proceed(
                        nextPosition, input, direction
                    )
                }
            } else {
                proceed(nextPosition, input, direction)
            }).apply {
                if (this) {
                    input[nextPosition.x][nextPosition.y] = input[currentPosition.x][currentPosition.y]
                    input[currentPosition.x][currentPosition.y] = '.'
                }
            }
        }

        'O' -> {
            proceed(
                nextPosition, input, direction
            ).apply {
                if (this) input[nextPosition.x][nextPosition.y] = input[currentPosition.x][currentPosition.y]
            }
        }

        '.' -> true

        else -> error("invalid state")
    }
}

[ephemient]

Day15.kt catching up…