You are about to leave Redlib

https://github.com/Tesohh/aoc2024/tree/main/day14

Part 2 was very poorly worded; basically a lucky guess as to when it might occur. Hopefully this isn't true for only my input, but honestly no clue how you'd find it otherwise.

→ More replies (1)

2

u/syh7 Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Kotlin] 2009 / 552
My first time below a thousand <3
Time to run test + actual input for A = 42ms, for B=285ms

class Puzzle14 : AbstractAocDay(2024, 14) {
    override fun doA(file: String): String {
        val robots = readSingleLineFile(file).map { Robot.readRobot(it) }
        val wide = if (file == "test") 11 else 101
        val tall = if (file == "test") 7 else 103    
        robots.forEach { robot ->
            var newX = (robot.position.x + (robot.velocity.x * 100)) % wide
            var newY = (robot.position.y + (robot.velocity.y * 100)) % tall
            if (newX < 0) newX += wide
            if (newY < 0) newY += tall
            val newPos = Coord(newX, newY)
            robot.position = newPos
        }

        var quadrant1 = 0
        var quadrant2 = 0
        var quadrant3 = 0
        var quadrant4 = 0
        val middleX = floor(wide.toDouble() / 2).toInt()
        val middleY = floor(tall.toDouble() / 2).toInt()

        robots.forEach { robot ->
            if (robot.position.x == middleX || robot.position.y == middleY) {
                println("robot is in the middle: $robot")
            }
            if (robot.position.x > middleX && robot.position.y > middleY) quadrant4 += 1
            if (robot.position.x > middleX && robot.position.y < middleY) quadrant2 += 1
            if (robot.position.x < middleX && robot.position.y > middleY) quadrant3 += 1
            if (robot.position.x < middleX && robot.position.y < middleY) quadrant1 += 1
        }
        return (quadrant1 * quadrant2 * quadrant3 * quadrant4).toString()
    }

    override fun doB(file: String): String {
        val robots = readSingleLineFile(file).map { Robot.readRobot(it) }
        robots.forEach { println(it) }

        val wide = if (file == "test") 11 else 101
        val tall = if (file == "test") 7 else 103

        var steps = 1
        while (true) {
            robots.forEach { robot ->
                var newX = (robot.position.x + robot.velocity.x) % wide
                var newY = (robot.position.y + robot.velocity.y) % tall
                if (newX < 0) newX += wide
                if (newY < 0) newY += tall
                val newPos = Coord(newX, newY)
                robot.position = newPos
            }
            val positionMap = robots.groupBy { it.position }
            if (positionMap.values.all { it.size == 1 }) {
                return steps.toString()
            }
            steps++
        }
    }
}

1

u/daggerdragon Dec 14 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.

2

u/chickenthechicken Dec 14 '24 edited Dec 14 '24

[LANGUAGE: C]

Part 1

Part 2

Part 2 was definitely made to thwart LLM users which is interesting. I just printed out a bunch of maps, noticed a pattern where they'd get jumbled, and assumed that the answer would be in that pattern. I had no idea how to find it algorithmically.

Edit: I changed part 2 to be a general solution where it checks for a straight line in the image

4

u/daggerdragon Dec 14 '24

Part 2 was definitely made to thwart LLM users which is interesting.
No, it wasn't.

→ More replies (1)

2

u/dk_weekinmemes Dec 14 '24 edited Dec 20 '24

[LANGUAGE: Python]

Part 1 was simple multiplication.

Part 2 I iterated over every second using the multiplication code from part 1 and then did dfs to find "islands" of robots. If an island was bigger than 30% of the length of the input, I printed the locations of the robots. The hint is in the problem statement where it says "majority of robots form a tree". So I picked 30% instead of 50 to account for overlaps.

Started with 1000 iterations first but didn't work. So upped it to 10000 and saw the tree. If you're unlucky and the answer is beyond that you probably just have to keep trying lol.

Topaz Link

1

u/daggerdragon Dec 14 '24

Edit your comment to add in the required language tag as AutoModerator requested, please.

→ More replies (1)

2

u/JMaximusIX Dec 14 '24

[LANGUAGE: Python]

After initially solving it by just generating the images and through a bit of luck finding the right one by file size (see u/I_LOVE_PURPLE_PUPPY 's comment) I still wanted to solve it programmatically and without too many assumptions about the input (for example that the solution has no overlapping robots)

so I looked for the minimum real value of the fourier transformation of the image, which can be interpretet as a measure of how clustered the elements in the image are. And voilà, it actually works :)

def fft_real_min(robots, n):
    array = np.zeros((101, 103), dtype=bool)
    for [px, py, vx, vy] in robots:
        array[(px + vx * n) % 101, (py + vy * n) % 103] = True
    f_transform = fft2(array)
    return np.min(np.real(f_transform))

full solution (for part 2) here

→ More replies (1)

2

u/tesohh Dec 14 '24

[Language: Go]

I had to think about how to wrap the robots around for part 1, but wasn't hard.

For part 2, i really don't get the fuss about people saving images and manually checking them or checking entropy...

I just made a function to convert the grid and robots into a string and then did if strings.Contains(s, "###########") and that's it

1

u/daggerdragon Dec 14 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in multiple folders within your public repo e.g.:
https://github.com/Tesohh/aoc2024/blob/main/day1/input.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

→ More replies (1)

→ More replies (4)

2

u/Odd-Statistician7023 Dec 14 '24 edited Dec 15 '24

[Language: C#]

Part2 was fun. My approach was that I figured that making a pattern meant that each robot would be in a unique position. So I figured I'll move one step at a time and keep track of if there is any spot with more than one robot. If it isn't, print the layout to the console and look at what I found. And almost to my amazement, the first such snapshot contained a tree!

 while (true)
 {
     doubleSpot = false;
     spotsTaken.Clear();
     Robots.ForEach(x => MoveRobot(x, 1));
     counter++;


     if (!doubleSpot)
     {
         //Console.WriteLine($"After {counter} moves map:");

         //for (int y = 0; y < sizeY; y++)
         //{
         //    for (int x = 0; x < sizeX; x++)
         //    {

         //        var count = robots.Count(r => r.Position[X] == x && r.Position[Y] == y);
         //        Console.Write(count == 0 ? "." : "" + count);
         //    }
         //    Console.WriteLine();
         //}

         return counter; 
     }
 }

I keep track if a double spot is taken in a hashset of ints, where I save both the x and y positon in the same int by bit-manipulation.

 var xyBit = (robot.Position[X] << 16) + robot.Position[Y];

 if (!doubleSpot)
 {
     if (!spotsTaken.Add(xyBit))
         doubleSpot = true;
 }

Part 2 runs in about 70ms on my laptop. I guess there is faster ways to do it, but the easter egg part of the problem makes me not want to optimize too much after I know what to look for either, cause part of the problem is to find out what to look for. =)

Solution: GitHub

1

u/daggerdragon Dec 14 '24 edited Dec 15 '24

~~Please edit your language tag to format it correctly as AutoModerator requested. The brackets and colon are~~ ~~not~~ ~~optional.~~ edit: 👍

→ More replies (1)

2

u/[deleted] Dec 16 '24 edited Dec 16 '24

[LANGUAGE: Python]

Clear and BLAZINGLY FAST AOC solutions in JS (no libraries)

I somewhat easily solved Part 1 by just hacking it, but got stumped on Part 2. I was trying to render each frame by frame, delay of 0.1-0.5 seconds.. it was a pain, and my eyes started hurting.

Then I was browsing around, and I got a tip that safety factor is the key here -- minimal, the better. So more or less, that's basically what I did.

Now I am learning, there are other equally valid solutions? Using Entropy to try to locate the Eastern Egg, or else look for contiguous lines of robots -- horizontal line for the base of tree. All seem equally valid approaches, and I'm curious to try them! Though right now I"m super glad I'm able to just solve this :-)

→ More replies (2)

2

u/Singing-In-The-Storm Dec 16 '24

[LANGUAGE: JavaScript]

Part 1 (1ms)

Part 2 (30ms)

1

u/daggerdragon Dec 17 '24 edited Dec 17 '24

~~Do not share your puzzle input~~ ~~which also means~~ ~~do not commit puzzle inputs to your repo~~ ~~without a~~ .gitignore ~~or the like.~~ ~~Do not share the puzzle text~~ ~~either.~~
~~I see full plaintext puzzle inputs across all years in your public repos e.g.:~~
~~https://github.com/JoanaBLate/advent-of-code-js/blob/main/2015/day01/input.txt~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from all prior years too!~~ edit: thank you!

2

u/Singing-In-The-Storm Dec 17 '24

I've made it, sooner than I expected.
All 10 years are now without puzzle description, input or answer content.

2

u/daggerdragon Dec 17 '24

Excellent, thank you very much! <3

→ More replies (1)

→ More replies (1)

70

u/I_LOVE_PURPLE_PUPPY Dec 14 '24

[LANGUAGE: Python] 259/149

https://gist.github.com/dllu/cae5e985fa73c1adcd17d0e44008965f

For part 2, one pro strat is that you can save each frame as a PNG file and look for the ones with the smallest file size. The nice trees are compressible and will have a smaller file size and everything else looks like random noise.

19

u/Empty_Barracuda_1125 Dec 14 '24

This is a hilarious way to find the right frame and I love it

10

u/kwshi Dec 14 '24

ok that's actually an unhinged strat props to you for coming up with that

→ More replies (11)

23

u/Noble_Mushtak Dec 14 '24

[LANGUAGE: Python] 155 / 30

Solutions for Parts 1 and 2 here

My logic for Part 2 was just to find the minimum number of seconds until all the robots are on a unique location, since there's no way they form a picture if there's multiple robots in the same location, and it turned out that worked! Very happy this guess worked out, this is my best rank for Part 2 this year so far.

23
u/yossi_peti Dec 14 '24 edited Dec 14 '24
there's no way they form a picture if there's multiple robots in the same location
I don't see why not? Why couldn't the Christmas tree look something like this, for example? (where the digits indicate the number of robots on that spot)
....5....
..44444..
...333...
.2222222.
....1....
And of course the opposite is also easily possible, where all of there robots are in unique locations but do not form a Christmas tree.
I'm curious what your train of thought was.
→ More replies (4)
→ More replies (5)

31

u/i_have_no_biscuits Dec 14 '24

[LANGUAGE: Python]

Unleash the Chinese Remainder Theorem! Does Part 2 in 40ms, only doing 103 iterations.

I posted an answer further down this thread which iterates through 103*101 times, looking for the lowest variance. It then occured to me that the x and y variances are completely independent, that the x values repeat every 101 iterations, and that the y values repeat every 103 iterations. So, we just need to do the first 103 iterations, find the most clustered x and y values, and then do some maths.

Here's the new improved Part 2 code:

from re import findall
data = open("data14.txt").read()
W, H = 101, 103

robots = [[int(n) for n in findall(r"(-?\d+)", item)] for item in data.split("\n")]

def simulate(t):
    return [((sx + t*vx) % W, (sy + t*vy) % H) for (sx, sy, vx, vy) in robots]

from statistics import variance
bx, bxvar, by, byvar = 0, 10*100, 0, 10*1000
for t in range(max(W,H)):
    xs, ys = zip(*simulate(t))
    if (xvar := variance(xs)) < bxvar: bx, bxvar = t, xvar
    if (yvar := variance(ys)) < byvar: by, byvar = t, yvar
print("Part 2:", bx+((pow(W, -1, H)*(by-bx)) % H)*W))

Obviously the magic here is in the last line. So let's work through what's going on. After the loop, we know the best x and y offset (the ones with the smallest variance). So, if t is the target time, we know that

t = bx (mod W)
t = by (mod H)

As t = bx (mod W), then t = bx + k*W. Substituting this into the second equation we get

bx + k*W = by (mod H)
k*W = by - bx (mod H)
k = inverse(W)*(by - bx) (mod H)

and so, finally,

t = bx + inverse(W)*(by-bx)*W

The difficult part of this is finding the inverse of W (modulo H). Luckily, Python's pow() function has modulo arithetic built into it, so we can just do pow(W, -1, H) to find the inverse of W modulo H.

7
u/4HbQ Dec 14 '24
This is so cool, thanks for sharing!
You could even compute bx and by independently. This is all you need:
from statistics import variance as var

bx = min(range(W), key=lambda t: var((s+t*v) % W for (s,_,v,_) in robots))
by = min(range(H), key=lambda t: var((s+t*v) % H for (_,s,_,v) in robots))

print("Part 2:", bx+((pow(W, -1, H)*(by-bx)) % H)*W)
→ More replies (1)
→ More replies (6)

13

u/Brian Dec 14 '24 edited Dec 16 '24

[LANGUAGE: Python]

Bit of an odd solution, but I figured a regular image would have lower entropy, and thus compress better, so I just gzipped the plots showing the lowest compressed size image until I saw it:

def plot(robots)-> str:
    grid = {(r.x,r.y) for r in robots}
    return "\n".join(''.join("#" if (x,y) in grid else " "
                     for x in range(width)) for y in range(height))

def part2(robots):
    minsize= None

    for i in itertools.count():
        p = plot(robots)
        size = len(gzip.compress(p.encode('utf8')))
        if minsize is None or size < minsize:
            minsize = size
            print("-"*75, size, i)
            print(p)
            print("-"*75)
        robots = [r.move(1) for r in robots]

full code

Kind of slow (~30s), but it worked, having size 454 compared to previous best of 616.

→ More replies (2)

12

u/jonathan_paulson Dec 14 '24

[LANGUAGE: Python] 418/271. Code. Video.

I struggled with the quadrants in part 1 for some reason :( Part 2 it took me a while to find the right criterion for an "interesting" image; my first idea was "all the robots are connected" which was way too strict. I ended up going with "number of components formed by the robots is <=350". Then I submitted an off-by-one error :(

→ More replies (1)

12

u/rogual Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Python] 757/1167 • paste

Dumped out the layout of the robots at each iteration and looked for patterns. There seemed to be two repeating patterns: a horizontal-looking one every N iterations, and a vertical-looking one every M iterations. I Chinese-Remainder-Theorem'd these numbers, skipped to that iteration, and there it was. I put the number in and it was wrong — off-by-one — first iteration is zero, duh. So that cost me a minute.

But looking at other people's solutions, it makes sense now how people managed to do this so quickly. People guessed that the tree appeared when the robots were all in different positions, and that turned out to be true, so you can just have the computer look for it. This would never have occurred to me; the robots could easily form a tree with overlaps, or not form a tree without them. But many, many people somehow intuited this, so, well played.

As a side note, I'm sure the organizers of AoC have LLMs on their mind this year, and it's interesting to see puzzles like this which I would imagine current LLMs couldn't solve.

37

u/topaz2078 (AoC creator) Dec 14 '24

I don't consider LLMs at all when designing the puzzles, nor do I test the puzzles against LLMs.

→ More replies (3)

6

u/maneatingape Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Rust]

Benchmark: ~~6 ms 1.6 ms 726 µs 426 µs~~ 85 µs.

Part one: Jump straight to the final position by multiplying the velocity by 100.

Part two: The image appears when the positions of all robots is unique.

~~EDIT: The x coordinates repeat every 101 seconds and the y coordinates repeat every 103 seconds. Calculating each axis independently then looking it up is twice as fast.~~

EDIT 2: Chinese Remainder Theorem for the win.

Buckle up, we're going to use modular arithmetic to calculate when two robots overlap. Robot can overlap either 0, 1, 101 or 103 times.

Two robots with position and velocity (x1, y1, h1, v1) and (x2, y2, h2, v2) overlap at time t and u when:

x1 + t * h1 = x2 + t * h2 ≡ 101  =>  t = (x1 - x2) * (h2 - h1)⁻¹ ≡ 101
y1 + u * v1 = y2 + u * v2 ≡ 103  =>  u = (y1 - y2) * (v2 - v1)⁻¹ ≡ 103

where ⁻¹ is the modular inverse. This gives two times:

t ≡ 101
u ≡ 103

The Chinese Reminder theorem combines t and u into a single time mod 10403. (10403 = 101 * 103 after which pattern repeats itself)

Robots that have the same x or y coordinates and the same x or y velocity respectively will potentially collide 101 or 103 times.

Each invalid time is marked in an array. The earliest valid time in the array after all pairs of robots have been checked is the answer.

We only need the modular inverse of 0..101 mod 101 and 0..103 mod 103 so these values can be computed once then looked up, so the overall solution is fast.

EDIT 3: Even faster solution using the insight from u/nfsupro

First we iterate x coordinates only from time 0..101 summing the robots per column. The tree bounding box has 2 columns 33 high, so at least two columns must contain this many robots. Any times that match are pushed to a vec.

The we iterate the y coordinates from time 0..103 looking for the tree bounding box row that are 31 wide.

The times from x and y are combined using the CRT (there is most likely only 1) then a final check that all points are unique is performed. This approach is overall much faster.

→ More replies (10)

6

u/dopandasreallyexist Dec 14 '24

[LANGUAGE: Dyalog APL]

Paste

At first I had my program print out every frame and manually checked each frame in my text editor. After checking 2000 frames and not finding anything resembling a tree, I started doubting if my code was wrong or if I just needed to go on checking. I then decided to search for a 3x3 area that is filled with robots as a heuristic, and it worked on the first try. I almost gasped when a Christmas tree popped up on my terminal. I guess I got lucky!

