Advent of Code 2023 Day 10 (BaseA Style)

Discussion thread for day 10 of the Advent of Code - https://adventofcode.com/2023/day/10

Accepted answers

All comments

Cool problem, good applications from Graph theory. Kind of "cheated" (brute forced/found a pattern in the data) to speed up initial solving time. Then went back and improved the Workflows to make them more generalized.

What follows is the algorithm I used in addition to pictures of my workflows (read at your own risk)

Spoiler

For part 1, it is assumed that the point S has exactly 2 connections (otherwise the loop wouldn't quite be continuous and you risk creating multiple interior points, which would make Part 2 much more difficult). Thus we simply need to find which neighbors of S could be connected (example: The only pipes that would be valid connections to the left of S are ("-", "F", "L")). By finding these 2 connections, I figured it would be simpler to trace the entire path than traverse both sides until I met back at the opposite side, so I select only one connected neighbor (doesn't matter which), keep track of which direction the pipe is moving, and then traverse the entire loop of pipe until I return to S. The answer to part 1 is however many pipes we went through along the way divided by 2 (It is a fun and simple challenge to show that for a grid setup like this, the total path length will always be even).

For part 2, we now make use of some data we collected as the loop of pipe was discovered, namely whether we turned left, right, or not at all (denoted -1, 1, 0, respectively). The trick here is that if you add all the turn values together, you can determine which side of the loop of pipe the interior is on since the interior will always be on the same side as the loop is traversed (To better understand this principle: imagine standing at the edge of a swimming pool such that the pool is to your right. If you then begin walking all around the pool to get back where you started, the pool will always be to your right). The reason that the sum of all the turn values allows you to know which side of the path is the interior is that in order to walk around the interior of a loop, you will necessarily have to turn more in the direction of the interior than you do away from it. Simplifying the pool example, imagine you stand next to a square pool with the water on your Right. Walking around the pool, you will have turned Right 4x before returning to the start.

Now that you know which side of the loop the interior is on, you can determine which interior points are immediate neighbors pipes in the loop and then do what is essentially a Breadth First Search (BFS) of all of those points to get all interior points of the loop. The count of those points should give you your answer.

Workflow:
Screenshot Main Workflow.png

Build Pipe Loop Macro:
Screenshot First Macro.png

Find Interior Points Macro:
Screenshot Interior Points Macro.png

Solution.yxzp

kelsey_kincaid

Coordinates always trip me up, but I am proud of my part 2 solution which I was able to accomplish in a few tools after my original macro. As a bonus I got some really neat visualizations from it. I'm slowly getting better at iterative macros and coordinate problems like these!

Spoiler

Part 1: I used generate rows to create a mapping table of each cell & value to each adjacent cell & value. Then I used a mapping table that I created to determine which adjacent cells contained valid values along the loop. From there, I used an iterative macro to loop through each cell in the loop, and divided the length of the full loop by 2 to get the answer. I think there are more optimal ways to do this calculation, and I'd like to explore it when I'm fresh.

Part 2: Yay spatial tools! Created points for the points along the path, built a sequence polygon, and then used a spatial match to determine which points were within the polygon. I beat my head against a wall trying to figure out how to determine which points were bound by the loop within my iterative macro, until I remembered the amazing spatial tools available in Alteryx

It took me a bit to figure out how to get my iterative macro to output the points in the correct sequence, but a very simple tweak fixed that for me (after lots of trial and error).

Workflow:

Mapping table of valid path values:

Iterative Macro:

Spatial Visualization of my pipe loop:
D10 Loop Map.jpg

Visualization of the points bound within the pipe loop:
D10 Matches.jpg

AOC2023_Day10_KelseyKincaid.yxzp

DaisukeTsuchiya

Day10 is so hard again.
It took 4.5 hours to create WF but process is completed in 2min for P1 and P2.

Spoiler

Gawa

My Sunday comes to an end while solving this.

Spoiler

What's going on in this WF? I don't remember.

patrick_digan

Spoiler

I did normal x/y coordinates for part 1 but spatial for part 2.

Day10part2.yxmd

Day10part1.yxmc

AkimasaKajitani

Tough challenge.

Spoiler

I could not think of a way to do Part 2 other than to use the spatial tool.
The macro to search for routes was also completed after some twists and turns, but it took quite some time until it worked properly. And my workflow is also messy.

JeffF

Spoiler

A Spatial Solution. Part 1 ran in under 2 minutes and part 2 ran in under 1 second.

Solution

Part 1 macro

Part 2 map

Gawa

Make Group tool is useful in case like D10P1. Here is how to create groups with Make Group tool without macro.

Spoiler

Overall WF

1) Create X-Y coordinates as usual
2) Create 'neighborhood' coordinate by two Generate Rows tool for X & Y respectively. For D10P1 case, they can have 2 neighborhoods.

3) Find the ID of neighborhood points, and create ID-ID mapping table

4) Count ID-ID combination, and if count=2 those ID-ID pair is deemed connected.
5) Go to Make Group tool, and you get grouping data like this

Day10_part1_MakeGroup_tool.yxmd

SuguruYoshinaga

Very hard challenge.

Spoiler

macro for Part 1

Macro for Part 2

day10.yxzp

DataNath

Finally caught up on day 10! Really enjoy the challenge of these grid problems and thinking how best to tackle them whilst limited to table structures in Alteryx. Part 1 and 2 macros are very similar - I just added an extra print output of the co-ordinates of each iteration so that I could build a polygon and conduct spatial matching for P2.

