Like a Rogue

Advent of Code 2016 Day 18

Part 1

1. Seems easy enough...by now
2. Visualizing the rules
3. Getting from relative coordinates to trap or safe
4. Creating the initial state of rows
5. Counting the safe tiles
6. Testing my algorithm

Seems easy enough...by now

• Reveal N number of rows in the grid
• Using specific adjacent tiles
• And a set of rules

I got this!

Visualizing the rules

Given...

ABC
 1

1 is a trap when:

ABC = T--
ABC = TT-
ABC = -TT
ABC = --T

1 is therefore safe when:

ABC = ---
ABC = -T-
ABC = T-T
ABC = TTT

Getting from relative coordinates to trap or safe

This animation outlines my planned algorithm visually:

This pseudocode better describes my planned algorithm and incorporates a modified dictionary from the one hinted at in the animation above:

Create an object with eight keys
  Each key is a 3-character representation of the rule to match, and the value is the resulting tile state

Set each tile as safe or trap based on the character returned from the following operations:
   Create a list of three relative coordinates:
     1. [-1,-1]
     2. [-1, 0]
     3. [-1, 1]
   Update each coordinate depending on the value of the cell that distance from the current tile:
     If the value is safe or the cell is outside the bounds of the grid
       Use 0
     Else, it's a trap
       Use 1
   Concatenate all three numbers together to form a 3-character string
   Return the character associated with the 3-character string in the eight-key object

This JavaScript is the actual working algorithm:

rules = {
    '000': '.',
    '010': '.',
    '101': '.',
    '111': '.',
    '100': '^',
    '110': '^',
    '011': '^',
    '001': '^'
}
// For each col in each row...
tiles[row][col] = rules[
  [[-1,-1],[-1,0],[-1,1]]
    .map(el => {
        let tile = tiles[row + el[0]][col + el[1]]
        switch (typeof tile) {
          case "undefined":
            return 0
            break;
          case "string":
            return tile == "." ? 0 : 1
            break;
        }
      }
    )
    .join('')
]

Creating the initial state of rows

The above JavaScript references an array of arrays called tiles.

What should that array look like before iterating through all cells but those in the first row?

For the input of ..^^. with 3 rows:

[
 ['.','.','^','^','.'],
 [ , , , , ]
 [ , , , , ]
]

How might I construct that nested array?

let tiles = new Array(3)
  .fill(null)
  .map(
    el => new Array(input.length).fill(null)
  )
tiles[0] = input.split('')

• All but the last line create a nested array with null as each cell's value
• The last line replaces the first array with one generated from each character in the input string

Counting the safe tiles

reduce() to the rescue, twice!

• The inner one counts up each safe tile in a row
• The outer one tallies each row's count

tiles.reduce(
  (sum1, row) => sum1 += row.reduce(
    (sum2, cell) => sum2 += cell == '.' ? 1 : 0, 0)
  , 0)

Testing my algorithm

I call my function like this:

part1(input, rows)

• part1('..^^.', 3): 6
• `part1('.^^.^.^^^^', 10): 38

And with my puzzle input for 40 rows: 1926

That is the correct answer!

Part 2

And with my puzzle input for 400K rows:
...
...
Nearly 20M!

That is the correct answer again!

Admittedly, it took over 10 seconds to run.

I did it!!

• I solved both parts!
• At this point, I feel very confident working with simpler adjacent cell-themed puzzles like this one!
• As long as the performance test in Part 2 isn't absurd!