https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 8> :thread:
# advent-of-code
a
d
What a pain
Solved it in an extremely ugly manner. Gonna clean it up later
k
Part 1:
Copy code
fun part1(input: List<String>): Unit {
    val height = input.size
    val width = input.first().length
    val grid = input.map { it.map { it.digitToInt() } }
    var numVisible = 0

    for (h in 0 until height) {
        for (w in 0 until width) {
            val curr = grid[h][w]
            if (w == 0) {
                numVisible++
            } else if (h == 0) {
                numVisible++
            } else if (w == width - 1) {
                numVisible++
            } else if (h == height - 1) {
                numVisible++
            } else {
                val columnValues = grid.map { it[w] }
                val leftVisible = grid[h].take(w).all { it < curr }
                val rightVisible = grid[h].drop(w + 1).all { it < curr }
                val topVisible = columnValues.take(h).all { it < curr }
                val bottomVisible = columnValues.drop(h + 1).all { it < curr }
                if (leftVisible || rightVisible || topVisible || bottomVisible) {
                    numVisible++
                }
            }
        }
    }
    println(numVisible)
}
Part 2:
Copy code
fun part2(input: List<String>): Unit {
    fun <T> List<T>.indexOfLastSequential(predicate: (T) -> Boolean): Int {
        val iterator = this.listIterator()
        while (iterator.hasNext()) {
            if (!predicate(iterator.next())) {
                return iterator.previousIndex()
            }
        }
        return size - 1
    }

    val height = input.size
    val width = input.first().length
    var highestScenicScore = 0
    val grid = input.map { it.map { it.digitToInt() } }
    println(grid)

    for (h in 0 until height) {
        for (w in 0 until width) {
            val curr = grid[h][w]
            val columnValues = grid.map { it[w] }
            val leftIndex = grid[h].take(w).reversed().indexOfLastSequential {
                it < curr
            }
            val rightIndex = grid[h].drop(w + 1).indexOfLastSequential {
                it < curr
            }
            val topIndex = columnValues.take(h).reversed().indexOfLastSequential {
                it < curr
            }
            val bottomIndex = columnValues.drop(h + 1).indexOfLastSequential {
                it < curr
            }
            val indexes = listOf(leftIndex, rightIndex, topIndex, bottomIndex)
            val scenicScore = indexes.map {
                it + 1
            }.reduce { acc, i ->
                acc * i
            }
            highestScenicScore = max(scenicScore, highestScenicScore)
        }
    }
    println(highestScenicScore)
}
I spent a few mins debugging why the indexes were off then I realized that 
indexOfLast
was returning the index of the last element matching the predicate, not the last index of the element when checking sequentially.
d
yeah I broke down and wrote code like
Copy code
var score1 = 0
    for (i in x - 1 downTo 0) {
        score1++
        if (this[y][i] >= height) break
    }
my 
takeWhile { }.size
were indeed not detecting whether or not we hit a tree or the edge
x
My dumbaass got 
all
and 
any
mixed up 😂
m
Part 1
Part 2
d
definitely adding 
takeWhile
to my arsenal for next time!
m
Got to use 
..<
for the first time in part 1. 😄
n
Even though I'm not remotely competitive, the "competitive" aspect of this is clouding my brain. I need to slow down and think more deeply. I'm not good at coding on the fly.
I jumped on this with alacrity because I had already written some "raycasting" code for 2020 Day 11. But in my flustered state, I couldn't make heads or tails of the "clever" sequence that I had written back then. And then I realized that that version had me looking in 8 directions, not 4...
j
m
That was pretty fun today
Copy code
object Day8 : Challenge() {
    val GROW_DIRECTIONS = listOf(-1 to 0, 0 to 1, 1 to 0, 0 to -1)
    val parsed = input.lines()
        .withIndex()
        .flatMap { (y, line) -> line.withIndex().map { (x, value) -> (y to x) to value - '0' } }
        .toMap()

    val growths = parsed.map { (key, value) -> growOutwards(key.first, key.second, value) }

    override fun part1() = growths.count { it.any { (canSee, _) -> canSee } }

    override fun part2() = growths.maxOf { growths -> growths.map { it.second }.reduce(Int::times) }

