Advent of Code 2023 Day 21 (BaseA Style)

[AlteryxCommunityTeam]

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

[gawa]

Today not purely solved by Alteryx but also hand-writing on paper and calculator.

Brute Force will not work. If you find something, it would turn to be a math problem, still complicated though.

I explain my way as nested spoiler here. More hints you want, more spoiler you can collapse.

Spoiler

Spoiler

First, let's have a look at part1 result on MS Excel. You will see all of points are marked as far as steps allowed.
I guess this is because:

Spoiler

There is nothing in the way from start point toward right/left/up/down direction till the edge.

Important observation here is that:

Spoiler

If you are given even(odd) step number, you can move to X-Y coordinates that has even(odd) distance from the start point.
For example, if you are given odd step number, you never come back to start point.

To prepare for part2, guess any reason of the given step number 26,501,365

Spoiler

In my case, X-Y range was 131 x 131, that has 65 steps from start to edge, thereby (26,501,365-65)/131=202,300
This means that even if you arrange a lot of map repeatedly, the farthest point will be exactly edge of map 

As said above, we have to care about each map is exactly not equivalent because:

Spoiler

if you cross the line between 2 maps, you will enter into different world. I mean if you walk in "odd" map so far, you enter to "even" map after crossing the border. So we need to have at least 2 patterns: odd map& even map (which location you can move if you are given odd/even step number, respectively) 
Upon this, please note that ;

Spoiler

There is a enclosed area, where you have no access by any means. Those shall be eliminated from count.

Next is how to calculate the answer. Combining the all of observation so far, you will notice there is some pattern appeared. There should be multiple way to make pattern, but my way was:

Spoiler

Categorized in three pattern: odd diamond, even diamond, other diamond.

By knowing the count of each diamond, and how many number of diamond exist, you can multiply them, and sum up. That is your answer.  

[Qiu]

@gawa 
OMG, how did you figure that out.... 🤔

[AndrewDMerrill]

Part 1 was very easy, Part 2 was full of pitfalls for me, I was able to quickly establish what needed to be done, but doing that was a different story. As @gawa - mentioned, there is no way to simply solve Part 2, you will need to analyze the underlying data for patterns that can simplify the problem. Pen, paper, and lot of test runs on random workflows revealed that structure to me and got me the answer I needed.

Algorithm:

Spoiler

There are several very interesting constraints that are hidden in plain sight in this problem that can help simplify things. One very important concept is the idea that it will always take 2 steps to get back to your starting point or, in other words, every step you take will be onto a garden square that you could not have been before that step. Or in other other words (a picture this time) a situation like this will never occur:

.	#	#	.
.	O	O	.
#	#	.	#

^ This is an impossible situation, since 2 'O's neighbor one another. This means that a garden (or garden tile for part 2) can never be filled completely, instead it will alternate between two roughly equal values. Take the following example with an unimpeded 3x3 garden; the final alternation will look like this (a 4 - 5 alternating pattern):

0	.	0
.	0	.
0	.	0

and

.	0	.
0	.	0
.	0	.

Building a workflow to handle this movement is quite easy with an iterative macro by iterating on the walk-able squares (row and column indices), calculating all possible steps, finding unique outcomes and removing any illegal moves based on the input data (i.e. the elf cannot step on a '#' square). This solves part 1!

Part 2 is trickier, but thanks to patterns in the data, we can solve this without too much of a headache. We just need to find the pattern (this may be slightly different for you relative to my data since inputs are apparently different in AoC).

Spoiler

You'll notice that S is in the very center of the garden at the beginning (Row = 66, Column = 66), and that all points in Rows 1, 66, and 131 as well as all points in Columns 1, 66, and 131 are not blocked at all. This means that the shortest distance from one garden tile (a garden tile is the 131x131 grid that gets copied infinitely) to another neighboring tile is a straight line. A helpful corollary to this fact is that this also means that no other step process will ever influence the reachable squares in a given garden tile:

As you can see it takes only 2 steps in the above example to get to the tile to the right of the starting tile. To get to the next closest tile takes 3 steps (bottom case), but that third step will already be accounted for by the top case. Thus, we can simplify our logic by focusing only on the first step into a new tile.

With the insight in the spoiler above, we know that this problem will have a lot of simple repetition. We have 3 groups totaling 9 cases to consider:
1. We start in the center of a tile (this will only happen once)
2. We start in the middle of an edge of a tile (Left, Right, Top, or Bottom Edge)
3. We start in one of the corners of a tile (Top Left, Top Right, Bottom Left, or Bottom Right)

