Garden Groups

Advent of Code 2024 Day 12

Part 1

Lots of cataloging. Then lots of side-checking.

My first task is to build an object representing each region.

For this small input:

AAAA
BBCD
BBCC
EEEC

My object should look like this:

{
    'A': [[0,0],[0,1],[0,2],[0,3]],
    'B': [[1,0],[1,1],[2,0],[2,1]],
    'C': [[1,2],[2,2],[2,3],[3,3]],
    'D': [[1,3]],
    'E': [[3,0],[3,1],[3,2]]
}

Except, I will need to account for multiple regions with the same character.

So, my object will look like this, instead:

[
    { 'char': 'A', 'cells': [[0,0],[0,1],[0,2],[0,3]] },
    { 'char': 'B', 'cells': [[1,0],[1,1],[2,0],[2,1]] },
    { 'char': 'C', 'cells': [[1,2],[2,2],[2,3],[3,3]] },
    { 'char': 'D', 'cells': [[1,3]] },
    { 'char': 'E', 'cells': [[3,0],[3,1],[3,2]] }
]

Thinking ahead, though, can this accomodate multiple regions per character?

I think so:

[
    { 'char': 'A',
      'regions': [
        [[0,0],[0,1],[0,2],[0,3]],
        [...]
      ] 
    },
    { 'char': 'B',
      'regions': [[1,0],[1,1],[2,0],[2,1]] 
    },
    { 'char': 'C',
      'regions': [
        [[1,2],[2,2],[2,3],[3,3]],
        [...]
      ] 
    },
    { 'char': 'D',
      'regions': [[1,3]] 
    },
    { 'char': 'E',
      'regions': [[3,0],[3,1],[3,2]] 
    }
]

This feels good in theory.

It could simpler, though:

{
    'A':[
         [[0,0],[0,1],[0,2],[0,3]],
         [...]
        ],
    'B':[
         [1,0],[1,1],[2,0],[2,1]
        ],
    'C':[
         [[1,2],[2,2],[2,3],[3,3]],
         [...]
        ],
    'D':[[1,3]],
    'E':[[3,0],[3,1],[3,2]]
}

I'm concerned about working with it, though:

• How will I know which region to add a cell to?
• Meaning, how will I look it up in this object?

There's no better way to find out than to start coding!

Prototyping my catalogue strategy

Getting my 2D array of characters:

input.split('\n').map(line => line.split(''))

And I see:

[
  [ 'A', 'A', 'A', 'A' ],
  [ 'B', 'B', 'C', 'D' ],
  [ 'B', 'B', 'C', 'C' ],
  [ 'E', 'E', 'E', 'C' ]
]

Perfect!

Next, my catalogue:

let regions = {}

Now it's time to iterate through each cell in the grid:

for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        ...
    }
}

First, I'll account for the first time a new character is found:

for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        let char = input[r][c]
        if (!(char in regions)) {
            regions[char] = [
                [
                    [r,c]
                ]
            ]
        }
    }
}

I should see a catalog with five keys and five nested arrays with a single item inside each:

{
  A: [ [ '0,0' ] ],
  B: [ [ '1,0' ] ],
  C: [ [ '1,2' ] ],
  D: [ [ '1,3' ] ],
  E: [ [ '3,0' ] ]
}

Perfect!

Now the complicated part: adding cells to the right region.

Here's the start:

else {
    let priors = [[-1,0], [0,-1]]
    let matchingRegion = regions[char].map(region => {
        priors.map(coord => input[r + coord[0]][c + coord[1]])
    })
}

Pause.

I forgot the usual edge case: incorrectly checking out-of-bounds cells.

When the algorithm is on a cell in the first row and column, it will throw an error when comparing to a coordinate of -1.

To combat this, I can pad the grid with non-conflicting characters, .s:

input = input.split('\n').map(line => line.split(''))
input = input.map(line => ['.', ...line, '.'])
input = [
    new Array(input[0].length).fill('.'),
    ...input,
    new Array(input[0].length).fill('.'),
]

That turns the example input grid into this:

......
.AAAA.
.BBCD.
.BBCC.
.EEEC.
......

And now I don't have to worry about checking out-of-bounds cells!

Now, where was I?

Oh, yea. I was way off-track with that else clause!

Here's what I intend to identify:

• Whether the current character exists above or to the left (ok if both)

Doing that may seem complicated, but I'll explain:

let match = [[-1,0], [0,-1]]
    .findIndex(
        coord => input[r + coord[0]][c + coord[1]] == char
    )

