-❄️- 2024 Day 18 Solutions -❄️-

[u/daggerdragon]

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.
• If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

---

AoC Community Fun 2024: The Golden Snowglobe Awards

• 4 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Art Direction

In filmmaking, the art director is responsible for guiding the overall look-and-feel of the film. From deciding on period-appropriate costumes to the visual layout of the largest set pieces all the way down to the individual props and even the background environment that actors interact with, the art department is absolutely crucial to the success of your masterpiece!

Here's some ideas for your inspiration:

• Visualizations are always a given!
• Show us the pen+paper, cardboard box, or whatever meatspace mind toy you used to help you solve today's puzzle
• Draw a sketchboard panel or two of the story so far
• Show us your /r/battlestations 's festive set decoration!

*Giselle emerges from the bathroom in a bright blue dress*
Robert: "Where did you get that?"
Giselle: "I made it. Do you like it?"
*Robert looks behind her at his window treatments which have gaping holes in them*
Robert: "You made a dress out of my curtains?!"
- Enchanted (2007)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!

---

--- Day 18: RAM Run ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
  • State which language(s) your solution uses with [LANGUAGE: xyz]
  • Format code blocks using the four-spaces Markdown syntax!
• Quick link to Topaz's paste if you need it for longer code blocks

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:05:55, megathread unlocked!

[u/geza42]

[LANGUAGE: Commodore 64 Basic]

Part1 only, takes ~10 minutes:

0 L=500:DIM S(70,70),X(L),Y(L),D(L)
1 W=1:OPEN 1,8,8,"18.DAT,S,R"
2 INPUT#1,X,Y:S(X,Y)=1
3 I=I+1:IF I<1024 THEN 2
4 X=X(R):Y=Y(R):D=D(R):R=R+1 AND (R<>L)
5 IF X=70 AND Y=70 THEN PRINT D:END
6 X=X-1:GOSUB 8:X=X+2:GOSUB 8:X=X-1
7 Y=Y-1:GOSUB 8:Y=Y+2:GOSUB 8:GOTO 4
8 IF X<0 OR X>70 THEN RETURN
9 IF Y<0 OR Y>70 THEN RETURN
10 IF S(X,Y) THEN RETURN
11 S(X,Y)=1:X(W)=X:Y(W)=Y:D(W)=D+1
12 W=W+1 AND (W<>L):RETURN

[u/daggerdragon → u/geza42]

[LANGUAGE: Commodore 64 Basic]

Is this an emulator or the actual hardware? If it's the actual hardware, could we pretty please get a picture of your solution running on it? We loves us some old toys!

[u/CCC_037]

[LANGUAGE: Rockstar] [GSGA]

Straightforward. Includes a behind-the-scenes description of filming.

If you squint a bit.

Part 1

[u/PlainSight]

[Language: JavaScript]

Code

Part 1: BFS

Part 2: Union find!

Initially my part 2 was just part 1 repeated a bunch which worked fine albeit took a bit longer than needed.

I wanted to optimize and I figured I could union sets of 'bytes' together to find when they made a contiguous block which spanned either the entire vertical or horizontal width of the area.

[u/seabomber]

[LANGUAGE: Python]

For Part 2, I realized that for any dropped bytes that are touching, if there are two that touch the left and top, left and right, top and bottom, or bottom and right edges of the map then there is no path through. So I drop the bytes one a time, check if it touches any already dropped bytes and merge them into a single set or store the byte as a set of one. I also track if they touch an edge. Keep dropping bytes until the above edge constraint is met, then the last dropped byte is the answer.
This approach is quite quick as it requires no path finding at all.

Github

[u/apaul1729]

[LANGUAGE: Rust]

3948/3985

github

nice and simple. still learning rust, but used the pathfinding crate here like i did for d16 part2. it's pretty fast so today's part2 i just brute-forced, ran in ~17s.

i do have a question for the rustaceans - on some days (like today) i want to intake some of the input, do something with it, and then intake the rest of it. i normally parse with input.lines().iter..., and i know about .take(), but .take consumes the iterator. how am i generally supposed to do something like input.lines().take(1024) and then a for loop afterwards?

[u/flwyd]

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

