Advent of Code 2023 Day 18 (BaseA Style)

AlteryxCommunityTeam

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

Advent of Code

Accepted answers

All comments

Qiu

Finally completed Part 1 and I am convinced that Part 2 is beyond my reach... 😂

But it really feels good when looking at the output.

Spoiler

mmontgomery

Got P1 thanks to D10 process! P2, well, that will take some time

Spoiler

I generated each point possible based on min/max column row.

Did a spatial match based on the polygon to that route.

DataNath

Part 1 only for today - need to have a think about how else I can approach P2 as using the same method here ends up generating over 300 billion rows!

Spoiler

Day 18.yxmd

phottovy

My solution which runs in about 1.5 seconds for both parts.

Spoiler

For P2, I got some help from the subreddit to relearn some basic geometry. It was pretty straightforward after that.

Macro:

aoc_ph_2023_18_final.yxzp

CoG

This problem is crazy! Part 2 became my white whale as I struggled to wrap my mind around what was going on. I'm cleaning up my workflow now, I have an idea that will simplify things greatly. My current workflow is too long to post a screenshot of....

Draft Part 3.yxmd

ScottLewis

First one in a while that has felt good. I've been able to do most of them but it felt like a hack but this one with the algorithm in place is .4 seconds to do part 2 no macros just multi-row formulas. There is probably more elegant way to handle next(last) = first but this does the job.

xymd has the remains of my original build path and fill solution to part 1, which worked but would not have run part 2 during the remainder of human civilization.

Day18_Scott.yxmd

Qiu

@phottovy
Thats crazy. 😁
Maybe you can share the geometry lesson again? 🤣

AncientPandaman

i ask bing AI for this question. it gives me some clues but still have to go to reddit for more idea.

luckily learn some python, and the code is explained well.

hint#

Spoiler

Bing AI give me Shoelace formula - Wikipedia
which generate the area, and it not same with example given.

then reddit said use that for another formula Pick's theorem - Wikipedia
still no clue till running one of the python code.

key#

Spoiler

b is sum of point of boundary of the shapes

notes: try with part1 example. it easier and similar.

Qiu

@PangHC @phottovy
I was looking at the Shoelace formula and the Pick's theorem seems to be more easier.
It turns out to be mathmatical problem. 😂

DaisukeTsuchiya

I try to find the calculation method using excel but finally followed other's idea.

Spoiler

For P2, I draw the figure and tried to calculate manually. The results of sample can be matched but I stopped to develop WF then go to easier method.

<Manual Calculation Trial in Excel >

Spoiler

Spoiler

Day18_Rev1.yxmd

ApekshaSharma

Spoiler

I will suck at explaining this, but here is my attempt.

Also, I am managing with a small laptop screen right now - not able to get very clear screenshots of the workflow-so skipped it.

P2 Approach:

Step 1: Split the digging input into two streams - i. Up & Down (Row Movement) ii. Left & Right (Column Movement)
Step 2: Retaining the digging order, generate next (Row,Column) point using Multi Row Formula for each stream.
Step 3: Union all the generated points together and order them by digging order. Using multi-row formula, populate the next (Row,Column) Point. The next point for the last point will be the first point.
Step 4: Using the current and next point, generate all the points that make up the perimeter. (I split the input into four streams based on the direction of digging and then used multi-row)
Step 5: After all the perimeter points were generated, I built a sequence polygon using poly-build tool.

Below is the main logic :

Screenshot 2023-12-23 143856.png

Step 6: I first ordered all the perimeter points by Row ID Asc, Col ID Asc. Like 1,1; 1,2; 1,5; 1,6; 2,1; 2,6; etc.......
Step 7: Then for each column within a row, I determined the next available column (within the same row) - consider only perimeter points. Like 1,1-1,2; 1,2-1,5; 1,5-1,6
Step 8: Count points between each pair of perimeter points created in the previous step - For 1,1-1,2; 1,2-1,5; 1,5-1,6, it would be 0,2,0
Step 9: Using the first perimeter point from each pair calculate the immediate next point on the right - Example - 1,1 - 1,2; 1,2 - 1,3
Step 10: Now using spatial match check whether the newly generated point lies in the polygon area using spatial match, if it does the counted points between the pair of perimeter points should count towards the total area otherwise, they should be discarded.
Step 11: To the above, add the total count of the perimeter points and that's the total area!
Day 18 .png

estherb47

Well, my first thought was "this looks a lot like day 10", so started in with a spatial approach.

While this worked, it took about 2.5 minutes to run. I did learn fun things about generating integer points and getting them to intersect (have them come from the same stream of data!). But knew this wouldn't be scalable for part 2

Read through solution descriptions, and found the shoelace method.

Runs in 0.5 seconds

Spoiler

Don't forget to account for the area of the path itself!

AOC18.yxmd

AkimasaKajitani

Part 1 : I use spatial tools.

Part 2 : The shoelace formula is needed.

Spoiler

Part 1 macro to get the route.

And then, I use the spatial tools.

Part 2, I use shoelace formula. But it can't be not applicable as is.

First, we need to remake the route data. HexToNumber function is needed to do it. And I prepare that data for shoelace formula.

Note that we can not get the answer only the shoelace formula. We need to consider the points on the outer circumsference. In this case we can use the length of outer circumsference. The final formula is as follows.