Took me about 15-20 minutes all in all, but the so...

# advent-of-code

[Edgars]

Took me about 15-20 minutes all in all, but the solution is not efficient at all, 700ms for the whole thing.

[ephemient]

I'm down to 20ms for each part now, but my original was 150ms + 300ms

[Edgars]

What's the trick? Different algorithm or more efficient models?

[ephemient]

in my case, I did all the neighbor-finding at parse time. while I'm running the cellular automata, I only need to follow some static pointers

[ephemient]

plus I'm just modifying a couple bools in-place (flipping back and forth between two of them) instead of creating any new objects

[ephemient]

it's still the slowest solution of all days by far...

[Jakub Gwóźdź]

yes. killed my karma tests because of 2s timeout xd 🙂

[Nir]

I missed a break statement from my part 2 lol, just a one line bug, was too lazy to debug last night

[andyb]

@ephemient I didn't think to cache the visible seats for each seat. That's a really smart optimisation.

[Nir]

indeed it is

[Jakub Gwóźdź]

tbh it didn't helped me much. it's only a few seats (of over 7000 total) where pre-caching mattered.

I tried various approaches for data storage - from initial List<List<Char>> to Set<Pair<Int,Int>> to finally two alternating BooleanArray(rows*cols) , but that also did not helped much

most improvement I got when testing if a set should be occupied changed from neighbours.count(::occupied)==0 to neighbours.none(::occupied) 🙂

but algorithmically - I didn't find any ways to optimise regular "for all sets, check neighbours"

[Nir]

Not sure I follow. Iterating the list of cached seats is definitely strictly faster then searching for them m every time, searching for the seats looks like one of the more expensive operations

[Nir]

Assuming you're doing in place mutation already, and assuming you aren't doing deep copies, or full comparison in a second pass or anything like that

[Nir]

A big optimization in C++, not sure if it's as relevant in Kotlin would be to use a single list to represent things instead of lists of lists which are very wasteful for a problem like this

[Jakub Gwóźdź]

two arrays:
``

val even = BooleanArray(rows * cols)
val odd = BooleanArray(rows * cols)
val counter = 0

while (...) {
    val (src, dest) = if (count % 2 == 0) even to odd else odd to even
...