Community Spring Cleaning week is here! Join your fellow Maveryx in digging through your old posts and marking comments on them as solved. Learn more here!

General Discussions

Discuss any topics that are not product-specific here.

Advent of Code 2021 Day 22 (BaseA Style)

jdunkerley79
ACE Emeritus
ACE Emeritus

Discussion thread for day 22 of the Advent of Code - https://adventofcode.com/2021/day/22

 

 

GT14239.jpg

8 REPLIES 8
dsmdavid
11 - Bolide
Spoiler
Part I - generate rows works
dsmdavid_0-1640192791402.png

Part II: So close, yet so far...

dsmdavid_1-1640192846116.pngdsmdavid_2-1640192887497.png

 


Apical view and a sample slice.
For now, utterly failed to reconvert those shapes to the proper coordinates to be able to count the cubes

cgoodman3
14 - Magnetar
14 - Magnetar
Spoiler
Like @dsmdavid I'm stuck on part 2. But I have heard of some BaseA solves. Assumed for a while I could continue with the generate rows but given the volume of the cubes is in the billions then creating 400 of these seems much harder than the handful that fall in the part A range of -50 : 50.

cgoodman3_0-1640195192672.png

 

Chris
Check out my collaboration with fellow ACE Joshua Burkhow at AlterTricks.com
LiuZhang
9 - Comet
Spoiler
22 - 1.png

Just brute forced part 1, unless there is really clever way to cache the results. I don't know anyway to even keep track of all the points.

SeanAdams
17 - Castor
17 - Castor

I'm in the final debugging stages of an alternative approach - also started out with a brute force like @cgoodman3 @LiuZhang  and @dsmdavid  - but for part two moved onto a different approach.

 

It works for all the routes in part 1, but for some reason is miscalculating something in the defined routes in part 2.

 

Update at 21:42 - found one problem - was overrunning an int16 data type - hopefully this fixes the problem.

 

Algo / recipe in the spoiler text below:

Spoiler

First: prep the data.    This has a parameter in for the maximum value so that I can use the same process for part 1 and part 2.

Then take the first cube defined by X1..X2; Y1..Y2; Z1..Z2, and use this as the starting point.
From there - the process iterates for each NewCube
- Take the next cube and split all the pre-existing cubes based on this cube's edges.     So if your existing cube was 1..10 and the newly introduced cube is 5..6; then you split your existing cube into 3 parts: 1..4; 5..6; 7..10.   This makes things much easier down the path
- Then look for any cubes which occupy the same space as NewCube (because you've done the splits above - this is pretty simple)
- drop all the cubes that intersect / overlap with NewCube
- if NewCube is ON, then add NewCube to the existing cube list.    if NewCube is off then ignore it - we only keep cubes that are on.
- get next NewCube.

As I said - this works well for the examples in part 1 and is relatively linear in time since it only increases the number of items in the list as a ratio of the number of new edges that are seen (not the number of points).

Now debugging to get a final good answer for part 2.

I wonder if @patrick_digan has got a workable solution for this one?

 

patrick_digan
17 - Castor
17 - Castor

@SeanAdams I neglected to post some of these last few days.

 

Spoiler
I had a simpler setup (or two or three) for part 2 but it was too slow, too much data. I finally got it down to 113M records and it completes in 3.5 minutes on my not so powerful machine. 

My idea is to take each cube and find out where it intersects in any direction with any other cube. Then i split the x,y,z intervals on all of these intersections (one container for each direction)  and then join it back together. I then had to use a few tools to basically condense this down to as few records as possible before joining x to y to z. It should be dynamic and handle any input. 

patrick_digan_0-1641267990513.png

 



SeanAdams
17 - Castor
17 - Castor

@patrick_digan  - after days of chasing down silly debugging, finally got mine up and running.    I remain impressed and intimidated that you got yours done within a day or two of the challenge being published!

SeanAdams
17 - Castor
17 - Castor

OK - here's my final solution for part 1 & 2.     This became complex enough that I built test harnesses for the sub-macros so that I could continue to run all my test cases as I built them out.   I've attached the solution and the two test harnesses.

 

The original approach was a simple brute-force explosion - but this had to be completely reengineered to make this work.

 

Spoiler
The recipe:
Take the first cube - this is the starting universe.
Then for each successive row: (called New)
- Identify which of the existing universe cubes intersect New
- If any intersect - then split these up so that the intersection is clean.    As an example - if existing is 8-20; and the new is 8-15 - then split the existing cube at the 15 point.
- Once you've split up the cubes so that any overlaps with New are simple  / clean - then you can remove the existing cubes that overlap with New, and replace them with New
- take the next row as New


Top level flow:
SeanAdams_0-1641419890818.png

 

The data prep
this just transforms and cleans up the raw data; along with setting a limit on the maximum size:

SeanAdams_1-1641419972613.png

Set up the Macro

This piece creates the initial version of the map file, containing the first row - i.e. set up the initial unverse

SeanAdams_2-1641420051397.png

 

 

The iterative process:
This is the process which takes every new row, and goes through the process of:
- Split the existing cubes in the universe
- Then join any new cubes
- Write down the new cubes as part of the universe

SeanAdams_3-1641420199198.png

 



The test harness:
In order to make sure that the Splitter was doing its job correctly - I also built a test harness that ran this under a dozen or so different test cases.
SeanAdams_4-1641420342307.png

 





Pang_Hee_Choy
12 - Quasar

@SeanAdams and @patrick_digan 

did you know why the sum is roundup after macro? 

but if i do it in new workflow, the sum is correct. 

 

Update: Quick solution, use formula tool for Mod 1000

Pang_Hee_Choy_0-1642579451709.png

 

Spoiler
Part 1 is simple hence i skipped.

for part 2, we find out and create a line for the intercept cube. 
record by record. then we have a list of On Cube, Overlap Cube and Off Cube.

After that just sum will found the correct answer.

hard part is how to identify the intercept cube. (take me 99% of time to try and error)

workflow
Pang_Hee_Choy_1-1642416762767.png

Macro

Pang_Hee_Choy_5-1642417203398.png

 

 

Pang_Hee_Choy_4-1642417189655.pngPang_Hee_Choy_6-1642417224412.png

 

Pang_Hee_Choy_9-1642417365663.png

 

 

  

Labels