    fun growOutwards(sourceY: Int, sourceX: Int, sourceValue: Int) = GROW_DIRECTIONS
        .map { (yDif, xDif) ->
            generateSequence(sourceY to sourceX) { (y, x) -> y + yDif to x + xDif }
                .withIndex()
                .drop(1)
                .first { !parsed.containsKey(it.value) || parsed.getValue(it.value) >= sourceValue }
                .let { (index, value) -> (!parsed.containsKey(value)).let { it to (index - if (it) 1 else 0) } }
        }
}
s
The mention of 
takeWhile
unclogged me, and I managed to come up with this. I still wonder if there is an easier, less-than-cubic time solution to the second part.
Copy code
fun part2(input: List<String>): Int {
    val array = input.map { it.chars().toArray() }.toTypedArray()
    return (1 until array.lastIndex).maxOf { i ->
        (1 until array.lastIndex).maxOf { j ->
            val height = array[i][j]
            var left = (i - 1 downTo 0).takeWhile { array[it][j] < height }.size
            if (left < i) left++
            var right = (i + 1 until array.size).takeWhile { array[it][j] < height }.size
            if (right < array.lastIndex - i) right++
            var top = (j - 1 downTo 0).takeWhile { array[i][it] < height }.size
            if (top < j) top++
            var bottom = (j + 1 until array.size).takeWhile { array[i][it] < height }.size
            if (bottom < array.lastIndex - j) bottom++
            left * right * top * bottom
        }
    }
}
j
I also went with takeWhile for part 2. Specifically with constructions like
Copy code
val c = rows[y][x]
val u = (0..y - 1).reversed()
  .takeWhile { i -> rows[i][x] < c }
  .lastOrNull()
  ?.let { if (it > 0) y - it + 1 else y }
  ?: 0
j
Optimizing my code for readability (and using as many Kotlin built-ins as possible) but I'm struggling to find some 
Sequence
operation that would take elements until a condition is met, but include also last element. For part 2 I need to stop at the tree with the same height but still include it and using 
takeWhile
either stops just before the last or skips past the equally-sized tree. Is there something built-in that would make this shorter?
s
I'm not sure how I ended up with this for part 1:
Copy code
fun part1(input: List<String>): Int {
    val array = input.map { it.chars().toArray() }.toTypedArray()

    val visibility = Array(array.size) {
        Array(array[0].size) { false }
    }

    var count = 0

    fun AtomicInteger.updateVisibility(i: Int, j: Int) {
        if (array[i][j] > this.get()) {
            if (!visibility[i][j]) {
                count++
                visibility[i][j] = true
            }
            this.set(array[i][j])
        }
    }

    for (i in array.indices) {
        AtomicInteger(-1).apply { array.indices.forEach { updateVisibility(i, it) } }
        AtomicInteger(-1).apply { array.indices.reversed().forEach { updateVisibility(i, it) } }
        AtomicInteger(-1).apply { array.indices.forEach { updateVisibility(it, i) } }
        AtomicInteger(-1).apply { array.indices.reversed().forEach { updateVisibility(it, i) } }
    }

    return count
}
k
Used 
indexOfFirst()
for the part2, (
takeWhile
could be better):
Copy code
fun List<List<Int>>.findHighestScore(): Int {
    var highScore = 0
    for (x in 1 until this[0].lastIndex) {
        for (y in 1 until this.lastIndex) {
            val myScore = ((x - 1 downTo 0).indexOfFirst { this[it][y] >= this[x][y] }.let { if (it < 0) x else (it + 1) }) *
                ((x + 1..this[0].lastIndex).indexOfFirst { this[it][y] >= this[x][y] }.let { if (it < 0) this[0].lastIndex - x else (1 + it) }) *
                ((y - 1 downTo 0).indexOfFirst { this[x][it] >= this[x][y] }.let { if (it < 0) y else (it + 1) }) *
                ((y + 1..this.lastIndex).indexOfFirst { this[x][it] >= this[x][y] }.let { if (it < 0) this.lastIndex - y else (it + 1) })

            highScore = max(highScore, myScore)
        }
    }
    return highScore
}
d
OK I have a version I’m happy with (I keep finding ways to improve it, lol)
j
Any one else get caught up on the part 2 sample? I kept getting 16 instead of 8, and thinking it was wrong. Spent a good 30 minutes debugging nothing.
d
My bugs kept failing for the test input which is good. But 16 is wrong, it should be 8, no?
c
@Jacob Moulton can you share the code? maybe someone can help 😄
r
tricky one with some 'edge' cases! 😅 I got caught up on part 2 as well, trying to use something like 
takeWhile { tree <= height }.size
, getting the wrong results. Then realized this fails when you have multiple trees of the same height in a row, where takeWhile will keep counting them even though you need to stop at the first one (maybe this helps others)
d
It turns out the right thing is 
minOf(takeWhile { it.height < height }.size + 1, size)
n
If anyone has time I'd appreciate a limited-scope code review. My code runs fine and for the moment I don't really care about efficiency. But as a hobbyist, there are a few things that I haven't been able to figure out for myself: 1. I have a 
Coord
class that holds two points and has a bunch of useful functions attached to it. Among these are 
north, south, east, and west
, which when called without arguments return a 
Coord
one away from the main one. I would like to create a list like 
listOf(Coord::north, Coord::south, etc.)
and then apply those functions to my coordinates. But the functions are identified as 
KFunction4
. Whenever I see any kind K-anything I don't know what to do. I can't seem to refer to them in a function signature. Is there a way to do this? 2. My 
part1()
function relies on a 
isVisible()
function, which in turn relies on a 
directionVisible()
function. What is the rule (if any) on nesting functions? Right now 
isVisible()
is separate from 
part1()
, but 
directionVisible()
is nested within 
isVisible()
. Should they both be nested? Should neither? Edit: here's the link: https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2022/d8/Y2022D8.kt
d
Basically there's a lot of not so clever looping through indices just to check everything, which means lots of duplication and no optimization, but at least it's pretty straightforward
Made an alternative for 
takeWhile
which includes the last element which breaks the condition:
Copy code
private inline fun <T> Iterable<T>.takeUntil(predicate: (T) -> Boolean): List<T> {
        val list = ArrayList<T>()
        for (item in this) {
            if (predicate(item)) {
                list.add(item)
                break
            }
            list.add(item)
        }
        return list
    }