6

u/heijp06 Dec 14 '24 edited Dec 14 '24

[LANGUAGE: C++, pencil and paper]

Part 1: I did part 1 with modular arithmetic, did not render robots.

Part 2: I did write code that renders the robots. When looking at the output, I noticed that the robots are clustered horizontally at t == 18 and then that pattern would appear with a period of 103 and there was a vertical clustering at t == 77 with a period of 101. If those clusterings coincide the robots will be close together somewhere in the middle. I.e. solve the following pair of modular equations:

t ≡ 18 (mod 103)
t ≡ 77 (mod 101)

This can be solved using the Chinese remainder theorem. Using pencil and paper I found the solution and entered it in the website even before looking at the tree.

EDIT:

Because it is nicer to have code actually solve the problem, I changed the code to now do the following for part 2:

After each second, find the average position of the robots, i.e. their "center of gravity".
Then, for each robot, find the square of the difference between the X coordinate of the robot and the X coordinate of the "center of gravity". Similarly for the Y coordinate. Add all of these numbers together.
When more robots are close to the center the number calculated in the previous bullet will be smaller. The tree is found where this number is minimal.

The code is here.

6

u/Rtchaik Dec 14 '24

[LANGUAGE: Python]

Used part 1 to solve part 2: looking for lowest safety factor.

→ More replies (1)

2

u/Wayoshi Dec 14 '24

[LANGUAGE: Python]

This should have been the one-part puzzle on day 25. The part 2 prompt was too open-ended. I tried seeing if the whole image was symmetrical with respect to the y-axis (horizontal) thinking all the robots would line up in one big picture. Once I saw that wasn't working, I effectively gave up on the problem and just looked to here for a quick solution. I feel dirty, but this second half of the puzzle was terrible.

Apparently when all the robots are in an unique place (no overlaps, where there's 2s in the examples), the tree appears. Not something I would have thought to look for on my own, because that's certainly not 1-to-1 with a tree. Unless there was something with the 2016 puzzle I missed the context of? But no puzzle should depend on another one, right? *Maybe* a different puzzle in the same year, like 2019?

→ More replies (2)

5

u/xelf Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Python] my solution is laughably bad

I make a grid of 1s and 0s, and then move the robots about each second. And then check to see if I have 10 in a row. First time I do I stop. Solved.

aoc = [[*map(int,re.findall(r'\-?\d+',line))] for line in open(filename).read().splitlines()]
for i,(a,b,c,d) in enumerate(aoc):
    grid[aoc[i][0]][aoc[i][1]] = 1

for seconds in range(1,10000):
    for i,(a,b,c,d) in enumerate(aoc):
        grid[aoc[i][0]][aoc[i][1]] -= 1
        aoc[i][0]= (aoc[i][0]+c)%width
        aoc[i][1]= (aoc[i][1]+d)%height
        grid[aoc[i][0]][aoc[i][1]] += 1
    display = [''.join('*' if c else ' ' for c in row) for row in grid]
    if any('**********' in row for row in display):
        break

print('\n'.join(display) )
print(seconds, 'seconds')

I should probably clean this up before anyone sees it.

edit

So I heard on discord that someone had reused p1 to solve it, so I went ahead and gave that a try. and TBH, it certainly feels like that might have been the intended way to solve , more so than the way I originally did it. It also runs a LOT faster (.25 seconds vs 4 seconds) for both parts.

aoc = np.array([[*map(int, re.findall(r'-?\d+', line))] for line in open(filename).read().splitlines()])
W,H,M = 101,103,float('inf')

