https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 14> (spoilers) :thread:
# advent-of-code
a
j
If you're wondering when the picture appears, just wait until the robots do not collide (i.e. are at unique positions)
😮 2
💡 1
m
manually going through an output.txt file and trying to find a smudge of black characters after 8179 iterations was harder than I thought lol
Untitled
k
Beautiful day again today. Not my fastest, but I was able to get a 💡 pretty quickly for part 2. Solution
🌴 1
m
why is your christmas tree perfect and mine is not 😆
k
It was hidden in the middle of a lot of other randomly placed robots. Had to print out the whole plane to see this beauty right there in the middle. You gotta love Easter on a Christmas day 😅
n
This was pretty easy once I implemented the "no robot collisions" condition. But I still do not understand where in the text this was hinted as the condition. How did you come up with that?
My solution picture for part 2:
🎄 1
j
@nkiesel It was not hinted anywhere.... just an observation/guess.. last time in a task like that (it was supposed to print some characters) I waited until they occupied the smallest possible space and started to diverge, but that did not work here (especially since there's wrapping around edges). Perhaps looking for some consecutive area of size at least X (20-30?) would help too, or at least would give you better point around which time to simulate
p
image.png
n
I only showed pictures which had less than 10 points in the top left and the top right 20X30 corners, but that - even after 100000 seconds - did not show this picture for my input.
k
I thought all the robots "should" be spread out with no collision in order to form a Christmas tree and I was actually expecting the image to look completely different. But it's also impossible to manually look through all the arrangements. So I figured I'd log all the cases where there was no collision. And surprise. It was exactly 1 in all 101 * 103 attempts
j
BTW.. on a different note... my IDE seems to be a bit indecisive today 🤦
n
My solution happened way earlier than 101 * 103 seconds, but I also did not see why that was the upper limit.
j
So found a solution for part 2 after I had a look at the pattern that emerged, was a bit sad that the pattern does not emerge for the example in a smaller way. https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day14.kt
n
I thought I should create checksums of the pictures to then be able to detect when it circles, but then I first took a peek at this channel and saw the "no collision" criteria.
j
My first observation was that both width and height were prime and that the multiplication of both gave the max number of possible positionings of robots so no need to simulate after that
➕ 2
❤️ 1
💡 1
m
With the dimensions being odd numbers and part 1 hinting at ignoring the middle lines, I thought you are supposed to check for symmetry. Which did work, but the tree is not actually exactly in the middle like I thought it would, and there is also some noise outside, so I had to check for some threshold of symmetry.
After seeing the result I switched to just checking for overlapping robots.
j
I had a look again and the width * height was not the real bound forgot about the lcm of the max velocity, but was interesting
j
@Marcin Wisniowski true... my first check impl was also "full middle column", especially since part 1 explicitly said to ignore middle row and column
j
I actually looked for robots in the position ..*.. .*. ***** that works too
m
My solution:
m
cleaned up part 2 to now programmatically find the answer. Introduced a 
operator fun Pair<Int, Int>.rem(other: Pair<Int, Int>)
I have a feeling we might need to use that again in the feature
Day 14 Michael.cpp
m
@Michael de Kaste I need to steal the idea of that 
extractInts()
util, seems super useful.
m
its just 
Regex("""-?\d+""").findAll(input)
But yeah, super useful for me thus far
b
dang i had no idea what to search for on part2, i tried a ton of things based on wrong assumptions
@Marcin Wisniowski i also spent a lot of time checking for symmetry of different types...
i eventually just started looking for robots in a pattern like 
/\
and printing them out until i spotted what the pattern looked like, then i changed my search to 10 robots in a horizontal line
👍 1
a
At least for my input, assumption that first arrangement without collisions is not true - tree appeared on second one.
🤔 1
same 1
b
no idea how people got "no conditions" from the puzzle description, never ocurred to me
d
I didn’t account for the border so I assumed that all points needed to not overlap AND be in a contiguous region
until I looked here
then I deleted part of my code and was done
m
@Aleksandr Pilipenko might dming me your input? I wanna see what other condition I can cook up
d
I figured it HAD to be a heuristic
👍 1
a
@Michael de Kaste sent you my input
d
I wonder if the “right” solution was to animate it and look. But it seems way too many frames in for that
b
that would be hard, mine was over 8k
d
Yeah mine was in the 6k-7k range
b
it seemed like the puzzle hinted to a previous year's puzzle, maybe that previous puzzle had a hint to the no-collision condition?
d
Not a fan, but I guess the condition is extremely easy to implement
👍 1
m
I had 14224 unique iterations and my output was roughly at 8000
imagine me scrolling through an output.txt file with HEIGHT * 14224 unique iterations just to find what I'm looking for 😂
Luckily I feel like working with files is a lot easier than my college would let me to believe, but then again, this was during Java 6 days
d
LOL you’d want to do terminal animation
you could do that though
actually the key is just to find what it looks like
so if you printed everything
you could search for XXXXXXX and find it pretty quick
b
thats what i ended up doing
👍 1
m
true, that was probably smarter than scrolling blob nervous
sadly my brain tends to turn off when in competitive mode
same 1
a
imagine me scrolling through an output.txt file with HEIGHT * 14224
Someone did almost that 😄
😁 1
m
sick! I almost want to do that
very nice
🤣 1
a
these were my Part 2 questions before I read this thread: • in "most of the robots" what is most? >50% 90%? • what is "Christmas tree"? any triangle? pascals triangle? 🤦 @ Mr. Wastl
e
ok this is weird. I used the equality check like it was hinted before. When I print the tiles, i do see my christmas tree. And when I submit the number of rounds it took, the answer is too low. Any idea what's happening?
m
offbyone error?
🚫 1
d
The rarer off by two error 😂
e
Copy code
part2() {
    var i = 0
    // input: List<Robot>, Robot has pos and velocity fields
    while(input.size != input.map { it.pos }.toSet().size) {
        input.forEach { it.move(w, h, 1) }
        i++
    }
    print() // print the tiles to see the tree
    i
}
off by 100. Kept the state after part 1 🤦‍♂️
🙃 7
💯 3
p
https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day14.kt This was a fun one! To detect the tree I was searching for a filled 3x3 square.
day14.mov
💯 3
K 2
❤️ 1
j
I assumed that image will be in the one that is most consistent -> has minimal number of adjacent positions. For sure this can be optimized even further, as it takes ~0.8s, but it's good first attempt.
Untitled.kt
but I love the idea of filled 3x3 way much more 🙂
➕ 1
l
I read a quite interesting idea on reddit that help me solve part 2: That the more clustered the robots are, the higher chance that their safety score will be low. So I listed the 10 lowest scores, and the image is the lowest one.
💡 1
a
apart from facepalming @ Mr. Wastl's description, one facepalm for myself is that I was doing a Ctrl + F looking for 5 stars in a row - except the IDE output console buffer had scrolled waaaay past it. my answer was in the 7k range
l
Mine is also in the 7k, I wonder if there is a deterministic solution or just look and see. Mine has a few pictures that has straight lines as well that are not the image.
Here is my solution. I'm curious if it is the same for everyone that the time with the lowest safety score is the one that produce the image. https://github.com/CongLuanTran/Advent-of-Code-2024/blob/main/src/Day14.kt
j
I have a result at 6516, but whole cycle that I check anyway is 10403 seconds
a
> I wonder if there is a deterministic solution or just look if Mr. Wastl had described it better, then one could look for the square grid & the whole tree. using the left edge as the offset, we could check that every point matches a christmas tree. heck, even if he just drew the tree in ascii, we could have used the points as the reference to check against but this is AFTER we know what the result actually IS, which is silly.
the most interesting part (of part 1) is that I got to write:
Copy code
groupBy { (point, _) -> grid.quadrant(point) }
which was a simple when clause:
Copy code
private fun Grid<Int>.quadrant(point: Point): Int? = when (point) {
    in 0..<midX to 0..<midY -> 0
    in midX + 1..<cols to 0..<midY -> 1
    in 0..<midX to midY + 1..<rows -> 2
    in midX + 1..<cols to midY + 1..<rows -> 3
    else -> null
}
j
You know, today is the day I'm so happy that part2 didn't have additional:
Due to a unit conversion error, the room is actually 
10000000000000
higher on both the 
X
and 
Y
axis!
🤣 3
l
ah that's beautiful. I used three partioning to split the list and then count their size.
j
yeah I had similar part1:
Copy code
fun Pos.quadrant(bounds: Pos) = when {
    first < bounds.first / 2 && second < bounds.second / 2 -> 0
    first > bounds.first / 2 && second < bounds.second / 2 -> 1
    first < bounds.first / 2 && second > bounds.second / 2 -> 2
    first > bounds.first / 2 && second > bounds.second / 2 -> 3
    else -> null
}
then
Copy code
.groupingBy { (p, v) -> p.quadrant(boundary) }.eachCount()
.filterKeys { it != null }
.values.fold(1, Int::times)
a
in case of that infinite space / 10 trillion offset, I had prepared a
Copy code
space: Pair<IntRange, IntRange> = Pair(0..<cols, 0..<rows)
but didn't need it (modulo does it). and for the quadrant check, I added overloads for Points in Pair-of-ranges; which I will now move the the common utils 🙂
Copy code
operator fun Pair<IntRange, IntRange>.contains(point: Point) =
    point.x in this.first && point.y in this.second
j
fun fact: for reason I cannot now comprehend, I've made it 
.fold(0, Int::times)
instead of 
.fold(1, Int::times)
at the beginning, and spend good chunk of time figuring out which of the quadrants has 0 robots and why 🙂
🤣 3
which taught me an important lesson for the future: whenever possible, use 
.reduce(...)
instead 🙂
p
did I just get lucky with
Copy code
private fun List<Robot>.isChristmasTree(): Boolean =
        distinctBy { it.px to it.py }.size == size
?
😑 2
j
same!
n
Lucky: yes. However, I now changed my code to instead find a filled 3x3 region from the robots. That also happens first for the correct picture, and makes more sense to me.
j
hoho ho.
Copy code
generateSequence(input) { robots -> robots.step(boundary) }
        .indexOfFirst { robots -> robots.map { it.first }.distinct().size == input.size }
l
But how did you guys come up with the non-collision idea?
n
That was fun if a bit frustrating. A bit of a sleuthing job. I already had an IteratorCoord.toGraphicString() function in the ol' library, so I thought I'd be done in 10 seconds. Turns out not so much. I tested for collisions early, but I did it wrong. I was examining a sequence of Robots with position and velocity vectors, and I forgot to unwrap to just position when counting distinct instances. Not knowing I messed up on the collision count, I tried a lot of different things. I went the other direction, looking for items with the fewest collisions. I then ran the cycle and did a frequency count to see whether there were any unique set sizes, and the answer was one of just two.
a
yeah, I think the non-collision thing is potentially wrong. since the tree shape could occur with overlaps of bots. (although, the entire tree has 30-40 3x3 grids, so one of them being filled with just one bot is likely but not guaranteed)
n
There's no logical connection, but there's a _meta_logical connection, if you will.
p
I like that it’s less code but it feels also wrong, to be that reliant upon the special observed behaviour of the robots. 🙃
n
Eric likes having puzzles with inputs crafted just so to help us in some way that we have to intuit or experiment to find out.
a
if not searching the tree itself, the safest grid check is a 9x9. but all this is after finding the answer anyway 😕
p
I liked having a 
robotsInSpace
method
Day14.kt
p
I just read the theory that the fact that robots don’t spread comes from how they generated the puzzles. Start from an image and then generate a bunch of randomized vectors. With that in mind it makes totally sense that this is a side effect 💡
l
But there could potentially be cases where the robot doesn't collide but still not form the tree right?
n
For a change of pace, code review time! I'm not a professional programmer, so I don't really get much feedback on what's idiomatic and/or hard or easy to read. The snippet here for sorting into quadrants is a bit fiddly and obscure, but honestly I don't like any of the options I could think of. I hate nested if statements. Also, I've been coding with lots of `?.let`s and such for a while, and so it seems to flow for me, but I don't know if it's confusing to others. I suppose the clearest way to do it would be non-nested 
if
statements with duplicative clauses, like: if (p.x in 0 until splitX && p.y in 0 until splitY) {...} x6 But I don't like that either.
Untitled
l
I do like this:
Copy code
fun quadrant(robots: List<Point>, size: Point) =
    robots.partition { it.first in 0 until size.first / 2 }
    .toList().flatMap {
        it.partition { it.second in 0 until size.second / 2 }.toList()
    }
👍 1
But it is kind of annoying that the result of partition is not ready to be piped into another stream but must be converted to List first
n
Also doesn't handle the stripes down the middle, does it? Much clearer though.
l
Ah the strip in the middle is handled in anothe filter
could combine it with this easily though
a
> if not searching the tree itself, the safest grid check is a 9x9. safest square grid, which we all probably already have with neighbours. and there are multiple 9x9 grids. can't do 10x10 because there won't be enough rows if we start one below. however, I have an Pair(IntRange, IntRange) neighbours so I check for a 9 wide, 13 tall grid
n
Can't search threads so don't know if it was mentioned, but I saw someone on Reddit solved by doing a flood fill just grabbing lots of contiguous characters. That's pretty clever.
a
to keep all the wording nearly the same and not adding any more input texts to parse, Mr. Wastl could have done is start the bots in that shape and then say "how many moves until they will next be in that shape?" then we would already have a reference for what an ASCII Christmas Tree looks like. and then for fun, additionally thrown in some curve balls by allowing 3x3, 4x4, ... 9x9 grids to randomly appear so that shortcut wouldn't work. Jakub pointed out that it cycles every 10k anyway, so we'd really just be doing a cycle check. Or he can make the Christmas tree re-occur with different bots or different bot counts, so it's not exactly the same and also not a cycle.
today's puzzle links to 2016 Day 2 - has anyone done part Two of that? does it have a Christmas Tree in part two? I'm still on 2015
j
the cycle comes from W*H. since W and H are both primes, the velocities of robots do not matter
p
The fact that the shape is unspecified makes it harder for AI to solve I guess 🤔
a
> the cycle comes from W*H. since W and H are both primes oh lol ok. well, if we include overlaps with different bots/bot counts, cycles could occur before that too. and that could have been the puzzle. since part 2 just needs "bot or not" rather than "how many bots" at location
p
AI isn’t super smart with unicode yet 😛
😁 1
p
Someone 3D print that.
🤣 1
d
101 and 103 did seem oddly specific
a
smallest primes greater than 100 ?
d
@Neil Banman if I were your readability reviewer I would suggest you write it like this:
Copy code
private fun List<Robot>.score(): Int {
    val quadrants = IntArray(4)
    val splitX = width / 2
    val splitY = height / 2
    for (p in this) {
        val index = when {
            p.x < splitX && p.y < splitY -> 0
            p.x < splitX && p.y > spliyY -> 1
            p.x > splitX && p.y < splitY -> 2
            p.x > splitX && p.y > splitY -> 3
            else -> continue
        }
        quadrants[index]++
    }
    return quadrants.reduce(Int::times)
}
👍 1
My solution was effectively
Copy code
fun List<Robot>.score(room: Point): Int {
    val xMid = room.x / 2
    val yMid = room.y / 2
    return count { it.x < xMid && it.y < yMid } *
           count { it.x < xMid && it.y > yMid } *
           count { it.x > xMid && it.y < yMid } *
           count { it.x > xMid && it.y > yMid }
}
Because single pass is not needed and it’s shorter
(my general goal for my solutions is short + readable)
m
Part 2 took me a bit, I thought they would probably be clustered in some way so my final solution was :
Copy code
fun countNeighbors(): Int {
    val positions = robots.map { it.pos }.toSet()
    return positions.count { it + Vec2i(1, 0) in positions }
}
And search for a neighbor count > 100
d
Cleaned mine up a bit more
a
I already have functions for Point + Point, Point * Int and now adding Point mod Point. which would then be
Copy code
(bot.pos + bot.vel * times).mod(Point(cols, rows))
but those functions always create new points (I mean, I'm creating new Bots anyway). Point is 
data class Point(val x: Int, val y: Int)
with those operator functions so would this kind of optimisation be useful?
Copy code
(bot.pos.x + bot.vel.x * times).mod(cols)
(bot.pos.y + bot.vel.y * times).mod(rows)
p
Wouldn*t you need to do another + cols before mod cols?
a
no, since each of those Point functions return points (and Kotlin follows algebra rules, so the multiplication is done first) and the added advantage that move once, move twice, move 10 times - all take the same amount of time.
👍 1
j
I decided to visualize it and look for sparse edge areas. That worked well. I used Kotlin Notebooks anyway, so I just needed to brush up a bit on how to create a BufferedImage.
❤️ 2
K 2
p
Can we use Compose in Notebooks? That would give AOC visualizations super powers
j
That would be cool yes. The UPDATE_DISPLAY that I used here does not work that well when you want to show animations.
d
I mostly didn’t like repeating myself for x and y, but it’s probably better without the operator overloading etc.
same LOC
j
good old awt, again 🙂 (it's because I cannot into compose)
Day14.mov
K 6
❤️ 3
👌 1
nope 🙂 coded myself, using some downloaded free font
a
wow, nice! (not sure if you have even seen that series, "24") those kinds of timers look cool
s
I rendered every image and put them all in a 
LazyVerticleGrid
with Compose, went through them all but it turned out to be not helpful. Eventually I managed to find the answer in some other way, and its corresponding image appears to be just common. Maybe my input is more peculiar. 😂
a
wrt above > so would this kind of optimisation be useful? tested with both options, multiple times (no warmup). • using the overloaded operators is 940ms • using the explicit co-ordinates is just a bit slower, 960ms • but I'll consider these to be effectively equal update: I set the generator/check to ensure times/index is greater than 1 million. the difference is 11.5 vs 11.6 seconds. I'll consider that to also be effectively equal
e
If you're wondering when the picture appears, just wait until the robots do not collide (i.e. are at unique positions)
@Jan Durovec that does not work for my input
Day14.kt I ended up looking for the longest consecutive vertical line
same 1
j
here I have fine input data for y'all to try 🙂
curious_input.txt
K 1
kodee welcoming 1
K 1
j
lol I'm appalled that I tried this and it actually worked - I iterated through an arbitrarily large # of steps (100k in this case) and just found the longest continuous row. I don't know if I should be proud of myself, or move into a different career. https://github.com/jsoberg/2024-Kotlin-Advent-Of-Code/blob/main/src/Day14.kt#L30-L45
a
@Jakub Gwóźdź lovely! kodee welcoming 👏👏👏 so you start with the grid you actually want, and then do the "reverse moves" of the provided bots N-times and that's our input, yes?
j
Well almost. I forgot I can do -2000 steps so I did 9000 forward and relied on the periodic nature of the puzzle 😁
a
haha, that was going to be my next guess. but yeah, you don't need to re-write the code if you only move forward 😎
oh yeah, if doing 'math' for movements, then 
times * velocity
with negative 
times
would work. I'll do 9000 backward to check 😉
j
No, I could easily provide negative number of steps, just forgot about it
a
generateSequence(0) { it - 1 }
with drop(9000) take(1) ✅ or just 
generateSequence(-9000) { it - 1 }
take(1)
j
well, I have 
(p + v * count) % boundary
:) And here's my image converter
same 1
a
but I'm running you input on Part Two code which does incrementing by 1 sequences, even though all steps are just O(1) time; and then does the prettyPrint
Copy code
(bot.pos + bot.vel * times).mod(Point(cols, rows))
(btw, it's missing one bot at the bottom right of the border. but it was auto-generated from the PNG, )
👍 1
n
argh, I was so close without looking at spoilers. for some reason I was expecting the tree cone to start from top line and in the center, I even tried sever different angles, before peeking here. But eventually by just looking at the following pattern in the whole grid will get the answer.
Copy code
......*......
.....*.*.....
....*...*....
...*.....*...
..*.......*..
I don't like relying on the fact of no overlapping to find the tree. The input could have well been created with collisions. Also my input produces several grids with 0 collisions which don't have the Xmas tree in them here is my code
D14P2.kt
c
Got mine working. I looked for the tip of the tree the same way as @nerses did. Wasn't too painful in the end after originally looking at it and just thinking "what".
a
> I was expecting the tree cone to start from top line and in the center yeah, that was a misread/misinterpretation. > I don't like relying on the fact of no overlapping to find the tree. The input could have well been created with collisions. @nerses I did not check for that, it just happens to work out that way for almost everyone. I think Mr. Wastl first put in the bot locations to make the tree and then generated the random input, so they happened to be without overlaps. And your conical-top search is also a correct approach, so you would need to do that offset-check for every point, maybe skipping left-most 5 columns, right-most 5 columns, and bottom-most 5 columns
another interesting approach I was told about - it turns out that the Tree is mostly in one quadrant. the part 2 description says nothing about this. but as a result of this input data, the safety factor calculation from part 1 is actually the lowest when the bots arrange into the tree. example, if there were 16 bots evenly spread out, the safety factor would be 4 x 4 x 4 x 4 (256). or slightly random: 5 x 3 x 4 x 4 (240) but when many are in just one quadrant, it's like 13 x 1 x 1 x 1 (13) or 10 x 3 x 2 x 1 (60) which are much lower than a random spread. agreed this requires already solving it to know that or assuming this happens when trying to solve. also, finding the minimum requires repeating Bot-moves till the cycle at ~10k. but everyone getting answers in the 7k-8k range means just 25% more iterations anyway. not like going from 7k to 100k or 1mil.
e
that gave me an additional idea: • look for the time 
t in 0..<width
when the most robots are in the same +x/-x half • look for the time 
t in 0..<height
when the most robots are in the same +y/-y half • as it's all linear, these repeat every 
width
and 
height
timesteps respectively • then it's just a simple linear diophantine equation to solve for the time when the robots are mostly in the same +x/-x and +y/-y quadrant implemented in https://github.com/ephemient/aoc2024/commit/ddd5f1706dc1745484b2091a6f945a0dc4905f2f, and since it requires far fewer steps, it clocks in at about 600x faster than my previous "scan all times for the longest lines" approach
💡 1
19 Views
Open in Slack
PreviousNext
Powered by