I used it to get the correct number of visible trees from a tree's perspective, at first I just added 1 to everything with 
takeWhile
but this goes wrong if you hit the edge and still haven't found a larger tree
p
d
Optimizations might be done in the form of remembering tree distances for part 2, for instance if you have a tree of height H which can see a distance of length N in a row or column and you are now looking at the tree besides it in the same row/column of height H+1, it can obviously see at least N+1
j
@Davio your alternative 
takeUntil
returns a 
List
where as the original 
takeWhile
returns 
Iterable
. I.e. the 
Iterable
content might not necessarily fit to memory. I suggest updating your code to return 
Iterable
since it's not a complicated change to your code (essentially instead of 
ArrayList
you wrap your code to 
Iterable {  iterator { ... } }
and use 
yield
instead of 
.add()
)
d
Hmm, I was looking at the source code for takeWhile which doesn't show in my IntelliJ and found this: https://github.com/JetBrains/kotlin/blob/cb8cc65fb825e1c7e003fcdfc399efab09f3e059/libraries/stdlib/common/src/generated/_Collections.kt
So I just copy-pasted that one to start
Note that 
takeWhile
also returns a List, not an Iterable
j
d
Ah yes, it's highly annoying I can't see those things from my IDE
There is also 
public fun <T> kotlin.sequences.Sequence<T>.takeWhile(predicate: (T) -> kotlin.Boolean): kotlin.sequences.Sequence<T> { /* compiled code */ }
It's also quite annoying that Sequence and Iterable/List don't share an interface so every extension function has to be implemented twice
j
Which IDE are you using? IntelliJ actually shows the code
d
IntelliJ 2022.3 with Kotlin 1.7.22 but it seems to be a known issue that some people are having
m
Got rid of takeWhile and went with indexOfFirst instead.
Copy code
package aoc2022

fun main() = day08(System.`in`.reader().readLines()).forEach(::println)

