https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 2> (spoilers) :thread:
# advent-of-code
a
j
My initial solution is so obnoxious it thinks Gary Oldman in Slow Horses is an upper class gentleman, but overall
Copy code
line.windowed(2).all { (a, b) -> (b - a) * sign in (1..3) }
does the trick
a
for part 2: and here I thought simply ignoring one error would be enough ❌
👍 2
👍🏼 1
same 2
m
Part 1
Part 2
I totally missed the "difference between 1 and 3 rule" and got a wrong answer, by only considering if it's sorted.
k
there is a 
is(Strict)Ascending
and descencing btw
avoids the need for actually sorting 🙂
j
For part2 was there any fancy trick to omit a single Element from a list, or do you have to do something like this:
Copy code
fun List<Long>.omit(index: Int): List<Long> = subList(0, index) + subList(index + 1, size)
k
wait, those are my util functions? NVM
😂 3
m
> there is a 
is(Strict)Ascending
and descencing btw In the stdlib? No there isn't
Oh yeah, your util makes more sense. 😄
j
This is my solution it not fancy or anything, but it works
k
Apparently I created my 
isStrictAscending
a few days before AOC 2020. Thank you past me!
😄 3
Unused before today. wow.
I'm happy it didn't contain a bug cause I have 0 tests in my util library
j
without boring loading and parsing:
Copy code
fun part1(input: List<List<Long>>) = input.count(List<Long>::isSafe)

fun part2(input: List<List<Long>>) = input.count { line ->
    line.indices.asSequence()
        .map { bad -> line.filterIndexed { index, _ -> index != bad } }
        .any(List<Long>::isSafe)
}

fun List<Long>.isSafe(): Boolean = windowed(2).all { (a, b) -> (b - a) in (1..3) } ||
        windowed(2).all { (a, b) -> (a - b) in (1..3) }
👍 1
j
Untitled.cpp
Untitled.cpp
b
dang, I used subtraction in part 2 which didn't work because of duplicates
j
@Jonathan Kolberg for me the fancy trick was to switch to mutable land and use removeAt
👍 1
same 3
n
As did I. 🤬
b
image.png
v
image.png
e
as a side effect I've came up with this utility method which can generate all the sublists from an original list with excluding N adjacent items (not production ready if you know what I mean):
Copy code
fun <T> List<T>.allSubListsWithAdjacentRemoved(size: Int = 1): List<List<T>> =
    this.indices
        .reversed()
        .windowed(size)
        .map { ix ->
            this.toMutableList()
                .apply {
                    ix.forEach { i ->
                        this@apply.removeAt(i)
                    }
                }
        }
there must be a more idiomatic Kotlin way of doing this
v
Something like this?
Copy code
fun <T> List<T>.omit(index: Int): List<T> = take(index) + drop(index + 1)

fun generateCandidates(report: List<Int>): List<List<Int>> = listOf(report) + report.indices.map(report::omit)
Edit: Actually, using 
subList
is more efficient because it just returns a view of the existing list 
fun <T> List<T>.omit(index: Int): List<T> = subList(0, index) + subList(index + 1, size)
j
Ok, since I hate unnecessary lists allocation and modifications and go for sequences whenever possible, this time I ended up with implementing my own iterable skipping an index:
Copy code
fun part2(input: List<List<Long>>) = input.count { line ->
    line.indices.asSequence()
        .map(line::skippingOne)
        .any(Iterable<Long>::isSafe)
}

fun List<Long>.skippingOne(indexToSkip: Int): Iterable<Long> = Iterable<Long> {
    object : Iterator<Long> {
        var i = if (indexToSkip == 0) 1 else 0
        override fun next(): Long = this@skippingOne[i++].also { if (i == indexToSkip) i++ }
        override fun hasNext(): Boolean = i < this@skippingOne.size
    }
}

fun Iterable<Long>.isSafe(): Boolean = zipWithNext().all { (a, b) -> (b - a) in (1..3) } ||
        zipWithNext().all { (a, b) -> (a - b) in (1..3) }
