https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 20> :thread:
# advent-of-code
a
m
Part 2. Not the cleanest, but it works!
j
I like the simulations we had to run this year, part 1 was pretty nice to simulate. I'm still thinking about weather simply simulating for part 2 is terminating early enough, also I'm a bit disappointed that there is no example that can be used for testing if the solution is correct, before trying on the real input
v
Part1&2: For me it was enough to just count cycles of the "ls" module.
Year2023Day20.kt.cpp
b
im guessing brute forcing p2 is a dead end?
✅ 1
j
@bj0 I gave up after 5min
b
this is giving me flashbacks of the old intcode problems, i could never figure out how to determine what to do for p2
v
@bj0 in the old one you had to determine an algorithm entirely 🙂
j
Hm I think I do something wrong, for me in each of the first 1000 simulation steps the input to "rx" is a conjunction module and always remembers low pulses
v
@Jonathan Kolberg definitely 1000 is not enough and you should check in the middle of the cycle, not just in the end of simulation
oh, and of cause you have to draw a couple of wires before rx first 🙂 (just to see how your graph looks like and which cycles you should check)
m
Mhhh, i've been near the answer for a long time... I got all the cycles, but somehow lcm isn't the correct answer. 😞
🤔 1
j
@Michael de Kaste have a look at chinese remainder theorem, might be you have to do a bit more
m
omg kill me, my cycles were 'x' instead of 'x - 2048' 🥹
I have been staring at my answer for the past hour 😂
j
My guess at the moment is that every "rx" module has an conjunction module as input
Have to say, did we have a part2 before where there was no example with result?
p
I’ve resolved part2 via Mermaid 😆 https://shorturl.at/dpzBV
k
Whew! That was quite interesting. All I needed was a little bit of inspection/debugging to put me into the right thinking mode for part 2: https://github.com/kingsleyadio/adventofcode/blob/main/src/com/kingsleyadio/adventofcode/y2023/Day20.kt EDIT: made solution a little bit more generic
w
Some helpful methods for these kind of problems:
Copy code
/**
 * Computes the greatest common divisor of two integers.
 */
tailrec fun greatestCommonDivisor(a: Long, b: Long): Long {
    if (b == 0L) {
        return a
    }
    return greatestCommonDivisor(b, a % b)
}

/**
 * Computes the least common multiple of two integers.
 */
fun leastCommonMultiple(a: Long, b: Long): Long {
    return if (a == 0L || b == 0L) 0L else {
        val gcd = greatestCommonDivisor(a, b)
        abs(a * b) / gcd
    }
}

/**
 * Takes a list of base/modulo combinations and returns the lowest number for which the states coincide such that:
 *
 * for all i: state(i) == base_state(i).
 *
 * E.g. chineseRemainder((3,4), (5,6), (2,5)) == 47
 */
fun chineseRemainder(values: List<Pair<Long, Long>>): Long {
    if (values.isEmpty()) {
        return 0L
    }
    var result = values[0].first
    var lcm = values[0].second
    for (i in 1 until values.size) {
        val (base, modulo) = values[i]
        val target = base % modulo
        while (result % modulo != target) {
            result += lcm
        }
        lcm = leastCommonMultiple(lcm, modulo)
    }
    return result
}
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day20.kt took quite a while to figure out what do to for part 2. when I translated the input into Graphviz dot language and charted it, that led me to the usable approach. had an off-by-one first though…
and my function has 
return null
in case any of the underlying assumptions are invalid
m
this is definitely a day im going to revisit later. Currently my code is based on a lot of assumptions (run once to see cycles, see that only 4 are different from the rest, than only calculate the lcm of the non-binary numbers), but those are all based on assumptions and doesn't feel like a general solution
p
e
Copy code
sed -e '1idigraph {' -e 's/%\(\w\+\)/\1[shape=box];\1/' -e 's/&\(\w\+\)/\1[shape=diamond];\1/' -e 's/$/;/' -e '$a}' input.txt | dot -Tsvg -oday20.svg
w
I guess the whole idea of a reverse engineering problem is to make concrete assumptions about your specific input/program. The best you can do is ‘decompile’ the problem where you would probably see that 4 counters are incremented independently and that the registers of the conjunction modules serve as binary bits for the counter(s). There is no general solution I’m afraid. It does set AOC apart from most other competitive programming sites where the problems (I think) are very dry.
m
that is true, it appears I need to learn some basic graphviz skills so that a quick input output scan can be checked
m
All I needed for the visualization was Ctrl+F in the input file following the flows and writing that down in some notes.
✅ 1
m
Again quite lengthy but relatively clean (I think): https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day20/Day20.kt Since a few people are writing about chinese remainder: Computing the lcm worked out of the box for me, was that just lucky or is it because I'm using the prime factor method?
e
like day 8, the inputs are constructed such that the the loops cycles loop back to the start. as there's no offset to consider, it's pure lcm
m
just for the sake of my future sanity
j
For me it was even just the product, as they were all prime.
same 1
m
how would chinese remainder theorem solve the 'not all cycles start at the same index' problem?
cycle1 : starts at 6, length of 10 cycle2 : starts at 12, length of 23 etc.
w
The chinese remainder theorem in general solves the problem of finding an x which is congruent to multiple base/modulo conditions. If base == modulo for all conditions the result is the same as the LCM. I watched this video of Errichto which explains it very nicely:

