DEV Community

Cover image for Like a Rogue
Robert Mion
Robert Mion

Posted on

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
Enter fullscreen mode Exit fullscreen mode

1 is a trap when:

ABC = T--
ABC = TT-
ABC = -TT
ABC = --T
Enter fullscreen mode Exit fullscreen mode

1 is therefore safe when:

ABC = ---
ABC = -T-
ABC = T-T
ABC = TTT
Enter fullscreen mode Exit fullscreen mode

Getting from relative coordinates to trap or safe

This animation outlines my planned algorithm visually:

Determining a tile's state

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
Enter fullscreen mode Exit fullscreen mode

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('')
]
Enter fullscreen mode Exit fullscreen mode

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:

[
 ['.','.','^','^','.'],
 [ , , , , ]
 [ , , , , ]
]
Enter fullscreen mode Exit fullscreen mode

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('')
Enter fullscreen mode Exit fullscreen mode
  • 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)
Enter fullscreen mode Exit fullscreen mode

Testing my algorithm

I call my function like this:

part1(input, rows)
Enter fullscreen mode Exit fullscreen mode
  • part1('..^^.', 3): 6
  • `part1('.^^.^.^^^^', 10): 38

And with my puzzle input for 40 rows: 1926

The tiles in my puzzle input for 40 rows

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!

SurveyJS custom survey software

Build Your Own Forms without Manual Coding

SurveyJS UI libraries let you build a JSON-based form management system that integrates with any backend, giving you full control over your data with no user limits. Includes support for custom question types, skip logic, an integrated CSS editor, PDF export, real-time analytics, and more.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay