https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 7> (spoilers) :thread:
# advent-of-code
a
m
Part 2
Not a very optimal solution, but short.
j
My solution: https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day07.kt I was a bit suppriesed that brute force was working today
m
There is some optimization I would like to add later, for now, I'm fine with this working. Made it recursive
Day7_Kotlin.cpp
j
Just thought about the optimization, that there are no negative numbers, so you can early exit branches if your temporary result is bigger than the wished result.
➕ 3
b
dang i completely misinterpreted the extra rule in p2 and tried to solve the harder problem of joining adjacent numbers before doing the math operators
m
@bj0 I had the exact same problem. I looked at the example: "7290: 6 8 6 15" and SOMEHOW concluded with my early groggy morning brain that 72 = 6 * 8 because 90 = 6 * 15
I was like: Yup seems right, || has lower precedence 😂
b
i was testing "7290: 6 ? 86 ? 15", but iterating over 
zipWithNext
in the end mine looks very similar to @Marcin Wisniowski but probably about 30 minutes behind them 🙂
image.png
o
Copy code
import java.io.File

fun main() {
    val input = File("/Users/oogbe/IdeaProjects/AdventOfCodeSolutions/solutions/src/2024/input.txt").readText()
    val lines = input.split("\n")
    lines.mapNotNull {
        val (expectedResult, testValues) = it.split(": ")
        val values = testValues.split(" ").map { it.toInt() }
        if(test(expectedResult.toLong(), values, 0, 0L)) expectedResult.toLong() else null
    }.sum().also { println(it) }
}

fun test(expectedResult: Long, testValues: List<Int>, currentIndex: Int, currentResult: Long): Boolean {
    val ans1 = currentResult * testValues[currentIndex]
    val ans2 = currentResult + testValues[currentIndex]
    val ans3 = (currentResult.toString() + testValues[currentIndex]).toLong()
    if (currentIndex == testValues.lastIndex)
        return ans1 == expectedResult || ans2 == expectedResult || ans3 == expectedResult
    return test(expectedResult, testValues, currentIndex + 1, ans1) || test(
        expectedResult,
        testValues,
        currentIndex + 1,
        ans2
    ) || test(
        expectedResult,
        testValues,
        currentIndex + 1,
        ans3
    )
}
s
Here's mine, tried to make it shorter
🙌 1
r
e
Copy code
fun main() {
    solve("Bridge Repair") {
        val eqsWithSolutions = mutableSetOf<String>()
        fun calculate(vararg ops: String, skip: Set<String>? = null) =
            (skip?.let { lines.minus(it) } ?: lines)
                .sumOf { l ->
                    l.longs().let { numbers ->
                        ops.toSet()
                            .combinations(numbers.size - 2)
                            .firstOrNull { c ->
                                numbers.drop(2)
                                    .zip(c)
                                    .fold(numbers[1]) { acc, (n, op) ->
                                        when (op) {
                                            "+" -> acc + n
                                            "*" -> acc * n
                                            "|" -> "$acc$n".toLong()
                                            else -> error("invalid operand")
                                        }
                                    } == numbers[0]
                            }
                            ?.let { numbers[0] }
                            ?.also { eqsWithSolutions.add(l) }
                            ?: 0
                    }
                }


        part1() { calculate("+", "*") }
        part2() { calculate("+", "*", "|", skip = eqsWithSolutions) }
    }
}
e
Day7.kt manual stack instead of recursion, and it goes fast in reverse. I might want to refactor the duplication out later though factored
👍 1
p
I have a reverse solution using substraction, division and removeSuffix, it goes ~50ms on part 2 https://github.com/glubo/adventofcode/blob/main/src/main/kotlin/cz/glubo/adventofcode/y2024/day7/day7.kt
🙌 2
@ephemient looks like we had similar idea 😄
p
I just reached for recursion. Happy enough with that :)
Day07.kt
p
Unbenannt.kt
Unbenannt.kt
n
Wow easy, especially compared to yesterday. First ideas worked, got the right answer for both on the first try. Second answer pretty slow at 240ms. Standard recursive DFS.
I bet the Reddit sub is littered with Pythonistas showing off their eval() solutions.
bog::std
Untitled
m
Simple refactored solution, done while my daughter was watching two cartoon episodes 🙃 https://github.com/MikeEnRegalia/advent-of-code/blob/be943f22823ec36cd85f5e102f94a36ef81df070/src/main/kotlin/aoc2024/day07.kt
c
That was suspiciously straightforward. First instinct when reading it was to reach for recursion but was expecting the puzzle input to have something to say about that, but no, that looked fine. Then Part 2 came along and may as well have not been there for any difference it made to my solution.
p
https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day7.kt I changed from a more straightforward approach (cutting lists) to a more efficient structure, passing through the indices and current sum. That brought it down to 150ms
👍 1
d
Late to the party — used a for-loop with bit indexes to enumerate all possible cases in part 1, had to switch to recursive search in part 2
Original check funtion
The recursive one is better obv. because it properly bails out of unproductive parts of the search tree
j
6ms cold start. no recursion, no list copying, just short stack od pairs. That wasn't my first solution though. I started with brute force of all possibilities, but it took over 2 seconds, so it was bad approach by definition 🙂 Then I recollected this trick with counting from back, it was on some previous AoC editions already.
Untitled.kt
🙌 3
after 5 second warmup:
Copy code
5702958180383
took 949.625us
92612386119138
took 1.428042ms
j
I used Kotlin Notebook, and was quite happy with it. Easy to check all intermediate steps. Autocompleting identifiers you wrote earlier is not always as easy as you would expect because of scoping with cell names, but mostly it works well. https://github.com/JBeet/MyAdventOfCode2024/blob/main/src/Day07.ipynb
t
That was fun. Part 1 and Part 2 share all the same code except for adding a new higher-order function to do concatenation. I used recursion because it made sense to me, I guess I could have got this down faster if I'd just used loops or a stack or something, but I'm happy with this. Fun puzzle today! • Code • Blog
🙌 1
f
My solution is almost identical to yours Todd, but also experiemented a bit to see if my 
concat
could be sped up a bit by calculating it instead of converting to string and back to long. Seems it can (by using guava), but not by very much:
Copy code
private fun concat(l1: Long, l2: Long): Long {
        val lengthOfL2 = floor(log10(l2.toDouble())).toInt() + 1
        val multiplier = 10.0.pow(lengthOfL2).toLong()
        return l1 * multiplier + l2
    }
