Advent of Code 2024 Day 18 (BaseA Style)

[AlteryxCommunityTeam]

Discussion thread for day 18 of the Advent of Code - https://adventofcode.com/2024/day/18

[ScottLewis]

Had fun with this one. If you struggled with it, take some time to look through other people's solutions. The skillset here, around iterative macros, distance calculations and checking for any possible path (vs. checking for the best one) comes up over and over on Advent problems and this one is a good example because it doesn't really have any extra complications.

Spoiler

Building the grid is just generate rowsx2 followed by a join with the coordinates of the obstacles. 
After that, part 1 is a pure form of path trace. Check every direction, throw out anything that is less efficient than an existing step. The fancy (right in a production world) way would be to keep a whole grid and compute shortest path to every point. The fast hack way is just to not track it and just prune less than shortest paths at each step. The difference is that the hack way goes around in circles behind the leading edge and doesn't terminate but you just set it to a reasonable number of iterations and if you see you've guessed high stop the workflow and lower the iteration count. 
Part 2 was more interesting. You could nest macros to either check everything or, more interestingly, check for the destination being reachable and go halfway to the next known opposite value each time. Or you could just build something that checks a number, do the  
A+ 1/2(B-A) bit yourself and find it in somewhere around log2N time, which unless you've mad skills is probably faster than writing the extra layer of macro.
My method of checking for the destination being reachable was a fill macro. This is something that came up a few times last year and will probably be useful at least one more time this year. You track the whole grid, but instead of distance you're just marking every location you can reach. You check for a count of new reachable spaces and if that count is ever 0 you've filled every possible space. Then you just check for destination filled. 

[gawa]

Part2 was not so difficult than I thought it would be while solving part1. 

Spoiler

Part1: Number of the candidates of path will be extremely increasing around mid-way of the path while they have less candidates near start/goal points. In order to find the best path, we need to wisely calculate. Basically the similar approach with Day16 can be applicable.

Part2: If calculation to find the path for part1 is very fast, we can try brute force until path is not made. In my case, calculation speed for part1 was slow, so I change approach and used Make Group tool. If the path from start to goal is discontinued, start and goal will fall into different groups, provided that we make grouping by adjacency=1. Even with this approach, it takes a lot of time to execute brute force, so I started to try with threshold for every 500, 100, 10....and come closer to the target answer gradually. I'm a lazy guy.

[CoG]

This one was fun. Got to re-purpose an older workflow, then nearly tried brute forcing Part 2, but I caught myself after 3 iterations, and realized there was a much better way!

Spoiler

Today's problem is very similar to D16 with the Reindeer. So much so, that with a few touch-ups I was able to use the same macro from that problem to solve the maze in this problem (i.e. the score needed to increase by one for every move to track the minimum distance to solve the maze):



But the second part is interesting. When is the path first obstructed? The answer is clear: this occurs when our maze solver finds no minimum distance to solve the maze. But how can we tell? when this occurs for the first time. As mentioned previously, brute force could work but will take forever, and I have meetings tomorrow that I need a good night's sleep for.

Enter in the Binary Search!!! Another very power algorithm. instead of linearly & sequentially searching each obstruction. we can instead add half of the bytes as obstructions. If a valid solution exists, then disregard every case with fewer obstructions since we are guaranteed a valid solution there too. If no maze solution exists, then disregard all solutions with more obstructions because we will still be blocked. Thus, with one check, we have eliminated HALF of the search space! Now that's efficient. But's what's to stop us from performing this process again on the remaining half? Laziness is our only enemy, but we are proactive fellow solvers, so we press forward. Every iteration we remove another half of cases until we are left with only one case to check, which is our answer. My macro found this solution in only 11 iterations! That blows my mind. This process sifted through thousands of mazes to identify the correct answer in just 11 "guesses".



As an added efficiency bonus, we can start the search from Byte 1025 (since we already know from part 1 that there is a valid solution after the first KB of obstructions.

[Tokimatsu]

P1 was solved by very similer way with my day16 soltion.

Spoiler

P1 and P2

 

 P1 macro

p2 called the macroed p1 workflow.　Checking every half point of rest of puzzle input.
 
macroed P1

 

[ntakeda]

My solution. 

Spoiler

My workflow is extremely terrible, so I do not provide an explanation.

  

[mmontgomery]

Day 18. More in spoiler

Spoiler

P1: D18 was very similar to D16 so was pretty straight forward - the only difference is to optimize for steps instead of points
P2: Trial and error on the magic number and splitting difference until I got there. Took me 14 trials

[Hub119]

See above responses for much smarter solutions to part 2... but because I started this last night and quickly finished part 1 before going to bed, I thought I would see what the computer could do overnight while I slept with the brute force approach... turns out it works (just takes several hours).  Posting this solution just to show that is CAN be done this way, not that it SHOULD be 🤣.

Spoiler

Workflow

Spoiler

P1 Macro

Spoiler

P2 Macro

[PangHC]

brute force but in reverse way. (from not clear to clear) 

I believe it faster because it blocked (only explore half of the map, even lesser), and cause each iteration take is lesser time. 

and the answer is near the end also, so it another huge time save.🤣 

runtime 15mins, still long but i satisfied.

[DaisukeTsuchiya]

I was able to utilize the workflow from Day 16. 

Spoiler

P1 was relatively straightforward, but I struggled with P2 as I couldn’t get the correct answer for quite some time. As the number of loops increased, the behavior became odd, so I displayed the maze in Excel to manually create one correct route. This helped me identify points where logic was wrong and I fixed the bug. It turned out there was a very simple bug that I hadn’t noticed in either Day16 or Day18 P1.

For P1, it runs within 100 iterations and completes in 37 seconds. Since the iterations for P2 reached nearly 200, I split the macro so it would stop as soon as even one route was found. P2 requires try and error but P2 can run in 1 sec.