private fun day08(input: List<String>): List<Int> {
    val H = input.map { it.map(Char::digitToInt) }

    fun linesOfSight(x: Int, y: Int) = sequenceOf(
        listOf((x - 1 downTo 0), (x + 1 until H[0].size)).map { it.map { x -> x to y } },
        listOf((y - 1 downTo 0), (y + 1 until H.size)).map { it.map { y -> x to y } }
    ).flatten().map { it.map { (x, y) -> H[y][x] } }

    fun List<Int>.isVisible(h: Int) = all { it < h }
    fun List<Int>.countVisible(h: Int) = indexOfFirst { it >= h }.let { if (it == -1) size else it + 1 }

    return with(H.flatMapIndexed { y, l -> l.mapIndexed { x, h -> Triple(x, y, h) } }) {
        listOf(
            count { (x, y, h) -> linesOfSight(x, y).any { it.isVisible(h) } },
            maxOf { (x, y, h) -> linesOfSight(x, y).map { it.countVisible(h) }.reduce(Int::times) }
        )
    }
}
f
a
d
Not great not terrible is exactly how I thought about my solution as well 🙂
It's funny and comforting to see many similar approaches with only differences in details 🙂
m
I think the main aspects most of us come here to learn about are: • idiomicity (not a word, but maybe it should be 😉) / elegance • performance • conciseness (and/or golfing) • fun 🙂
a
spent too much time trying to make takeWhile work with purely functional code. then decided to save the list of tree heights in the path and use strictly 
<
height followed by a if-not-last-index, add 1 (edge vs non-edge). I also went with a Sequence of Ranges for the lines of sight, but did not map them to tree heights. reversing the order the left & top trees for part 2 was just adding a 
.reversed()
. maybe will put it in "utils" for future puzzles. https://github.com/aneroid/advent-of-code-2022-kotlin/blob/main/src/Day08.kt
x
Im think i'm going to spend the whole day optimising my solution 😅
e
https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day8.kt not super happy with my solution but I've been trying out a few alternatives and nothing is really working better so I guess this is what I'll share
m
^ Intriguing! 🙂
s
https://github.com/simonbirt/advent-of-code-2022/blob/main/src/Day08.kt a lot of revisiting elements but at least it worked!
o
r
c
Today was very fun!
m
Today was a lesson in humility. The irony - yesterday I was handing out advice to read the instructions extra carefully. Should have listened to it 😉
c
Fun is clearly relative too ha. I created flows of stencils and processed everything in parallel. That’s pretty fun :)
m
Here’s my solution again. Golfed it down to 14 sloc, still reasonably readable IMHO. https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2022/day08.kt
c
The `.also { println}`is a cute trick
r
Can it be better than O(N*N)? I believe not, as grid needs to be iterated.
m
@chiroptical Yes, but the also(::println) is surely a golfing thing. Takes away from readability, but the official Kotlin formatting kept it in one line 😉 (EDIT: replaced with good old println calls, the also was quite unnecessary here).
d
A lot of stuff doesn't need to be iterated twice I think
If you work your way from the outside to the inside when iterating over the trees in the grid, I believe you can reuse earlier results in later calculations
m
^ Yes, in part 1 that is possible. You can also sort of ray-trace from the outside, exploring the trees from all four directions, then you’ll definitely skip many cells in the center. However, it’s probably not worth it, since the cost of the exploration is so small.
d
Yes I'm pretty sure it makes the code neigh unreadable and I didn't feel like exploring this avenue personally, but I'm sure there are others who enjoy these kinds of things so they can have at it 😄
r
I didn't explore in that direction tbvh, i just wanted to get done with it and get 2 stars.
p
A little late to post, but I was happy with how this turned out
f
@Michael Böiers @Davio I also had some thoughts on ray-tracing, but you would also have to implement some sort of "already" found 
x,y
and keep track of them to avoid counting them twice I guess.
t
I went around and around on this a few time and finally settled on an approach that probably isn’t as efficient as it could be otherwise, but I think it clearer (to me). For each spot, I take all four vectors comprising the view from that spot, and then test them against what the puzzle calls for in each part. I also ended up writing some fun extension functions - 
Iterable<Int>.product()
and 
Iterable<T>.takeUntil()
• Blog • Code
f
missed 
takeUntil
as well ended up with this:
Copy code
private fun List<Pos>.scenicScore(intGrid: IntGrid, value: Int): Int {
        val idx = indexOfFirst { intGrid[it] >= value } + 1
        return if (idx == 0) size else idx
    }