• Start with an array of relative coordinates for above and left
• Use findIndex() to ultimately return a number that is 0, 1 or -1
• Based on whether the character in that cell is the same as in the current cell

When testing it, I see the expected results for the small example input:

• No -1s
• 0s when the character above is the same
• 1s when the character to the left is the same

How should I use this number?

• Look for this new coordinate in one of the existing regions for the current character

Getting there took some trial, error and debugging.

But I got there:

else {
    let options = [[-1,0], [0,-1]]
    let match = options.findIndex(coord => input[r + coord[0]][c + coord[1]] == char)
    let coord = [options[match][0] + r, options[match][1] + c].join(',')
    let matchingRegionIndex = regions[char].map(
        region => region.includes(coord)
    ).findIndex(bool => bool == true)
    regions[char][matchingRegionIndex].push([r,c].join(','))
}

• The relative coordinates are saved in a variable since I use them several times
• Find the matching coordinate index
• Save the actual location of the computed coordinate
• Iterate through each region in search of the one containing this coordinate
• Use the index to locate the correct region
• And add the current coordinate to that region

And I see this expected output:

{
  A: [ [ '1,1', '1,2', '1,3', '1,4' ] ],
  B: [ [ '2,1', '2,2', '3,1', '3,2' ] ],
  C: [ [ '2,3', '3,3', '3,4', '4,4' ] ],
  D: [ [ '2,4' ] ],
  E: [ [ '4,1', '4,2', '4,3' ] ]
}

So, it works on the first small example.

How about the second small example, with Xs and Os?

Nope: ERROR!

Why?

Oh, because I didn't account for -1, or when a second region of a previously-seen character is found.

Here's that logic incorporated into my algorithm:

else {
    let options = [[-1,0], [0,-1]]
    let match = options.findIndex(coord => input[r + coord[0]][c + coord[1]] == char)
    if (match !== -1) {
        let coord = [options[match][0] + r, options[match][1] + c].join(',')
        let matchingRegionIndex = regions[char].map(
            region => region.includes(coord)
        ).findIndex(bool => bool == true)
        regions[char][matchingRegionIndex].push([r,c].join(','))    
    } else {
        regions[char].push(
            [
                [r,c].join(',')
            ]
        )
    }
}

And the expected catalog logged:

{
  O: [
    [
      '1,1', '1,2', '1,3', '1,4',
      '1,5', '2,1', '2,3', '2,5',
      '3,1', '3,2', '3,3', '3,4',
      '3,5', '4,1', '4,3', '4,5',
      '5,1', '5,2', '5,3', '5,4',
      '5,5'
    ]
  ],
  X: [ [ '2,2' ], [ '2,4' ], [ '4,2' ], [ '4,4' ] ]
}

Excellent!

And how about the larger example input?

Uh-oh, another problem:

 E: [
    [ '5,10', '6,10', '7,10', '8,10', '9,10', '10,10' ],
    [ '6,9', '7,9', '8,9', '9,9', '10,9' ],
    [ '9,8', '10,8' ]
  ],

There should only be one E region.

It turns out, looking above and left wasn't enough.

Can I just add looking right?

Apparently not.

Here's why:

CFE
JEE
JEE

Looking at the E in the middle:

• It will generate a match for the E on the right
• But that E hasn't been catalogued yet
• So it's coordinates won't be in any region
• And my algorithm generates an error when trying to push to a non-existent array

Well...shoot!

This kind of blows up my strategy.

Time to consider a different one, I guess.

Strategy #2: Recursion, Memoization, and Hope

I'll use the small first input as the example:

AAAA
BBCD
BBCC
EEEC

I'll track:

• Visited cells
• List of regions of contiguous cells with the same symbol

Starting in the top-left corner:

Initial state:
No visited cells
No regions

1st iteration at 0,0:
Visited 0,0
One region
Check each adjacent cell
Found 1 unvisited cell with identical symbol

1st iteration, 1st recursion at 0,1:
Visited 0,0; 0,1
One region
Check each adjacent cell
Found 1 unvisited cell with identical symbol

1st iteration, 2nd recursion at 0,2:
Visited 0,0; 0,1; 0,2
One region
Check each adjacent cell
Found 1 unvisited cell with identical symbol

1st iteration, 3rd recursion at 0,3:
Visited 0,0; 0,1; 0,2; 0,3
One region
Check each adjacent cell
Found 0 unvisited cells with identical symbol

2nd iteration at 1,0:
Visited 1,0
Two regions
Check each adjacent cell
Found 2 unvisited cells with identical symbol

