Like a Rogue
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-08-19 17:01:43

## [Advent of Code 2016 Day 18](https://adventofcode.com/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:
![Determining a tile's state](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jvz6zz5osla3gc3ttgmj.gif)

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:
```js
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:
```js
[
 ['.','.','^','^','.'],
 [ , , , , ]
 [ , , , , ]
]
```

How might I construct that nested array?

```js
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
```js
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

![The tiles in my puzzle input for 40 rows](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/48ni3q9lqeehryvtsk2n.png)

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!