t
Man, this is the second puzzle where my brain has dodged the fact that 
indexOfFirst
exists. Doh!
p
Shush its getting more and more hardcore. Solving is one part but then having readable non deduplicated code is the other thing ^^ https://github.com/PaulWoitaschek/AdventOfCode/blob/main/src/main/kotlin/de/woitaschek/aoc/year2022/Day8.kt
p
@todd.ginsberg 
Iterable<Int>.product()
can also be written as 
reduce(Int::times)
😉
t
@phldavies Yeah, true! Kinda surprised product wasn’t already there, but I guess that’s not nearly as common as summing.
k
It is very hard to win against the fastest algorithm of part1. Initially, my way of solving the task was the same as Elizarov's, but I decided to optimize it a little. I keep the index of the highest tree and truncate the for reversed loop path to it or to the encounter at height 9. This optimization is only useful for larger grids. It can be a bit trickier in the picture as there are unnecessary checks.
Copy code
fun part1(a: Array<IntArray>): Int {
    val n = a.size
    val m = a[0].size
    val b = Array(n) { BooleanArray(m) }
    var hIndex: Int
    var h1: Int
    var h2: Int
    for (i in 0 until n) {
        hIndex = 0
        h1 = -1
        for (j in 0 until m) {
            if (a[i][j] > h1) {
                h1 = a[i][j]
                hIndex = j
                b[i][j] = true
            } else if (h1 == 9) break
        }
        h2 = -1
        for (j in m - 1 downTo hIndex) {
            if (a[i][j] > h2) {
                if (h1 == h2) break
                h2 = a[i][j]
                b[i][j] = true
            }
        }
    }
    for (j in 0 until m) {
        hIndex = 0
        h1 = -1
        for (i in 0 until n) {
            if (a[i][j] > h1) {
                h1 = a[i][j]
                hIndex = i
                b[i][j] = true
            } else if (h1 == 9) break
        }
        h2 = -1
        for (i in n - 1 downTo hIndex) {
            if (a[i][j] > h2) {
                if (h1 == h2) break
                h2 = a[i][j]
                b[i][j] = true
            }
        }
    }
    var count = 2 * m + 2 * n - 4
    for (i in 1 until n - 1)
        for (j in 1 until m - 1)
            if (b[i][j]) count++
    return count
}
k
For part 1, if you have a row of trees that looks like this: 1 3 3 3 5 5 5 2 Isn't the total #trees from the left side = 2? You'd see the first 3 and 5 You the 3 height trees repeat so they hide each other. All the solutions posted just compare w/ the initial height so you'd get 6 if you do that but that doesn't make sense for line of sight...
p
[1] [3] 3 3 [5] 5 5 2
are the seen trees, I believe
For part 1 you’re looking at the forest from a height of 
0
so can always see the first tree
k
yep..I always count the edge trees
edge trees count is
Copy code
2L * rowSize + 2 * colSize - 4
p
[1] [3] 3 3 [5] 5 [5] [2]
would be all seen in that row (both from left and right)
v
My solution.happy that i got my first puzzle answer correct in my first run
k
Since the task is not very big data, it can be solved with complexity O(n^2). But Elizarov's solution is the fastest and it has complexity O(n)
g
I solved puzzles in the morning but I wasn't satisfied with the code. So, after the day I did hard refactoring and this is my solution for now
Solution Day 8.cpp
p
Another attempt, wanting to use the input string directly
g
@Karloti sorry but his solution is definitely O(n^3) check lines 44..47. I'm not sure it can be anyway better. Even just matrix creation is already O(n^2)
x
aite im done making this anymore nicer 😅
y
my day 8 solution: https://github.com/ylegall/AOC-Kotlin/blob/master/src/main/kotlin/aoc2022/Day8.kt it was a struggle to make the code feel "clean"
36 Views
Open in Slack
PreviousNext
Powered by