https://youtu.be/EHDEvFuYPRQ?si=lzkU82TA6T28NZo0▾

j
that is equivalent to cycle1: x == 6 mod 10 cycle2: x == 12 mod 23 ... and then you solve for x
w
There are more mathematical methods, which are harder to appreciate and rely on mod inverse calculations
e
CRT is supposed to be the special case where all the moduli are coprime, it's solvable even without that restriction, assuming a solution exists at all, just factor out the gcd and handle that separately
m
Ah I see, very insightful 👍 thanks guys
e
n
Proud of myself for getting this, as past me would never have gotten it in a million years without looking at others' ideas. As it was, I solved Pt1 last night so I could think about Pt2 overnight, and as soon as I laid my head on the pillow I knew what I needed to do. I'm only disappointed that CRT wasn't necessary.
Also, I had a lot of fun coding it up Java OOP-style, with interfaces, dummy functions that don't do anything, stateful objects with a reset function, etc. 🙂
m
coding it up Java OOP-style, with interfaces, dummy functions that don't do anything, stateful objects with a reset function, etc. 🙂
I'm guilty on that one too 😅
p
I got bitten by an off-by-one that made me think there were offsets to the cycles, which led me to CRT and a wrong answer.
k
This one was quite a tricky one... past AOCs with cycles finding were a great help into working out the best approach
p
I thought it risky to assume none of the required inputs cycles before any of the others which is why i used a map to accumulate them. Turns out for my input it wasn't required and looks the same for you too, @Kash Kabeya
m
Finally got around to cleaning up my code; the input parsing and classes can be found here: https://github.com/mdekaste/AdventOfCode2023/blob/master/src/main/kotlin/day20/Day20.kt
day20.txt.kt
k
@phldavies my assumption is that all inputs were `Conjuction`s, which is the case and they require all of their inputs to be 
high
. I recorded the 5 entries for each inputs and the increase was linear. I am guessing that was the intention 🤷🏾‍♂️
n
Inspired by this post, I reduced my Part 2 calculation time to 250us by having the code analyze the chains of flip flops to figure out what number the counter cycles at, rather than simulation. My (super OOP) code is here, but here's the money shot:
Copy code
override fun part2(): Long {
    val flipFlops = Module.lookup.values.filterIsInstance<FlipFlop>().map { it.name }.toSet()
    val binaryCounterResults = Module.lookup.getValue("broadcaster").downstream
        .map { name ->
            val start = Module.lookup.getValue(name)
            generateSequence(start) { module -> Module.lookup[module.downstream.firstOrNull { it in flipFlops }] }
                .map { if (Module.upstreamCount.getValue(it.name) == 1) 1 else 0 }
                .foldIndexed(1L) { index, acc, i -> acc + (i shl index) }
        }
    return lcm(binaryCounterResults)
}
🙌 1
20 Views
Open in Slack
PreviousNext
Powered by