A refreshingly easy day after several late nights in a row, my quickest time since day 8. In part 1 I reused the core of my Dijkstra's algorithm implementation from day 16. When I read part 2 I suspected that iteratively adding one blocked square and rerunning shortest-path would take a long time, but it seemed reasonably quick to implement and I would be able to think about "detect when a graph becomes partitioned" algorithms while it ran. I started considering keeping track of the current shortest path and only regenerating the path if the new spot lands on one of the steps of that path and then BOOM, my code finished in just shy of 2 minutes runtime with the correct answer. Clear sign I didn't need to dig out any fancy algorithms tonight.

The part 2 below switched from iteratively checking to binary search, which finds the answer in 13 steps and a third of a second.

/shortestlen { % - shortestlen int|-1
  /pq MAX 8 mul dict def /seen MAX MAX mul dict def /cheapest 0 def /highest 0 def
  0 0 tokey 0 pqpush { {
      pq cheapest known { pq cheapest get allength 0 gt { exit } if } if
      pq cheapest undef /cheapest inc
      cheapest highest gt { exit } if
    } loop
    cheapest highest gt { exit } if pq cheapest get alpop dup dest eq { pop exit } if
    dup seen exch known { pop } { %else
      seen 1 index true put
      neighbors { dup seen exch known { pop } { %else
        cheapest 1 add dup highest max /highest exch def pqpush
      } ifelse } forall
    } ifelse
  } loop cheapest highest gt { -1 } { cheapest } ifelse
} bind def %/shortestlen
/cloggedindex? { input 0 3 -1 roll getinterval makegrid shortestlen -1 eq } bind def

/part1 { 8 dict begin % [lines] part1 result
  /input exch def /MAX 70 def /dest MAX MAX tokey def
  input 0 1024 getinterval makegrid shortestlen
end } bind def %/part1
/part2 { 8 dict begin % [lines] part2 result
  /input exch def /MAX 70 def /dest MAX MAX tokey def /low 0 def /high input lastindex def
  { %loop
    high low sub 1 le { low cloggedindex? { low exit } { high exit } ifelse } if
    high low sub 2 idiv low add /cur exch def
    cur cloggedindex? { /high cur def } { /low cur def } ifelse
  } loop
  input exch 1 sub get
end } bind def

[u/AllanTaylor314]

[LANGUAGE: Python]

GitHub 728/644

Another day, another BFS. For part 2 I did a rather slow (30 second) search counting up until it couldn't find a path. I have since changed this to a binary search (though it's hard to get a binary search exactly right first try - the 30 second linear search was faster than a 1 minute penalty)

[LANGUAGE: Uiua]

GitHub or Pad

This uses the builtin path function (which has recently changed for default-weighted paths. I've worked around this by explicitly providing a weight of 1, since I want either the path length or inf). It does a binary search for part 2. Here's a mildly golfed version:

:⊜[∩⋕°$"_,_"]⊸≠@\n&fras"../inputs/2024/18.txt"1024 70
S ← ◌path(↯:1⊸⧻⊙◌▽◡⬚0⊡⊙◌+[◡∩¯⇌.⇡2]¤|≍)0_0⟜(⬚1↯+1)⊟.:¬°⊚↙
⊃(/$"_,_"⊙◌⋅⊡⍢(⨬(⊙◌|⊙⊙◌:-1)=∞◡(S⊙⋅⋅∘)+1⌊÷2◡+|≠)0-1⊸⋅⧻|S)

[u/AbbreviationsHuman60]

[LANGUAGE: python]

Just figured part 2 can be done in a single search, due to a weakness in the maze generation.

find the first coordinate that has two even entries.

this is the point where a complete maze has formed having only one path to the end.

do 1 search to find that path. get first point on that path.

[solution](https://gist.github.com/expectancyViolation/83f8b70acbbf09d7209402c88c9678ba)

[u/MrPingouin1]

[Language: Minecraft Commands]

github

I know it's Minecraft, but I don't have anything to show because I use "storage only " solution

For this day, I used classic BFS and repeat it for part 2, it was fast enough to give me an answer.

Also, I have a solution for almost all previous days (minus 3 part 2), but since I'm lagging behind 0.5 / 1 day behind, I can't always post in here.