DEV Community

Cover image for Monitoring Station
Robert Mion
Robert Mion

Posted on

Monitoring Station

#adventofcode #algorithms #computerscience #programming

Advent of Code 2019 Day 10

Task: Solve for X where...

Part 1 

X = the number of visible asteroids that can be detected from the asteroid where the most asteroids are visible
Enter fullscreen mode Exit fullscreen mode

Part 2 

X = the result of an equation leveraging the coordinates of the 200th asteroid destroyed by a laser located on the asteroid identified in Part 1
Enter fullscreen mode Exit fullscreen mode

Example input 

.#..# ..... ##### ....# ...##
Enter fullscreen mode Exit fullscreen mode

It represents:

  • A map of all the asteroids in a region of space
  • .s are emptiness
  • #s are asteroids (tiny ones that only occupy a small space at the center of that location)

Part 1

  1. Visualizing each angle for a few points to try crafting an algorithm
  2. Considering better paths that an algorithm could follow
  3. A visual depiction of the algorithm I plan to build
  4. A written summary of how the algorithm should work
  5. Woah. That worked! I'm shocked!

Visualizing each angle for a few points to try crafting an algorithm

Here's the example input again:

.#..# ..... ##### ....# ...##
Enter fullscreen mode Exit fullscreen mode

I'll use the center asteroid in the example input map region:

 #
Enter fullscreen mode Exit fullscreen mode

The eight easy lines of sight to check are horizontal, vertical and diagonals:

\ | / 812 -7#3- 654 / | \
Enter fullscreen mode Exit fullscreen mode

Using center as (0,0):

  • 1 is at angle (-1, 0)
  • 2 is at angle (-1, 1)
  • 3 is at angle ( 0, 1)
  • 4 is at angle ( 1, 1)
  • 5 is at angle ( 1, 0)
  • 6 is at angle ( 1,-1)
  • 7 is at angle ( 0,-1)
  • 8 is at angle (-1,-1)

But how would I get each of the other 352 angles?
Or, well, other 8 angles in this example?

 8 1 7 2 # 6 3 5 4
Enter fullscreen mode Exit fullscreen mode

Using center as (0,0):

  • 1 is at angle (-2, 1)
  • 2 is at angle (-1, 2)
  • 3 is at angle ( 1, 2)
  • 4 is at angle ( 2, 1)
  • 5 is at angle ( 2,-1)
  • 6 is at angle ( 1,-2)
  • 7 is at angle (-1,-2)
  • 8 is at angle (-2,-1)

Do I notice any patterns?

  • The range for X,Y values spans the boundaries of the region: from (0,0) it's (-2 to 2, -2 to 2)

Here's the example input again:

.#..# ..... ##### ....# ...##
Enter fullscreen mode Exit fullscreen mode

Now, I'll use the winning asteroid in the example input map region:

..... ..... ..... ..... ...#.
Enter fullscreen mode Exit fullscreen mode

The direct lines to check are:
First angle: (-1,0) until an asteroid is spotted or the region boundary is exceeded

  • Check (-1,0): empty
  • Check (-2,0): hit! stop

Next angle: (-4,1)...

  • Check (-4,1): hit! stop

Next angle: (-3,1)...

  • Check (-3,1): empty
  • Check (-6,2): out of range! stop

Next angle: (-2,1)...

  • Check (-2,1): hit! stop

Next angle: (-1,1)...

  • Check (-1,1): hit! stop

Next angle: ( 0,1)...

  • Check (0,1): hit! stop

Somehow skip to degrees 90 - 269.

Next angle: (0,-1)...

  • Check (0,-1): empty
  • Check (0,-2): empty
  • Check (0,-3): empty
  • Check (0,-4): out of range! stop

Next angle: (-1, -3)...

  • Check (-1, -3): empty
  • Check (-2, -6): out of range! stop

Next angle: (-1, -2)...

  • Check (-1, -2): empty
  • Check (-2, -4): out of range! stop

Next angle: (-1, -1)...

  • Check (-1, -1): empty
  • Check (-2, -2): hit! stop

Next angle: (-2, -1)...

  • Check (-2, -1): hit! stop

Next angle: (-3, -1)...

  • Check (-3, -1): empty
  • Check (-6, -2): out of range! stop

