6
votes

# Day 21: Step Counter

## Today's problem description: https://adventofcode.com/2023/day/21

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python`

with any of the "short names" listed in this page of supported languages):

```
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
```

Did an

extremelybrute force part 1, and I got my best finish of the event so far, rank 557. Previous best was Day 6 part 2, where I finished at 676, mostly I think because I hand-manipulated the input (deleted a couple spaces) instead of writing any code.## Part 1 Python code

Part 2 was another story. I ended up pair programming this with the same friend I did Day 17 with, and we finished around ~ rank 750. code here which is mostly his code but I changed some variable names to make it a bit more readable long-term.

## Part 2 comments

I started out by considering what would happen in an empty grid, no rocks. Wasn't sure if this would be helpful but I wanted to understand the problem.Then I looked at the output of part 1 in my favorite visualizer, Notepad++, and realized the edges of the diamond/rotated square are all perfectly filled in at n=64. But there's this parity thing going on. scratch paper here

At this point I called my friend, and we looked at some manual cases (one of which demonstrated that there's an enclosed set of

`.`

that you have to flood fill to find) and then he did some numpy magic with masks.Specifically, we called the final area an

`enclosure`

, each tile that's exactly equal to the center a`garden`

, and each point a`square`

. The parity of a square is the parity of`x+y`

, and the parity of a garden is its origin's`x+y`

. The order of an enclosure is the number of gardens between the origin and the endpoint along an axis (rounded up since the origin is at the center of one garden).Let the order be

`n`

. Then there are`n^2 + (n-1)^2`

complete gardens fully inside the enclosure. Of these,`n^2`

have even parity and`(n-1)^2`

have odd parity (wlog for what 'even' and 'odd' mean). Furthermore, there are (n-1) per each quadrant of:And there are 4 gardens located on the axis, which are different pentagons.

Two masks are needed to compute all of this, one even-odd parity mask, and one perimeter mask. The mask for ugly pentagons is the mask for the triangle, but inverted; and the mask for the corners is 2x of the mask for the traingle, one rotated the other way from itself.

If the order is odd, all pentagons (including the corners) have even parity, and all triangles have even parity.

So, sum the possibilities for the masks & the allowed squares you can step on, and multiply each one by the # of times it occurs. That's the answer.

Pretty sure we did this in a very complicated way based on what I've seen on reddit, but that's ok. It was a lot of fun tbh.

Congrats on the rankings! I love seeing people's scratchwork to see how everyone thinks about the problem slightly differently.

thanks! I ended up updating my entire repo to include all my scratch paper, anything where the last commit is

`Create README.md`

has some random doodling in it now (and I didn't use any scratch paper for any other day)Interesting problem for sure! Just like yesterday, careful inspection of the input was key (I forget this every year with AoC and relearn this tip every time). I didn't even catch the special property of the number of steps until after solving...

## Solution Discussion

Part 1 went smoothly enough, just tracking a set of reachable positions for each step. I suppose I could have memoized the neighbor finding, which may have sped up part 2 a bit, but I didn't bother.

Part 2 was an endeavor! I recognized that the expansion of the reachable positions would leave a large area in the middle just flipping between two states, which wouldn't need to be calculated. My initial thought was to only track the positions at the perimeter of this area, reducing the size of the reachable positions from ∝n^2 to ∝n. This actually worked, and I kept it as "part 1.5", but I had forgotten that I would still need to step n times, so this solution just brought brute force from n^3 to n^2...

I then figured that, due to the repetition of the map, with any number of steps that was a multiple of the map size, the reachable states should grow quadratically. Using the "part 1.5" solution, I found 3 points with the same step offset as the goal number of steps, did a quadratic interpolation, and then plugged in the actual number of steps.

## Haskell Solution

Ugh, I think I am going to have to DNF part 2. I have to get the house ready for family coming and have spent far too long on it already.

## Discussion

Part 1 was easy to brute force. I had a similar idea as @scarecrw about not needing to compute the center region, but it didn't scale (as they noted).

I started thinking about the pattern in terms of the pattern that is present in each copy of the grid, and I found the diamond pattern, and even the way it will grow. Here's an example from the test input. The values here are hash values for the state of each cell in the copy of the grid, so each each entry represents an entire grid copy, not a single cell. The numbers are arbitrary and don't have any relationship to each other.

From here, it's just a matter of figuring out the period of the pattern, picking the pattern that starts on the right offset to get an even number of steps to the target steps, then computing the growth of the pattern over how ever many pattern iterations it takes to get to the max. I have it 90% of the way there, but I'm out of time.

I think in the end, the math I'm doing is pretty much the same (but more complex and less efficient) than the interpolation that @scarecrw did.