https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 8> :thread:
# advent-of-code
a
m
Part 1
Part 2
Having my pre-written utility function 
leastCommonMultiple
from previous years helped in this one!
yes black 2
j
@Marcin Wisniowski I'm afraid that this only works if the 1st node ending with Z on each path is the one where the loop will eventually stop. If there were multiple Z-ending nodes in a loop, you'd need smarter code (however, it somehow seems to work for real input)
๐Ÿ˜ฌ 1
๐Ÿ‘ 1
t
Not sure how I feel about these tasks where the input actually only contains the easy part of a hard problem. On one hand relief, on the other hand annoyed I thought about the general problem for too long.
๐Ÿ‘ 1
b
@Jan Durovec I had that same thought, but looped it twice to see if the intervals changed and they didn't, so just taking the first interval and finding the lcm works
it took me a while to realize my lcm function was overflowing because it was using 
Int
...
โœ… 2
l
I got lucky, mine was written with Long. Probably past years experience ๐Ÿ™‚
s
So nice that I already had the 
lcm
function from last year
Unbenannt.cpp
b
my first year doing it in kotlin...
previously i did it in python, so i didn't have to think about such things
e
it turns out that (at least for my input) LCM wasn't necessary, the resulting path sizes were coprime. but I wrote a gcd/lcm anyway (couldn't find one from my past years in Kotlin)
e
my brain is melted, I just cannot see how/why is it an LCM problem ... can someone explain?
j
For part2 it would have been nice to have a hint, that in the inputs the ghosts return to a final state after doing the same number of steps, I thought way to long about solving it generically, to then just use chinese remainder theorem to solve it
e
that's a good point, I didn't have that precondition check in mine, but the solution does rely on it
j
My guess is the puzzle was to introduce the chinese remainder theorem, but Eric did not want to make it too obvious
e
@Jonathan Kolberg thanks. What I don't see is how the task "run the hops in parallel simultaneously until all current nodes end with Z" leads to either lcm or the chinese remainder
e
all paths are cyclic (otherwise the puzzle would have other issues)
if we're entering the cycle on some offset like "00A -> 00B -> 00C -> 00Z -> 00C", you'd need to deal with the remainders, but we're not
m
e
m
my logic was apparantly flawed. I build up a startposition to list of steps until the next Z (assuming one start could cycle through multiple) so you could have 65234 to (12342, 25635, 25412, 234, 9988) and then have multiple of these variations. Because you can't 'LCM' that, I manually ran it, and ofcourse, given my answer of 18,024,643,846,273, I could never find it within the scope. Was my assumption wrong to begin with? I checked the graphs and they appeared to be just that: 65234 to (65234), so I could LCM
e
the problem could be harder in full generality
r
> my brain is melted, I just cannot see how/why is it an LCM problem ... can someone explain? I think the idea is to find the repeating cycle i.e calculate steps for each node and then take a lcm of all steps for each node.
e
thank you!
m
Untitled.kt
Untitled.kt
n
I was working on a solution that would find all loops, and keep track about where along that path was a potential end (i.e. node ends with "Z"). My idea of the conditions for the end of the loop was that I should be at the same node with the same index in the directions string. And then find a point in all the tracks which align. The very last part would have used "lcm". So while coding this, I tried the "just assume the first end is the correct count for every start" and was very surprised that the result was accepted as correct solution.
Just scrolled up and saw the "Chinese remainder theorem". Never heard of it, so will study now...
n
Started late, took me 40 min for pts 1 and 2. Which let me tell you, for me, is fast. Apart from spending 5 min on a naive solution and watching computer go brr for a minute or two, everything worked the first time. This was fun but definitely recycled content. It's like an easy version of the bus stop and discs problems of years past, without having to worry about staggered starts. https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d8/Y2023D8.kt
@ephemient
it turns out that (at least for my input) LCM wasn't necessary, the resulting path sizes were coprime.
This was the case in last year's "LCM" problem too, Day 11.
@Jan Durovec
I'm afraid that this only works if the 1st node ending with Z on each path is the one where the loop will eventually stop.
Like many on this thread, I had the same fear. But then I told myself that it's a day 8 and that wasn't very likely to be the case.
๐Ÿ‘ 1
a
hi all, another math problem! ๐Ÿฅด It took me longer to implement LCM than everything else. I couldn't just use formula since I restricted myself to non-mutable data only: no mutable collections, no `var`s. Also no recursive functions. I had to familiarize myself with 
generateSequence()
this time. and of course I've become master of `fold`ing. It's my favorite operation now ๐Ÿ™‚ I had to use it even to replicate count() since the count() doesn't work for our favorite data type 
Long
. https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day08.kt
l
reduce(Long::times)
is easier that 
fold
a
that's for multiplication, no? I needed count() on a sequence
m
@Neil Banman I wish I told myself that. I spend an hour debugging and implementing a follow algorithm whilst making graphs in order to find the solution. After an hour I just looked at the scoreboard and thought to myself: "No way..." Then I printed my graphs... They were all
Copy code
56643 -> (56643)
2412 -> (2412)
12345 -> (12345)
9862 -> (9862)
32521 -> (32521)
53212 -> (53212)
instead of the expected
Copy code
56643 -> repeat(2541, 2352, 1634, 56, 8756)
2412 -> repeat(2542, 2381, 2634, 34, 241)
12345 -> repeat(1541, 2951, 3634, 81, 1252)
9862 -> repeat(7541, 2371, 4634, 97, 1251)
32521 -> repeat(2531, 7351, 5634, 23, 1257)
53212 -> repeat(2581, 4351, 6634, 13, 99)
I'm pretty mad at myself because the follow algorithm will never find 18024643846273 in a reasonable time...
l
@andriyo Yes sorry, it should also work with plus
a
@Lidonis Calhau yeah, np - I did use fold to multiple and add so it's a useful shortcut with Long::times. 
fold
is easier to fall back on though since it's pretty much does everything
๐Ÿ‘ 1
p
A nice quick one - having an 
lcm
function ready to hand certainly helps! I did try brute-forcing it while I modified the code to use LCM but my code change unsurprisingly got there first ๐Ÿ™‚
Day08.kt
d
LCM wins the day
n
I changed my code now to run the cycles until I hit the end node a second time, and then check that the cycles really align using
Copy code
check(firstEnd == node) { "Not at same node" }
check(firstCount.rem(count - firstCount) == 0L) { "Not a valid cycle length" }
p
Inspired by @andriyo's challenge, an implementation without 
var
Performance is worse than mutable ๐Ÿ™‚
Copy code
year 2023 day 8 part 1
	 Default took 801.796us (1.00x): 16343
	 Immutable took 983.66us (1.23x): 16343