2nd iteration, 1st recursion at 1,1:
Visited 1,0; 1,1; 2,0
Two regions
Check each adjacent cell
Found 1 unvisited cell with identical symbol

2nd iteration, 1st recursion at 2,1:
Visited 1,0; 1,1; 2,0; 2,1
Two regions
Check each adjacent cell
Found 0 unvisited cells with identical symbol

2nd iteration, 2nd recursion at 2,0:
Visited 1,0; 1,1; 2,0; 2,1
Two regions
Check each adjacent cell
Found 0 unvisited cells with identical symbol

And so on.

What walking through this helped me understand:

• I should add all unvisited cells with identical symbols to the list of visited cells to avoid counting a cell multiple times during recursion
• The number of adjacent cells that don't match the symbol also counts as that cell's perimeter amount
• This algorithm should only visit each cell once and have great performance

I really hope this works. It seems like it will.

Time to write this up with code!

Programming strategy #2

I kept my array-padding code:

input = input.split('\n').map(line => line.split(''))
input = input.map(line => ['.', ...line, '.'])
input = [
    new Array(input[0].length).fill('.'),
    ...input,
    new Array(input[0].length).fill('.'),
]

I leverage three data structures:

let regions = {}
let visited = new Set()
let nearby = [[-1,0],[0,-1],[0,1],[1,0]]

• Dictionary of regions
• Unique list of visited cells
• The four relative coordinates of adjacent cells

And the nested for loop that checks every cell:

for (let r = 1; r < input.length - 1; r++) {
    for (let c = 1; c < input[0].length - 1; c++) {
        // call recursive function here
    }
}

Then came time to write the recursive function.

It took a few hours.

I struggled to write code that did what was in my head.

Ultimately, though, I prevailed.

Here is my recursive function in its entirety:

function plotter(r, c, memo, depth) {
    if (memo.has(`${r},${c}`)) {
        return false
    } else {
        memo.add(`${r},${c}`)
        let adjacents = nearby.map(rc => {
            let [r1, c1] = [r + rc[0], c + rc[1]]
            let letter = input[r1][c1]
            let isDot = letter == '.' ? true : false
            let isSame = letter == input[r][c]
            let isVisited = memo.has(`${r1},${c1}`)
            if (isDot) {
                return false
            } else if (isSame && !isVisited) {
                return [r1, c1]
            } else if (isSame) {
                return true
            } else {
                return false
            }
        })
        let perimeter = adjacents.filter(el => el == false).length
        let char = input[r][c]
        if (!(char in regions)) {
            regions[char] = []
        }
        if (depth == 0) {
            regions[char].push([])
        }
        regions[char][regions[char].length - 1].push(perimeter)
        adjacents
            .filter(el => typeof el == "object")
            .forEach(el => plotter(el[0], el[1], memo, depth + 1))
    }
}

Here's a walkthrough:

Input is four things: row, column, visited cells, and the depth of the recursion

If this cell has been visited, skip it
Otherwise:
  Mark it as visited
  For each of the four nearby cells
  Determine the letter in the cell
  Is it a dot?
  Is it the same letter?
  Was it visited?
  If it is the same letter and wasn't visited
    Return the cell's coordinates
  If it is the same letter
    Return true
  Otherwise
    Return false
Calculate the perimeter of this cell by tallying which of the four transformed values returned false

Determine the letter in the current cell
If there's no key in the list of regions for this letter
  Make one and make its value an empty list
If this recursive call is the first one in a new series
  Add an empty list to the list associated with this letter in the regions dictionary
Add the perimeter to the last list in this letter's region list
For each item in the transformed list of adjacent cells, excluding any non-array values
  Recurse into this function with the appropriate inputs:
    Row
    Column
    List of visited cells
    A depth that is one greater than the current depth

The logic of depth was the final addition.

It allows my program to figure out when to add a new list to a letter's list of regions.

Does it work?

Small example 1: Yes!
Small example 2: Yes!
Large example: YES!
My puzzle input: YEESSS!!!

Woohooo!!!!!

That was a loooonnngggg road to a gold star.

And I loved almost every minute of it.

I'm glad my first strategy didn't work, too.

Because it helped push me to figure out a much better one that does work!

On to Part 2...

Part 2

Just beyond my grasp

I really want to solve this.

But I can't think of how I would do it programmatically.

I thought hard, too.

Whatever computer science technique this challenge requires, I'm not privy to it.

I must throw in the towel.

I'm still proud of myself for completing Part 1.