Advent of Code 2022 Day 12 (BaseA Style)

Discussion thread for day 12 of the Advent of Code - https://adventofcode.com/2022/day/12

Accepted answers

All comments

D12 reminds me of another path-finding question in last season, and this is when we start to explore the limit of Alteryx as a "pseudo programming language", I think.

I think the method I used is closest to the "Breath-First Search (BFS)" algorithm (TBH when I did the workflow I did not know this is called BFS). This algorithm is considered greedy and probably is the reason it took 16.8 seconds to run Part 1 but a whopping ~50min to run part 2 on my laptop (Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz, 8GB RAM). There is definitely a more efficient BaseA solution and I look forward to see the solutions by the wizards amongst us :-)

Spoiler

Main

Part 1 macro

Part 2 macro (which uses part 1 macro)

DawnDuong

Inspiration struck when I was having dinner with my husband... so I flipped the workflow to a reverse Dijkstra and voila both part 1 and part 2 finished together in 40 seconds. See hint in the spoiler 😎

Spoiler

Nothing fancy. I just flipped the methodology to go from E to S (instead of going from S to E). Both part 1 and part are now on the same order of magnitude. In fact, Part 2 finishes faster than part 1 in this reverse Dijkstra method because the termination happens earlier as part 2 terminates at either S or a whereas Part 1 only terminates at S.

patrick_digan

It took a couple tweaks to keep the macro from blowing up the count.

Spoiler

I just go from one spot to the next and found a couple ways in the macro to keep the record count down. First I implemented a second iterative part by reading and writing to the same file. This helps prevent it from visiting the same spot twice. I also added in a unique in the macro to again prevent going to the same spot.

Workflow:

Macro:

Day12part1.yxmc

Day 12 part 2.yxmd

Jean-Balteryx

Day 12 done ! ✔️

It's not pretty, it doesn't even fully work, but it gives the solution ! 👌

Workflow

Spoiler

Macro

Spoiler

AkimasaKajitani

I finishes today'ss challenge using Breadth First Search algorithm. Today, I didn't have a concentable time because of my work. As a result, I did this challenge after the work.

Spoiler

The difference between part1 and 2 is only input data. So I use the same macro in part1 and 2.

Macro:

mmontgomery

Not an easy one and h/t @patrick_digan 's solution for removing already-seen paths, which was my main struggle.

Spoiler

Built out the relationships using the formula tool for adjacent points and find/replace to map the current point position to adjacent points. The final part was adding interface tools to the macro to pick row/column. To find matches, I did a regex count matches of "," to an additional macro output that wrote out each relationship on each iteration. Since the removing matches was part of a file that read/wrote to itself, it was run once initially then disabled when the macro was run.

P1/P2 difference was changing the "start -change value here" filter before the macro

clmc9601

Thankful for @patrick_digan 's hint about keeping rows from exploding. My original solution was very close but couldn't keep the row count small enough.

Spoiler

It took me a while to understand why the unique worked. Turns out, it doesn't matter *how* the path reached any given location, as long as it did so in the same number of steps as another path variation. Then, you only need one of those path variations.

Workflow:

Screen Shot 2022-12-12 at 5.22.46 PM.png

Screen Shot 2022-12-12 at 5.22.46 PM.png

Macro:

Screen Shot 2022-12-12 at 5.11.34 PM.png

AncientPandaman

thankful for @patrick_digan for the tips.

Spoiler

workflow:

macro:
add a message tool as a stopper when have a solution.

JarekSkudrzyk

thank you for the tips - I have used Djinkstra with slight modification and finally managed to solve the issue

Spoiler

makro:

DataNath

Finally caught up on Day 12! Part 1 was incredibly quick to run... The time taken for part 2 to complete shall remain a secret other than to those that were present in the Alteryx friends & AoC virtual happy hour!

Spoiler

Batch macro to load in all a starts:

Iterative macro - generates possible next steps for the current tile until an end is met:

Part 1 was the same approach without the batch!

Edit: Upon reversing the logic and starting from the End - as suggested by @DavidP and others - my Part 2 actually ran in 18.6 seconds which is a whopping 1,490 times faster than my first attempt!

Day 12.yxzp

DaisukeTsuchiya

Spoiler

SeanAdams

OK - so this took 1.5 days but it's done. Main snag was a silly logical error on part 2 where instead of running the part 1 once for each new starting point, I was running it once per each cell in each starting point.

Solution summary in spoiler below.

Spoiler

So - the key to part 1 is to do a path-finding algo.

Algo
- Start from a specific cell (s) that you want to investigate (and remember the least cost of getting to this cell).
the first time round, this is only your S cell, and the min cost is 0
- Then figure out which cells you can potentially go to next
- Then look at these cells - if you've never been there before, or if you've now found a cheaper way of getting there than you had previously - then mark these as "good to investigate"
- Repeat from step 1

Eventually you will run out of cells to investigate, and you'll have the minimum cost of getting to every cell from the starting point.

Data Prep:
To do this - I did 2 stages of prep:

Firstly: take the puzzle input into a matrix of cells:

which looks like this:

BTW - using the cell ID instead of Row and Column comes in handy for speed.

Valid moves:
Then I wanted to figure out which were valid moves - so that during the working phase I didn't have to do this every time.

This is pretty simple - it just takes every cell; joins it to each of its neighbours and checks if the move is valid ( based on height).

This gives you a simple list of which transitions from cell X to cell Y are allowed.

So - now we know the starting point, we know which moves are valid - now we just need to do the algo above:

Although this may look kinda complex - it's actually pretty practical:
- The top input is all the cells on the map - with some of them marked as "Investigate"
- The bottom input doesn't change - it's just a list of the valid moves

- Take these "investigate" cells and go to any neighbours which are valid moves.
- if you've been there before via a different route, and this way is cheaper - then mark this neighbour for investigation next round
- if you've never been there before - same
- if this is more expensive than previous attempts - ignore this
- Join this back to the non-investigate nodes and repeat until you have nothing more to investigate

Part 2:

For part 2 I was SUPER lazy. I just looked for every cell that had an 'a' in it, and marked this as the start "S" and ran part 1. So essentially - this was just running part 1 x 1600 times with different starting points.

Day12_Dirty.yxzp

DawnDuong

I meant to post this earlier, but kept forgetting. Here it is, at last, the "reserve Dijkstra" macro that helps me solve both part 1 and part 2 together in 65 seconds :-) @Mildman

I used this same macro, with some modifications to solve for one or two other AoC too.
Cheers,
Dawn.

Testing reverse Dijkstra.yxzp

caitlynmcintyre

just submitting my backlog of old challenges

Spoiler

AoC Day 12.yxmd

NewMacro1.yxmc

Quick Links

This months top contributors

atcodedog05 19458

Qiu 15866

binu_acs 15708

MarqueeCrew 13708

apathetichell 13703