👍 1
p
I've had trapped myself by prematurely optimising part 2 by only testing two lists, by omiting just the elements of the first errorneous pair. It took me half hour to also test the list without first element also 😄
d
You can implement it like:
Copy code
fun <T> List<T>.omit(index: Int): List<T> = filterIndexed { i, _ -> i != index }
Extracting that helped simplify part 2
r
Screenshot 2024-12-02 at 12.25.25 PM.png
p
p
Copy code
fun List<Int>.withoutElementAt(listIndex: Int): List<Int> {
        return this.let { it.toMutableList().also { it.removeAt(listIndex) }.toList() }
    }

    fun List<Int>.isMatching() = this.windowed(2).all {
        it[1] - it[0] in (1..3)
    }

    fun part1(input: List<String>): Int {
        return input.count { line ->
            val report = line.split(" ").map { it.toInt() }
            val strictlyIncreasing = report.isMatching()
            val strictlyDecreasing = report.reversed().isMatching()
            strictlyIncreasing || strictlyDecreasing
        }
    }


    fun part2(input: List<String>): Int {
        return input.count { line ->
            val report = line.split(" ").map { it.toInt() }
            val strictlyIncreasingFaultTolerant = List(report.size) { listIndex ->
                report.withoutElementAt(listIndex).isMatching()
            }.any { it }
            val strictlyDecreasingFaultTolerant = List(report.size) { listIndex ->
              report.withoutElementAt(listIndex).reversed().isMatching()
            }.any { it }
            strictlyIncreasingFaultTolerant || strictlyDecreasingFaultTolerant
        }
    }
n
Same as everybody else, though I note most everyone is using .windowed(2) rather than .zipWithNext(). Had a little FOMO so I switched to windowed and the program took twice as long (cold start, but run a couple times).
p
Managed to squeeze in Day 2 before the school run 🙂 Not sure how much longer that'll last...
Day02.kt
I used 
zipWithNext
with a transform to avoid creating a list of Pair when all I needed was the deltas.
p
Managed to squeeze in Day 2 before the school run
Same! At 6:40 my school lunch-prep service finished so I had until 7:00 when the teeth-brush service was supposed to start 😛
a
I went with a more imperative approach to avoid re-iterating each list "too often" but 1. the lists are quite small 2. re-checking the list safety after dropping an element requires iterating over it again anyway ◦ or re-checking from at least one element before the current pair if the lists were 100+ items and allowed up to 3 errors, then maybe the individual steps would have been worth it
j
I think I have a winner. Only stdlib used, no list creation, everything short-circuiting as soon as possible
Day02.kt
👍 2
m
also decided to use a custom builder pattern from now on so that I can actually destructure my input on the fly. Also not needing a 'return' in the solutions for each part also helps in quickly 'scripting' my way through. I tried to do a folding algorithm so that part2 is O(n) instead of O(n²) but in the end decided not to... yet... lol
Michael Day 2.cpp
c
Also used the 
filterIndexed
trick for building my sublists:
Copy code
val subLists = mutableListOf<List<Int>>()
        for (i in this.indices) {
            subLists.add(this.filterIndexed { j, _ -> j != i })
        }
Also fell for the trap of part 2 where I coded it to allow 1 "mistake" but that's not what was being asked.
t
Initially had an answer that was "too low" for part 2 where I didn't have 
()
after the 
?:
to group that 
&&
conditional.
@Jakub Gwóźdź or @Michael de Kaste how do you share your code in this thread? Is that file upload? Or are you specifying code-blocks somehow?
p
Snippets
🙏 1
v
This solution avoids unnecessary collection copying with the help of Kotlin sequences. https://github.com/vkopichenko/Contests/blob/main/adventofcode/src/2024/y24day2.kt:
Copy code
import kotlin.math.abs
import kotlin.math.sign

fun main() {
    val reports = generateSequence {
        readlnOrNull()?.split(' ')?.map(String::toInt)
    }.toList()

    fun Sequence<Int>.isSafe(): Boolean =
        windowed(2) { (a, b) -> a - b }.run {
            val firstSign = first().sign
            all { diff ->
                diff.sign == firstSign && abs(diff) in 1..3
            }
        }

    // Day 1
    reports.count { it.asSequence().isSafe() }.also(::println)

    // Day 2
    fun <T> List<T>.subsequences() = sequence {
        repeat(size) { iToSkip ->
            yield(asSequence().filterIndexed { i, _ -> i != iToSkip })
        }
    }
    reports.count { levels ->
        levels.run { asSequence().isSafe() || subsequences().any { it.isSafe() } }
    }.also(::println)
}
p
you can also type 
/snippet
to start a text snippet
❤️ 1
k
Copy code
fun main() {
    val report = mutableListOf<List<Int>>()

    fun load(fileName: String) {
        report.clear()
        readInput(fileName).map { line -> report.add(line.split(Regex("\\s+")).map(String::toInt)) }
    }

    fun List<Int>.checkSafe(): Int = zipWithNext { a, b ->
        when (b - a) {
            in 1..3 -> 1
            in -3..-1 -> -1
            else -> 0
        }
    }.run { if (sum().absoluteValue == size) 1 else 0 }

    fun part1(): Int = report.sumOf { levels: List<Int> -> levels.checkSafe() }

    fun part2(): Int = report.sumOf { levels: List<Int> ->
        levels.indices.asSequence().map { i ->
            levels.toMutableList().run {
                removeAt(i)
                checkSafe()
            }
        }.firstOrNull { it == 1 } ?: 0
    }

    load("Day02_test")
    check(part1() == 2) { "incorrect result part1" }
    check(part2() == 4) { "incorrect result part2" }

    load("Day02")
    part1().println()
    part2().println()
}
Advent_of_Code_2024
image.png
y
I solved without removing elements and re-counting. Just skip invalid elements in the loop
K 1
j
BTW folks. Anyone managed to do the part2 in less than O(N^2)? Of course for max 8 elements per line it does not really matter, but still I wonder how such solutions could look like? E.g. some smart traversal counting increments and decrements...
haha. I just asked about that @y9san9
😁 1
can you post copy-able code?
y
j
Just to try I did something like this. It should be fast, but the State enum is 13 different states and the total solution is > 150 lines of code.
Copy code
input.intLists().count { line ->
  line.asSequence().windowed(3).runningFold(State.First) { acc, window ->
     acc.nextState(window[0], window[1], window[2])
  }.none { it == State.Invalid }
}
The nice thing about having a state machine is that you can add some color depending on the new state (blue is decrease, magenta is increase, red is fail, bright color is perfect, darker color is with single bad level)
very nice 1
😍 1
j
is there a 
.fold(...) {..}
version that can short-circuit on some condition? I mean, I can always do 
return....
but it seems somewhat unelegant.
p
@Jakub Gwóźdź with stdlib probably just using 
asSequence().runningFold {}.takeWhile {}.last()
think smart 1
k
Copy code
import kotlin.math.absoluteValue
import kotlin.time.measureTime