The question we seek to answer is how long does it take to fill up a tile to the point that it starts alternating (remember the 4 - 5 alternating example above for 3x3 grid) for each possible starting point. If your data is the same as mine, the answer is the same for each case within a group (e.g. it doesn't matter which corner you start in, it will always take ~261 steps to fill up and begin alternating). Now we just need to calculate when we start filling each tile (which step first sets foot in the new tile), and by adding on the time it will take to fill up and accounting for the total required steps, we can calculate how many tiles will be filled within the step limit. Don't forget to account for the alternation to determine how many possible garden squares can be reached in the total required steps.

If we think about the garden tiles as integer points on a 2D plane then we more easily understand that the origin (our starting tile) is the only center tile, the x,y - axes start on the edge closes to the origin (e.g. every tile on the +x axis will start from the Left edge of the tile), and the entirety of each quadrant is comprised of tiles that start in the corner closest to the orgin (e.g. tiles with (x,y) > (0,0) like (1,3) will always start in the Bottom Left corner).

You'll notice that at the end of your steps you will not fill the final tile you reach, this is a separate calculation that needs to be done, and will be different for every direction/starting point (e.g. starting from the bottom or top edges give different results), which is due to slight asymmetries in the input data. Once you have this extra overhang, you can add up the total, and get your answer.

As a final hint/note: The corner cases (tiles that you start in the corner) will be the biggest contributor to your total answer. Don't try counting each tile separately, but rather group them by similar values and multiply the value a single tile by the count of all tiles in that same state.

Workflow:

Spoiler

Main Workflow (quite a mess):


Iterative Macro (Part 1):

Iterative Macro (Part 2):

Happy Solving!

[Pang_Hee_Choy]

refer lot of codes. and built workflow based on answer.

create lot of excel files for helper, and it really helpful

Spoiler

part1: i skipped, it as it basic

part2: i cant explain why, but i just share what my progress.

take days to play around. then give up and get some hint from reddit. (and run with my input and get the answer of course). 

I start build based on that. 

first, since the steps 26,501,365 is 202,300*131+65.
hence I run for step 327 (2*131+65), and get all the similar data.

export the data to the excel then use lot of countif to get the answer for each section.
So, I can solve the issue piece by piece.

1. to get full map count for odd and even, it required to go through the whole map, because it has some spot that are close, 4 adjacent is "#".
2. the steps for partial map (the edge, small side and big side) need to -1, (i.e. 131-1, 65-1, 195-1, 65-1.)
no idea why. I change it because only then it map with the answer in excel.

excel:

workflow:

part1_macro

part2 macro

[AkimasaKajitani]

To be the honest, I don't like the quiz to find the pattern to solve part 2. This year, there are many such that quiz.

Spoiler

Part 1 is oasis problem.

To solve the part 1, I made the simple macro below.

 

The workflow for part 1 as follows.

 

Part 2: I needed subreddit hint.
First, we can make the workflow for a endless map. I added two fields for map number(for x and y). And then, we need to find the pattern.

Spoiler

I repeat the macro 330 times because the edge of the map comes every 131 steps and the first edge come at 65 steps(65+131+131=327). So we can get the first three pattern.
 - 1st : 65 steps 3726 O
 - 2nd : 196 steps 33086 O
 - 3rd : 327 steps 91672 O
O's number is my pattern(another people will get another number)

Let's use these numbers to solve the quadratic equation(ax*x + by + c = 0). But we need to use 0 instead of 65, 1 insted od 196 and 2 insted of 327.

And then, we need to remember the quiz. The last step is 26,501,300 steps. This means 202,300 * 131 +65. So if you can get the complete quadratic equation, you can use it.

 

Final workflow :

 

[Tokimatsu]

I was happy when I found the pattern for Part 2, but it was a long process until I got it right.

Spoiler

Stuck in my own logic, I managed to debug it by looking for the same idea.
https://github.com/villuna/aoc23/wiki/A-Geometric-solution-to-advent-of-code-2023,-day-21

 

[Carolyn]

After taking a couple week break, I FINALLY solved Part 2. I forgot how good the "you earned a star" message feels! That was gnarly.

Spoiler

I first made an Alteryx WF which used mod to track if a point was in the initial grid or if it was 1 to the left or 1 up, etc. I then scrapped it, spent a lot of time with a few other ideas that all failed. I then used my mod version to run 327 iterations = 131 * 2 (131 = distance from edge to edge directly across) + 65 (distance from my starting point in the center to an edge in one direction). 

That gave me a list of points that my guy ended up on, including if it was x_mod=1 and y_mod=1, etc. I then took that into Excel and used that to figure out how many completed grids I would have and how many partial grids, based on patterns with the (65M total steps - 65) / 131 sets of grid iterations.