907ms
Copy code
private fun concat(l1: Long, l2: Long): Long {
        val lengthOfL2 = l2.toString().length
        val multiplier = 10.0.pow(lengthOfL2).toLong()
        return l1 * multiplier + l2
    }
837ms
Copy code
private fun concat(l1: Long, l2: Long): Long {
        return "$l1$l2".toLong()
    }
805ms 
log10
and 
pow
from guava (to avoid converting between long and double)
Copy code
private fun concat(l1: Long, l2: Long): Long {
        val lengthOfL2 = log10(l2, RoundingMode.FLOOR) + 1
        val multiplier = pow(10, lengthOfL2)
        return l1 * multiplier + l2
    }
673ms Added later for reference (see comments below)
Copy code
private fun concat(l1: Long, l2: Long): Long {
        var t = l1
        var l = l2
        while (l > 0) {
            t *= 10
            l /= 10
        }
        return t + l2
    }
772ms
@Jakub Gwóźdź: mind blown I actually initially thought of something along those lines when reading the input. What if I just took out all the 
/3
, 
/2
etc - that would reduce the number of remaining tests dramatically. But then I just implemented the brute force variant, not seeing how to convert my thoughts into code. Thank you for actually showing how!
🙇 1
j
@Fredrik Rødland In my brute force solution I was also curious how to do concat without translating through string. I ended up with
Copy code
private fun Long.concat(other: Long): Long {
    var t = this
    var l = other
    while (l > 0) {
        t *= 10
        l /= 10
    }
    return t + other
}
but it was on par with toString/toLong. Which only shows how well optimized these methods are 🙂
f
cool - just saw the stream - and @Olaf Gottschalk actually goes through the same concat-performance tests at the end and concludes with more-or-less the same variant as your version. On my machine the guava-version is still a bit quicker though - they might do some magic
👍 2
t
@Fredrik Rødland - I'm glad you tested that! I pushed my code and then took my dog on a walk and the whole way was thinking "I bet I could make that a bit faster with math instead of conversions". I like all the different attempts! 🙂
j
Fun fact about Rust: I translated my solution from Kotlin and instantly after launch Rust got the same benchmark times as JVM got after 5seconds warmup. (depending on profile - in "dev" it was actually several times slower than JVM)
p
Got it down to ~360us for part2
Copy code
year 2024 day 7 Default warmup (8 iterations) took 4.536497751s
year 2024 day 7 Inline warmup (126 iterations) took 8.797861427s
year 2024 day 7 Retrograde warmup (1514 iterations) took 813.961093ms
finished warmup after 14.156842791s
year 2024 day 7 part 1
	 Retrograde took 278.363us 👑: 3245122495150
	 Inline took 3.635531ms (13.06x): 3245122495150
	 Default took 11.622636ms (41.75x): 3245122495150
year 2024 day 7 part 2
	 Retrograde took 357.441us 👑: 105517128211543
	 Inline took 69.571818ms (194.64x): 105517128211543
	 Default took 484.402215ms (1355.19x): 105517128211543
Day07Retrograde.kt
🙌 1
👍 1
n
My first thought was "360ms isn't impressive at all." Then I looked again. 🤪
🤣 2
d
Key to high performance is to go in reverse?
👌 2
blob thinking upside down 1
n
If you go in reverse you can prevent combinatorial explosion because you only need to divide when the number is evenly divisible and you only need to shift right when the current number ends with the next number.
e
for most inputs anyhow. I think the worst case is still exponential
Copy code
11111: 1 1 1 1
yes black 1
j
Best I can do in 
1111: 1 1 1 1
case is reducing from O(3^n) to O(2^n), but still - that's heavy
n
I've got enough problems without going out to look for more! 😂
1️⃣ 1
27 Views
Open in Slack
PreviousNext
Powered by