topic Re: Advent of Code 2021 Day 22 (BaseA Style) in General Discussions

Advent of Code 2021 Day 22 (BaseA Style)

jdunkerley79 — Wed, 22 Dec 2021 15:43:12 GMT

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

Re: Advent of Code 2021 Day 22 (BaseA Style)

dsmdavid — Wed, 22 Dec 2021 17:11:15 GMT

Part I - generate rows works

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

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

Re: Advent of Code 2021 Day 22 (BaseA Style)

cgoodman — Wed, 22 Dec 2021 17:46:53 GMT

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.

Re: Advent of Code 2021 Day 22 (BaseA Style)

leozhang2work — Wed, 22 Dec 2021 21:07:03 GMT

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.

Re: Advent of Code 2021 Day 22 (BaseA Style)

SeanAdams — Tue, 04 Jan 2022 02:42:40 GMT

I'm in the final debugging stages of an alternative approach - also started out with a brute force like @cgoodman @leozhang2work 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:

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?

Re: Advent of Code 2021 Day 22 (BaseA Style)

patrick_digan — Tue, 04 Jan 2022 03:47:25 GMT

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

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.

Re: Advent of Code 2021 Day 22 (BaseA Style)

SeanAdams — Wed, 05 Jan 2022 21:48:59 GMT

@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!

Re: Advent of Code 2021 Day 22 (BaseA Style)

SeanAdams — Wed, 05 Jan 2022 22:05:53 GMT

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.

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:

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

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

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

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.

Re: Advent of Code 2021 Day 22 (BaseA Style)

AncientPandaman — Wed, 19 Jan 2022 08:05:49 GMT

@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

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

Macro