year 2023 day 8 part 2
	 Default took 2.757020ms (1.00x): 15299095336639
	 Immutable took 4.056470ms (1.47x): 15299095336639
Day08Immutable
d
Very friendly input, length from A->Z == length from Z->Z. I started writing a general solution then checked the cycles.
p
@andriyo just checked your solution - you could argue using a closed-over 
iterator
the way you have is consuming a mutable data type. Running your sequence twice would fail due to it relying on uncontrolled (from it's perspective) state. You may want to look into 
runningFold
to avoid this ๐Ÿ˜‰
d
First I verified that same Z went to same Z, and I started to solve for (first offset, cycle length) pairs, but then I noticed they were multiples
my cycle lengths were not coprime
n
yeah, which is why I added these checks to ensure all cycles align and then use
Copy code
return startNodes.map { steps(it) }.reduce { acc, c -> lcm(acc, c) }
to compute the lcm
d
Copy code
tailrec fun gcd(x: Long, y: Long): Long = if (y == 0L) x else gcd(y, x % y)
fun lcm(x: Long, y: Long): Long = (x * y) / gcd(x, y)
I had that from project euler
j
no they are not coprime for me either, but lcm does the job although for various reasons it shouldnโ€™t. consider: 10A has cycle that have stops: 11Z at 3rd step and 12Z at 7th step 20A has cycle that have stops: 21Z at 5th step and 22Z at 7th step all are separate stops, but naive lcm says 3x5=15, while answer should be 7.
n
I'm using 
x / gcd(x, y) * y
to reduce the risk of overflow
n
now that you mention it mine weren't coprime either
@phldavies Thank you for helping me rid myself of a disgusting 
var
befouling my code.
๐Ÿ‘ 1
e
not that I was intentionally aiming for it, but none of my solutions this year so far use `var`โ€ฆ except for today, in 
gcd
that's "fixable" but there's no reason to
n
My only remaining 
vars
are left and right indexes for finding the numbers in the parts bin. There's an easy functional substitution but I think the while loop incrementer is clearer. So I guess they'll stay.
d
I find it much more straightforward to reason about imperative graph traversal code
n
Is it somehow mentioned in the task that we need to use the full lengths of instruction path to solve the problem, and the subpaths are not relevant?
d
You have to analyze the input to find the simple solution
I was trying to derive the Chinese Remainder Theorem myself until I looked at the input more closely
e
easier to derive it if you have an extended gcd implementation already
that's one that I usually have to look up though
a
@phldavies thank you for checking the code! you're right since iterator was declared somewhat on the side, theoretically it could drift away eventually, say, to some other function or class, and become a nasty side effect that the main code would be coupled with. That's great catch! After looking into it a bit, it looks like I don't need that sequence and iterator at all. I've updated the code. So it's pure now ๐Ÿ™‚ I hope https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day08.kt I didn't have to use 
runningFold
but thanks for suggestion!
since I didn't have LCM available to me, I needed to write one. but I didin't want to use 
var
or recursive functions (just because) so, behold: the 
sequence
based implementation of LCM! I feel like sequenceGenerator is like writing a tail recursive function without writing a tail recursive function. I know, i know it's overkill but just for fun
Untitled.kt
p
@andriyo wait until you come across 
DeepRecursiveFunction
a
I think I saw it somewhere ๐Ÿ™‚ could it be in Jetpack Compose? yes, I didn't want to use recursion since it's like using mutable stack collection and I had this thing about avoiding mutable state in my code
j
I've created a test case that according to my naive implementation should return 16... My (accepted) solution returns 20. Can anyone check?
Copy code
L

11A = (11B, 11B)
11B = (11C, 11C)
11C = (11D, 11D)
11D = (11Z, 11Z)
11Z = (11B, 11B)
22A = (22B, 22B)
22B = (22C, 22C)
22C = (22D, 22D)
22D = (22E, 22E)
22E = (22Z, 22Z)
22Z = (23Z, 23Z)
23Z = (22C, 22C)
t
If I didn't check this thread looking for people saying "I can't solve part 2", and if I didn't spot "LCM" mentioned, my code would've probably been running until now without success ๐Ÿ˜› (my answer was 9858474970153)
s
Got rid of mutability after playing around with folds
t
@Sergei Petunin I found 
runningFold
very useful for making it immutable ๐Ÿ™‚
Copy code
fun DesertMap.countSteps(startBranch: Branch, endNodeCondition: (String) -> Boolean): Int =
        generateSequence { turns }.flatten()
            .runningFold(startBranch, this::nextBranch)
            .takeWhile { branch -> !endNodeCondition(branch.node) }
            .count()
๐Ÿ†’ 2
k
p
@Tomasz Linkowski I think I prefer your 
generateSequence { turns }.flatten()
to my 
sequence { while(true) yieldAll(turns) }
๐Ÿ‘ 2
e
could also be
Copy code
generateSequence {}.flatMap { turns }
but that probably reads more confusingly than either of the above ๐Ÿ˜›
๐Ÿ˜‚ 1
d
Okay, I may have gotten a bit lucky (or was super genius) for this one, I had a feeling there would be something with cycles and least common multiple (LCM), that is my solution would work pretty well if: โ€ข At some point, starting from each starting element, after having performed all of the turns (left, right), it would end up at an end element โ€ข When it ends up at an end element, it would at some point, after having performed all movements, end at that element again (hey a cycle) โ€ข The actual final number of steps would be the LCM of all of the steps taken
The implementation is basically this:
Copy code
return elements.filter { it.isStartElement }.map {
            getCycleLength(it)
        }.reduce { acc, l ->
            lcm(acc, l)
        }
But I'm sure there are inputs for which it would not work, oh well ๐Ÿ˜„
It runs in ~7ms, so I'm pretty happy ๐Ÿ™‚
@Jaap Beetstra your example returns 20 for me
t
โ„น๏ธ eventually, I removed 
runningFold
because someone here made me realize that the condition can be checked after the last turn only:
Copy code
fun DesertMap.countSteps(startBranch: Branch, endNodeCondition: (String) -> Boolean): Int =
        generateSequence(startBranch) { branch -> turns.fold(branch, this::nextBranch) }
            .takeWhile { branch -> !endNodeCondition(branch.node) }
            .count() * turns.size
j
@Davio Sounds like you picked the same solution I did initially; it works for the test data, but is not completely correct I think. These are the first 16 steps for the test data, and I don't see why it shouldn't finish at that 16th step
Copy code
0: [11A, 22A]  1: [11B, 22B]  2: [11C, 22C]  3: [11D, 22D]
 4: [11Z, 22E]  5: [11B, 22Z]  6: [11C, 23Z]  7: [11D, 22C]
 8: [11Z, 22D]  9: [11B, 22E] 10: [11C, 22Z] 11: [11D, 23Z]
12: [11Z, 22C] 13: [11B, 22D] 14: [11C, 22E] 15: [11D, 22Z]
16: [11Z, 23Z]
v
My solution for Day 08, used sequences and lcm : https://github.com/bravura-quark/aoc-kotlin-2023/blob/main/src/Day08.kt
t
@Jaap Beetstra Your input doesn't use full cycles (11Z redirects to 11B not 11A) and that's why the approach with LCM doesn't work properly here (the LCM approach is not a general approach). I believe you'd need a brute-force approach to get 16 in your example.
d
Yeah I think my code has the same issue, we may need to find the end element first and only then detect how long the cycle is?
j
@Tomasz LinkowskiI don't think the explanation specifies that there are only full cycles. The input data has only full cycles, but I don't think the explanation mentions it.
It does mention "the number of nodes with names ending in 
A
is equal to the number ending in 
Z
. My test data doesn't match that part, but I think it's not enough to exclude the situation
I'm not completely sure though
a
> it turns out that (at least for my input) LCM wasn't necessary, the resulting path sizes were coprime. Same. The cycle lengths, as in times that you must go through all the directions, were under 100 and prime for all starting points (not just coprime, I believe every single one was a prime number). So I just multiplied them, then multiplied the result by the number of directions.
t
@Jaap Beetstra I think the equal number of start and end nodes does make the difference here. Consider this input (removed 23Z and replaced the target of 22Z with 22B):
Copy code
L

11A = (11B, 11B)
11B = (11C, 11C)
11C = (11D, 11D)
11D = (11Z, 11Z)
11Z = (11B, 11B)
22A = (22B, 22B)
22B = (22C, 22C)
22C = (22D, 22D)
22D = (22E, 22E)
22E = (22Z, 22Z)
22Z = (22B, 22B)
which gives this result (at step 16 we have 22B so we have to iterate further till step 20):
Copy code
0: [11A, 22A]  1: [11B, 22B]  2: [11C, 22C]  3: [11D, 22D]
 4: [11Z, 22E]  5: [11B, 22Z]  6: [11C, 22B]  7: [11D, 22C]
 8: [11Z, 22D]  9: [11B, 22E] 10: [11C, 22Z] 11: [11D, 22B]
12: [11Z, 22C] 13: [11B, 22D] 14: [11C, 22E] 15: [11D, 22Z]
16: [11Z, 22B] 17: [11B, 22C] 18: [11C, 22D] 19: [11D, 22E]
20: [11Z, 22Z]
j
@Tomasz Linkowski What about this test data?
Copy code
LR

11A = (11B, 11C)
11B = (11C, 11D)
11C = (11D, 11A)
11D = (11Z, 11A)
11Z = (11B, 11D)
22A = (22B, 22B)
22B = (22C, 22C)
22C = (22D, 22D)
22D = (22Z, 22Z)
22Z = (22A, 22B)
k
not sure if this implies you end at beginning
Copy code
You had the camel follow the instructions, but you've barely left your starting position
p
t
@Jaap Beetstra This test data doesn't follow "repeat the whole sequence of instructions" (11A takes 3, 5, 7, ... steps to 11Z which is not a multiple of the number of turns: 2).
c
For part 2 I implemented the obviously going to be too slow solution. I then realised it was going to be a LCM exercise. So I just altered my solution to print out when each point had reached a Z location, made a note of them, then popped over to https://www.calculatorsoup.com/calculators/math/lcm.php to get my answer.
e
there are plenty of days where the inputs are more constrained than the puzzle text suggests
you don't have to solve the general case if you don't want to (and in the case, the full general case is pretty damn hard)
K 2
t
Day08.kt
Day08.kt
c
Even the instructions lengths are carefully curated. In the first example instruction length is 2 and it takes 2 steps. Second example length 3 and takes 6 steps. Both cases a multiple of instruction length. Part 2 is slightly more complex taking lcm into account but even then the highest value will be a multiple of your instruction length.
e
anything other than a multiple of instruction length is likely not a cycle
(but yes, the inputs have been set up to avoid funny edge cases)
t
I went right to LCM because I've done an Advent of Code or two in my time and figured that this cycles in a way that is friendly to us. โ€ข Code โ€ข Blog (with text diagram of part 2, if it helps)
m
@Jan Durovec Yes! Taking into account properties of the input is important so that you don't waste time solving a different / more general problem.
m
I sure learned my lesson today haha. I should print early and often ๐Ÿ‘€
n
Untitled.cpp
Untitled.cpp
Anybody use an IntArray instead of a Map? Each letter can be represented in 5 bits, so the entire space is 32,768. Then with bitshifting each int can hold representations of two locations. I did it for fun but don't think I'll keep it. It's the same speed cold and only about 50% faster after warmups.
a
50% faster is nothing to sneeze at
๐Ÿคง 2
n
Yes, but for AoC the benchmarking numbers are highly artificial since there's no reason anyone would fire the program up and calculate the same answer over and over again.
e
the example includes digits though ๐Ÿ˜ž not only did that break my initial parser, but you can't compress 
[0-9A-Z]{3}
quite like that
p
j
to bei fair - i needed the LCM and some other hints ๐Ÿ™ˆ the puzzle instructions puzzled me ๐Ÿ˜„
Pouch.kt.cpp
a
whoever used
Copy code
generateSequence { "ABC".toList() }.flatten().map { it.println() }.count()
should be burned at the stake for witchcraft ๐Ÿ™‚ still can't get my head around how it works exactly to produce infinite sequence without stack overflow
p
It's a sequence. It emits value by value. The lambda is the nextFunction. Whenever the sequence body returns (happening immediately) it will be called again when all values were consumed. Flatten will just transform the string to it's chars
a
@Paul Woitaschek that makes sense, thanks - I don't know why I though it would cause stack overflow
g
Ofc, I missed one important phrase from today's instruction "repeat the whole sequence" ๐Ÿ˜„ here my solution for today, full source code you may find here: https://github.com/grzegorz-aniol/Kotlin-AoC-2023/blob/main/src/main/kotlin/pl/appga/aoc2023/days/Day08.kt
GregADay08.kt
โž• 1
17 Views
Open in Slack
PreviousNext
Powered by