Next angle: (-4, -1)...

  • Check (-4, -1): empty
  • Check (-8, -2): out of range! stop

Wait, that's only 7 hits. There should be 8. What did I miss?

..... ..... *.... ..... ...S.
Enter fullscreen mode Exit fullscreen mode

That is at angle: (-2, -3)
How could I have targeted that?

  • Not via any (-1,x) path
  • Only via the (-2,x) path

But from (-2,-1) there's:

  • (-2,-2), which has already been checked

I guess I could have just kept going until out of range:

  • (-2,-3): hasn't been checked, is a hit!

So, what might my path have been?

Part 1 ....3 ....4 ...25 ...16 ...#7 Part 2 ....x ....x .7.xx 456xx 321#x Part 3 987.x 654.x 321xx xxxxx xxx#x
Enter fullscreen mode Exit fullscreen mode

That seems like a custom path, not one followed by some consistently incrementing or decrementing X,Y relative coordinates.

Considering better paths that an algorithm could follow

The example input, again:

.#..# ..... ##### ....# ...##
Enter fullscreen mode Exit fullscreen mode

From the middle point, four paths that start from each diagonal and continue toward a border:

^^ -> || -> # <- || <- vv
Enter fullscreen mode Exit fullscreen mode

Followed by checks of the horizontal and vertical lines of sight:

 ^ | <-#-> | v
Enter fullscreen mode Exit fullscreen mode

Altogether forming this pattern:

^^^-> |||-> <-#-> <-||| <-vvv
Enter fullscreen mode Exit fullscreen mode

Or, following concentric circles:

First pass \ | / 812 -7#3- 654 / | \ Next pass .8.1. 7...2 ..#.. 6...3 .5.4.
Enter fullscreen mode Exit fullscreen mode

Yikes. This feels overly complicated.

But I've got to try building it!

A visual depiction of the algorithm I plan to build

This demonstrates how the algorithm I plan to build should work:
Visualization of my Part 1 algorithm

A written summary of how the algorithm should work 

For each value in the region map that contains an asteroid Perform two rounds: one starting from each immediate diagonal coordinate, and another from each horizontally- and vertically-adjacent coordinate Round 1 For each of the four immediately diagonal coordinates Visit every cell in that quadrant bordered by the x- and y-axes Track the tally of asteroids spotted, starting at 0 Track a unique set of values representing coordinates of each visited cell From each initial cell Track how many asteroids were spotted via a list of boolean values Do as long as the cell exists in the map region As long as the cell hasn't been visited yet If it is an asteroid, add True to the list of spotted asteroids Else, add False to the list Add it to the list of visited cells Move a distance equal to the relative distance between the originating coordinate and the initial cell's coordinates If there is at least one True value in the list of spotted asteroids, increment the tally by 1 Return the tally Return the sum of all four tallies Round 2 For each of the four horizontally- and vertically-adjacent coordinates Track the tally of asteroids spotted, starting at 0 Do as long as the cell exists in the map region If the cell's value is an asteroid Increment the tally by 1 Break Else, move one step in the current direction (up, right, down or left) Return the tally Return the sum of all four tallies Return the sum of each sum of tallies Return the largest sum from the new list of summed tallies
Enter fullscreen mode Exit fullscreen mode

Woah. That worked! I'm shocked!

  • I ran it on each example
  • Each time it generated the correct answer
  • I ran it on my puzzle input
  • And it, too, generated the correct answer!

Part 2

  1. Yikes! Order matters now.
  2. Throwing in the towel

Yikes! Order matters now.

  • We're still counting...
  • But from a specific angle...
  • In a specific direction...
  • So the order of asteroid detection is important

Throwing in the towel

I can't think of an algorithmic way to re-create a pathfinding algorithm akin to the abstract laser rotating in this puzzle.

So, sadly, Part 2 will go unsolved.

Celebrating my accomplishments

  • I solved Part 1! I really didn't think I would.
  • I made a cool GIF that accurately visualized my peculiar algorithm

Bummer:

  • No simulator...mostly because it didn't seem worth it
  • No correct answer for Part 2...though I'm content with solving Part 1

Today's puzzle was a wonderful twist on the recurring 'find adjacent things' theme.

And I'm so delighted I solved Part 1.

Top comments (0)