https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 18> :thread:
# advent-of-code
a
s
Today's was a chill. Just needed to figure out how to number the faces properly and use BFS for the second part.
c
Nice and easy 😃. Helps to have a graph class you can just build and search on to not do the same boilerplate everyday.
d
Easy one is welcome after the last 2 nights
e
r
Will get some time now to solve prev few problems 🙂
s
e
I'm writing search from scratch every day… good practice but probably not the best idea for speed lol
I spent forever trying to track down a bug where I copied 
y
instead of replacing it with 
z
when computing `minZ`/`maxZ` though, that really sucked
n
Yeah, today was a relief. Search space was small, so iterating over all points of the whole cube multiple times was no issue.
j
Yeah today was way easier than yesterday
Oh man my recursive bfs for part2 takes ages for the real input
d
Part 1 took a few mins to write, then I needed to do some stuff before finishing part 2. Here is is: https://github.com/dfings/advent-of-code/blob/main/src/2022/problem_18.main.kts
You need to memoize then
I am also writing a self contained script every day, most I do is copy/paste old code
Copy code
val airCache = mutableMapOf<Point, Boolean>()
    fun Point.isAir(): Boolean {
        airCache[this]?.let { return it }
        val frontier = ArrayDeque<Point>(listOf(this))
        val visited = mutableSetOf<Point>()
        while (!frontier.isEmpty()) {
            val current = frontier.removeFirst()
            when {
                !visited.add(current) -> continue
                current in airCache -> return addToCache(visited, airCache.getValue(current))
                current.outsideRange() -> return addToCache(visited, false)
                else -> frontier.addAll(current.adjacentNonLava())
            }
        }
        return addToCache(visited, true)
    }
p
Well that was relaxing after the last few days! https://github.com/tKe/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day18.kt Went for a breadth-first-search from outside the grid for part2, marking any visited points as non-filled, and the using that for the surface area calculation from part1. Timings including parsing:
Copy code
year 2022 day 18 part 1
	 Default took 1.185278ms: 3396
year 2022 day 18 part 2
	 Default took 4.743437ms: 2044
j
Oh man these elephants are something, first we need to teach them opening valves, then they want us to simulate tetris, at least today we were the ones that wanted to know something, maybe the reason, why today was easier.
a
Maybe the creator is a secret php 🐘 lover 😄
p
It seems Eric isn't a fan of PHP... http://phpsadness.com/
a
It's a secret lover 🧌
t
While I didn’t finish it nearly as quickly as the first person on the global leaderboard (1m and 5s!), this wasn’t especially challenging, which I appreciate after the last couple of days. Also, we got to work with

Frinkahedrons▾

, which is always fun. • Blog • Code
k
For part2, could someone explain the concept behind the solution? Part1 made sense because you're essentially looking for sides w/ neighbors. Part2 is about eliminating the inner sides are in an enclosed object (sounds like the shape is enclosed) but I don't see how the min/max solutions folks did accomplish this? 🤔
p
By using min/max you can determine a space directly outside of the shape in which you can start a breadth first search for all reachable points resulting in a set of external air. Using that set you can apply the same process as part1 but limited to only counting sides in the external air.
d
You can also start from any given point and BFS until you run out of points (air) or you go past the cube the lava is in (water) as determined by the min max xyz.
If you then cache the value for every point you visited, you can ensure you don't BFS the same points twice.
p
e
the party never ends 🙂 you'd probably get a bit better performance with something like
Copy code
fun parseInput(input: String): Set<Cube> = buildSet { input.lines().filter(String::isNotEmpty).mapTo(this, Cube::parse) }
o
Question about this, if there is space between two cubes does it count as an air pocket? Or it has to be completely between the four sides of four cubes?
p
It counts as an air pocket if it is entirely unreachable from the outside
e
not sure what you mean by "four sides of four cubes", cubes have six sides. e.g. it takes
Copy code
1,2,2
2,1,2
2,2,1
2,2,3
2,3,2
3,2,2
to make an air pocket at 
2,2,2
11 Views
Open in Slack
PreviousNext
Powered by