Spoiler

Day 10.yxzp

mmontgomery

Good lord this took me a while

Spoiler

kelsey_kincaid), I built two separate polygons based on my two paths. After that I combined the objects and compared them to my '.' data points.

My P1 approach was to define the pieces as 'match' or no match based on the prior step, current step, and next step (long formula below). Also, I created a yxdb to read from/write to with updated path info to ensure the same coordinate wasn't used twice. So I populated the .yxdb first, then disabled the container and ran the macro

2023_Day10.yxzp

ccanterman

FINALLY got Day 10 done. I was busy on Sunday and missed this and finally had a chance to get it done.

I appreciate @kelsey_kincaid posting their solution. I got to the Spatial Match on Part 2 and wasn't sure what to do with the output

Spoiler

alisonpitt

I knew I would get to use spatial tools sooner or later! I feel like this is one where Alteryx definitely makes part 2 easier. NOT that it was easy 😅

Spoiler

Part 1 - since we know it's a closed loop, traverse paths until you hit a coordinate you've hit before, sum up the steps on the intersecting paths and divide by 2. Ish.

Part 2 - this time I retained the whole path in a big old string with the sequence of directions...and stuck the two paths end to end (reversing the second one to create a full loop). Then I used spatial tools to find all the points inside the polygon but not on the border, and counted them up.

Update - I just HAD to render the final map because it felt like such an achievement when I finally got there!

Day 10 - AP.yxzp

AncientPandaman

think of spatial for part2 but no luck, thanks @kelsey_kincaid

Spoiler

part1:
no idea why it run for 2~ minutes.

part2:
go for spatial to get right answer
and after that I search in YouTube got one comment is said
just x2 the map, free up the space and use fill-up the tank method.

built for both methods.

Day 10.yxzp

Watermark

D10P2 -

This hot rod runs in a smokin 0.8 sec!!

Spoiler

AOC 2023 Day 10P2v2.yxmd

DaisukeTsuchiya

I post again with solution in yxzp.

Spoiler

Day10.yxzp

SeanAdams

Tunnel problems – really allows you to dig into them <wah wah wah>

Part 1 was pretty brute force – and ran in 6:28

Part 2 I gave up on computational approaches (I need to go an look at other people’s solutions) and used spatial – worked like a charm.

😊 oh, and got to use control containers here too!

Details in the spoiler below.

Spoiler

Part 1:

Really just 2 steps:

First prep the data – just break this into rows and columns
Then go into an iterative macro that generates all combinations of moves from that starting position.
Before we go into this – we set the starting position and mark this as current (i.e. being processe)

Find paths macro:

The way this works is that from each current point, you look at where you can move to – if there are no possible moves then exit

The explosion to possible moves happens in the join and in the formula immediately after it

The output of this is a list of all the tunnel pieces (from X to Y) and an engine iteration number. The highest engine iteration number is also the furthest point from the start since it took us the most steps to get there – so the problem is solved.

Part 2:

So – we’re coming into Part 2 with all the tunnel pieces – however I couldn’t figure out a pretty way to computationally see if something was inside or outside the tunnel. I did start by working from the outside edges inwards, but that doesn’t work for the stuff where the rabbit squeezes between the tunnel pieces.

Enter Spatial.

Here’s the recipe:

Take each of the vertices (tunnel pieces) and convert them into a Spatial Line
Then take all of the lines, and convert them into a single polygon

Then create a dot for each non-tunnel point (row / col)
Then all you need to do is use the spatial formula ST_Within([Centroid],[newPoly]) to see if the point is inside the poly or not – job done!

And why the control container – ‘cause you only want part2 to run when the output from Part 1 completes and the output file finishes writing

2023_Day10-Part2V2.yxzp

SeanAdams

thank you for writing this up @CoG - very generous of you to spend the time - and your explanation makes complete sense.

I feel like I cheated a little and used the spatial tools for part 2 - but it is BaseA :-)

SeanAdams

great writeup and unique solution - thank you for taking the time @gawa

estherb47

For whatever reason, I really enjoyed solving part 1 of this, but had very little time each day to work on it.

My first approach was a spatial one. Look at the orthogonal neighbors by generating points on a map. And even though I only used that approach to generate neighbors for tiles, for whatever reason my iterative macro started throwing lots of iterative records after about 100 iterations, which was completely wrong.

So just tried the neighbor by numbers approach that @grossal mentored me through last year (at least I think it was last year. Could have been two years ago).

It could definitely be more efficient.

Spoiler

My macro is super simple and I'm relying on the shape of the tile and the next direction that flows from the tile to find the next pieces of the pipe.

estherb47

For part 2, I did go with a spatial route. Really enjoyed this challenge, and it was the second this year when I got the answer on the first and then second try.

Spoiler

Used the data from part 1 to assign centroids to each point. Realized quickly that I needed to use Integer as Lat/Lon for the number of points, and then generated the pipe.

Took an outer join from all of the points and the completed pipe to show what wasn't on the pipe, and then spatially matched these to the pipe, using Target Within Universe.

My first answer was wrong, so thought to look for patterns in the contained points. Lo and behold, one was zero distance from the pipe, and the rest were offset from the pipe. Filtered that zero distance out, and go the correct answer.

AOC10.yxzp

Tokimatsu

I used spatial tools.

Spoiler