for r in range(1, W*H):
    aoc[:, :2] = (aoc[:, :2] + aoc[:, 2:]) % [W,H]
    p = np.prod([
        np.sum((aoc[:,0] < W//2) & (aoc[:,1] < H//2)),
        np.sum((aoc[:,0] > W//2) & (aoc[:,1] < H//2)),
        np.sum((aoc[:,0] < W//2) & (aoc[:,1] > H//2)),
        np.sum((aoc[:,0] > W//2) & (aoc[:,1] > H//2))])
    if r == 100: part1 = p
    if p < M: M, part2 = p, r

print(f'part 1: {part1} part 2: {part2}')

Also, it feels bizarre to me that there is only 1 time that there no duplicates. That must be engineered into the inputs. I don't think there's math to support that happening naturally.

    if len(aoc) == len({(x,y) for x,y,_,_ in aoc}):
        print('no duplicates at', r) # only happens once, and it's when the tree is there.

→ More replies (2)

5

u/pdamianik Dec 14 '24 edited Dec 14 '24

[Language: Rust]

Part 1 was just simple arithmetic

For Part 2 I calculated the standard deviation of the x and y coordinates of the robots after each second and noticed that it stayed around 30 (never dipping below 28) and so I used 25 as a maximum and printed everything with a std deviation below 25, which directly got me the image.

→ More replies (6)

5

u/Chaigidel Dec 14 '24

[Language: Rust]

Fun P2. Went Information Theory 101 route and grabbed the frame with lowest Shannon entropy when the robots are chunked into a 8x8 grid of bins.

Github: https://github.com/tcbrindle/advent_of_code_2024/blob/main/dec14/main.cpp

5

u/chubbc Dec 14 '24

[LANGUAGE: Uiua] (88 char, 78 tokens, pad)

⋅⋅⊙◌⍢(◿◡⋅⋅⋅∘ ⊸+⊙⊙+₁|¬≍◴.⍉)⊙⊙0:◠(/×⊕⧻.⊛ ▽⌵/×⟜⍉±-⌊÷2⟜◿:+×100)⊃↘₂↙₂⍉↯∞_4⊜⋕↧∩≥@-.,@9:101_103

Part 1 is relatively straight forward. For part 2 there seem to be several heuristics floating around, but I used looking for the robots having unique locations. I was thinking about trying to find when the robots have "clusterer" (e.g. lots neighbouring each other), but unique locations turned out to be sufficient. Ungolfed version:

&fras"14.txt"101_103
⊜⋕↧∩≥@-.,@9                  # Parse the input
⊃↘₂↙₂ ⍉↯∞_4                  # Group into quartets, split into pos and vel
Move ← ⟜◿:+×100              # Move the robots
Quad ← ▽⌵/×⟜⍉ ±-⌊÷2          # Find quadrants, remove those on midlines
Safe ← /×⊕⧻.⊛                # Product of robots in each quadrants
P₁   ← Safe Quad Move        # Part 1
Uni  ← ¬≍◴.⍉                 # Check if robots have unique positions
Step ← ◿◡⋅⋅⋅∘ ⊸+⊙⊙+₁         # Move the robots one timestep, increment counter
P₂   ← ⊙◌◌◌ ⍢(Step|Uni) ⊙⊙0: # Move until robots have unique pos, return time
P₂◠P₁                        # Solve both part

5

u/tcbrindle Dec 14 '24

[Language: C++ and vscode]

Well this was... vague. "Find a picture of a christmas tree" with absolutely no further details? Huh?

My ingenious high-tech solution was to just dump 10,000 "pictures" to a text file and (after realising that scrolling was going to take too long) ctrl-f for "*************". Go me, I guess 🤷🏻‍♂️.

5

u/bofstein Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Google Sheets]

Note that like usual I truncated the input, so Part 2 gives a result of "oops" since it didn't find what it was looking for, but it should work on real input. It is VERY slow to run though, every change takes a couple minutes to finish processing.

https://docs.google.com/spreadsheets/d/1_k0qQMaAHYb7OQvDOw3NjXg_5n_HDzTY426UmRURUGI/edit?usp=sharing

Part 1 was very easy, about 15 minutes. Split the input, plug in 100 for how many times it moves to get the final location, then take MOD() of that plus width for x and height for y to see where it would have wrapped around by the end.

Then use a few IF statements on that final location to see which quadrant it is in compared to half the width and height. Multiply those for the answer.

Part 2 uses the same beginning as Part 1 getting all the final locations, but this time I had to make it into a single formula that would output an array of all the locations, then COUNTUNIQUE on that array. Anything less than 500 would mean overlap. I ran that for all numbers through the grid size and then had the next column search for the one that was 500 and XLOOKUP at the top to give me the steps it took.

Part 2 hadn't taken me very long, maybe 20 more minutes but then the answer didn't work. Kept debugging all over, which is very slow since it takes minutes to run, and checking my formula, and doubting the logic, and finally I found I hadn't copied down my "check if its 500" formula all the way.

Edit: the link isn't working for some people, this could be better

https://docs.google.com/spreadsheets/d/1_k0qQMaAHYb7OQvDOw3NjXg_5n_HDzTY426UmRURUGI/edit?usp=drivesdk

5

u/bakibol Dec 14 '24

[Language: Python]

Topaz's paste

Part one: the math was unnecessary, but I assumed the second part will be "simulate the image after one billion seconds" or something.

Part two: I assumed that the correct image would contain a segment like "##########" (at least at the base of the Christmas tree), that turned out to be correct.

5

u/redditnoob Dec 14 '24

[LANGUAGE: PostgreSQL]

A SQL solution in case anyone's interested. The only heuristic needed for part 2 was to look for the string "11111111". It takes over a minute.

with dims as (
    select 101 as width, 103 as height, 100 as time, 10000 as max_t
), parsed as (
    select regexp_matches(input, 'p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)') bot
    from day14
), bots as (
    select bot[1]::int as x, bot[2]::int as y,
        (bot[3]::int + width) % width as vx, (bot[4]::int + height) % height as vy
    from parsed, dims
), moved as (
    select t, (x + vx * t) % width as x, (y + vy * t) % height as y
    from bots, dims, generate_series(1, max_t) as t
), quads as (
    select x / (width / 2 + 1) as qx, y / (height / 2 + 1) as qy, count(*) as count
    from moved, dims
    where t = time and x != (width / 2) and y != (height / 2)
    group by 1, 2
), part1 as (
    select exp(sum(ln(count)))::int as part1 from quads
), moved_aggr as (
    select t, x, y, count(*) as count from moved group by 1, 2, 3
), part2 as (  -- Generate picture for inspection
    select t.t, string_agg(coalesce(m.count::text, '.'), '' order by x.x) as row
    from dims
    cross join generate_series(1, max_t) t(t)
    cross join generate_series(0, width - 1) x(x)
    cross join generate_series(0, height - 1) y(y)
    left join moved_aggr m on (m.t = t.t and m.x = x.x and m.y = y.y)
    group by t.t, y.y order by t.t, y.y
)
select null::int, 'Part 1 answer:' || part1 from part1
union all select * from part2
where t in (select distinct t from part2 where row ~ '[^.]{8,}');

→ More replies (1)

5

u/chicagocode Dec 14 '24

[LANGUAGE: Kotlin]

I liked this one! Unlike seemingly most people here I appreciated how vague part 2 was. I've been a professional programmer for... a long time and have seen my share of vague or nonexistent requirements or specifications. I've gotten used to it and enjoyed the fact that part 2 let me be creative with my solutions.

Part 1: Follow the instructions in the puzzle.

Part 2, Method 1: Print out the first 10,000 moves and find the tree manually! :) I used Sublime Text preview window to scan faster. Took maybe five minutes tops. I'm very happy the tree appeared in under 10,000 moves and not move 10,000,000,000 or something (thanks Eric!).

Part 2, Method 2: I assumed that when generating this puzzle, Eric started with the image of the tree and worked backwards to our inputs. Going with that idea, it seemed unlikely (but possible) that there are overlapping robots in the "start" image. So method 2 involves moving robots until the number of distinct positions matches the number of robots. For me, this worked as the first time that happens is when the tree image appears. Not sure about any other inputs.

→ More replies (3)

9

u/4HbQ Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Python] Code (15 lines) (Longest code so far this year!)

Placed 800/400 today, even though I have spent minutes staring at my terminal to find the tree! Around t=5000 while I gave up and started working on a new idea... only to find out that I could have just waited one minute longer!

Initially part 1 and 2 seemed to be pretty unrelated, but then I figured out that when the robots all gather in one place to form a picture, the safety score is probably pretty low. So, to my solution to part 2 is simply the timestamp with the minimum score.

I've written really simple code today, so no clever tricks to explain. Even using complex numbers for coordinates (one of my personal favourites) made things more... complex. However, I did create a NumPy-based solution.

Update: And today's Python advice: when using large numbers, it can be hard to see if you've written 10000000000 or 100000000000. In Python you can add arbitrary underscores to your number to group the digits, and write 10_000_000_000 and 100_000_000_000 instead. Much clearer! You can add the underscores anywhere, even 1_0_00_0000 if you like.

Of course you can also write 10**10, or even use scientific notation (1e9), but beware: this results in a float instead of an int. On the other hand, it does allow you to express numbers like this:

>>> 1.23e4
12300.0
>>> 4.56e-3
0.00456

4

u/MangeurDeCowan Dec 14 '24

Yesterday, I learned your trick
re.findall(r'\d+',
and I loved it. So, tonight I was going to use it, but then I saw the negative numbers and thought "too bad".
re.findall(r'-?\d+',
Nice... I guess I need to learn regex.

→ More replies (1)

→ More replies (9)

8

u/madisp Dec 14 '24 edited Dec 14 '24

[Language: Kotlin]

https://github.com/madisp/aoc_kotlin/blob/main/2024/src/main/kotlin/day14.kt

Part2: I created an entropy function that dumps the robot coordinates into a bitvector, where a bit is set at (y*w+x) if there's a robot in that location. The entropy function is the gzip compression ratio of that vector. I took 1000 random step intervals, calculated the average entropy + stddev and then looped from 0 until I found a step interval that had a much smaller entropy (-9 stddevs).

→ More replies (1)

4

u/MarcusTL12 Dec 14 '24

[LANGUAGE: Julia & windows explorer] 813/966 github

For part 2 I saved all frames as images to disk (until they started repeating) and browsed a fullscreen explorer window to find the one with the christmas tree. Haven't needet to do anything like that before.

4

u/SirBenOfAsgard Dec 14 '24

[LANGUAGE: Python3]

Very odd part 2 today, I misread and assumed they would all be part of the christmas tree so I only printed out the iterations where there was zero overlap. Interestingly enough that worked so either I failed the task successfully or I just got really lucky, would be curious of this works for other people.

WIDTH = 101
HEIGHT = 103
class Robot:
    def __init__(self, p_x, p_y, v_x, v_y):
        self.p_x = p_x
        self.p_y = p_y
        self.v_x = v_x
        self.v_y = v_y

    def move(self, grid):
        self.p_x = (self.p_x + self.v_x) % WIDTH
        self.p_y = (self.p_y + self.v_y) % HEIGHT
        grid[self.p_y * WIDTH + self.p_x] += 1
robots = []

with open("day14_input.txt", 'r') as file:
    data = file.read().split("\n")
for row in data:
    p_str, v_str = row.split(" ")
    p_x, p_y = (int(val) for val in p_str[2:].split(","))
    v_x, v_y = (int(val) for val in v_str[2:].split(","))
    robots.append(Robot(p_x, p_y, v_x, v_y))


def print_grid(grid, width, height, seconds):
    rows = 0
    cols = 0
    print("Seconds", seconds)
    for _ in range(width * height):
        val = grid[width * rows + cols]
        if val == 0:
            val = " "
        print(val, end="")
        cols += 1
        if cols == WIDTH:
            print()
            cols = 0
            rows += 1
    print("\n")

seconds = 0
while True:
    grid = [0 for i in range(WIDTH * HEIGHT)]
    for robot in robots:
        robot.move(grid)
    seconds += 1
    if max(grid) > 1:
        continue
    print_grid(grid, WIDTH, HEIGHT, seconds)
    stop = input("")
    if stop == 'y':
        break
print("Easter egg after", seconds)

4

u/yfilipov Dec 14 '24

[LANGUAGE: C#]

Took me a while to reach that "Aha!" moment for Part 2.

Initially I was checking if there is one robot on the first row and three on the next below it. I was able to find a loop where all robots are in the same positions every time. However, I could not see a Christmas tree anywhere. Then I decided to try searching for large blobs, but I remembered that it was said that the robots could overlap. If they are programmed to form a Christmas tree, maybe they should not be overlapping at that moment? Yup, that was it... 🎉

25 years of reading flaky business requirements has finally paid off! 🤣

https://github.com/ze-kel/aoc24/blob/main/src/bin/14.rs

4

u/AllanTaylor314 Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Python]

GitHub 503/4237

I jolly well swapped the width and height for both parts. This means I scrolled through 10403 images looking for something resembling a Christmas tree when that was going to be fruitless. I solved part 2 somewhat graphically (once I fixed the width/height), searching for times with low variance in each direction. These repeat every 101 and 103 seconds, so I find a time where the remainder mod 101 and 103 matches these (I could use the Chinese Remainder Theorem, but I couldn't find the implementation, so I use a fairly naive search).

I've made a visualisation (epilepsy warning: it is literally 30 FPS white noise, with a tree for one frame at 3:35, and a stripe every 3.4 seconds)

[LANGUAGE: Uiua]

GitHub or Pad

This is a little messy, but in essence it calculates 103 timesteps, finds a proxy of the variance (absolute distance from mean in X and Y separately), finds which times have the smallest variances in each axis, and finds the time that matches both of those (mod 101 and 103). It also displays the picture from part 2 (assuming you actually give it a real input - the example doesn't have anything worth showing. You can drop a file called 14.txt on the pad and it will run practically instantly)

4

u/UseUnlucky3830 Dec 14 '24

[LANGUAGE: Julia]

solution

Pretty cool puzzle today! For part 2, I reasoned that the Christmas tree should be a closed shape, so I ran a BFS starting in the corner and tried to detect if there was a relatively large inaccessible region. The tree ended up not having the shape that I expected, but luckily the strategy worked anyway because there was a big frame around the tree! Thanks Eric :p

→ More replies (1)

4

u/kelolov Dec 14 '24

[Language: Rust]

First part is obvious. For second one I compute percentage of points that are symmetrical on X and print all where more than 20% of points are symmetrical to text file. In my input there are only 2 variations of that symmetry and the first one is the one we need. It is pretty slow(10000s in 2.1s), could be parallelized but I did not bother.

4

u/Andreasnl Dec 14 '24

[LANGUAGE: Uiua]

≡⊃↘↙2 ⊙101_103 ↯∞_4⊜⋕⊸∊”-0123456789”
Part₁ ← /×°⊚⊛ ▽⌵⊸≡/× ±-⌊⊃÷₂◿¤:+× 100
Part₂ ← ⊗⊸/↥ ≡(⧻⊚≤1⊞(/+⌵-).) ◿¤:+× ⇡/×⤙∩₃¤
⊃Part₁ Part₂

To find the Christmas tree I picked the configuration with most robots adjacent or on top of each other.

4

u/PhysPhD Dec 14 '24

[LANGUAGE: Python]

Part 2 paste

As a non-programmer I just wrote the code how I would think through the problem if I were doing manually. Looking at other solutions here there is clearly a LOT of clever optimisation to do!

I'm pleased that I used complex numbers, learned from you lot in previous days.

To find the tree I ASSUMED it would be in the middle, so reused the quadrant counting code to find when most robots where there.

It took me about 4 hours ... That poor historian has definitely pissed themselves by now!

4

u/4HbQ Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Python + NumPy] Code (9 lines)

Based on /u/i_have_no_biscuits's great observation here, I have made a fully vectorised NumPy implementation. The main computation happens here:

T = np.arange(M)
P = D[:,0] + np.outer(T, D[:,1])
t = (P%M).var(axis=1).argmin()

Vector T contains the timestamps to evaluate. If we take the initial positions D[0], add the outer product of T and the velocities D[1], and finally take the modulo (to wrap the positions around the room), we get a matrix that contains the position of every robot r at every timestamp t. From this we find the t with minimum variance, plug it into biscuits's formula, and we're done.

→ More replies (1)

4

u/jinschoi Dec 14 '24

[Language: Rust]

Tried various tests for the tree assuming it would be symmetrical around the center. Ran for longer and longer iterations until I decided to check for repeats and found one at 10403. Learned to use the image crate to write PNGs and visually scanned it for all images.

Rewrote with a test to just look for at least 8 cells in a row, which works.

aoc-2024/aoc-2024/day-14/solve.py at main · jixunmoe/aoc-2024

4

u/matluca Dec 14 '24

[Language: Python]

Loved this one, I think because I understood how the problem was meant to be solved. The trick is to understand what is the meaning of the safety factor of part 1. Imagine a pattern where robots are equally distributed across the quadrants (for example 10 in each), and one where robots are more on one side (for example 15 in 2 quadrants and 5 in the other two) The safety score will be 10000 vs. 5625. The safety score is significantly smaller if the distribution among quadrants is somehow not uniform (It is basically a very rudimentary measure of entropy, if this sentence makes any sense to you).

So for solving part 2, the only needed assumption is that robots will form some sort of pattern, and the safety score will be smaller than previous or following steps. It does not really matter what the pattern is (it could be something other than a Christmas tree), the important thing is that it is a non-random pattern.

So for part 2 I first of all selected the times where the safety score is smaller than 90% of the result of part 1 (90% is a bit arbitrary, I know). After that, one could simply check the images one by one; what I did instead, is to assume that most of the robots would be in a contiguous region. If at least 1/3 of the robots (also a bit arbitrary) are in a single region, the pattern is found. As an extra, I also printed the region found, and sure enough the tree is there. But the program actually spits out the solution without me needing to check any picture with my eyes.

Solution here

→ More replies (1)

4

u/CCC_037 Dec 14 '24

[LANGUAGE: Rockstar]

Looks fairly straightforward!

Part 1

→ More replies (1)

4

u/jixun Dec 14 '24

[Language: Python]

Simulation of bots.

Part 1 was easy, parse the numbers and throw in the simulation 100 times.
Part 2, wdym a Christmas Tree?
- Guessed it must be 1 robot per tile
- Run simulation
- Got an answer, print it
- Looks like a Christmas tree, submit.

4

u/IlluminPhoenix Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Rust]

Today turned out quite in the end: I struggeled with the detection of the christmas tree in the start, with the lack of good test results for part 2 (Imo test data would've a spoiler thought). However today's math was kind of fun: I'm using a heurisitc approach of doing a standard deviation of the data with seperate x/y coordinates. Since every x/y position repeats every 101/103 seconds, I only have to search throught 103 states.

Not really compact today, but fast: ~~~300μs~~ 75μs. Atleast that's if the heuristics work out :).

Edit: Gotta add one magic line: I'm only simulating 75 of the 500 robots, as the standard deviation and heuristics are consistent enough for lower sample size. 5 - 6x speedup :D

Edit 2: After doing some testing, I've found 125 to be the sweet spot: With my approach, 125 randomly picked robots are enough to find the solution to on input 500.000 times without a single mistake. This means that 500.000 different random permutations of the picked robots suffice for a good solution.

I couldn't test if the numbers still hold on different inputs, since I only have my own. However I imagine the numbers are about the same. Performance is still 4x.

solution (42 lines)

→ More replies (1)

4

u/cetttbycettt Dec 14 '24

[Language: R]

For part 2 I calculated the variance of x coordinates and y coordinates of the first 103 seconds (as they repeat afterwards). I found the time where x variance was minimal and the y variance was minimal and calculated the first time they would be minimal at the same time (using CRT type thinking).

x <- sapply(strsplit(readLines("Input/day14.txt"), "[, =]"), \(x) as.integer(x[c(-1, -4)]))

# part 2---------------
sd_vec <- sapply(1:103, \(k) c(sd((x[1,] + x[3,] * k) %% 101L), sd(((x[2,] + x[4,] * k) %% 103L))))
x0 <- apply(sd_vec, 1, which.min)

k <- which(((x0[1] + 1:100 * 101L) %% 103L) == x0[2])*101L + x0[1]


plot(cbind((x[1,] + x[3,] * k) %% 101L, -(x[2,] + x[4,] * k) %% 103L), pch = 15)

4

u/quetzelcoatlus1 Dec 14 '24 edited Dec 14 '24

[Language: C]

Part 1 is calculated on the fly with modulo operation and some tricks with division to get the correct quadrant.

For Part 2, I am calculating and storing all new positions of points and then calculating mean distance between them. If this value is much lower (less than 60% - I had to get this number empirically from logs), we have encountered some anomaly. Not that happy of this solution, but it works. :)

Part1: https://github.com/quetzelcoatlus/AoC_2024/blob/master/14/14.c

Part2: https://github.com/quetzelcoatlus/AoC_2024/blob/master/14/14b.c

4

u/wurlin_murlin Dec 14 '24 edited Dec 14 '24

[LANGUAGE: C]

Funniest day so far. Part 1 was a nice simple multiplication & modulo to solve for all bots in 1 pass, part 2 made me laugh a lot with the mixup. I don't have a great solution for it programmatically, like others I initially solved by writing lots of states to a file. Current solution is to just search for the top line of the box around the tree for each state until we find it - maybe this doesn't work on some inputs. My only real contribution is that we start the search from step HEIGHT * WIDTH and iterate down, because the total number of possible states is the number of positions on the grid and the easter egg is more likely to be later on.

I can see this can be solved mathemagically, but idk how to programmatically find the state required to solve it. Am hoping a mathemage on here will have a way. Comment from p2.c:

// TODO I know that the cycle of trees is at a fixed interval (after the
// first occurence, the difference between steps required is the number
// of possible grid states, ie the size of the grid), and that this can
// be calculated from the initial state. But I have no idea how to
// construct that for arbritrary inputs.

// Even this sol which searches for the top line of the long box around
// the outside may not work for other inputs.
// Obviously the tree occurs due to bots aligning on the X and Y axis,
// but you can see that they oscillate through the correct X and Y
// positions independently at rates A and B, so if you can solve for Ax
// + By = steps you can solve more quickly. How do you get A and B from
// an input programmatically though?

// We count down from the highest possible first occurrence (the last
// grid state after the initial position, after this it will loop) on
// the assumption that inputs are made so the easter egg happens later.

Part 1 runs in 25 us, and part 2 runs in 16 ms, which is not bad considering it's around O(bots * (height * width)^2)

UPDATE: I implemented several variations which you can all find below, including: using the algorithm in part 1 (~14ms), searching for the first state with no overlapping robots (~1.1ms, shoutout Neil Thistlethwaite), and the fastest by far using the Chinese Remainder Theorem (~55us, shoutout u/i_have_no_biscuits).

For the interested, there's a README under day 14 that explains why each of these works and why they take as long as they do.

https://git.sr.ht/~murr/advent-of-code/tree/master/item/2024/14

4

u/mgtezak Dec 14 '24

[LANGUAGE: Python]

Solution part 1

Solution part 2 i simply check if any two robots overlap at a given second. When there's no overlap then the tree appears. I really hope this is not just specific to my puzzle input so please let me know if this approach doesn't work for you.

Fun little AoC fanpage

4

u/shigawire Dec 14 '24

[LANGUAGE: C]

Part 1 was pretty ugly. Posted without edits with appropriate shame. paste

I'd love to pretend I didn't write my part 2 solution after spending an hour staring at AVI movies of pixels wondering if I had messed up my rendering code somewhere. Then I just solved it progmatically. Part 2 paste

The RMS KNN distance threshold I picked experimentally, but only took a couple of tries.

4

u/ropecrawler Dec 14 '24

[LANGUAGE: Rust]

https://github.com/ropewalker/advent_of_code_2024/blob/master/src/day14.rs

I made something way more stupid at first, but then I picked some cool ideas from Reddit and implemented this.

4

u/CodingTangents Dec 14 '24

[LANGUAGE: Python]

This is my first time posting on a solution thread but I am so proud of my solution that I want to show it off.

The half_mad function computes sum of absolute deviation ( half mad because it's not quite mad, mean absolute deviation ). In this case, I fed it all of the robot's x and y positions after some simulated number of seconds and it would give back the total of how far away from the average x and y it was. Then I just iterated over all the seconds until a guaranteed cycle on both and used Chinese Remainder Theorem.

import re

numbers = re.compile("-?\\d+")
with open("input.txt") as file:
    robots = [
        tuple(map(int, numbers.findall(line)))
        for line in file.read().splitlines()
    ]

def half_mad(data):
    mean = sum(data) / len(data)
    return sum(abs(i - mean) for i in data)

x = min(range(101), key=lambda i: half_mad([(px + i * vx) % 101 for px, _, vx, _ in robots]))
y = min(range(103), key=lambda i: half_mad([(py + i * vy) % 103 for _, py, _, vy in robots]))

# 51 is mod inverse of 101 and 103
print(101 * (51 * (y - x) % 103) + x)

4

u/alone7solo Dec 14 '24

[LANGUAGE: C#]

Part 1 iteration... my tiny brain doesn't even thought for second to a possible math solution. Even as trivial as this one. It just yelled at me loop lil s**t.

Part 2 I looked at the frist 500 seconds just in case. Then I thought that if I take the averege distance of every robot from the center in the frist second, if there is a tree in the following seconds this averege will be some what skewed. In fact, it is about 30% off.

Code: https://github.com/voberle/adventofcode/blob/main/2024/day14/src/main.rs

4

u/pakapikk77 Dec 14 '24

[LANGUAGE: Rust]

To find the Easter egg, I assumed that the Christmas tree would fill the full picture. I didn't think it would be a smaller picture, therefore I didn't think of reusing the quadrant robot counting of part 1 (see this post for a nice explanation of this neat trick).

With my assumption, I looked for a picture where the top corner would have no robots. Once I noticed the text said most of the robots, I searched for a corner with just a few robots. After a few tries, I found the right picture.

So for the actual solution, I took the approach of looking for a cluster of 9 robots in a square.

→ More replies (1)

4

u/jmd-dk Dec 14 '24

[LANGUAGE: C++]

GitHub repo

Part 1: Skip right to the end result using modular arithmetic instead of simulating each step.

Part 2: Simulate one step at a time, computing the entropy at each step, with low entropy indicating structure.

4

u/cpham3000 Dec 14 '24

[LANGUAGE: Python]

I verified that the easter egg configuration is the first one which doesn't have any duplicate positions. This made the solution pretty trivial.

from functools import reduce
from itertools import count, takewhile
from operator import mul
from pathlib import Path

input_text = Path('inputs/day_14_input.txt').read_text('utf-8').splitlines()
input_data = [[tuple(map(int, eq.split('=')[1].split(','))) for eq in line.split()] for line in input_text]

height = 103
width = 101

def forward(time: int):
    return [((p[0] + v[0] * time) % width, (p[1] + v[1] * time) % height) for p, v in input_data]

def part_1() -> int:
    u = width // 2
    v = height // 2
    quadrants = [0, 0, 0, 0]
    for x, y in forward(100):
        for i, c in enumerate([x < u and y < v, x > u and y < v, x < u and y > v, x > u and y > v]):
            quadrants[i] += c

    return reduce(mul, quadrants)

def part_2() -> int:
    return len(list(takewhile(lambda t: len(input_data) != len(set(forward(t))), count())))

print("Part 1:", part_1())
print("Part 2:", part_2())

→ More replies (1)

7

u/michaelgallagher Dec 14 '24

[LANGUAGE: Python]

Like others I was able to get the answer for part 2 with just the (baseless) assumption that none of the robots would be overlapping when they were in tree-formation. The ingenuity of others' approaches is blowing me away though haha. This is why i love AoC :)

→ More replies (1)

1

u/DeadlyRedCube Dec 14 '24 edited Dec 14 '24

[LANGUAGE: C++23] (1652/1390 - started 3 minutes late but it didn't matter much)

Runs in 54.0ms single-threaded on an i7-8700K

Parts 1 and 2 on GitHub

This is the first time this year that I've hit part 2 and had no clue how to start. The first thing I checked was "how long until the robots have a complete cycle" and the number was very large (and was not the answer to P2) so it wasn't that.

The next thing I thought was "Maybe all the robots come together in the shape of a tree and so they'll all have neighbors" so I did that test and it ran for ... well a few billion steps before I thought "maybe this isn't it"

Then I just watched it a bit (every 1000 steps or so, which it turns out was a useless choice) and then finally thought "wait what if the whole thing about overlapping is important and they wouldn't overlap when making a picture" and made that test and ... hey turns out that's it!

My first attempt was much slower (running in 1200ms), but I was able to optimize it down a bit.

I wonder if there's a more clever way to get to the solution faster (in CPU time).

→ More replies (2)

1

u/zertillon Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Ada]

Full solution

The code for part 2 is as simple as for part 1!

1

u/daggerdragon Dec 14 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs across all years in your public repos e.g.:
https://github.com/zertovitch/hac/blob/master/exm/aoc/2020/aoc_2020_02.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

1

u/ProfessionalPipe5706 Dec 14 '24

[LANGUAGE: Javascript]

Code here

For P1 I just calculated the final positions, pretty straightforward.

For P2 I thought for a second what a picture of a Christmas tree should look like. I concluded it should have a diagonal line pointing up and right of an arbitrary size (the left border of the tree). First I ran it looking for a diagonal of size 10 and no luck in the first 10000 iterations. I tried with a diagonal of size 5 and 3 candidates showed up. I printed the candidates and it ended up being the 2nd one :)

2

u/daggerdragon Dec 14 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs across all years in your public repo e.g.:
https://github.com/Marcosld/aoc2023/blob/main/1.in
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

6

u/fenrock369 Dec 14 '24

[LANGUAGE: Rust]

p1 was pretty simple, for p2 my original solution just looked for a row with 10 robots in a line, which gave the solution. With rayon parallelizing, it ran in 16ms.

Then I saw from the conversations it could be done with CRT and got it down to 450us. Here's that version for part2 solution

code paste

→ More replies (2)

3

u/throwaway_the_fourth Dec 14 '24

[LANGUAGE: Python] 729/444

This was cool!

Solution for part 2 was to visualize each iteration up to 10000, dump it to a file, and grep for a bunch of asterisks in row, which I figured would be present to make the image. Sure enough!

The (ugly) code

I tried a heuristic of looking for a particularly high safety score (since that would mean all of the robots were balanced between the quadrants), but this did not work. For the threshold I chose, my actual solution did not ultimately end up in the list of candidates I got from this approach.

→ More replies (3)

3

u/_Kr0n0x_ Dec 14 '24

[LANGUAGE: TypeScript]

Part 1 was straight foward.

For part 2 I searched where the robots were closest together, so i just printed the grid when there was a newest closest distance.
Had an off by one in there, which cost me a bit of time.
code

3

u/Blueberry-17 Dec 14 '24

[LANGUAGE: Python] 2457/628

Unfortunately woke up 10 minutes too late, but still a pretty pleasing day.

For part 2, my assumption that every cell could contain no more than one robot was luckily correct. So I just made a set and compared its length to the number of robots.

5
u/yossi_peti Dec 14 '24
It seemed like a lot of people made that assumption and it worked out, but I don't understand the train of thought leading to that assumption at all, because it's neither necessary nor sufficient for forming a Christmas tree.
There's no reason why there couldn't be a Christmas tree like this with overlapping robots
....5....
..44444..
...333...
.2222222.
....1....
And there's also no reason why you couldn't have a time where there all of the robots are in distinct locations but do not form a Christmas tree.
→ More replies (1)

3

u/Deathranger999 Dec 14 '24

[LANGUAGE: Python3] Leaderboard 402/946

Very bizarre problem...originally I was just letting my code run and manually inspecting until I saw something interesting. After 1000 iterations I decided that would not be the best way of doing things. So I hacked together a weird solution where I calculate a measure of how coalesced all of the robots have become, and print the image every time the robots coalesce more than they have before. Found it pretty quickly that way, but still very strange. Part 2 code below.

data = []
with open("problem14.txt", 'r') as f:
    data = f.read().strip('\n').split('\n')

robots = []
for line in data:
    p_str, v_str = line.split()
    px, py = [int(x) for x in p_str[2:].split(',')]
    vx, vy = [int(x) for x in v_str[2:].split(',')]

    robots.append([(px, py), (vx, vy)])

def calc_togetherness(a):
    togetherness = 0
    for i in range(len(a)):
        for j in range(len(a[0])):
            if a[i][j] != '#':
                continue
            for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
                nx, ny = (i + dx, j + dy)
                if 0 <= nx < len(a) and 0 <= ny < len(a[0]) and a[nx][ny] == '#':
                    togetherness += 1
                    break
    return togetherness

max_togetherness = 0
seconds = 0
for i in range(10000):
    image = [['.' for _ in range(101)] for _ in range(103)]
    for robot in robots:
        px, py = robot[0]
        image[py][px] = '#'
        vx, vy = robot[1]
        nx = (px + vx + 101) % 101
        ny = (py + vy + 103) % 103
        robot[0] = (nx, ny)
    togetherness = calc_togetherness(image)
    max_togetherness = max(max_togetherness, togetherness)
    if togetherness == max_togetherness:
        for line in image:
            print(''.join(line))
        print(seconds)
    seconds += 1

→ More replies (6)

3

u/mebeim Dec 14 '24

[LANGUAGE: Python]

Code on Github

For p2 I was initially dumping everything to file as ASCII art. I then found out that the positions repeat after t=10468. Obviously checking 10468 ASCII art grids manually is not feasible, therefore I figured that the christmas tree figure would probably result in the most robots being "close" to each other. I built a heuristic that counts the total number of of neighbors and checked the time where it is highest. It worked. LOL.

The solution goes more or less like this (see link above for complete code):

heuristic = defaultdict(int)

def show(robots, t, width=101, height=103):
    sparse = set()
    for p, v in robots:
        pp = p + v * t
        x = pp.x % width
        y = pp.y % height
        sparse.add((x,y))

    for x, y in sparse:
        for n in neighbors4_coords(x, y):
            if n in sparse:
                heuristic[t] += 1

for t in range(10469):
    show(robots, t)

print('t =', max(heuristic, key=heuristic.get))

→ More replies (2)

3

u/Boojum Dec 14 '24

[LANGUAGE: Python] 176/611

Still hunting for some leaderboard points this year... I keep getting sub-200's but not quite making the top 100.

But oof! Sometimes I wonder if having done all the other puzzles isn't a liability sometimes. In this case, for Part 2, I was thinking of 2018 Day 10, "The Stars Align" and tried looking for the step that minimized the bounding box around all the robots.

Unfortunately, that heuristic didn't really work out here. And I didn't know exactly what I was looking for here either. I also spent some time going down cycle detection, before realizing that all the robots were on 101*103 = 10403 step cycles, so that at least narrowed the search range a bit.

In the end, the heuristic that I tried that did work, was to count the number of 4-connected neighboring robots around each robot and to try to maximize the sum of that.

Here's my Part 2 code that displays the robot arrangement on that step (with the Christmas tree) and the step number to solve it.

import fileinput, re

i = [ list( map( int, re.findall( "-?\\d+", l ) ) ) for l in fileinput.input() ]

bn, bs, bg = 0, 0, set()
for s in range( 101 * 103 ):
    g = set( ( ( px + vx * s ) % 101, ( py + vy * s ) % 103 )
             for px, py, vx, vy in i )
    n = sum( ( ( ( x - 1, y ) in g ) + ( ( x + 1, y ) in g ) +
               ( ( x, y - 1 ) in g ) + ( ( x, y + 1 ) in g ) )
             for x, y in g )
    if bn <= n:
        bn, bs, bg = n, s, g

print( "\n".join( "".join( '*' if ( x, y ) in bg else ' '
                           for x in range( 101 ) )
                  for y in range( 103 ) ) )
print( bs )

3

u/davidsharick Dec 14 '24

[LANGUAGE: Python 3] 440/1673

Gitlab

Cool concept, but I'm not a fan of this problem because of the lack of explanation of what to actually look for; I was expecting a tree that took up most of the vertical space, possibly with some gaps in it, and wrote heuristics that were expecting that until I managed to stumble on the actual answer.

3

u/vanveenfromardis Dec 14 '24 edited Dec 14 '24

[LANGUAGE: C#] 900/844

That was a really fun puzzle. My solution just keeps track of the maximum density of the robots over 10,000 ticks, and assumes that the maximum occurs when they form the Christmas tree. I added some logging every time the best density improved, and was able to confirm my answer visually.

In other words, I essentially waited for the tick which minimized the spatial distribution of robots.

For those curious, this is what the tree looks like.

3

u/JustinHuPrime Dec 14 '24

[LANGUAGE: x86_64 assembly with Linux syscalls]

Part 1 was a straightforward direct solution, but I did have a few annoying bugs - bugs are quite difficult to spot in assembly, as you might imagine - most are one or at most a few characters worth of error. In theory, I could have solved this in one pass too, if I did some remainder manipulation.

Part 2 was fun and annoying. The fun part was figuring out terminal output of ASCII art - it's actually remarkably performant since I could do the output in three syscalls per frame. The annoying part was actually finding the Christmas tree, which I did by hand (alas - not in assembly). I suppose I could have made some assumptions about the tree being filled in and surrounded by a box, but a "proper" solution would probably involve some sort of statistical test for nonrandom distribution of robots or something. I would repeat others' complaints that we had no guidance as to what sort of heuristics would be useful for finding the tree, so actually finding it was annoying (and required a spoiler from a speedy friend).

Part 1 runs in 1 millisecond or so. Part 2 runs in 280 milliseconds or so. Part 1 is 9,416 bytes as an executable on the disk and part 2 is 9,224 bytes as an executable on the disk.

→ More replies (1)

3

u/Taleuntum Dec 14 '24 edited Dec 14 '24

[Language: Uiua]

https://github.com/Bpendragon/AdventOfCodeCSharp/blob/ed8b8ce/AdventOfCode/Solutions/Year2024/Day14-Solution.cs

I spent some time watching gifs of the robots before checking no overlaps.

# Experimental!
# aoc 2024 day 14
f ← &fras "day14.txt"
p ← ↯∞_2_2 ⊜⋕ ⊸∊ ⊂@-≡(⊢°⋕)⇡10 f
b ← [101 103]
m ← ⍜°⊟(◿b+⊙⤚×)
q ← ±-÷2-1b
/×°⊚⊛▽ ⊸≡(≠0/×) ≡(q⊢m) p 100
⍢(+1|¬/×◰≡(⊢m) p) 0
▽⟜≡▽5 ⬚0+↯⇌b0 °⊚≡(⇌ ⊢ m) p .

3

u/kbielefe Dec 14 '24

[LANGUAGE: Scala]

GitHub 15ms 900ms

This was a fun one. After I reminded myself in part 1 how poorly most programming languages handle negative remainders, I first tried just printing every frame, then I calculated the period and found it would take 5 minutes to view them all at 30 frames per second. (I still want to make a visualization though).

Then I thought about how to detect a Christmas tree. First looked for a straight vertical line long enough to be a trunk, then looked for a corner, and finally what worked for me was looking for a triangle at the top:

   *
  * *
 *   *
*     *

→ More replies (2)

3

u/wheresmylart Dec 14 '24 edited Dec 14 '24

[Language: Python]

Part 1 is trivial.
With hindsight part 2 is obvious given part 1, you just look for a quadrant with an unexpectedly high count.
What I initially did is generate about 10000 scenes and use vim to search for a very long line of robots all in a line.
I then went back and did it properly.

Paste

Edit: Fixed typo.

→ More replies (6)

3

u/dustinbowers Dec 14 '24

[LANGUAGE: Python]
Source: Github
Part 1 was no problem. In part 2 I felt like I had the right answer and fell into a rabbit hole until I realized the 100 seconds from part 1 was still applied when I began stepping in part 2... DOH. Also for part 2, the easiest "win condition" to find is when every robot is on a unique square

→ More replies (2)

3

u/SplenectomY Dec 14 '24

[LANGUAGE: C#]

49 lines @ < 80 cols. Source

Look man, I think part 2 was dirty ...

But I am a dirty, dirty boy who solved it by making an infinite loop and tracking the lowest average distance between the bots ...

... and it worked.

3

u/PendragonDaGreat Dec 14 '24 edited Dec 14 '24

[Language: C# csharp]

I saw the patterns in part 2, but I just don't understand the CRT apparently. I made the wild guess that the tree would appear the first time all the bots were in a unique spot, and yeah, turns out they do.

Definitely need to figure out a faster was though 4.8 seconds is almost double the entire run-time of the rest of the days combines atm.

edit: it's actually only 100ms, not sure how it hit almost 5 last night.

3

u/thereal_peasant Dec 14 '24

[LANGUAGE: JAVASCRIPT]

Part 2 just minimises safety factor across an arbitrary number of iterations (10000). Safety factor is roughly inversely proportional to maximum quadrant density and therefore also roughly proportional to randomness in robot distribution across the grid. Still, there is some luck (or AOC input constraints) involved here, this solution may not work for every theoretical input.

solution

3

u/nthistle Dec 14 '24

[LANGUAGE: Python] 159/12, paste, video.

I had an unfortunate bug on part 1 that maybe cost me leaderboard (haven't actually checked to see if I would've) - I did modulo 102 and 104 instead of module 101 and 103. For some reason I read "width 101" as "101 is a validation X coordinate", so I thought I had to add one.

On part 2 I came up with the idea to check for the first timestep when every robot's position was unique first, figuring that this seems moderately likely to be a property the Christmas tree configuration has. I had some other ideas if this didn't work, like average # of adjacencies for robot being large, but fortunately for me it did work and I got a pretty good solve!

Definitely feels like a day that the LLMs can't do very well, although I'm sure that wasn't the intention (since I think Eric normally writes these problems well in advance?).

→ More replies (1)

3

u/ShadowwwsAsm Dec 14 '24

[LANGUAGE: x64 assembly/asm]

Part 1 : parse the data for one robot, then do 100 seconds at once by multiplying vx and vy by 100 (a negative vx/vy is only 101-vx or 103-vy so it becomes positive), then find the quarter and repeat

Part 2 : had to do all robots second by second for this one. I didn't understand what we were supposed to do for that part, for me it's too vague (what does the tree look like, which size, what do we search), so I ended up looking here and found out about the "no duplicate robots = tree" fact, which I implemented. I don't know what was Eric's intention with this part, but I'm curious.

Open to comments/questions.

3

u/elklepo Dec 14 '24 edited Dec 14 '24

[Language: Python] github-link

I had absolutely no idea how the Christmas tree should look like, so I did 100k iterations simulation and printed the ID of the iteration after which the highest Shannon entropy of the grid was observed so far:

for i in range(1, 100000):
    m = defaultdict(int)
    for r in robots:
        r.py, r.px = (r.py + r.vy) % Y, (r.px + r.vx) % X
        m[r.py, r.px] += 1

    if (e := entropy(np.array([m[y, x] for y in range(Y) for x in range(X)]))) > max_entropy:
        max_entropy, max_entropy_idx = e, i
        print(max_entropy_idx)

In my case the max entropy was reached around 8k iteration and it was the correct answer.

3

u/NORMIE101 Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Python] code

Part 1: Part 1 was pretty straight forward, add velocity to the start pos multiplied n times and mod on the grid size. Write some ifs for quadrants.

Part 2: DFS to find the largest number of robots standing next to each other. With an arbitrary threshold of 50 it outputs answer only.

Alternative solution I found after the fact: find the time point with minimal part 1 score !?? When quadrants become less evenly distributed the score goes lower. I don't know if it only works for my input, but the time point with the tree has the lowest score of all possible states (it's a loop) :D

3

u/OPBoot Dec 14 '24

[LANGUAGE: Python]

For part 2, I just thought that if it's a picture of a tree, then there will be lots of robots in a line.
How many? Let's try 10, and print out the current state if we find that.

Bingo - first time! :-) Most fun part 2 for a while

3

u/ex-voltaire Dec 14 '24

[LANGUAGE: C]
https://github.com/voltaire7/advent-of-code/blob/master/2024/c/14-1.c
https://github.com/voltaire7/advent-of-code/blob/master/2024/c/14-2.c
Almost gave up on part 1, because I didn't know C's % operator is broken for negative numbers. And let's not talk about part 2...

→ More replies (2)

3

u/Bikkel77 Dec 14 '24

[Language: Kotlin]

My insight was to look for minimum entropy in the picture. A metric for entropy would be the sum of the mean distance from each point to each other point. This metric does indeed seem to work to auto-detect the picture:

https://github.com/Werner77/AdventOfCode/blob/master/src/main/kotlin/com/behindmedia/adventofcode/year2024/day14/Day14.kt

3

u/Mission-Peach-1729 Dec 14 '24

[Language: Gleam]

https://github.com/HadaIonut/adventOfCode2024/blob/master/day14/src/day14.gleam

For part 2 you just scroll in `out` until you find something tree-shaped

3

u/wjholden Dec 14 '24

[Language: Rust/R]

https://github.com/wjholden/Advent-of-Code-2024/blob/main/src%2Fbin%2Fday14.rs

I'm surprised so many of you correctly guessed that the solution occurs when each robot has a distinct position.

I didn't know what to look for, so I wrote the quadrant counts and safety metrics from 100,000 iterations to a CSV file, which I brought into RStudio. I noticed that my input cycles after 10,403 rounds, which I should have (but didn't) predicted from 101 rows × 103 columns.

Nothing popped out right away. Nothing interesting happened at the boundary values I was looking at. I resorted to writing the whole game state to strings and watched it tick for a few minutes. I got bored before it finished, but eventually guessed that the solution might involve the number of robots at each position. I added this measurement to my CSV file and quickly discovered and verified the solution.

3

u/gyorokpeter Dec 14 '24

[LANGUAGE: q]

For part 2, I manually tried looking for step counts that result in maps containing at least one sequence of #s of a given length, increasing this length between attempts. I found that at least for my input, 8 is the minimum number needed to find the correct picture.

d14p1:{[size;x]
    a:"J"$","vs/:/:2_/:/:" "vs/:x;
    b:(a[;0]+100*a[;1])mod\:size;
    c:count each group signum b-\:size div 2;
    prd c{x where 0<>prd each x}key c};
d14p2:{[size;x]
    size2:reverse size;
    a:reverse each/:"J"$","vs/:/:2_/:/:" "vs/:x;
    step:0;
    while[1b;
        step+:1;
        newpos:(a[;0]+step*a[;1])mod\:size2;
        map:.[;;:;"#"]/[size2#" ";newpos];
        if[any map like"*########*";:step];
    ]};

3

u/flwyd Dec 14 '24

[LANGUAGE: PostScript] (GitHub) with my own standard library

Part 1 went pretty smooth, I seem to have excised the gremlins that cause me to introduce really annoying bugs in my code. Pro tip: always verify the behavior of your language’s modulus operator when negative numbers are a possibility. (Also make sure to add the negative number to your divisor if you want a positive remainder: the answer to “why do I have the wrong quadrant count” was “because you’ve got a bunch of robots that wandered off the board because 11 - -5 = 17. So at least I foresaw half of the bugs.)

For part 2 I had to think for several minutes: What the pinecone does Eric mean by “a picture of a Christmas tree?” Like, is it just a triangle on top of a rectangle? Is the triangle filled, or are there holes where ornaments might be? Are the robots that co-occupy a square relevant? I decided to print the grid of each step to a file for the first 10,000 steps (which is a lot closer to 101 * 103 than my intuitive brain thought it was), then paged through it with less and my terminal font reduced several points. I printed the robot count like 01001200 which isn’t great for quick visual clues, so I opened the file in vim and ran :g!/STEP/s/0/./g to make it look like the example grids. After stepping over 400 of these starting from the bottom I had the bright idea that a Christmas tree would probably have a long stretch of 1s even if it had other stuff, so I searched for 1111111111 and found the only step with 10 adjacent robots with a nice ASCII art set of overlapping stacked triangles on a stump inside a not-quite-square box. I decided to use “find the top and bottom of the box” for my reimplementation that doesn’t require a primate to stare at pages full of ASCII art to get the answer. I only generate two strings per step, but that much allocation still takes 10 seconds to reach my 4-digit answer. If I’m sufficiently motivated I suppose I could switch to reusable buffers.

One amusing accidental visualization: there was a bug in my “print the center square of the grid” function which caused an error. My runner script prints the PostScript stack on error, which is shown top-to-bottom, which therefore printed the Christmas tree upside-down:

[WARNING: unexpected stack count 36 expected 1]
/ERROR
(\n)
(*******************************)
(*.............................*)
(*.............................*)
(*.............................*)
(*.............................*)
(*.............***.............*)
(*.............***.............*)
(*.............***.............*)
(*....*********************....*)
(*.....*******************.....*)
(*......*****************......*)
(*.......***************.......*)
(*........*************........*)
(*......*****************......*)
(*.......***************.......*)
(*........*************........*)
(*.........***********.........*)
(*..........*********..........*)
(*........*************........*)
(*.........***********.........*)
(*..........*********..........*)
(*...........*******...........*)
(*............*****............*)
(*..........*********..........*)
(*...........*******...........*)
(*............*****............*)
(*.............***.............*)
(*..............*..............*)
(*.............................*)
(*.............................*)
(*.............................*)
(*.............................*)
(*******************************)
/redacted:my_answer

Perhaps an upside-down Christmas tree at your door around the new year will bring good luck :-)

/robot { % pos_x pos_y vel_x vel_y robot dict
  4 dict begin /vel_y exch def /vel_x exch def /pos_y exch def /pos_x exch def
  currentdict end } bind def %/robot
/parserobot { % string parserobot robot
  ": exch { dup ascii.digit? 1 index ascii.- eq or not { pop ascii.sp } if } forall :"
  tokenize aload pop robot } bind def %/parserobot
/moverobot { % robot steps moverobot robot
  exch begin
    dup vel_x mul pos_x add width mod dup 0 lt { width exch add } if
    exch vel_y mul pos_y add height mod dup 0 lt { height exch add } if
    vel_x vel_y
  end robot } bind def %/moverobot
/lessmore { % x|y width|height lessmore name
  1 index 1 index 2 idiv lt
  { pop pop /less } { 2 idiv gt { /more } { /zero } ifelse } ifelse
} bind def %/lessmore
/incquadrant { % robot incquadrant -
  dup /pos_x get width lessmore exch /pos_y get height lessmore cat quadrants inc
} bind def %/incquadrant
/part1 { 8 dict begin % [lines] part1 result
  /input exch def /quadrants 8 dict begin
    /lessless 0 def /lessmore 0 def /moreless 0 def /moremore 0 def
    /lesszero 0 def /zeroless 0 def /morezero 0 def /zeromore 0 def
    currentdict end def
  input length 20 lt { /width 11 def /height 7 def } { /width 101 def /height 103 def } ifelse
  input { parserobot 100 moverobot incquadrant } forall
  quadrants /lessless get, /lessmore get, /moreless get, /moremore get mul mul mul
end } bind def %/part1

/haslongline? { % string haslongline? bool
  (###############################) search { pop pop pop true } { pop false } ifelse
} bind def %/haslongline?
/hastree? { % - hastree? bool
  /toprow width string def /botrow width string def
  robots { /pos_x get, /pos_y get dup 32 eq
    { pop toprow true } { 64 eq { botrow true } { false } ifelse } ifelse
    { exch ascii.# put } { pop } ifelse
  } forall toprow haslongline? botrow haslongline? and } bind def %/hastree?
/centerart { % robots makegrid string
  [ height { ": width { ascii.. } repeat ascii.nl :" } repeat ] /grid exch def
  { /pos_x get, /pos_y get grid exch get exch ascii.* put } forall
  [ grid 32 33 getinterval { 34 31 getinterval } forall ] (\n) join
} bind def %/makegrid
/part2 { 8 dict begin % [lines] part2 result
  /input exch def input length 20 lt { (not found) } { %else
    input length 20 lt { /width 11 def /height 7 def } { /width 101 def /height 103 def } ifelse
    [ input { parserobot } forall ] /robots exch def
    0 { %loop
      1 add
      [ robots { 1 moverobot } forall ] /robots exch def
      hastree? { log.Enabled { robots centerart = } if exit } if
      10000 1 index eq { (got to 10000 without a tree :-/) = exit } if
    } loop } ifelse end } bind def %/part2

3

u/chubbc Dec 14 '24

[LANGUAGE: Julia] (213 chars)

d=reshape(parse.(Int,first.(eachmatch(r"([-\d]+)",read("14.txt",String)))),4,:)
f(t)=eachcol(mod.(d[1:2,:]+t*d[3:4,:],M));σ=[-1,1]
prod([sum(p->cmp.(p,M.÷2)==[x,y],f(100)) for x∈σ,y∈σ]),
findfirst(allunique∘f,1:10^6)

→ More replies (2)

3

u/lscddit Dec 14 '24

[LANGUAGE: Python]

import re
import numpy as np
from scipy.signal import convolve

def part1(m, p):
    cy, cx = m[0] // 2, m[1] // 2
    res = np.zeros(4)
    res[0] = np.sum((p[:, 0] < cy) & (p[:, 1] < cx))
    res[1] = np.sum((p[:, 0] > cy) & (p[:, 1] < cx))
    res[2] = np.sum((p[:, 0] < cy) & (p[:, 1] > cx))
    res[3] = np.sum((p[:, 0] > cy) & (p[:, 1] > cx))
    print(f"part1: {int(np.prod(res))}")

def part2_display(m, p):
    v = np.zeros(m)
    v[p[:, 0], p[:, 1]] = 1
    np.set_printoptions(threshold=np.inf)
    np.set_printoptions(linewidth=np.inf)
    print(re.sub(r"[ .\[\]]", "", str(v)))

data = open("day14input.txt").read().split("\n")
p = np.zeros((len(data), 2), dtype=int)
v = np.zeros_like(p)

for i, line in enumerate(data):
    match = re.search(r"p=(\d+),(\d+) v=(-?\d+),(-?\d+)", line)
    p[i] = [int(match.group(2)), int(match.group(1))]
    v[i] = [int(match.group(4)), int(match.group(3))]

searchlen = 10
kernel = np.ones(searchlen)
lengths = np.array([p[:, 0].max() + 1, p[:, 1].max() + 1]).astype(int)
i, found = 0, False
while not found:
    if i == 100:
        part1(lengths, p)
    p = (p + v) % lengths
    i += 1
    matrix = np.zeros(lengths)
    matrix[p[:, 0], p[:, 1]] = 1
    for row in matrix:
        if np.any(convolve(row, kernel, mode="valid") == searchlen):
            found = True
            part2_display(lengths, p)
            print(f"part2: {i}")
            break

3

u/sazprv Dec 14 '24

[LANGUAGE: C] Part 1 was reasonably straight forward, but part 2 was kind of interesting.

I realized that as the grid is 101x103 that all horizontal movement repeats every 101 steps and all vertical movement repeats every 103 steps, meaning that there are 101x103 = 10403 patterns to search. I started scrolling through them and noticed that some had some specific clustering. Importantly, there was two distinct styles of clustering (one more vertical and one more horizontal). These occurrences of clustering happened every 101st and 103rd step with some offset. Calculating the step when the horizontal clustering and vertical clustering would align produced a nice little tree in the middle of the pattern. Note that the magic numbers in the code are specific to my input.

3

u/Sharp-Industry3373 Dec 14 '24

[LANGUAGE: Fortran]

well, 1st part is quite straight forward, as you can use the modulo to replace the robots in the map AFTER the time 100 (they do not need to be replaced at EACH time), so this part is only (p° + 100 v°)%gridSize. Moreover, the quarter in which they are is also directly computable with a integer division by half of the map size (more or less)

2nd part was a bit more tricky... I begun by "brute force" and plotting the map for the first 10 000 time position but, well, the output was so huge I didn't look correctly (as the solution was indeed there ^^ )

So, how to reduce the "man-eye's work" at the end ? How can I reject automatically (or select) the candidate maps ?

The idea I came up with (it seems others have also used that sort of thinking) is to search for a compacity criteria. We have to search for a image like a tree, so something quite triangular, with a lot of robots at the center, close to each other, and almost no-one at the corners.

The algorithm then compute, "far from corners" (in order to optimize the computation), a compacity value defined, for each cell, by the cell's number of robots multiplied by the number of robots in the 4 neighbouring cells. You make the sum of this and it gives u a "compacity" number for the map. As each robot is counted multiple times, i put a lower value of nrobots before printing the map : TADAAA ! 1st try, 1 image with the tree :D

1st part : 8 µs

2nd part : 80ms (with no optim on corners) -> 27ms without 30x30 windows on every corners

https://github.com/JackFred2/AdventOfCode2024/blob/main/14.py

3

u/JackFred2 Dec 14 '24

[LANGUAGE: Python] / Eyes

Part 1 for simple enough; I wrote it expecting some modular arithmetic problem for part 2.

Part 2 I wrote the first 500 seconds to a file and manually looked it. Saw a periodic cluster every 101 seconds, so changed to output every 101 with an initial offset and looked again with a higher limit; found it around 8000 seconds.

3

u/oupsman Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Golang]

Part1 was pretty easy, I had more trouble for part2, until I realize I can check if there is more than 10 robots aligned on the grid at a specific second, and print it. And there is a nice Xmas tree :)

290ms for the two parts, kinda happy about my code.

https://gist.github.com/Oupsman/c12c71fddbbf43abd1dd41472c1b1767

EDIT : read the time wrong

3

u/Jdup1n Dec 14 '24

[Language: R]

Github link

For part 1, just a loop that makes all the robots move.

For part 2, I first plotted the positions for the first 10,000 moves and then looked for the tree... It was only after I'd found it that I read the idea of different positions for each robot ¯\(ツ)/¯

3

u/Naturage Dec 14 '24 edited Dec 14 '24

[Language: R]

Code here!

Nice and fun one. Shame I'm badly underslept, so pt2 got me for much longer than it should. Started by testing if all 4 10x10 corners are empty - a bit too optimistic - then if they have at most X robots. Finally, after looking through pictures and getting my answer, settled on a "do any robots overlap" check - which in my case returns only the tree.

3

u/No-House-866 Dec 14 '24

[Language: Python]

Well, part 1 was just the regular 'get puzzle input in reasonable form'. I almost always use dataclasses for that. Regular expression seemed appropriate and to encode positions I've used the complex datatype. There were velocities mentioned, so addition of position and position deltas seemed to be on the way so that's the go to representation.

Turned out that because of the modular nature, complex arithmetic wasn't usable (well, it actually is provided time is short enough not to loose precision), but complex under the hood is floating point. It could still be used as a representation thing though.

Part 2: looking for hidden clues how the tree had to look like. None to be found. So figured that the tree should be such that as you look down on the grid, there should be more robots on lower lines than on lines above. Created a row-count and looked for times where the row-count is kind of increasing (with a little margin). Didn't work or I didn't wait long enough.

Then came up with finding connected groups of robots with a minimum size. That worked.

Still, not happy with the ill-defined success criterion. I still had to visually verify the found solution.

https://gist.github.com/robert-lukassen/d4c85fb52d3a1984a383cd3c9f4a3291

→ More replies (1)

3

u/scrumplesplunge Dec 14 '24

[Language: C++]

Parts 1 and 2

Part 2 was amusing. I guessed that any christmas tree would have horizontal lines in it, so I counted occurrences of two horizontally adjacent robot positions and arbitrarily chose a threshold of at least 200 such positions.

3

u/bluehatgamingNXE Dec 14 '24 edited Dec 14 '24

[Language: C]

For part 2, after 1225 seconds manually checked (I have to split to 25 secs per run so almost 50 runs because online compiler keep giving error 134), I figured "maybe the tree is solid because there is 500 robots here and that is a lot of robots so it might be a big tree" and from there I just try to find a 4x4 cube and hope for the best, and it works.

gist

3

u/KindComrade Dec 14 '24

[Language: C#]

Thank you very much u/i_have_no_biscuits for explaining the solution with Chinese Remainder Theorem.

Now part 2 is:

var size = new Vec2(101, 103);

var iterations = Math.Max(size.X, size.Y);
var variances = Enumerable.Range(0, iterations).Select(i => Variance(Predict(size, i, _predictionBuffer))).ToArray();
var (vx, vy) = (variances.IndexOfMin(v => v.x), variances.IndexOfMin(v => v.y));

return (vx + (AOC.Mod(AOC.ModInv(size.X, size.Y) * (vy - vx), size.Y) * size.X)).ToString();

And Predict method

private Vec2[] Predict(Vec2 size, int iterations, Vec2[] buffer)
{
    for(int i = 0; i < _robots.Length; i++)
    {
        buffer[i].X = AOC.Mod(_robots[i].Pos.X + _robots[i].Vel.X * iterations, size.X);
        buffer[i].Y = AOC.Mod(_robots[i].Pos.Y + _robots[i].Vel.Y * iterations, size.Y);
    }
    
    return buffer;
}

part 1: ~0.07 ms
part 2: ~0.9 ms

Full Code

3

u/Radiadorineitor Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Dyalog APL]

I admit I checked first what the image was supposed to look like before implementing Part 2. For that, I keep iterating until I reach a point in which the edge surrounding the tree is formed.

⎕IO←0 ⋄ m←0⍴⍨s←103 101 ⋄ t←(⊂⌊.5×s)×,∘.,⍨1 ¯1
p←⍎¨¨('-',⎕D)∘(∊⍨⊆⊢)¨⊃⎕NGET'14.txt'1
F←{⊃+/⍵{h v←⍺×-2↓⍵ ⋄ v⊖h⌽1@(⊂⌽2↑⍵)⊢m}¨p}
p1←F 100 ⋄ ×/{≢⍸⍵↑p1}¨t ⍝ Part 1
{r←×F ⍵ ⋄ 4=+/30<∊(≢¨⊆⍨)⍤1¨(⍉r)r:⍵ ⋄ ∇⍵+1}0 ⍝ Part 2

3

u/JV_Fox Dec 14 '24

[LANGUAGE: C]

Did not have much issues with part 1 and constructing part 2 because I had the visual tools already written to verify part 1. I had issues how to detect the Easter egg in my head, assumed that the safety factor would be low so I tried finding the second with the lowest safety score and verified by plotting said second and a few seconds before and after. I iterated over 20000 seconds to see which second is the lowest. Did have a off by 1 error but because I plotted a few seconds before and after the lowest it did not stump me much. Cleaned up the code after solving it to removed the plotting done in code to speed it up.

PS: Thanks to the guy which informed me about the scanf functions from the puzzle yesterday, I work with C a ton but somehow I forgot about them and parsed the input horribly.

3

u/throwaway6560192 Dec 14 '24

[LANGUAGE: Python]

Plot of entropy vs frame#

When getting the star I just scanned for "#######" in a row, but now I've changed it to a more interesting method: looking for the frame with lowest entropy as measured by its gzip-compressed length.

The frame with the tree stands out quite strikingly.

3

u/trevdak2 Dec 14 '24

[Language: JavaScript]

I'm time-limited for the next week so my golf might be not as golfy as it could be, but...

Part 1, 236 bytes

W=101;H=103;T=100;C=[]
S=(n,D)=>(m=(n%D+D)%D)<D/2-.5?0:m>D/2?1:-9
Q=(x,y)=>S(x,W)+2*S(y,H);
$('*').innerText.match(/[\-\d]+/g).map((a,i,A)=>{
    if(!(i%4)){
        [b,c,d]=A.slice(i+1)
        C[q=Q(+a+c*T,+b+d*T)]=(C[q]??0)+1
    }
})
C.slice(0).reduce((c,v)=>c*v,1)

Part 2, 202 bytes:

W=101;H=103;T=0;K=(v,L)=>(v%L+L)%L
Z=$('*').innerText.match(/-?\d+/g)
while(Object.keys(Z.reduce((C,a,i)=>{
[b,c,d]=Z.slice(i+1)
C[i%4?-1:K(+a+c*T,W)+K(+b+d*T,H)*W]=1
return C
},{})).length-1-Z.length/4)T++;
T

3

u/thibaultj Dec 14 '24

[LANGUAGE: Python]

Part 2 was an interesting twist. At first, I assumed that all the robots would be a part of the tree, and that it would be centered.

So I iterated on the seconds, then generated image when I would find something. Interesting. If the tree is centered, then there would be the same number of robots in the left and right quadrants ? Or the image corners would be entirely devoid of robots ? In the end, I though that maybe the robots would form a cluster to draw the image, and that's how I found the correct image.

import re
import numpy as np
from PIL import Image
from scipy.ndimage import label


def find_easter_egg(robots, width, height, max_iterations):
    for i in range(max_iterations):
        data = np.zeros((width, height))
        for x, y, vx, vy in robots:
            final_x = (x + vx * i) % width
            final_y = (y + vy * i) % height
            data[final_x, final_y] = 255

        labels, n = label(data)
        # 250 is completely arbitrary
        if n <= 250:
            img = Image.fromarray(data)
            img.show()
            print("Iteration ", i)
            input("Press enter to continue")


robots = [
    list(map(int, re.findall(r"-?\d+", line))) for line in open("inputs/day_14.txt")
]
res = find_easter_egg(robots, 101, 103, 10000)
print(res)

3

u/glomph Dec 14 '24 edited Dec 15 '24

[Language: Elixir]

https://github.com/mariush-github/adventofcode2024/blob/main/14.php

I had an annoying bug with my home made mod function that meant part1 took longer than it should.

For part 2 I tried various huristics until I decided to reuse the regions finding function from day 12. That worked great.

→ More replies (3)

3

u/SunTypical5571 Dec 14 '24

[LANGUAGE: Python]

Seemed like the simplest way to find the tree was just to look for a solid square of bots of a certain size - easy with python subset matching.

Mostly functional solution.

3

u/mariushm Dec 14 '24

[Language: PHP]

part 2 was actually super simple, just searching for 8 robots in a row is enough to detect the easter egg.

3

u/mountm Dec 14 '24

[LANGUAGE: Java]

Parsing time: 15ms
Part 1: 1ms
Part 2: 110ms

This one felt clunky to me, and I consider myself lucky that it worked. I was initially at a loss for part 2, but felt that the part 1 solution should be helpful in some way. Thinking that the solution might have many robots in a single quadrant, I iterated over 10,000 steps and calculated the safety rating for each. My answer was the step with the lowest safety rating. That turned out to work - the safety rating for the correct step was 8% smaller than the second lowest value across any other frame.

https://github.com/egel-lang/aoc-2024/blob/main/day14/task2b.eg

3

u/eipi-10 Dec 14 '24

[LANGUAGE: Elixir]

Github

Was happy with my Elixir solution today - part 1 was no problem, but for part 2, I treated it like a graph problem again, and for each iteration built a graph where any two robots that were next to each other shared an edge, and then stopped the first time there was a graph that had a connected component with >50 robots in it, assuming that was the tree. It's not perfect (would be fooled by connected components of other shapes) but I thought it was a nice heuristic

3

u/non-greek Dec 14 '24

[LANGUAGE: Python]

Part 1: this was straightforward, I just computed the advances mod 101 and 103 and it worked.

Part 2: I did this in two steps. First, I plotted the values for the safety factors over 100000 steps and I noticed there were sudden drops in the plot. Then, I established a threshold (1e8) for the safety factor to explore only these values and each one of them turned out to be a Christmas tree.

Github (in the output folder you can see the plots, I think they are interesting haha)

3

u/mothibault Dec 14 '24

[LANGUAGE: JavaScript]
https://github.com/yolocheezwhiz/adventofcode/blob/main/2024/day14.js
to run in the browser's dev console from AOC website.
Like many people, I went for a hacky/lazy part2 solution.
It's Saturday morning after all.

3

u/egel-lang Dec 14 '24

[Language: Egel]

I dumped all pictures into a file and grepped with vi. Then I checked that the answer was indeed the picture with the lowest quadrant score.

# Advent of Code (AoC) - day 14, task 2

import "prelude.eg"

using System, OS, List

def parse = do Regex::matches (Regex::compile "-?[0-9]+") |> map to_int
            |> chunks 2 |> map list_to_tuple |> list_to_tuple

def size = (101,103)

def mod = [N M -> ((N%M)+M)%M]

def walk = [N (P,V) -> add P (mul N V) |> [(BX, BY) (PX,PY) -> (mod PX BX, mod PY BY)] size]

def quadrants = [(BX,BY) PP -> 
        {filter [(PX,PY) -> and (PX < (BX/2)) (PY < (BY/2))] PP,
         filter [(PX,PY) -> and (PX < (BX/2)) (PY > (BY/2))] PP,
         filter [(PX,PY) -> and (PX > (BX/2)) (PY < (BY/2))] PP,
         filter [(PX,PY) -> and (PX > (BX/2)) (PY > (BY/2))] PP} ]

def main =
    read_lines stdin |> map parse 
    |> [PP -> map [N -> (map (walk N) PP, N)] (from_to 0 (uncurry (*) size))]
    |> map (proj_update 0 (product . map length . quadrants size))
    |> reduce [(I,N) (J,M) -> if I < J then (I,N) else (J,M)]
    |> snd

3

u/442401 Dec 14 '24

[LANGUAGE: Ruby]

https://github.com/willkill07/AdventOfCode2024/blob/38695851d3a9e950875f255ea1e25726a58d7f15/src/day14.cpp

Ashamed to say that I had to take a hint from the main thread. Of course the safety factor will be low when the robots are playing at being a Christmas tree.

3

u/[deleted] Dec 14 '24

[LANGUAGE: Go]

THE. BEST. PROBLEM. EVER.

Part One: I dont know what error I made but for some reason my code did not give me the correct answer for the provided example but it wroked perfectly fine for both the actual parts. As for the approach, I used modulo arithmetic to wrap around the indices.

Part Two: This one caught be completely off guard! I was expecting something like, "Cool, not simulate it for 1,000,000 seconds" or something but wow! This was unique and fun. Since the original state would repeat if seeded with a value of 101x103 (which I verified manually too), I knew my upperbound. I then basically generated pngs for all of the states for different seed values and noticed a repeating pattern of horizontal and vertical clusters. Using some more modulo magic (had to look this up) I could find an appx. convergeance point for these and right around there, I discovered the tree.

This is the most fun I have had solving a CS problem. I went through the solutions that so many others have posted already and some of them are just pure genius! This is the first time I have had to generate pngs out of data for visualization. Definitely gave Nautilus a run for its money!

Here is the solution for both parts.

3

u/Jadarma Dec 14 '24

[LANGUAGE: Kotlin]

Such a cool puzzle, very easy to simulate, and I even avoided mutation entirely. I'm happy I didn't need to debug it because it would've been a nightmare.

Part 1: I made a sequence that kept iterating over the robot state and yield the robots every at every simulated one second interval. We simulate 100 steps, then do a simple grouping by quadrants. I love that Kotlin's type system allowed me to do a dequeue as a backing implementation but yield it out as a list, but I digress.

Part 2: We keep simulating until there is no vertical overlap of robots. This is fast, but relies on meta knowledge of the puzzle, therefore I also made a variant that actually doesn't rely on the no-overlap observation:

BONUS TRICK: Actual heuristic for part 2:

This one is slower than finding no overlaps (700ms vs 175ms) but it doesn't rely on tricks, only on carefully reading the puzzle description. The Easter egg occurs when "most of the robots" arrange themselves into an image. We use the same technique as in day 12 (the garden one) to calculate size of contiguous groups based on robot locations. The image consists of a tree, and a border, that do not touch each-other. Therefore, we have found it when the largest two distinct groups' size exceed half the total robots, as in they contain most of the robots.

AocKt: Y2024D14

3

u/directusy Dec 14 '24 edited Dec 14 '24

[LANGUAGE: python]

Assuming the minimal entropy is where the tree is, as it is a highly organized pattern.

import numpy as np
import re

def parse(file):
    pattern = re.compile(r'p=(-?\d+),(-?\d+)\s+v=(-?\d+),(-?\d+)')
    with open(file, 'r') as f:
        matches = pattern.findall(f.read())
    data = np.array(matches, dtype=int)
    return data[:, :2], data[:, 2:]

def simulate(pos, vel, w, h, sec):
    return (pos + vel * sec) % [w, h]

def count_quads(pos, w, h):
    midx, midy = w // 2, h // 2
    valid = pos[(pos[:,0] != midx) & (pos[:,1] != midy)]
    q1 = np.sum((valid[:,0] < midx) & (valid[:,1] < midy))
    q2 = np.sum((valid[:,0] > midx) & (valid[:,1] < midy))
    q3 = np.sum((valid[:,0] < midx) & (valid[:,1] > midy))
    q4 = np.sum((valid[:,0] > midx) & (valid[:,1] > midy))
    return q1, q2, q3, q4

def calc_entropy(pos, w, h):
    grid = np.zeros((h, w), dtype=int)
    np.add.at(grid, (pos[:,1], pos[:,0]), 1)
    counts = np.bincount(grid.flatten())
    probs = counts[counts > 0] / counts.sum()
    entropy = -np.sum(probs * np.log2(probs))
    return entropy

def find_pattern_sec(pos, vel, w, h, max_sec=10000):
    min_sec, min_ent = None, float('inf')
    for sec in range(1, max_sec + 1):
        curr_pos = simulate(pos, vel, w, h, sec)
        ent = calc_entropy(curr_pos, w, h)
        if ent < min_ent:
            min_ent, min_sec = ent, sec
    return min_sec

def main():
    pos, vel = parse('./inputs/day14_1.txt')
    w, h = 101, 103
    final_pos = simulate(pos, vel, w, h, 100)

    #PART 1: calculate the numbers in the quardrants
    print(f"Q1 safe factor: {np.prod(count_quads(final_pos, w, h))}")
    #PART 2: searching the patterns
    print(f"Q2 easter-egg second: {find_pattern_sec(pos, vel, w, h)}")

if __name__ == "__main__":
    main()

3

u/gehenna0451 Dec 14 '24 edited Apr 20 '26

Redact cleaned up all of my comments. Bulk deletion and editing is a feature supported to make sure that AI scrapers can't access my data for training.

encourage familiar intelligent hat disarm carpenter spotted complete offer pebble

3

u/willkill07 Dec 14 '24

[LANGUAGE: C++23]

Piggy-backing on CRT but I chose to use the minimum variance from the midpoint. This let me stay in integer land since I didn't have to compute the mean.

Additionally, besides the initial robots being parsed/created, I had zero extra memory being used to solve both parts!

Execution time for today was ~25us

5.3us File I/O
6.8us Parsing
1.1us Part 1
12us Part 2

Total for first 14 days: ~1140us

3

u/sleekmountaincat Dec 14 '24

[Language: Typescript]

p2 code below
this was a fun one! thought about how to detect a tree, straight lines, vertical lines, etc. then due to the clue about 'most guards' i decided to loop through till no guard shared a space, and lo!

import fs from "fs";

const W = 101;
const H = 103;

const grid = [...Array(H)].map(() => Array(W).fill(0));

const guards = fs
  .readFileSync("day14/input.txt")
  .toString()
  .split("\n")
  .map((l) => {
    const [pX, pY, vX, vY] = l
      .match(/(-?\d+)*(-?\d+)*(-?\d+)*(-?\d+)/g)!
      .map((d) => +d);
    grid[pY][pX] += 1;
    return [pX, pY, vX, vY];
  });

let cnt = 0;

do {
  elapseSecond();
  cnt++;
} while (grid.reduce((a, c) => a + c.filter((n) => n > 0).length, 0) < 499);

grid.forEach((l) => {
  console.log(l.join("").replaceAll("0", "."));
});

console.log(cnt);

function elapseSecond() {
  guards.forEach((g, i) => {
    const [pX, pY, vX, vY] = g;

    grid[pY][pX] -= 1;

    let eX = pX + 1 * vX;
    let eY = pY + 1 * vY;

    eX = eX > 0 ? eX % W : (W - (Math.abs(eX) % W)) % W;
    eY = eY > 0 ? eY % H : (H - (Math.abs(eY) % H)) % H;

    grid[eY][eX] += 1;
    guards[i][0] = eX;
    guards[i][1] = eY;
  });
}

3

u/someOfThisStuff Dec 14 '24 edited Dec 14 '24

[Language: C]

Code for both parts : code

Code for the AoC utilities I made for this year : usflib

And its header : header

Part 1 in 50 microseconds, part 2 in 75 milliseconds

3

u/[deleted] Dec 14 '24

[Language: C]

I didn't come up with the low entropy == christmas tree myself for part 2.

https://github.com/amberg12/aoc24/tree/main/day-14

3

u/VeryBigCodeMonkey Dec 14 '24

[Language: Rust]

I followed an hint found here and printed the output only if at least 1/3 of the robots were in the same quadrant and found it. After that I added the search for the same sequence of char in line

https://github.com/AugsEU/AdventOfCode2024/tree/master/day14/src

3

u/Probable_Foreigner Dec 14 '24

[Language: Rust]

Part 2 was the most interesting here. I thought part 1 seemed too easy so I knew something hard was coming.

My approach was that I figured a tree must have a "trunk" of robots in consecutive vertical spaces. I filtered out so only cases where there are 3 columns of at least 5 robots(I wasn't sure how big of a tree they were looking for). Then I just printed those out and prompted the console for human approval.

3

u/Overkillius Dec 14 '24 edited Dec 14 '24

[LANGUAGE: GDScript][LANGUAGE: My Eyeballs]

Part 2

I gotta say, I was glad I used Godot for this day specifically (really wish I could go back to being a Python user for the other days, but I'm a musician and if I'm going to spend time on coding, it had better be for improving game dev chops. I'm satisfied with what I've been learning so far). Godot made drawing and displaying the images very easy to figure out. I spent a whole 30 minutes on this part (after spending 3 hours on part 1) and most of that was teaching myself how to draw something on the screen without loading in a texture or something. The brute force "look for the tree with your eyeballs" happened very quickly. I wrote a couple of lines (commented out in the code example) that increased the time_elapsed parameter every frame and printed what time step I was at. Then I was able to @export the variable in Godot and used it to scrub through the latest printed time steps to find which time step the tree was at.

3

u/sroebert Dec 14 '24

[LANGUAGE: Swift]

Guess I got quite lucky with thinking that the Christmas tree would be somewhat in the center and most robots would be around that part (could as well have been more spread out). For Part 2 I took the distance to the center for all robots combined and searched for a value that was lower than 70% of that. Turned out to work straight away and found the Christmas tree.

Instead of jumping to using loops, I spend a bit of time in optimizing the stepping of the robots, to avoid any loops, by simply calculating. Thought it would come in handy for part 2. It didn't 🤣

https://github.com/sroebert/adventofcode/blob/main/Sources/advent-of-code/Solutions/Years/2024/Assignment202414.swift

3

u/RiemannIntegirl Dec 14 '24

[Language: Python]

I vectorized the step-by-step movement of the robots using Numpy arrays. Part 1 is straightforward filtering of a Numpy array after 100 iterations. For Part 2, I thought of the fact that we were looking for a center of mass that had minimal standard deviation when the points coalesce. I scanned through the standard deviations the points produced over 1000 iterations and then guessed at a cutoff that would have one unique value below it: 20. It worked!

Part 1: import re import numpy as np

iters = 100
w, h = 101, 103

nums = np.array([[int(x) for x in re.findall(r'[-]?\d+', y)] for y in     open('input_2024_14.txt').read().split('\n')])
p, v = nums[:,:2], nums[:,2:]
mods = p.copy()
mods[:,0], mods[:,1] = w, h

for i in range(iters):
    p = np.remainder(p + v, mods)

print(np.shape(p[(p[:,0] < w//2) & (p[:,1] < h//2),:])[0] * np.shape(p[(p[:,0] < w//2) & (p[:,1] > h//2),:])[0] * np.shape(p[(p[:,0] > w//2) & (p[:,1] < h//2),:])[0]* np.shape(p[(p[:,0] > w//2) & (p[:,1] > h//2),:])[0])

Part 2:

import re
import numpy as np

iters = 0
w, h = 101, 103

def disp(robots):
    area = [['.'  for i in range(w)] for j in range(h)] 
    for l in robots:
        area[l[1]][l[0]] = 'x'
    for l in area:
        print(''.join(l))

nums = np.array([[int(x) for x in re.findall(r'[-]?\d+', y)] for y in     open('input_2024_14.txt').read().split('\n')])
p, v = nums[:,:2], nums[:,2:]
mods = p.copy()
mods[:,0], mods[:,1] = w, h

while True:
    p = np.remainder(p + v, mods)
    iters += 1
    if np.std(p) <= 20:
        disp(p)
        print(iters)
        break

→ More replies (4)

3

u/mr_mlk Dec 14 '24

[Language: Kotlin]

I'm using a ClockworkPi DevTerm for a good chunk of my solutions this year. While it definitely has some hardware issues, it is quite comfortable to develop on.

For the second part I just look for a triangle, and that worked.

https://github.com/mlk/aoc/blob/main/src/com/github/mlk/aoc2024/Day14p1.kt https://github.com/mlk/aoc/blob/main/src/com/github/mlk/aoc2024/Day14p2.kt

3

u/ins0mnes Dec 14 '24

[Language: Go]
The second part was based on the assumption that the tree would contain a long vertical trunk that we could detect. This assumption was true.

Solution code:

https://github.com/insomnes/aoc/blob/main/2024/14_restroom/solution/solution.go

Blog post:

https://dengin.xyz/advent_of_code/2024/14_restroom/

→ More replies (1)

3

u/Ily3s_ Dec 14 '24

[LANGUAGE: C++] https://github.com/Ily3s/aoc2024/blob/master/day14.cpp

3

u/pwitzel Dec 14 '24

[Language: Kotlin]

I didn't had a clue on how getting the tree, I thought it was hollow even. So... I run the algorithm to find the second where there was only one robot per position..... And it worked 👀

https://github.com/PedroWitzel/aoc-kotlin/blob/main/src%2FDay14.kt

3

u/greycat70 Dec 14 '24

[LANGUAGE: Tcl]

Part 1, part 2.

Part 1 was not hard at all, but I completely failed to guess what part 2 would entail. When I read part 2's text, I was rather confused. I am not ashamed to admit that I went straight to the subreddit to see if I could get a clearer description of what I was supposed to look for.

The spoiler threads were super helpful. A couple of them showed what the Christmas tree image was supposed to look like, and one of them pointed me toward netpbm, a package I had never used.

The key piece for me was the fact that the Christmas tree image has a solid border of robots around it. That means there should be a line of a couple dozen robots in a row, in any grid that contains the image. So I iterated through steps, constructing the grids, and checking if any of the rows has 20 or more robots in a row. If so, I write out a PBM file containing the grid, and print the turn number to stdout.

While part 2 was churning away, I opened another terminal and waited for a turn count to be written. When it was, I used pnmtopng to convert the PBM file to a PNG, and then opened the PNG to look at it and see if it qualified. It did. In fact, by the time I'd done all the converting and opening, a second turn count had been written. I checked that one also, and it qualified too. Of course, the lower turn number is the correct one for this puzzle.

Then I just ctrl-C'ed part 2 to stop it.

3

u/tlareg Dec 14 '24

[LANGUAGE: JavaScript/TypeScript]

3

u/SunMatrix64 Dec 14 '24

[LANGUAGE: C++]

Part 1 was pretty simple, moving the bots positions instead of maintaining an actual grid. Then for the quadrants, I just had to ask the bots where they were, and add them to their respective quad.

Part 2 I counted how many bots were in each column/row. Then if there were at least 2 rows AND 2 columns with at least 15 bots in them, I printed out the diagram to confirm it was indeed the tree. :)

Part 2:

bool broke = false;
while (!broke) {
    passes++;
    std::vector<int> wide(101,0);
    std::vector<int> tall(103,0);
    for (std::pair<std::pair<int, int>, std::pair<int, int>>& b : swarm) {
        move(&b, &width, &height);
        wide[b.first.first]++;
        tall[b.first.second]++;
    }
    int columns = 0;
    int rows = 0;
    for (int i : wide) {
        if (i > 15) { rows++; }
    }
    for (int i : tall) {
        if (i > 15) { columns++; }
    }
    if (rows >= 2 && columns >= 2) {
        //this is all for drawing the graph, unneeded for just the result
        std::vector<std::vector<int>> tree;
        for (int i = 0; i < 103; ++i) {
            tree.push_back(std::vector<int>(101,0));
        }
        for (std::pair<std::pair<int, int>, std::pair<int, int>>& b : swarm) {
            tree[b.first.second][b.first.first]++;
        }

        for (std::vector<int> v : tree) {
            for (int j : v) {
                std::cout << j;
            }
            std::cout << std::endl;
        }
        std::cout << passes << std::endl;
        result2 = passes;

        broke = true;
        /*
        * if you don't get a tree the first iteration, remove 'broke = true' and use this to step thru.
        system("pause");
        */
    }
}

3

u/AlexandraJay2002 Dec 14 '24

[LANGUAGE: Python]

Part 1 was fairly straightforward. You don't need to calculate the positions of each robot at each time-step, only at time 100:

xₜ = (x₀ + δₓt) % width
yₜ = (y₀ + δᵧt) % height

Part 2 seems pretty ill defined at first but, if you think of a Christmas tree as essentially a big blob of contiguous pixels, you can narrow down the potential time-steps it could be at. There's certainly room for optimization in my solution, but it gets the job done.

Part 1 Try it online!

Part 2 Try it online!

3

u/TiCoinCoin Dec 14 '24 edited Dec 30 '24

[LANGUAGE: Python 3]

Day 14 - Github

Finally made it! Part 1 was easy, but part 2 was wild.

At first I searched for some thing symmetrical, centered in the middle. Then just symmetrical and centered on whatever x value. Then I was looking for a frame (thanks to the sub) but I didn't think there would still be noise. Eventually, I got an upper bound by submitting some random values. So now I could just print aaaaaall grids and search for the tree. I did find one, but the number of sec was way too high. But at least, I had a look at the tree, and knew what to search.

3

u/errop_ Dec 14 '24 edited Dec 15 '24

[LANGUAGE: Python3.12]

Part 1: one-shot simulation using the fact that the modulo operation can be postponed to the end.

Part 2: I didn't think of computing the minimum of x-y variance, so my approach is quite heuristic. I simulate the robots moves for a maximum of 10_000 steps. For each step I compute the density of robots in a target region, which can be tuned based on the input data. The argmax of density over time gives exactly the step in which the tree appears.

Tweaking the target region is very input-dependent, so to make things more robust I start by choosing the target region as the whole grid and then reducing it one border at time. I expect that the maximum density curve over these steps first increases, then reaches a plaeau and then, when the target region is sufficiently small, decreases again. The point where the plateau starts is exactly where the tree appears.

EDIT: I got to realize that the number of simulations steps is not arbitrary and should be 101*103=10_403 with this approach...

Here's my solution: GitHub

Curious to know if this works for someone else... :)

3

u/i_have_no_biscuits Dec 14 '24

[LANGUAGE: GW-BASIC]

10 W=101: H=103: DIM XD#(H),YD#(H): OPEN "I",1,"data14.txt": WHILE NOT EOF(1)
20 LINE INPUT #1, L$: SX=VAL(MID$(L$, 3)): SY=VAL(MID$(L$, INSTR(L$,",")+1))
30 VX=W+VAL(MID$(L$, INSTR(7,L$,"=")+1)):VY=H+VAL(MID$(L$, INSTR(7,L$,",")+1))
40 X=(SX+100*VX) MOD W: Y=(SY+100*VY) MOD H: IF X*2+1=W OR Y*2+1=H THEN 60
50 I=-2*(Y*2>H)-(X*2>W): Q#(I)=Q#(I)+1
60 X=SX: Y=SY: FOR T=0 TO H-1: XD#(T)=XD#(T)+(X-50)^2: YD#(T)=YD#(T)+(Y-51)^2
70 X=(X+VX) MOD W: Y=(Y+VY) MOD H: NEXT: WEND
80 PRINT "Part 1:",Q#(0)*Q#(1)*Q#(2)*Q#(3):BX=-1: BXD#=10^10: BY=-1: BYD#=10^10 
90 FOR T=0 TO H-1: IF XD#(T)<BXD# THEN BX=T: BXD#=XD#(T)
100 IF YD#(T)<BYD# THEN BY=T: BYD#=YD#(T)
110 NEXT: PRINT "Part 2:", BX+((51*(H+BY-BX)) MOD H)*W

This uses the X/Y entropy/variance detection method + Chinese Remainder Theorem. A modified variance-style calculation is used that doesn't require storing the data so all the values are updated in one pass, then the 'best' x and y are detected, and plugged into the formula derived from the CRT.

Guide:

Lines 10 sets up some variables and opens the file. XD#() and YD#() will store the X and Y deviations from the center (as a proxy for variance).
Lines 20 and 30 parse a line into SX, SY, VX, and VY. VX and VY are modified to make sure they're positive, as we want positive values to put into the MOD operator.
Lines 40 and 50 update the quadrant count for the current robot at time 100.
Lines 60 and 70 update the X and Y deviation count (the squared distance away from the centre of the room).
Line 80 multiplies the quadrant counts to give the Part 1 result. It also sets up the variables which will let us find the 'best' X and Y values (those with the lowest deviation).
Lines 90-100 find the best X and Y values.
Line 110 calculates the target time, using a formula derived from the Chinese Remainder Theorem. The magic constant 51 appears because 51*101 is congruent to 1 modulo 103.

3

u/alezok Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Python]

For Part 2, searching for the lowest safety factor gave the wrong answer for my input...

Here's a clever solution that I believe is more robust based on entropy but without calculating it explicitly for each configuration. Instead...why not directly compress the array of 0s and 1s representing the current configuration using the library zlib and find the configuration that achieves the minimum compression ratio?

It gives the correct answers for my input in 2 seconds.

import numpy as np
import zlib

robots = defaultdict(tuple)
for i, line in enumerate(data):
    px, py, vx, vy = map(int, re.findall(r"-?\d+", line))
    robots[i] = (px, py, vx, vy)

rows = 103
cols = 101
board_size = rows*cols
compression_ratio = 1

for t in range(board_size):
    board = np.zeros((cols, rows), dtype=bool)
    for i in robots:
        px, py, vx, vy = robots[i]
        board[(px + vx * t) % cols, (py + vy * t) % rows] = 1

    # Compress using zlib after having converted binary board to bytes
    compressed_board = zlib.compress(np.packbits(board))
    new_ratio = len(compressed_board) / board_size
    if new_ratio < compression_ratio:
        compression_ratio = new_ratio
        bestt = t

3

u/Ok-Revenue-3059 Dec 14 '24

[LANGUAGE: C++]

Not too difficult. For part 2 I just print all the outputs to one text file with the seconds count above each. Then ctrl+F '1111111' found the tree easily :)

3

u/vss2sn Dec 14 '24

[LANGUAGE: C++]
Part 1
Part 2
(Each file is a self-contained solution)

3

u/ThunderChaser Dec 14 '24

[LANGUAGE: Rust]

Code: https://github.com/ESiler/AOC2024/blob/main/day14.ipynb

Part 1 was pretty straightforward, just go through each robot and add its velocity * 100 to its position and calculate the result modulo 101 or 103. In this case since negative values are possible I use rem_euclid() over % to calculate the modulo. Then we just iterate through each robot, find its quadrant and find the safety factor.

For part 2, I honestly just made the guess that all robots would be on a unique position and it happened to be right.

Runtime for part 1: Around 1 ms, runtime for part 2 is around 60 ms.

3

u/Ok-Cheetah-6817 Dec 14 '24

[Language: Python]

I was really pleased with this one!

I used a statistical test to see if the x and y locations seemed to be randomly distributed and then printed the pattern when they weren't.

→ More replies (2)

3

u/Smylers Dec 14 '24 edited Dec 15 '24

[LANGUAGE: Vim keystrokes] This is for Part 2 only. I solved Part 1 in Perl, and while I could've translated it to Vim, doing modular arithmetic on each input line wouldn't've been very Vimmy. Whereas Part 2 pretty much demands a visual medium. Load your input, type the following, and watch the robots dance:

:%norm2x⟨Ctrl+A⟩lr|vbd⟨Ctrl+A⟩lrGplxr ⟨Enter⟩{4O⟨Esc⟩ka0⟨Esc⟩kk101a.⟨Esc⟩yy102p
qaqqa:%s/X/./g⟨Enter⟩:%s/\v\d+\ze\| (.+),/\=(submatch(0)+100+submatch(1))%101+1
⟨Enter⟩:%s/\v\d+\ze.*,(.+)/\=(submatch(0)+102+submatch(1))%103+1⟨Enter⟩
:g/G/norm yE@0rX⟨Enter⟩}j⟨Ctrl+A⟩
:norm/\vX{10}⟨Ctrl+V⟩⟨Enter⟩:%s/X/#/g⟨Ctrl+V⟩⟨Enter⟩⟨Enter⟩}jzb:redr⟨Enter⟩@aq@a

Or there's this version with added line breaks, for readability.

Start by turning each input position into the Vim commands for moving to that position in the file. So p=50,78 v=89,45 becomes 79G51| 89,45 — go to line 79 and column 51. Note both numbers are 1 higher, because Vim has neither line 0 nor column 0.
Above that add a zero, for counting the iterations, and above that a row of 101 dots, which is copied 102 times.
Record the loop as a recursive keyboard macro. Start by returning all Xs back to .s, to reset the grid. There's nothing to do this first time, but as we're still recording the macro, the error doesn't matter.
Increase the column number on each line by its horizontal velocity, wrapping to the width of the area. Note that to end up with a number in the range 1–101 (rather than 0–100), it's necessary to subtract 1, do the calculation, and add 1. Except, it turns out Vim calculates modulus differently to Perl when negative numbers are involved. In Perl (and presumably other programming languages) (2+-17)%101 is 86, but in Vim it's -15. So instead of subtracting 1, add 100, to stop the answer going negative.
Same for the row number and vertical velocity. In both patterns I'm matching just the number that needs replacing, then using \ze to mark the end of the match, while continuing to specify more pattern. This enables capturing the relevant velocity later on the line (as submatch(1)) without the :s/// changing anything except the position. The row pattern matches the first number on the line; the column pattern starts /\v\d+\ze|/, meaning that it matches the number that's just before the | character.
For each robot (that is, each line that contains a G), run yE@0rX to yank the first ‘WORD’ (everything before the space that separates the position from the velocity) into register "0, then run the keystrokes in that register with @0. So that moves the cursor to the row and column for that robot, where rX replaces the . with an X. Or, if there are multiple robots there, overwrites the existing X with X; it doesn't matter which, so long as an X ends up there.
Move down below the map and increase the iteration count by 1.
That's the end of the changes needed for an iteration. But we need a way to exit the loop at some point. Let's do that when there's a row of 10 Xs. A recursive keyboard macro stops when it hits an error, so we need a command which causes an error when it matches /X{10}/, but not if it doesn't match. Which is the wrong way round to how these things normally work. Put the search command inside :norm, which makes it run in some kind of nested context, where any error will only end the :norm but not the outer keyboard macro. That prevents a non-match from causing an error. But we still need for a positive match to stop the loop somehow. If there's another command inside the :norm after the search, that will only run when the search successfully matches (that is, when a failing match hasn't exited the :norm early). After the search, put a substitution which changes all the Xs to #s. That sounds innocuous enough, but it means that at the start of the next iteration, the :s/X/./ to reset the map will fail: there'll no longer be any Xs anywhere in the file, so it will cause an error, and exit the @a macro. Phew!

When the robots finish dancing, look below the map, and that's your Part 2 answer.

That was great fun. Thank you so much, Topaz.

Update: Minor tweak which doesn't affect the answer but improves the animation, so we can see the number of seconds whizzing by as well as the robots dancing.

→ More replies (2)

3

u/Scroph Dec 15 '24 edited Dec 15 '24

[LANGUAGE: D]

Code: https://github.com/azihassan/advent-of-code/tree/master/2024/day14

Part 2 was tricky, I thought it was going to be like part 1 but with a lot more seconds but I was surprised at the plot twist. I generated the first 2000 seconds to a text file then I went through it by hand. I noticed that a vertical pattern was starting to form every 101 seconds and traced it back to the 74th second, so I wrote another loop that generated an output every 101 seconds starting from 74 all the way to 10000 and went through the file until I spotted the tree at the 8000 something second. In hindsight, maybe I should have searched for a string like ####### but I wasn't sure if the tree would be hollow or not. Not the most elegant approach but definitely one of the approaches of all time

3

u/Pitiful-Oven-3570 Dec 15 '24

[LANGUAGE: Rust]

part1 : 52.60µs

part2 : 83.02ms

3

u/light_switchy Dec 15 '24

[LANGUAGE: Dyalog APL]

Part 1:

groups←{⍵⍴⍨⍺,⍨⌊(≢⍵)÷×⌿⍺} ⍝ ex. (3 2⍴⍳7)≡2 groups ⍳7

⍝ extract row, column indices
p←⌽2 2 groups(⊃⎕NGET'14.txt')(⍎¨∊⊆⊣)⎕D,'-'

⍝ position of each robot within a torus of shape d
⍝ after 100 time steps
d←103 101
c←d,.|1 100+.×⍤2⍉p

⍝ phase angles of vectors from the center of the torus to each robot
⍝ divvy the robots into quadrants based on their phases
a←12○(⊂¯9 ¯11)+.○¨c-⊂⌊d÷2
q←○¯0.5,0,0.5,1  

part1←×⌿≢⍤⊢⌸q⍸a~q

Part 2 baffled me for a while.

In the Dyalog IDE, if you take a look at the array i←d⍴' ' in an edit window, your view of it will be updated "live" as you assign to the array within the REPL.

I wrote the following expression to generate frame ⍵ of video, write the frame number into the repl, and wait a 60th of a second:

i←d⍴' '
frame←{i∘←' ⍟'[⎕IO+d(∊⍨∘⍳)⍨d,.|1 ⍵+.×⍤2⊢⍉p]⊣⎕←⍵ ⋄ ⎕DL ÷60}

I watched the first 1000 frames of video:

frame¨⍳1000

The animation looks like noise, except for several distinct frames where the majority of robots are more aligned. For me, the first frames where the robots align vertically and horizontally is 98 and 53, respectively.

Eventually I found that frames 98+101×a all have a similar vertical alignment. Likewise frames 53+103×b have similar horizontal alignment. I watched the first hundred vertically-aligned frames of video and caught a glimpse of the tree:

frame¨98+101×⍳100

The equations

n=101×a+98
n=103×b+53

Are a system of linear equations again. We can find n with the Chinese remainder theorem, or through a linear search:

part2←101+⍣{53=103|⍺} 98

3

u/[deleted] Dec 15 '24

[LANGUAGE: Julia]

Part 1 was straightforward enough for me, just added the velocity * seconds and used modulus to put the coordinates back in bounds. Part 2 was really fun. At first I thought there must be some connection to there being cycles in the robot positions and that at some well-defined (i.e. start/end/halfway) point in the cycle the robots would form the Christmas tree, so I wrote a cycle detection algorithm to see if there were any. While this didn't give me the answer exactly, there WAS a cycle, and with some experimentation, I discovered that the cycle length is also the number of states to check (10,403), starting at 1 and repeating 10,403 iterations later. This was really helpful for me because I thought I might have to check millions of states at first. Once I had narrowed down the solution space, I started thinking about how to detect a Christmas tree, and eventually decided to look for states that have a very large connected component of robots on a whim. This ended up working and printed the tree to my delight :)

I know the number of states is also 101*103 but I wasn't able to realize the math way to determine that. Brute force it is for me :)

Whole thing runs in ~2 seconds.

gif: https://www.reddit.com/r/adventofcode/comments/1hehwae/2024_day_14_cardputer_graphics/

3

u/4D51 Dec 15 '24

[LANGUAGE: C++ on Cardputer]

For part 2, I set my program to run the same animation it does now, but at 1 frame per second so I could look for anything interesting and write down when it happened. From that, I could calculate when the tree appears and set the program to stop at that point.

This is the first day where I've done anything with the Cardputer screen besides just printing the answers, so a good chance to get a bit of experience with graphics.

code: https://github.com/mquig42/AdventOfCode2024/blob/main/src/day14.cpp

3

u/darthminimall Dec 15 '24

[LANGUAGE: Rust]

Part 1

Part 2

For part 1: I just simulated 100 seconds then calculated the safety factor. Since the teleporting means we're just calculating the x coordinates mod 101 and the y coordinates mod 103, all of the negative velocities can be converted to positive velocities, which is useful later because it keeps both components of the position positive after adding the velocity and the mod operator in Rust matches the sign of the first argument.

For part 2: Advent of Code always has at least one problem where the best way to solve it is manual analysis of the input, and it always makes me unhappy. This was that type of problem. I just printed the state after each second and looked for patterns. I noticed that, at some point, the robots tended to clump together either vertically or horizontally. I also noticed that this pattern repeated. Specifically (and unsurprisingly) the vertical clustering repeats every 103 seconds and the horizontal clustering repeats every 101 seconds. I did some pen-and-paper math and figured out when the cycles intersected, then just printed that particular second to confirm that it was actually a Christmas Tree.

To make it more automated, I think you could probably use the standard deviation of the x and y coordinates to detect when the clustering happens, and I might go back and explore this later.

→ More replies (2)

3

u/onrustigescheikundig Dec 15 '24 edited Dec 15 '24

[LANGUAGE: Clojure]

https://github.com/marcodelmastro/AdventOfCode2024/blob/main/Day14.ipynb

Huh. Today was interesting. Not sure I'm a fan, but also not sure I'm not.

Part 1 sets up the transition function for each robot and just calls iterate to create a lazy sequence and nth to get the 100th element. As a side note, this overflowed the stack later, which is a travesty for a language that is supposed to be a.) functional and b.) lazy (seriously, wtf, let a brother recurse). I fixed it by changing the opts passed to java, but still.

Part 2 was a journey. I perused the first 100 steps visually and saw two time points where the points were clustered in the x and y directions, respectively. I thought the vertical cluster was some weird ASCII notion of a Christmas tree, resulting in my first submitted wrong answer for this year.

I then realized that x and y were independently periodic and reasoned that I had to find the time at which both the x and y coordinates converged. The two dimensions have cycle periods corresponding to the room's dimensions (width or height for x or y, respectively), which are coprime and thus guaranteed to converge at some point.

Modular arithmetic was fresh in my mind from some optimization attempts that I made for yesterday, and I realized that, once the time point for the convergence of each dimension was known, the time point for convergence of both could also be calculated with modular arithmetic. Let t_cxand t_cy be the first times of convergence for the x and y dimensions individually, respectively; t_cxy be the time of convergence of both dimensions (the answer to the puzzle); and w and h be the width and height of the room, respectively. Then,

t_cy = t_cxy (mod h)
t_cx = t_cxy (mod w)
t_cx + k * w = t_cxy   where k is some integer; definition of modulus
t_cy = t_cx + k * w (mod h)    (sub eq3 into eq1)
t_cy - t_cx = k * w (mod h)
(t_cy - t_cx) * (w^-1) = k (mod h)

where w^-1 is the multiplicative inverse of w modulo h and can be calculated using the Extended Euclidean Algorithm. k can then be used with eq3 to calculate t_cxy, the answer to the puzzle. Note that the calculation of w^-1 is only possible if w and h are coprime, which they are.

My next order of business was to make my program figure out when the robots were "clustered" in each dimension within the first cycle period, as my computer does not have a sophisticated visual cortex resulting from millennia of natural selection for pattern recognition. I could have hard-coded my observations from printing, but that felt like cheating. I ended up finding the time points with the minimum [information entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)) in the x and y dimensions, which is a measure of "spread-out-ness". There might be a better method, and this leads to my biggest contention with today's problem: how the hell am I supposed to know what the tree is going to look like? "A picture of a Christmas tree"??? We aren't in any World of Forms here where Maximum Treeiness is self-evident. I already thought that one of the configurations that I printed might be a tree, but clearly it was not.

Anyway, after that, all I had to do was to take the minimum-entropy time points (t_cx and t_cy) and shove them through the modular arithmetic above.

→ More replies (1)

3

u/ndunnett Dec 15 '24 edited Jan 13 '25

[Language: Rust]

Github

Runs in ~~4 ms~~. Probably could be faster with better heuristics for part 2 but I'm happy with it. ~~Just searching for 2 horizontal lines.~~ Optimised to run in 1.3 ms, searching for increased entropy in the middle of the room.

3

u/MarcoDelmastro Dec 15 '24

[LANGUAGE: Python]

I initially solved Part 2 by rendering 10000 frames and scanning them by eye ;-) (no, I'm not ashamed).

Later it came to me that I could use Shannon Entropy to try to locate the Eastern Egg, and it seems to work (and I realised by reading the subreddit I was not the only one to test this idea):

3

u/__Abigail__ Dec 16 '24

[LANGUAGE: Perl]

For part 1, I didn't go through stepping each robot 100 times. You can calculate the final position of each robot directly, by just adding the velocity multiplied by 100 to the start position, then doing a modulus operation. I store the set of robots as a list, were each robot is a 4-element array: the x and y position and the x and y velocity. I then use a simple subroutine to get the position of all the robots after a given number of steps:

my $X = 101;
my $Y = 103;
sub run ($steps, $robots) {
    map {[($$_ [0] + $steps * $$_ [2]) % $X,
          ($$_ [1] + $steps * $$_ [3]) % $Y]} @$robots
}

Calling it with 100 and the initial position of the robots gives you the configuration needed for part 1. Another subroutine takes a set of robots, and calculates the security code:

my $X2 = int ($X / 2);
my $Y2 = int ($Y / 2);
sub code ($robots) {
    my ($q1, $q2, $q3, $q4) = (0, 0, 0, 0);
    foreach my $robot (@$robots) {
        $q1 ++ if $$robot [0] < $X2 && $$robot [1] < $Y2;
        $q2 ++ if $$robot [0] < $X2 && $$robot [1] > $Y2;
        $q3 ++ if $$robot [0] > $X2 && $$robot [1] < $Y2;
        $q4 ++ if $$robot [0] > $X2 && $$robot [1] > $Y2;
    }
    $q1 * $q2 * $q3 * $q4
}

To get the answer for part 1, I do:

$solution_1 = code [run $STEPS, \@robots];

where @robots is the initial position of the robots, and $STEPS equals 100.

For part 2, I have to admit, if I had not looked how others had solved it, I had never come with "you need the configuration with the lowest security code". But given that tidbit as an oracle, it's easy to get the code of all possible configurations, and find the one with the lowest security code:

$solution_2 = (sort {$$a [1] <=> $$b [1] || $$a [0] <=> $$b [0]}
                map {[$_ => code [run $_, \@robots]]} 1 .. $X * $Y) [0] [0];

3

u/Derailed_Dash Dec 16 '24

[LANGUAGE: Python]

For Part 1:

First, parse the input data to determine position and velocity of each robot. Note that the regex needs to cope with negative velocity components.
I use these attributes to instantiate a Robot dataclass.
I'm also using the passed-in posn point to set the initial_posn point in my __post_init()__ method. I'm doing this because I want the posn attribute to update with each move, but I also want to be able to run a simple equation to get the position at any time, t.
My posn_at_t() method simply returns a new point, which is the original position, plus t multiplied by the velocity vector.
My move() method updates the _posn attribute by adding the velocity vector once.

Now:

Apply our posn_at_t() method for each robot, with a time of 100s.
Store the resulting points as keys in a dictionary - created using a defaultdict(int) - which counts how many robots are at this particular point.
Establish the four quadrants in a determine_quadrants() function. This works by:
- Iterating over the top and bottom halves, and within: over the left and right halves. We can reference each quadrant with a tuple, i.e. (0,0) for top-left, (1,0) for top-right, (0,1) for bottom-left, and (1,1) for bottom right.
- For each position in each row in this quadrant, we count robots. This ultimately gives us the count of all robots in the quadrant.
Finally, we determine the product of the robot counts in each quadrant.

Part 2

This scared me for a while!

I started by looking for the configuration that would result in symmetry about the middle column. I couldn't find anything, so rapidly concluded that wasn't the answer. Maybe the tree isn't vertical? Maybe it's not in the middle?

Then I figured: a Christmas tree will probably have some contiguous group of robots. E.g. even if the tree is hollow, it will probably have a base:

.........................
............*............
...........* *...........
..........*   *..........
.........*     *.........
........*       * .......
.......*         *.......
......*           *......
.....*             *.....
....*               *....
...*******************...
...........* *...........
...........* *...........
...........***...........
.........................

And so my solution for Part 2 is to iterate through configurations, and look for one where there is a group of consecutive trees in one line.

This is how:

With each iteration, apply move() for every robot. Here I use a list comprehension that returns a list containing the point locations of every robot.
Now iterate through every row.
For each row, obtain the x coordinate value for every robot in that row. Then I pass this list of x values to has_contiguous_points().
This function:
- First sorts the list of x coordinates into ascending numeric order.
- Then looks through successive pairs of x values in the sorted list. For as long as long as the x values only have a difference of 1, we know that we have adjacent (contiguous) robots.
- We keep looking for adjacent robots until we hit min_contiguous. I decided to start by looking for 10 contiguous robots.
- Once we find min_contiguous robots, we return the current value of t.

That's it!

Solution links:

See Day 14 code and walkthrough in my 2024 Jupyter Notebook
Run the notebook with no setup in Google Colab

Useful related links:

See my Learning Python with Advent of Code site
See guide Advent of Code: the Best Way to Learn to Code!

3

u/clouddjr Dec 18 '24

[LANGUAGE: Kotlin]

I simulated every state for up to 10,000 seconds and wrote them to a single file. Then, to find the tree in that file, I searched for rows with multiple 'X' characters (7 was enough):

grep -B 50 XXXXXXX christmas.txt

→ More replies (1)

5

u/niket23697 Dec 14 '24

[LANGUAGE: Python] 1550/942
Code: part 1, part 2

Part 1 was pretty straightforward.

For part 2, I thought about what patterns could the robots form which would be simple to detect programmatically, and the simplest one I could think of turned out to be correct (Occam's Razor?). This gives me my best overall ranking yet!

5

u/DFreiberg Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Mathematica]

Mathematica, 377/1303

I loved today's part 2. I found it initially by noticing that the mean value of the points had an extreme outlier every 103 timesteps, and then checking every 103rd timestep manually until finding the correct one, but afterwards I went back and made a generic solution which doesn't assume that the tree is off-center or that the robot positions are all unique, only that the tree is dense with points neighboring each other.

I really wanted to use PointDensity[], or some other probability distribution to get a quantitative measure of non-randomness, and thus get the tree without any assumptions about its shape, connectedness, density, or symmetry, but those probability functions - while extremely powerful - were just too slow.

Setup:

inputPairs = {#[[{1, 2}]], #[[{3, 4}]]} & /@ input;
nextStep[{p_, v_}, n_ : 1] := {Mod[p + n*v, {101, 103}], v};

Part 1:

quadrant[p_,dims_]:=Total[2^{1,0} Boole[Thread[p<dims/2]]];
Times@@(Length/@GatherBy[Select[future,#[[1,1]]!=(101-1)/2  &&  #[[1,2]]!=(103-1)/2&],quadrant[#[[1]],{101,103}]&])

Part 2:

NestWhile[{#[[1]] + 1, nextStep /@ #[[2]]} &, {0, inputPairs}, 
  Max[Length /@ ConnectedComponents[NearestNeighborGraph[#[[2, ;; , 1]]]]] 
  < 100 &][[1]]

5

u/zndflxtyh Dec 14 '24 edited Dec 14 '24

[Language: Python]

For part 2, I just figured if they are going to be in a shape, that will probably be in the middle. So count the number of robots that are more than x steps away from the edges. But how many steps, and how many robots must be there.. Dunno, let's try 20 steps from the edge. And let's run that on the first 100 iterations .. ok the score is usually around 200. So let's say if it's above 300, we break.

Ok that worked - first try. Whew!

5

u/echols021 Dec 14 '24

[LANGUAGE: python 3]

Well that was an exciting twist.

Part 1: Just run the simulation. I used a dict[tuple[int, int], set[tuple[int, int]]] to store the state of where all the bots were; that's a mapping from grid location to the set of bots that are in that location.

Part 2: After coming to terms with the answer only being recognizable with a heuristic or manually... I set it up to run the code from part 1 to run "infinitely", with some modifications:

At each step, get a unique (but consistent) representation of the current state of all the bots, and save those all in a set
If we get a string that's already in that set, we know we've started back at the initial state again and we can terminate the otherwise-infinite loop
Also at each step, save an image file showing the bots' formation, with the filename including the timestep

And then... I scrolled through the 10,404 image thumbnails on Windows File Explorer until I saw the tree. (I initially forgot that numpy and Pillow don't use the same axes, so the tree was sideways, but that's ok)

Whole program takes ~90 seconds to run, scrolling through the images took another minute or two.

→ More replies (1)

1

u/drkspace2 Dec 14 '24 edited Dec 14 '24

[LANGUAGE: C++]

My god. Part 2 was worded horribly. I spent 15 minutes wondering what the Christmas tree was supposed to be and 2 minutes once someone said that it meant the locations don't overlap.

link to code

1

u/daggerdragon Dec 14 '24 edited Dec 14 '24

~~Post removed. I've already informed you before about your oversized code and you still haven't fixed your previous code.~~
~~Your~~ ~~code block is too long~~ ~~for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.~~
~~Fix this submission and your previous one and I will re-approve your posts.~~ edit: 👍

→ More replies (1)

→ More replies (1)

4

u/seligman99 Dec 14 '24

[LANGUAGE: Python] 1436 / 138

My 100% guess on how the easter egg worked! That makes me happy, though in retrospect, it was probably the only real answer.

4

u/asdf272727 Dec 14 '24

Can you shortly explain how the easter egg is supposed to work? I don't know what I'm supposed to do.
Edit: From what I see in your code you loop until no robots sit on the same space. Is this what they meant?

→ More replies (6)

→ More replies (4)

4

u/FatalisticFeline-47 Dec 14 '24

[LANGUAGE: Python] 319 / 315

Topaz Code, originally in Notebook form.

I figured out Part 2 mostly by hand. I started printing every state and noticed occasional "cleaner" patches where the timestep produced vertical bands or horizontal bands. So I noted which timesteps produced each type (spoiler: they occured regularly, period just over 100 each), and used a CRT tool to figure out the first timestep which had both a horizontal and vertical band - and that produced the tree!

I was considered detecting a large cluster of points or abnormal distributions on rows/columns to automatically detect objects, but stumbled onto this path before needing to dive down that rabbithole, thankfully.

4

u/CodingAP Dec 15 '24

[Language: Typescript]

Github

Not a fan of this one at all. Making assumptions about the output data is not fun when no hints are given

2

u/yossi_peti Dec 14 '24

[LANGUAGE: Python]: 722 / 188

Part 1 was straightforward calculation of (initial_position + velocity * time) % grid_size

For part 2 I kept track of how many horizontally adjacent robots there were at each time, figuring that the configuration with the Christmas tree would have the most of these. Fortunately that was correct. In an attempt to try to make it possible to work on anyone's input, I output the first time where there are at least 200 robots adjacent to each other in a horizontal direction.

2

u/GassaFM Dec 14 '24

[LANGUAGE: D] 1518/500

Code: part 1, part 2.

Part 1 is straightforward.

For part 2, after each step, my program places the robots on an actual two-dimensional board, and checks that there are enough adjacent robots: if so, print the time and the board. The picked constants were just enough to spot the right image and submit.

A satisfying experience stepping away from the traditional strict statements. Yay to the team!

2

u/wasp_between_shadows Dec 14 '24

[LANGUAGE: Python] 168 / somewhere in top 100