fun main() {
    val report = mutableListOf<List<Int>>()

    fun load(fileName: String) {
        report.clear()
        readInput(fileName).map { line -> report.add(line.split(Regex("\\s+")).map(String::toInt)) }
    }

    fun direction(b: Int, a: Int) = when (b - a) {
        in 1..3 -> 1
        in -3..-1 -> -1
        else -> 0
    }

    fun Iterable<Int>.checkSafe(): Int = zipWithNext { a, b -> direction(b, a) }
        .run { if (sum().absoluteValue == size) 1 else 0 }

    fun Iterable<Int>.checkSafe2(): Int {
        var lastElement: Int? = null
        var lastDirection: Int? = null
        var countCorrection = 0
        return zipWithNext { a, b ->
            val result = when {
                direction(b, a) == lastDirection -> 1
                lastElement == null -> 0
                direction(b, lastElement!!) == lastDirection -> run {
                    countCorrection++
                    if (countCorrection == 1) 1 else 0
                }

                else -> 0
            }
            lastElement = a
            lastDirection = lastDirection ?: direction(b, a).takeIf { it != 0 }
            result
        }.run { if (sum().absoluteValue == size - 1) 1 else 0 }
    }

    fun part1(): Int = report.sumOf { levels: List<Int> -> levels.checkSafe() }

    fun part2(): Int = report.sumOf { levels: List<Int> ->
        levels.indices.asSequence().map { i ->
            levels.toMutableList().run {
                removeAt(i)
                checkSafe()
            }
        }.firstOrNull { it == 1 } ?: 0
    }

    fun part2New(): Int = report.sumOf { levels: List<Int> -> levels.checkSafe2() }

    load("Day02_test")
    check(part1() == 2) { "incorrect result part1" }
    check(part2() == part2New()) { "incorrect result part2New" }

    load("Day02")
    part1().println()
    part2().println()
    part2New().println()

    measureTime {
        repeat(100_000) { part2New() }
    }.let(::println)
    measureTime {
        repeat(100_000) { part2() }
    }.let(::println)
}
Fastest O(n) - Part 2 solution
image.png
d
My solution for part 2 checks each list at most 6 times (forward/reverse and then removing up to 2 elements in each direction)
k
The program code I shared above measures the speed of both solutions. The quadratic solution takes about 30 seconds and the linear solution takes 5 seconds. Of course I intentionally repeat each solution 100,000 times.InIn the event that the report was larger, it would not have been necessary. This is to see the huge difference.NoI haven't encountered any competitive programming problems so far that require a quadratic solution.
Linear O(n) solution for part2 ------------------------------------ fun IterableInt.checkSafe2() .... https://github.com/karloti/Advent_of_Code_2024/blob/main/src%2FDay02.kt
n
@Karloti Your part2New function gives the wrong answer on my input, while your part2 function gives the right answer. I'm guessing there's a corner case somewhere. All of these are false negatives: [1, 3, 4, 7, 10, 13, 16, 20]: false [13, 11, 8, 5, 1]: false [18, 18, 19, 20, 21, 22]: false [2, 6, 9, 10, 11, 12]: false [22, 22, 25, 26, 28]: false [28, 23, 20, 18, 15, 12, 10, 8]: false [31, 29, 26, 25, 26]: false [37, 39, 36, 35, 32, 29, 28]: false [44, 47, 50, 51, 53, 54, 53]: false [47, 49, 52, 53, 55, 57, 60, 65]: false [48, 44, 43, 40, 38, 37, 36, 34]: false [53, 59, 61, 64, 67, 70]: false [54, 54, 51, 49, 46, 44, 42, 40]: false [56, 60, 61, 62, 65, 68]: false [62, 59, 63, 65, 68, 69, 72]: false [63, 60, 59, 61, 57]: false [71, 68, 71, 73, 74, 75]: false [72, 69, 68, 67, 66, 62]: false [73, 76, 79, 81, 85]: false [77, 74, 72, 69, 67, 66, 65, 58]: false [82, 84, 85, 86, 87, 89, 91, 97]: false [89, 85, 84, 81, 79, 77, 74, 72]: false [96, 94, 93, 92, 91, 90, 87, 90]: false [97, 90, 88, 86, 84, 81, 78, 77]: false [98, 97, 96, 94, 91, 88, 83]: false
d
First/last element removal it looks like
n
My inelegant O(n) solution is ~7s on my old machine when repeated 100_000 times, vs. ~10s for @Karloti's, and ~63s for my old quadratic solution. I sort of did the logic by trial and error and would not be surprised if there were unaccounted for edge cases not present in my input. https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2024/d2/Y2024D2.kt
🙌 1
j
Single pass solutions tend to fail when error is between first two elements. I guess the best way to fix it is to do like @y9san9 did: if there's more than one error in normal pass, test reverse. My approach:
Copy code
fun List<Long>.maxOneError() = asSequence().maxOneErrorOneWay() || reversed().asSequence().maxOneErrorOneWay()

data class Acc(val prev: Long = 0, val sign: Int = 0, val errors: Int = 0)

fun Sequence<Long>.maxOneErrorOneWay() = drop(1).runningFold(Acc(first())) { acc, curr ->
    val delta = curr - acc.prev
    if (delta == 0L || abs(delta) > 3 || delta.sign == -acc.sign) acc.copy(errors = acc.errors + 1)
    else acc.copy(prev = curr, sign = delta.sign)
}.none { it.errors >= 2 }
(very helpful method this runningFold(), to bad it's only usable during AoC xd)
y
@Jakub Gwóźdź it's better to go with asReversed() since it will not create a copy of all the data
j
absolutely! (we need only reverse iterator after all)
j
Did some timing and brought it down to 1.4 seconds for 100_000 iterations; my machine takes 4.6 seconds for the solution @Neil Banman gave. https://github.com/JBeet/MyAdventOfCode2024/blob/main/src/Day02WithStateEnum.kt
🙌 1
m
Went back and made a walking algorithm that should, theoretically, work for all errorCounts
Day2_2.cpp
j
would it work for [1,1,2,3,4,4] allowing 2 errors?
m
I just checked, it says its valid
j
hmmm, great. how about [2,1,2,3,4,3]? 🙂
my approach (similar after all, with two passes, back and forth) would fail with "errorCount 2"
m
Would fail checking the logic 🤔
e
I chose to use 
IntArray
before the discussion about how arrays are an ugly compatibility wart on the language in the stream blob stuck out tongue doing a slightly sneaky trick for part 2: reusing the same array, just mutating one element at a time (moving the missing element hole down the line)
👌 1
s
thanks for sharing that solution @Michael de Kaste, it works great! I refactored it into a massively over-engineered version that’s a little easier for my brain to grok 😆 sharing here in case it helps someone else: Day02.kt
62 Views
Open in Slack
PreviousNext
Powered by