Monkey Map

Advent of Code 2022 Day 22

Try the simulator for Part 1 using your puzzle input!

Part 1

1. One gold star is within reach
2. Parsing the notes using regex
3. Parsing the map into a nested array
4. Accounting for each type of edge
5. Tracking where the cursor faces
6. Placing the initial cursor
7. My algorithm in pseudocode
8. An error, then a few more conditions
9. Building a simulator to try and solve this puzzle
10. Trying every scenario with the example input
11. Could it be? The correct answer??

One gold star is within reach

• With patience, persistence and attention to detail, I could probably earn this star by solving it visually, performing each move in my design tool
• But I really want to solve it with an algorithm
• I feel like I can
• The tough part will probably be accounting for any times where the cursor wraps vertically (and, let's be honest, horizontally)

Like all AoC puzzles that I understood before, I'm up for the challenge!

Parsing the notes using regex

The pattern seems to be:

• A number of steps - either one or two digits
• A direction - either R or L - after each number except the last

I want to use the set syntax in regex to match one or two digits or R or L.

Sadly, sets are restricted to matching a single character.

Using the example input, I'd like a list like this:

[ 10, 'R', 5, 'L', 5, 'R', 10, 'L', 4, 'R', 5, 'L', 5]

I don't think I can get that with a single regex.

Instead, I'll make two lists:

• One for each number
• Another for each direction change

The list of numbers should be one longer than the list of directions.

The regexes look like this:

/\d+/g
/[RL]/g

Now I have a choice:

• Combine the lists and pull from a merged list, accounting for each type every other turn?
• Or incorporate into my larger algorithm a process of pulling the first item from each list every other step?

It seems like either way I'll need logic to check whether I'm dealing with a number or a direction.

I choose: merge both.

My algorithm in JavaScript:

const steps = [...input.matchAll(/\d+/g)].map(el => +el[0])
const turns = [...input.matchAll(/[RL]/g)].map(el => el[0])
let notes = steps
  .flatMap(
    (el, i) => [el, turns[i]]
  )
  .slice(0,-1)

• I make two lists
• Then I generate a combined list by turning each item in the steps list into a 2-element array containing that item and the item at the same index in turns
• Then I flatten those nested arrays so that the wrapping array contains only the values
• Then I chop off that last value since it will be undefined

That is the most eloquent way I could think of to achieve the result I wanted.

Parsing the map into a nested array

I wish it was simple enough to split at each new line character, then again at each character.

However, the character lengths of all lines are not equal.

Therefore, my algorithm has to identify the longest line length and pad every line to that length with empty space characters.

My algorithm in JavaScript:

let longest = Math.max(...MAP.map(el => el.length))
MAP = MAP
  .map(row => row
    .padEnd(longest,' ')
    .split('')
  )

Accounting for each type of edge

If a movement instruction would take you off of the map, you wrap around to the other side of the board.

Great. There are so many ways to go off the map!

Horizontally and vertically:

• Move to a tile that is outside of the boundaries of the map (e.g. index of -1 or >= length of the outer or inner arrays)

Horizontally:

• Move right to a tile
• Move left to a tile

Vertically:

• Move down to a tile
• Move up to a tile

Then there is accounting for a wall as the tile next once wrapped.

That merits its own section.

Heck, I'll come back to all this after solving for two easier tasks:

• Tracking where the cursor faces
• Placing the initial cursor

Tracking where the cursor faces

I'll use a rotating four-element coordinate array:

[ [0, 1], [1, 0], [0, -1], [-1, 0] ]

Those correspond to the directions:

Right, Down, Left, Up

Handling rotation looks like this in pseudocode:

If the direction is R
  Remove the first element
  Place it at the end
Else, the direction is L
  Remove the last element
  Place it at the front

I will always move according to the relative coordinates of the first element.

Placing the initial cursor

You begin the path in the leftmost open tile of the top row of tiles. Initially, you are facing to the right (from the perspective of how the map is drawn).

• An open tile is indicated by a .
• I know there is one in the top row
• I can't be certain it is the absolute leftmost tile - that could be a wall

I'll use indexOf('.') to find the correct starting point:

let cursor = [0, MAP[0].indexOf('.')]

And my directions array is correct because the first item refers to facing right.

My algorithm in pseudocode

For each note
  If the note is a string
    If it is an R
      Update direction appropriately
    Else if it is an L
      Update direction appropriately
  Else if the note is a number
    Do as many time as the number
      Identify the character at the tile the cursor would move to next
        If it is a .
          Move to that tile
        Else if it is a #
          Don't move
        Else if it is a space character
          Identify the character at the tile on the opposite end of the section of map
            If it is a .
              Move to that tile
            Else if it is a #
              Dont move
        Else if it is outside of the bounds of the map
          Identify the character at the tile on the opposite end of the section of map
            If it is a .
              Move to that tile
            Else if it is a #
              Dont move

My JavaScript is highly nested and rather messy.

But it is working so far.

I still need to account for the bulk of those last two Else clauses, which require the most work identifying and checking value in the tile the opposite end of the section.

An error, then a few more conditions

After feeling like I accounted for those last two Else clauses, I ran my algorithm on my puzzle input.

It threw an error.

Turns out, I forgot to account for the cursor being at the very top and trying to move up, and being at the very bottom and trying to move down.

My fix: two more conditions to catch those scenarios, and one last one to catch everything I already had.

I ran it again.

No error!

But, what I saw in my simulated map seemed odd.

Even more odd, my ending row was the top row.

I just feel like that isn't right.

Still, I had to try it.

I calculated my sum by hand and submitted.

As expected, wrong answer: too low.

Now I really want to see the cursor move in attempts to diagnose my issue.

That means I have to - nay, get to! - build a simulator.

Building a simulator to try and solve this puzzle

Hopefully it's a fairly simple copy-paste of my massive algorithm, along with replacing some loops with manual updates to a running counter.

Off I go!

...

I was right: it was mostly a copy-paste task.

With it now built, I could see the path followed using my puzzle input at a speed I dictate and attempt to identify incorrect movements.

Trying every scenario with the example input

It turns out that testing on my puzzle input is too difficult.

It is just too large and visually noisy to watch the path move.

But the example input is wonderfully small.

And adjusting the path is as simple as changing an R to an L and using smaller or larger numbers!

I need to know...does my algorithm successfully wrap:

• From top to bottom?
• From bottom to top?
• From right to left?
• From left to right?

Revelation #1: I assumed there would always be a wall

My algorithm compares the indices of .s and #s in a row or column to determine whether to move.

The problem with doing that is when there is no wall the index of # is -1, which will be less than the index of any ., thereby screwing up my algorithm.

To solve for this, I added a logical operation to my condition that checks for the lack of any walls first.

Revelation #2: I forgot to use lastIndexOf() in a few places

When attempting to move from top to bottom and left to right, I need to know whether the wrapping tile has a wall or is open.

I can assume that when searching from the end of a row or column, whichever one has a higher index is located further to the right.

Using the simulator showed me that my algorithm was screwing up when moving from the top of a section to the bottom.

As expected, my algorithm was mistakenly using indexOf() instead of lastIndexOf() in that condition. So it was incorrectly searching from the beginning of the row or column.

Feeling good about my algorithm

I tried several small paths in my simulator using the example input.

After fixing the above issues, it seemed like my algorithm was finally traversing the correct path no matter where it wrapped.

It was time to try it on my puzzle input again and hope for a final password higher than my current highest: roughly 20k.

Could it be? The correct answer??

I swapped inputs once again.

I ran my algorithm.

I generated a final password of roughly 165k.

That's way higher!

It could be the correct answer!

Do I want to run my simulator and try to follow the path to confirm?

Nah, that will take a while and probably cause a headache.

I'll risk submitting a wrong answer and sacrificing another 'Too high' or 'Too low' guide.

Submitting...

It is the correct answer!!!

Woohoo!

Part 2

Oh, wow! How cool! But...pass.

The map makes a cube when folded!

What a fantastic twist to this puzzle!

Sadly, I feel I have neither the skills to solve this part, nor the patience to continue with this puzzle.

I'm tapped out, honestly.

I did it!

• I solved Part 1!
• After what feels like an eternity of grinding my way toward the correct answer!
• And after using my simulator and example input to troubleshoot and debug my very complex and complicated algorithm!

Wow. That was a tough one.

I'm glad I stuck with it.

I'm glad I was able to use my simulator to find and fix the errors in my code.

I'm glad I'm leaving today with one gold star earned.