https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 11> :thread:
# advent-of-code
a
x
That was easy thanks to kotlin's lambdas
b
I hard coded a hell lot in today's puzzle. I basically typed all the Monkeys' items and logic by hand.
x
yeah parsing 7 monkeys wasn't that bad
m
Took me a while to think of the trick for part 2 but I was so happy when it worked!
h
Copy code
input.removeAll { it.isBlank() }
input.windowed(size = 6, step = 6)
helped a lot for me parsing the input
d
yay! I found the trick too - clever! (I also "cheated" and hand-coded the input.)
k
I'm not sure if I understand Part 2 correctly. Comparing to part1, is it merely remove the "divid by 3" logic and "repeat" 10k times? For the test-input, after 20 rounds, I get the expected result without "div by 3", however, after 1000 rounds, my solution gave different result... I'm confused.... ๐Ÿ˜ž
j
hm I'm stuck on part 2 if we do not divide by 3 that means just adjusting by the instruction. after 1 round I get the correct output but after 20 rounds it's not ok. Any help?
v
@Jonathan Kolberg @Kai Yuan Its because of Int/Long overflow I still did-not figured a trick to workaround this, but issue is with overflowing
e
In part 2 you have to find a trick how to reduce your worry level, otherwise you will be dealing with huge numbers more than Int or Long can handle. You have to apply some math and find a way how to reduce worry level but not to mess with test results
j
ah so even Long is not enought, hm I got real close for the example 2637590098 instead of 2713310158L with just using Longs, thats what throws me off
e
When you find a trick even Int will work, donโ€™t think about types of variables
b
Found the trick after I'd moved to Long (and was starting to move to BigInteger but that didn't even complete running ๐Ÿ˜› )
h
did anyone get the right answer with the example data but the wrong answer on the test data? ๐Ÿ˜ž
b
Yes
j
yes!
on part1
j
@Brian Hartvigsen was on BigInt to, have not found it yet
h
Not sure whats different in teh data causing the bug ๐Ÿ˜ž
b
@Hayden Meloche on part 1 or part 2?
h
part 1
j
Do you even need the trick while computing worry level?
b
I figured it out (with the math trick) but curious if anyone used code instead of math?
b
@babel anything you did with code would be using the same math principle TMK
The BigIntegers get too big to do math on in a reasonable amount of time, so yes, you need to do something to reduce your worry levels
@Hayden Meloche tried to go back in my history to see what it was, but I didn't commit around then and apparently intellij just stops remembering after a while ๐Ÿ˜›
j
haha I was just comming to post that
j
oh no, it's so dumb
b
I'm actually really interested to see how others solved it. Mine works, but I feel like it could be way better ๐Ÿ˜›
h
@Brian Hartvigsen haha thanks. I wonder if its something to do with a rounding error somewhere ๐Ÿค” maybe im using an int someone where I shouldnt be
n
It's an old trick but it checks out. My math background is my weak spot, but luckily this is one that has popped up in previous AoC challenges so it came to mind pretty quickly.
Parsing, OTOH, was a PITA.
b
Copy code
input.lines().chunked(7).forEach {
and then reading the necessary into a class I created made it work. ๐Ÿ™‚
j
no number theory has failed me
b
@Hayden Meloche so I learned to use Local History, but turns out i didn't have the issue of it working with the example but not test data for Part 1, just Part 2
h
all good! I got it figured it out. Onto part two. Thanks!
s
Spent so much time on this stupid overflow bug ๐Ÿ˜„ Use Longs!
j
for part1 ๐Ÿ™‚
j
oh man I hate number theory, and even if I got it right, I still had overflows with how I handled the operation sad panda
m
Copy code
object Day11 : Challenge() {
    class Monkey(
        val inspection: (Long) -> Long,
        val testNumber: Long,
        private val ifTrue: Int,
        private val ifFalse: Int
    ) {
        fun throwTarget(number: Long) = if (number % testNumber == 0L) ifTrue else ifFalse
    }

    val parsed = input.split(System.lineSeparator() + System.lineSeparator()).map {
        it.lines().drop(1).let { (a, b, c, d, e) ->
            Monkey(
                inspection = b.substringAfter("old ").split(" ")
                    .let { (type, value) -> (type == "+") to value.toLongOrNull() }
                    .let { (isAdd, long) -> if (isAdd) { x -> x + (long ?: x) } else { x -> x * (long ?: x) } },
                testNumber = c.substringAfter("by ").toLong(),
                ifTrue = d.substringAfter("monkey ").toInt(),
                ifFalse = e.substringAfter("monkey ").toInt()
            ) to a.substringAfter(": ").split(", ").map(String::toLong)
        }
    }.unzip()

    private val monkeys = parsed.first
    private val initialItems = parsed.second

    private fun solve(times: Int, worryMitigation: (Long) -> Long): Long {
        val inspections = LongArray(monkeys.size)
        val itemsToTrack = initialItems.map { it.toMutableList() }
        repeat(times) {
            for ((index, monkey) in monkeys.withIndex()) {
                inspections[index] = inspections[index] + itemsToTrack[index].size
                for (item in itemsToTrack[index]) {
                    val monkeyDoInspection = worryMitigation(monkey.inspection(item))
                    itemsToTrack[monkey.throwTarget(monkeyDoInspection)] += monkeyDoInspection
                }
                itemsToTrack[index].clear()
            }
        }
        return inspections.sortedDescending().let { (a, b) -> a * b }
    }

    override fun part1() = solve(20) { it / 3 }

    override fun part2() = solve(10_000) { it % monkeys.map(Monkey::testNumber).reduce(Long::times) }
}
not sure about a functional approach, but the parsing is already so bloated
n
I solved part 2 by using Long and using mod of all "worries" by the product of all the test divisors. This works for the example and the actual input (and runs in < 35ms), but does not work for part1 of my input (it does work for part1 of the example data).
j
At first I thought I had to implement redacted but then I realized that the input contains just redacted so simple redacted was enough ๐Ÿ˜‰
m
@nkiesel it probably has to do with the order in which you apply the 'worry mitigation tactic' because I had the same at first, but thats just because I returned the wrong value
n
Ahh! part1 does not work because I do "/ 3" and "% divProd". I can only use one.
m
yes
j
btw are some of the number theory functions in the std I could not find the ones needed for part2?
j
@Jonathan Kolberg yes, you should find everything you need in std (i.e. you don't really need any complicated extra functions for part 2)
j
@Evegenii Khokhlov do you not have a monkey with operation 
new = old * old
? unless I'm missing something this means Long is necessary. it would be pretty unfair if for some inputs it works with just Int and for others it doesn't.
j
@Jan Durovec hm maybe number theory lead me to want to do it to generic
b
@Jonathan Kolberg the "function" I used does not exist in std from what I can find, but is stupid easy to implement. I have it as part of my utils
j
@Jonathan Kolberg you're right but check the actual input
j
@Brian Hartvigsen yeah I remember implementing that in one of the first algebra classes
@Jan Durovec as if I know primes by looking at it ๐Ÿ˜€ at 6 something in the morning
j
@Johannes Gรคtjen That's my observation too. 
Long
is necessary and it doesn't work with just 
Int
(for the worry level; the inspection counters can be 
Int
)
n
@Jan Durovec I didn't even look at the test values. But I already had a redacted utility function so I just threw it in there and it did its thing.
d
BigInteger does not work (too slow), ring arithmetic does
Late start tonight
Havenโ€™t refactored yet, may not get to it tonight, but hereโ€™s what I have: https://github.com/dfings/advent-of-code/blob/main/src/2022/problem_11.main.kts
s
I had a hunch about the trick with modulo arithmetic, but I've banged my head for too long trying to figure out at which point to apply it during the calculations. Finally this is what worked: https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/Day11.kt
d
Applying ring arithmetic produces the right answer in part 1 for both test and real inputs, but maybe only because I mod each item once at the end of the round. May change this to be a fn that gets applied that either divides or mods though.
j
I kinda had hoped that today we expand the instruction set of Day10, but alas here my solution: https://github.com/bulldog98/advent-of-code-2022/blob/main/advent2022/src/main/kotlin/Day11.kt
x
The clue you'll need to find another way to keep your worry levels manageable.
is a very subtle clue.
j
c
Staring at the same code and failing to find the error for half an hour, only to discover it's an Integer overflow error, because you didn't use Long ๐Ÿ˜ญ
d
Also if you include 3 as a factor in your ring it should always work (I think)
e
@Johannes Gรคtjen yeah, my comment could be misleadingโ€ฆ And I apologize for everyone who got it wrong. 
Long
is necessary to perform computations. but actual worry level never overflow 
Int
. That was my point
r
I solved part2 - after few hit and trials with modulo ๐Ÿ˜„
e
https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day11.kt my runner's auto-splitting is kind of getting in the way again. maybe I should revisit that decision
I kinda want to implement 
lcm
but Eric fairly obviously only gave us prime divisors so there isn't really a needโ€ฆ
j
@ephemient did not check first, so I implemented it. Had to look up the algorithm on wikipedia again
k
x
@ephemient Would we need LCM if it was not all prime? ๐Ÿค”
k
Since I was too lazy to look up the LCM, I saw that the multiplication of divisors did not exceed the size of the long and used it as a modulus in the operations.
p
Took me far too long to realise the โ€œtrickโ€
j
@xxfast LCM would be needed if simple multiplication of all monkeysโ€™ divisors would not fit into 
long
, otherwise, nah.
r
today I realized (yet again) that I do not know enough math tricks mind blown
r
It keeps coming back to give a hard time (to me) in every aoc - Math tricks.
Is there any other approach for part2 - not taking sum of all divs and then 
%
it with 
worryLevel
k
In Bulgaria the weather is 20โฐC. I couldn't wait to finish the code so I could go out and walk around. How is it with you? It will probably get pretty cold soon, as it should.
d
Okay, I have not finished part 2 yet, but my feeling is there are cycles, items coming / going to the same monkeys over and over again, so when I have time (not sure when) I'll maybe go this route
In the example they give I have a cycle of items going from 0 to 3 to 1 to 0 to 3 to 1 etc.. even if the item starts at monkey 2, once it enters that cycle (after 1 round), it stays in the same cycle
I don't have any mathematical proof for if and how/why this works, but after I inspected the items going round and round I noticed that they were always following the same cycle. So maybe instead of continuously calculating the new worry level, I could just look at the cycle and pass it to the next monkey without calculating a new value
g
I was so happy today when my first idea was working in part2 ๐Ÿ™‚ I cleaned up the code from the morning and I'm sharing now. Quite nice puzzle. I'm impressed by author's imagination ๐Ÿ™‚ https://github.com/grzegorz-aniol/Kotlin-AoC-2022/blob/main/src/Day11.kt
p
j
@Davio you donโ€™t need any math proof, just an observation, that the tests is always about modulo. And 
3 mod 10
is the same as 
13 mod 10
, as 
23 mod 10
and 
123456789012345678903 mod 10
๐Ÿ™‚
d
Yeah I also noticed just now that the divisor tests of all the monkeys is all with prime numbers, wonder if that is going to help me
a
part 1: โ€ข initially, I didn't like the mini-calculator we needed to create in the middle of solving this. then I decided to map them to lambdas during initialisation. including that thing with 
old
being possibly repeated. and I didn't want to hardcode the rules (even if only 4 or 7)
Copy code
fun String.toOperation(): (Long) -> Long {
    ...
    return { old: Long -> operator(arg1 ?: old, arg2 ?: old) }
}
โ€ข also, it's only created once per monkey at 
inputParse
time rather than at every round or every item in the monkeys list โ€ข really wanted a 
monkey.see().monkeyDo()
in my code ๐Ÿ˜‚ but without global state, the closest I could come to it was:
Copy code
monkey.see().map { monkey.`do`(it) }
โ—ฆ which also makes me happy
part 2: โ€ข I realised the issue with the modulo factor but was trying to reduce only by the next monkey's "divider". โ€ข the trick isn't just the modulo but that it's associative so affects other monkeys too. โ€ข I spent too much time debugging off-by-one's in part2's test input before realising the factor was totally wrong https://github.com/aneroid/advent-of-code-2022-kotlin/blob/main/src/Day11.kt
j
Hi, I'm trying to refactor my code to make the modulus an "private static" (in Java terminology) member of 
Monkey
class so that it is updated as necessary when new 
Monkey
is instantiated. The documentation says that the Kotlin equivalent of static field is 
companion object
however, if I try to apply it to my class, I get an error saying that "Modifier 'companion' is not applicable inside 'local class'". I could move the 
Monkey
class out of 
fun main()
(and then the error disappears) but that would pollute the global package/namespace with my class. Is there some way how to declare "private static" field in a class that is local to a function (
main
in this case) in Kotlin?
a
@Jan Durovec a private class will only be accessible within the file its declared in
Copy code
// src/kotlin/main.kt

private class Monkey { 
  companion object { }
} 

fun main() { }
j
and can it be done for a local class declared inside 
fun main
?
AFAIK even the private class causes the issue (i.e. if I declare private class with the same name in multiple files I'll get a redeclaration error)
e
private top-level constructs by the same name in different files only cause a conflict on JVM, not the other platforms Kotlin supports (although JVM is definitely the most popular backend)
a
@ephemient Iโ€™m using Kotlin Native, and I see a compilation error if there are two classes with the same name in the same package *in different files
j
OK... but I'm not trying to solve top level constructs with the same name ๐Ÿ™‚ I'm after private static field of a local class so maybe the solution is different
e
d
Okay with the help of looking at @PoisonedYouthโ€™s solution and realizing that all the divisor tests were with prime numbers (which may not have mattered in the end), I finally understood that I could just take the LCM for all the divisor test numbers and keep the results small by %-ing with that number each time, luckily I already had an LCM function in my util from previous years ๐Ÿ™‚ But because they are prime numbers, the LCM is just everything multiplied anyway
r
This was a lot easier in python where there's no such thing as integer overflow... Love the puzzle. Also took me far too long to figure out the mod trick. Had to look up to confirm the fact that multiplication still works even in a mod space.
Day11.kts.cpp
j
@Jan Durovec This is only a guess because I can't find anything in the documentation, but perhaps companion objects are not allowed in local classes because the class gets recreated every time the enclosing function gets called. So if you change the value of some static variable it would be confusing because it gets reset on the next call.
@Jan Durovec I keep my code organized by doing something like this:
Copy code
object DayXX {
    fun part1(input: Lsit<String>): Int {
        // do stuff
        return result
    }
    // ... all the other functions and classes to solve it
}

fun main() {
    readInput("resources/dayXX")
    println(DayXX.part1(input))
}
p
No guarantee for optimization. Just have the time for straight forward ๐Ÿ˜ฌ
j
Iโ€™m new to AoC and this is the first day that had some kind of trick question, got really confused at first
Maybe mostly because my result was almost correct with longs
Only reason Iโ€™m aware of this mathematical property is from FizzBuzz
And even on part 1 I wondered why bother with the modulo throwing thing hehe
Parsing with โ€œkonbiniโ€ lib
Hmm I think I like this inline version better
c
Add me to the list who spent ages before realising Ints werenโ€™t big enough in part 1 ๐Ÿ˜ž
m
I must have been lucky with my input because I used ints and it worked (in part 1)
LCM is obviously more proper, but for speed I didn't bother implementing it until after I got the star, just multiplied all the divisors. Just needs to be a common multiple, doesn't need to be the smallest one.
c
Part 1 not working with Ints felt harsh, considering the sample did. Especially as Part 2 was all about dealing with the overflow from larger numbers.
h
my part one also worked with just ints ๐Ÿ˜…
m
This being a problem every year gave me an idea a while ago for a compiler plugin that would throw exceptions on integer overflows (automatically add checks for every int operation). I should get on that some time.
f
sad panda I nailed the mod-trick more or less right away, and part 1 also passed; so I was confident something was right, but failed to think of the Int to Long overflow and struggled way too long (pun intended) on it
c
The fact it worked for some people and not others suggests it wasnโ€™t an intentional trap. I only solved it because I just went โ€œlets change longs to ints in case its overflowโ€. Would have taken a lot of logs to work it out otherwise.
p
I got the wrong answer for part 2 example, switched the operation lambdas to use StrictMath to watch it blow up and confirm my suspicions
a
WHY is it not efficient to create the lambdas for the input? we're creating lambdas just one time at the start so then it's just execution right? is it not 'static'-ish?
d
@Marcin Wisniowski you can emulate it with a value class, here is a very rudimentary example (just to illustrate the point):
Copy code
@JvmInline
value class MyInt(private val i: Int) {
    operator fun times(other: MyInt): MyInt {
        if (i == 0 || other.i == 0) return MyInt(0)

        var result = 0
        repeat(other.i.absoluteValue) {
            if (this.i.sign != other.i.sign) {
                result -= this.i.absoluteValue
            } else if (this.i.sign == 1 && other.i.sign == 1) {
                result += this.i
            } else {
                result -= this.i
            }
            if (this.i.sign != other.i.sign && result.sign != -1) throw ArithmeticException()
            if (this.i.sign == 1 && other.i.sign == 1 && result.sign == -1) throw ArithmeticException()
            if (this.i.sign == -1 && other.i.sign == -1 && result.sign == -1) throw ArithmeticException()
        }
        return MyInt(result)
    }
}

fun main() {
    println(MyInt(5) * MyInt(7))
    println(MyInt(5) * MyInt(-7))
    println(MyInt(-7) * MyInt(5))
    println(MyInt(-5) * MyInt(-7))
    println(MyInt(Int.MAX_VALUE - 1) * MyInt(2))
}
This example uses repeated addition / subtraction to implement multiplication and watches for changes to the sign, if the sign changes other than what it expects (it expects pos * pos -> pos, neg * neg -> pos and the others to yield a negative answer) then it assumes the value has wrapped around and throws an exception. I'm using absolute values here, so Int.MIN_VALUE being its own absolute value probably screws this up, but I just wanted to make a fun demo. ๐Ÿ™‚
t
Another late start, and another busy morning getting in the way. I donโ€™t think I could have solved this puzzle without help a few years ago. Iโ€™m going to credit Advent of Code with helping me think my way though the more mathematical puzzles, something which I am weak at, but getting better. I wouldnโ€™t blame anybody for hand-coding the input values, parsing is a bit complicated. โ€ข Blog โ€ข Code
f
What the hell? I spent so much time debugging my output to the second puzzle failing for hours on the fact that the example output given by the website did not match my output for the example. But when I tried it on the actual data, it worked fine and I got the correct result... I don't want to read this whole thread. Did someone have the same problem?
n
@Filip Wiesner I don't think so... and the example result is correct.
l
yeah i think i only noticed 'the trick' in a few seconds 'cause of the old maths degree ๐Ÿ˜… also with parsing, i split the input on `"Monkey"`and pulled each value out with regex - turning the logic into a function got kind-of hard-coded, but it's as generic as it needs to be for the variation on the input. 10/10, another great puzzle ๐Ÿ˜„
p
@Filip Wiesner I would guess you didn't fall afoul of arithmetic overflow either in the monkey operations or the product of the highest counts.
f
Than I guess I got lucky ๐Ÿ˜„ Because when I use the same code that got me the correct answer for the example, I get a different result.
d
Yeah part 1 worked with Int for me
f
oh my god ๐Ÿคฆโ€โ™‚๏ธ I am so dumb... I used the LCD of the actual data on the test data. At least two hour wasted on this...
r
I am not very good at maths - but i do the understand the 
mod
part of it, in today's problem. I also saw few folks not using 
mod
. I wonder if some other maths trick is involved apart from this one.
l
interesting that this is the first time I've found myself missing the "everything is data" part of Clojure from last year's AoC... don't miss much else ๐Ÿ˜‚
o
Even shorter using chunked(6) or without the remove all chunked(7) ๐Ÿ˜‰
p
c
My solution isnโ€™t any different than anyoneโ€™s but my parser is fun: https://github.com/chiroptical/advent-of-code-2022/blob/main/src/main/kotlin/dayEleven/DayEleven.kt also, oops all folds
Also, what is the concept called to simplify part 2? I multiplied all the divisors but could you use the smallest number divisible by all the divisors instead? (Assuming those arenโ€™t equal)
n
@chiroptical You're probably thinking of least common multiple. But since all the numbers are prime that's the same as multiplying all the divisors together.
c
Ahh, I didnโ€™t realize they were all primes.
n
Neither did I, didn't stop to look. But that's incidental. You don't need the least common multiple for it to work. You just need a common multiple that is small enough to not overflow. Since all the numbers are small, you could multiply them all even if they weren't prime and that would still work.
c
Yeah, that makes sense. I was just thinking about making the number as small as possible.
e
if they product is too large, you could also keep n separate worry levels for each item, one for each monkey's modulus
but it's not so you don't need to
n
My last refactor was not strictly necessary:
Copy code
import kotlin.collections.fold as luv
...
val me = inspections.apply { sortDescending() }.take(2)
val u = 1L
return me.luv(u, Long::times)
a
Was scratching my head since yesterday on why my Part2 results are incorrect. Just realised that I have reused the monkeys from Part1. ๐Ÿคฆโ€โ™‚๏ธ
l
@Abdul Khaliq been there, done that. shared state between the two runs?
a
Yup! ๐Ÿ˜ญ
e
yep that's why my monkeys are immutable
p
I parsed the input into a separate monkeys list and items list
m
Immutable monkeys immutable monkeys immutable monkeys immonkeyable mutablesโ€ฆ too hard
m
Very late to the party, took me forever to figure out part 2. Of course in the end it seems trivial, but when I googled for divisibility shortcuts I was lead down a rabbit hole of irrelevant concepts ๐Ÿ˜‰
Copy code
package aoc2022

fun main() {
    data class Item(private val initial: Int, private val remainders: Map<Int, Int>) {
        fun rem(d: Int, useInitial: Boolean) = 0 == if (useInitial) (initial % d) else remainders.getValue(d)
        fun transform(op: (Int) -> Int) = Item(op(initial), remainders.toMutableMap().apply {
            keys.forEach { prime -> set(prime, op(getValue(prime)) % prime) }
        })
    }

    fun Int.toItem() = Item(this, buildMap {
        for (prime in listOf(2, 3, 5, 7, 9, 11, 13, 17, 19, 23)) set(prime, this@toItem % prime)
    })

    data class Monkey(val items: MutableList<Item>, val operation: (Item) -> Item, val test: Triple<Int, Int, Int>) {
        fun test(item: Item, useInitial: Boolean) = if (item.rem(test.first, useInitial)) test.second else test.third
    }

    val input = System.`in`.reader().readText()
    fun doMonkeyBusiness(rounds: Int, div: Boolean): Long {
        val monkeys = input.split("\n\n").map { it.split("\n") }.map { lines ->
            val items = lines[1].split(" ", ",").mapNotNull(String::toIntOrNull).map { it.toItem() }.toMutableList()
            val opChar = lines[2][lines[2].lastIndexOf(" ") - 1]
            val operand = lines[2].substringAfterLast(" ").toIntOrNull()
            val operation: (Item) -> Item = when {
                opChar == '+' -> { old -> old.transform { it + operand!! } }
                operand != null -> { old -> old.transform { it * operand } }
                else -> { old -> old.transform { it * it } }
            }

            val divBy = lines[3].split(" ").mapNotNull(String::toIntOrNull).single()
            val ifTrue = lines[4].split(" ").mapNotNull(String::toIntOrNull).single()
            val ifFalse = lines[5].split(" ").mapNotNull(String::toIntOrNull).single()
            Monkey(items, operation, Triple(divBy, ifTrue, ifFalse))
        }

        val inspections = LongArray(monkeys.size) { 0 }
        repeat(rounds) {
            for ((i, monkey) in monkeys.withIndex()) with(monkey) {
                inspections[i] = inspections[i] + items.size
                for (item in items) operation(item)
                    .let { newItem -> if (div) newItem.transform { it / 3 } else newItem }
                    .also { monkeys[test(it, div)].items += it }
                items.clear()
            }
        }
        return inspections.sortedDescending().take(2).reduce(Long::times)
    }
    listOf(doMonkeyBusiness(20, true), doMonkeyBusiness(10_000, false)).forEach(::println)
}
e
you'll need to find another way to keep your worry levels manageable
is the important hint in the text
or just compare the numbers you're getting to the example and see where you start diverging
23 Views
Open in Slack
PreviousNext
Powered by