Parabolic Reflector Dish

Advent of Code 2023 Day 14

Part 1

Plenty of time to strategize

I first read the puzzle details several days ago.

I understood the challenge clearly.

I had a decent idea for what I want an algorithm to do.

But I wasn't sure how I'd get it to work.

I think I know well enough now to explore what's in my mind on the page with some code.

Start at the end: Sorting teeny-tiny substrings

That's what I intend to do.

Os first, then .s.

So, a substring like this:

.0...0.

Should become this:

00.....

The way sorting algorithms work is by comparing two items and either:

• Moving one before the other if the difference is -1
• Moving one after the other if the difference is 1
• Moving nothing if the difference is 0

Well, I'm not working with numbers.

So, I'll have to manually return -1, 1 and 0 based on whether the character is a O or ..

Something like this:

For each character in the substring
  If the first character is a 0, return -1
  Else if the first character is a . return 1

There's no need to handle a case returning 0, I don't think.

Let's see if this does what I hope it will.

My algorithm in JavaScript:

str.split('').sort(
  (a, b) => {
    if (a == '0') return -1
    if (a == '.') return 1
  }
).join('')

Running it on:

.0..0.0.

Successfully generates:

000.....

Woohoo!

Back to the beginning: padding the grid with #s

There's a vertical line in the example that, when rearranged in order to appear horizontal, looks like this:

.#.0.......

As shown in the north-tilted output, that line must end up looking like this:

.#0........

My algorithm above is prepared to take this string:

.0.......

And generate:

0........

But how would I isolate that substring from the larger string?

Well, Each # acts as a wall.

If I can identify the location of each # in a string, I can extract all characters between each # as a substring to sort.

But that will be tough with the example string above:

.#.0.......

Sure, there's the one # in it. But it's not on an edge.

I'd need some pretty complicated logic to check whether the first and last #s are on edges.

And I'd rather not. I'd rather trust that there are or aren't.

So, I'll make it so there are.

Right from the start, I'll pad the grid with a border of #s.

So, what starts as:

.O#O
#.0.
.#.0

Will become:

####
.O#O
#.0.
.#.0
####

Now, I can be certain that #s bookend each string. And in most cases there will be at least one substring in each column of the grid to sort.

I suppose there could be a column filled with #s which would have no substrings. My algorithm should account for that naturally, too.

So, how can I pad the grid?

Well, first I have to make a grid from the puzzle input:

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

That should take me from:

.O#O
#.0.
.#.0

To:

[
  ['.','O','#','O'],
  ['#','.','O','.'],
  ['.','#','.','O'],
]

Then, I need to insert two arrays. Both will be four elements. Each element will be a #:

grid.splice(0, 0, ['#','#','#','#'])
grid.splice(-1, 0, ['#','#','#','#'])

Now the grid has #s for bookends...once I turn each column into a string.

Sanity check: writing and testing the code

I wrote my algorithm and tested on the example given.

I had to adjust my splice() calls for two reasons:

• Using -1 inserts items just before the last item, not after. I used the length of the grid instead.
• The example has more than four columns - and my input has tens of columns - so I need a dynamic amount

Here's my working JavaScript algorithm for generating the padded grid:

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

Printing the joined grid string reveals:

##########
O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....
##########

I can now safely attempt to extract substrings from each column string...once I identify the position of each #.

Finding each hashtag in a column

First, I need to turn each column into a string:

grid[0].map((char, index) => {
  let colString = grid.map((row, i) => {
    return grid[i][index]
  }).join('')
})

Viola! When printed, I see the grid rotated and flipped:

#OO.O.O..###
#...OO....O#
#.O...#O..O#
#.O.#......#
#.#.O......#
##.#..O#.###
#..#...O.#.#
#....O#.O#.#
#....#.....#
#.#.O.#O...#

Next, I can use regex to match each # and generate the list of indices:

let hashtags = [...colString.matchAll(/#/g)].map(el => el.index)

As expected, I get lists of numbers, each one containing a 0 and an 11 which represent the bookend #s, along with any others in the column string.

Now what?

Well, I need to slice up the substrings, sort, and concatenate together the final, larger, 'tilted' string!

Extracting each substring

I'll use this string as a working example:

#.O.#......#

The # indices are:

[0, 4, 11]

I therefore want the substrings from indices:

• 1-3
• 5-10

Hmm. So:

For each hashtag index except the last
  Generate a substring from the location one greater than the current index up to and including the location one less than the number one greater than the current index

That sounded real confusing, so here it is with numbers:

   [0, 4, 11]
i = 0  1  2

for i from 0 to 1
  when i is 0
  get substring from (0 + 1) to (4 - 1)

  when i is 1
  get substring from (4 + 1) to (11 - 1)

That makes more sense, to me at least.

In some cases, this for loop may generate an empty string.

That should be ok, though.

I'm ultimately going to concatenate strings together. An empty string will leave a string practically unchanged.

My algorithm for extracting the substrings:

for (let h = 0; h < hashtags.length - 1; h++) {
  let subString = colString.slice(
    hashtags[h] + 1, hashtags[h + 1]
  )
}

Constructing the tilted string

I need hashtags in their original place and modified substrings between the right hashtags.

Here's my algorithm in JavaScript:

let finalString = ""
for (let h = 0; h < hashtags.length - 1; h++) {
  finalString += "#"
  let subString = colString.slice(hashtags[h] + 1, hashtags[h + 1])
  subString = subString.split('').sort(tilt).join('')
  finalString += subString
}
finalString += "#"

Analyzing my results:

Original #OO.O.O..###
Modified #OOOO....###
Original #...OO....O#
Modified #OOO.......#
Original #.O...#O..O#
Modified #O....#OO..#
Original #.O.#......#
Modified #O..#......#
Original #.#.O......#
Modified #.#O.......#
Original ##.#..O#.###
Modified ##.#O..#.###
Original #..#...O.#.#
Modified #..#O....#.#
Original #....O#.O#.#
Modified #O....#O.#.#
Original #....#.....#
Modified #....#.....#
Original #.#.O.#O...#
Modified #.#O..#O...#

I like what I see!

Calculating the total load

Lastly, I need to sum up each round rock's value based on it's location in the tilted string.

I need to account for my padding of #s at each end, too.

So, in this modified string:

#OOOO....###

The amounts by which to multiply each round rock are:

11 10 9 8 7 6 5 4 3 2 1 0
 #  O O O O . . . . # # #

Hmm. Perhaps I can make this easier by reversing the string first, then multiplying by the index.

0 1 2 3 4 5 6 7 8 9 10 11
# # # . . . . O O O O  #

Ya, I like that better.

My algorithm in JavaScript:

let sum = finalString
  .split('')
  .reverse()
  .reduce(
    (accumulator, current, index) => {
       if (current == 'O') {
         accumulator += index
       }
      return accumulator
    }, 0
  )

Works great!

Altogether now

Here's my full algorithm:

function tilt(a,b) {
  if (a == 'O') return -1
  if (a == '.') return 1
}
const part1 = grid[0].reduce((load, char, index) => {
  let colString = grid.map((row, i) => {
    return grid[i][index]
  }).join('')
  let hashtags = [...colString.matchAll(/#/g)].map(el => el.index)
  let finalString = ""
  for (let h = 0; h < hashtags.length - 1; h++) {
    finalString += "#"
    let subString = colString.slice(hashtags[h] + 1, hashtags[h + 1])
    subString = subString.split('').sort(tilt).join('')
    finalString += subString
  }
  finalString += "#"
  let sum = finalString
    .split('')
    .reverse()
    .reduce(
      (acc,curr,idx) => {
         if (curr == 'O') {
           acc += idx
         }
        return acc
      }, 0
    )
  return load += sum
}, 0)

By golly, it works, too!

It generates the correct answer for the example input.

And for my puzzle input!

Woohoo!!!

Part 2

It was inevitable, right?

• Checkpoint: a single direction, one time
• Real race: four directions, one million times

Because of course!

My problem won't be each direction.

It will be re-constructing the original grid layout after each tilt...since my algorithm reassembles columns and flips the grid horizontally and vertically.

Time to get back to work!

First: fixing north

As I just mentioned, my algorithm generates a mutated copy of the grid after 'tilting' it.

I now need to perform the tilt and ensure the resulting grid retains columns and rows, albeit 'sorted' correctly after a tilt.

Fast-forward: finished, after two obstacles

Obstacle #1: I needed to pad all four sides with #s first. I was hoping I could wait to do it, but I needed a square area grid.

Obstacle #2: I mistakenly attempted to access my original grid when I meant to access one of several intermediate grids. Ultimately, I just re-assign updated grids to the same variable to keep things foolproof.

Here's my completed north-tilting function:

function north() {
  grid = grid[0].map((char, col) => {
    let colString = grid.map((row, i) => {
      return grid[i][col]
    }).join('')
    let hashtags = [...colString.matchAll(/#/g)]
      .map(el => el.index)
    let finalString = ""
    for (let h = 0; h < hashtags.length - 1; h++) {
      finalString += "#"
      let subString = colString.slice(hashtags[h] + 1, hashtags[h + 1])
      subString = subString.split('').sort(tilt).join('')
      finalString += subString
    }
    finalString += "#"
    return finalString.split('')
  })
  grid = grid[0].map((char, col) => {
    return grid.map((row, i) => {
      return grid[i][col]
    })
  })
}

Running it on the example grid generates these before-after states:

Before
############
#O....#....#
#O.OO#....##
#.....##...#
#OO.#O....O#
#.O.....O#.#
#O.#..O.#.##
#..O..#O..O#
#.......O..#
##....###..#
##OO..#....#
############ 

After
############
#OOOO.#.O..#
#OO..#....##
#OO..O##..O#
#O..#.OO...#
#........#.#
#..#....#.##
#..O..#.O.O#
#..O.......#
##....###..#
##....#....#
############

Tilting south: one small change, twice

I really mean that. One small change. In two places.

I just have to reverse the strings I generate from each column. This simulates tilting in the other direction.

Here's my south-tilting function, with two added reverse() method calls:

function south() {
  grid = grid[0].map((char, col) => {
    let colString = grid.map((row, i) => {
      return grid[i][col]
    }).reverse().join('')
    let hashtags = [...colString.matchAll(/#/g)]
      .map(el => el.index)
    let finalString = ""
    for (let h = 0; h < hashtags.length - 1; h++) {
      finalString += "#"
      let subString = colString.slice(hashtags[h] + 1, hashtags[h + 1])
      subString = subString.split('').sort(tilt).join('')
      finalString += subString
    }
    finalString += "#"
    return finalString.split('').reverse()
  })
  grid = grid[0].map((char, col) => {
    return grid.map((row, i) => {
      return grid[i][col]
    })
  })
}

Running it on the example grid generates these before-after states:

Before
############
#O....#....#
#O.OO#....##
#.....##...#
#OO.#O....O#
#.O.....O#.#
#O.#..O.#.##
#..O..#O..O#
#.......O..#
##....###..#
##OO..#....#
############ 

After
############
#.....#....#
#....#....##
#...O.##...#
#...#......#
#O.O....O#O#
#O.#..O.#.##
#O....#....#
#OO....OO..#
##OO..###..#
##OO.O#...O#
############

Tilting west: the easiest of the four

Why the easiest?

• No generating strings from each column
• No need to reverse anything

Here's the function:

function west() {
  grid = grid.map((row) => {
    let hashtags = [...row.join('').matchAll(/#/g)]
      .map(el => el.index)
    let finalString = ""
    for (let h = 0; h < hashtags.length - 1; h++) {
      finalString += "#"
      let subString = row.join('').slice(hashtags[h] + 1, hashtags[h + 1])
      subString = subString.split('').sort(tilt).join('')
      finalString += subString
    }
    finalString += "#"
    return finalString.split('')
  })
}

And the before-after:

Before
############
#O....#....#
#O.OO#....##
#.....##...#
#OO.#O....O#
#.O.....O#.#
#O.#..O.#.##
#..O..#O..O#
#.......O..#
##....###..#
##OO..#....#
############ 

After
############
#O....#....#
#OOO.#....##
#.....##...#
#OO.#OO....#
#OO......#.#
#O.#O...#.##
#O....#OO..#
#O.........#
##....###..#
##OO..#....#
############

Tilting east: same small change, twice

Much in the same way south differed from north, I have to do two reversals: one initially and one again to reset things.

Here's the function:

function east() {
  grid = grid.map((row) => {
    row = row.reverse()
    let hashtags = [...row.join('').matchAll(/#/g)]
      .map(el => el.index)
    let finalString = ""
    for (let h = 0; h < hashtags.length - 1; h++) {
      finalString += "#"
      let subString = row.join('').slice(hashtags[h] + 1, hashtags[h + 1])
      subString = subString.split('').sort(tilt).join('')
      finalString += subString
    }
    finalString += "#"
    return finalString.split('').reverse()
  })
}

And the before-after:

Before
############
#O....#....#
#O.OO#....##
#.....##...#
#OO.#O....O#
#.O.....O#.#
#O.#..O.#.##
#..O..#O..O#
#.......O..#
##....###..#
##OO..#....#
############ 

After
############
#....O#....#
#.OOO#....##
#.....##...#
#.OO#....OO#
#......OO#.#
#.O#...O#.##
#....O#..OO#
#.........O#
##....###..#
##..OO#....#
############

Testing a few cycles on the example input

I get 3 cycles to use as tests for my algorithm.

Here's my algorithm that will run a complete cycle:

function cycle() {
  north()
  west()
  south()
  east()
}

Running it once produces the expected grid!

Running it twice produces the expected grid!

Running it thrice produces the expected grid!

This is a good sign.

Now I need to re-incorporate my calculation of the total load.

Finishing with the total load calculation

Things get tricky because I padded my grid.

I have to account for the extra row on each end of the grid.

I need the numbers to the right as multipliers for each row:

############
#O....#....# 10 
#O.OO#....## 9
#.....##...# 8
#OO.#O....O# 7
#.O.....O#.# 6
#O.#..O.#.## 5
#..O..#O..O# 4
#.......O..# 3
##....###..# 2
##OO..#....# 1
############

To get that, I figure:

  Grid length = 12
- 2
------------------
  10
- One less than index of current row
------------------
  Correct multiplier amount

For the row that should be 10

  12
- 2
-----
  10
- (1 - 1) = 0
-----
  10

For the row that should be 9

  12
- 2
-----
  10
- (2 - 1) = 1
-----
  9

And so on.

Here's my function with what I am fairly confident is correct math:

function calcLoad() {
  return grid.reduce(
    (sum, row, index) => {
      return sum += [...row.join('').matchAll(/O/g)].length 
                    * ( (grid.length - 2) - (index - 1) )
    }, 0
  )
}

The part I overlooked: cycle completion speed

I have to simulate running a billion cycles!

I presumed that my algorithm would process cycles quickly - at least on the example input.

Sadly, these are the metrics:

• 80k cycles/min on example input
• <1k cycles/min on my puzzle input

So...there's no way I'll ever process a billion cycles with my multi-array-generating algorithm.

New strategy: identify whether grid state repeats

I'll bet that after enough cycles, the state of the grid repeats.

I'll further bet that I just have to figure that out and extrapolate it out far enough to find the grid's state after a billion cycles have completed.

Worth a try!

Collecting states and cycles completed

I think I need a dictionary that looks like this:

{
  'O.#.O\n#..OO.\n': [3, 433, 866],
  '#O..O\n##.O.O\n': [15, 448, 914],
}

With that, I could:

• Print anytime a state has occurred
• Print all states and look for patterns in the difference between occurrences

Off to code!

...

I'm back.

This is my state-checking-and-saving function that gets called from my for loop:

function checkState(i) {
  let state = grid.map(row => row.join('')).join('\n')
  if (!(state in states)) {
    states[state] = [i]
  } else {
    states[state].push(i)
  }
}

The results are in:

• The arrays are amassing values, as expected!
• The values in each array that tracks which cycle the repeated state occurred in differ by exactly 7!

This is great news.

Now, I have to find the state that repeats on a cycle interval that will eventually intersect with a billion.

Fast-forward: so much trial and error

Once I got the code above working, I just kept going.

And getting stuck.

Then going.

Then getting stuck.

How?

• I calculated the remainder after dividing 1B by 7. It's 6.
• I wrote code to find the state string corresponding to the array of repeated cycles with a 6 in it
• I updated the grid to reflect that state
• I calculated the total load
• I got an answer different from the expected answer

What was I doing wrong?

• My cycle loop starts at 0
• So, I should have looked for the remainder after dividing 999,999,999 by 7. It's 5.
• I ran the code to find the right state string
• I updated the grid
• I calculated the total load
• I got the correct answer!

I figured I could do the same for my puzzle input.

I was quite wrong.

How wrong was I?

• The example input's states start repeating almost immediately: after just a few cycles
• My puzzle input's states don't start repeating until after at least 100 cycles

It took a lot of troubleshooting to come to that realization.

Like, major scavenger hunt through multiple console logs.

But once I discovered that fact, I knew I was close to solving this part.

My cycles start repeating after the 102nd cycle.

They repeat every 14 cycles.

So, I needed to calculate:

• The nearest whole number after dividing 999,999,999 by 14
• The first number below that number in increments of 14 that, when increased by the correct number from 102-115, equates to 999,999,999

After doing some mental math, I determined that my magic winning number is 103:

 999,999,999
/         14
------------
  71,428,571
  71,428,570
  71,428,569
  71,428,568
  71,428,567
  71,428,566
  71,428,565
  71,428,564 !!!
*         14
------------
 999,999,896
+        103
------------
 999,999,999

• I ran the code to find the right state string whose array value started with 103
• I updated the grid
• I calculated the total load
• I got the correct answer!

Woohoo!!!

That took forever!

But, once again, I'm glad I persisted.

And now, for some time away...before moving on to Day 15.