DEV Community

Cover image for Chronal Coordinates
Robert Mion
Robert Mion

Posted on

Chronal Coordinates

Advent of Code 2018 Day 6

Try the simulator using your puzzle input!

Region revealed!

Task: Solve for X where...

Part 1

X = the size of the largest area that isn't infinite
Enter fullscreen mode Exit fullscreen mode

Part 2

X = the size of the region containing all locations which have a total distance to all given coordinates of less than 10000
Enter fullscreen mode Exit fullscreen mode

Example input

1, 1
1, 6
8, 3
3, 4
5, 5
8, 9
Enter fullscreen mode Exit fullscreen mode

It represents:

  • A list of coordinates
  • They may be safe or dangerous
  • They exist among a 2D grid that extends infinitely in all directions
  • Only the coordinates that have a finite amount of adjacent coordinates whose Manhattan distance is closest to the source coordinate are considered safe

Part 1

  1. Outlining the steps required to render my input's 2D grid
  2. Step by step
  3. Completing step 5/5
  4. Filtering, counting, hoping

Outlining the steps required to render my input's 2D grid

  1. Parse the input for each X,Y coordinate
  2. Determine the frame of the area that bounds my coordinates
  3. Assign each coordinate a unique symbol
  4. Render the 2D grid containing just the target coordinates
  5. Render the 2D grid with all other coordinates marked using the symbol of the target coordinate that has the closest Manhattan Distance

Step by step

Steps 1-4 were straightforward.

Within a half hour, I wrote an ~14-line algorithm that generated the 2D grid with each target coordinate placed, and built a simulator to render the grid at the press of a button.

Initial setup of simulator

Completing step 5 would take a bit more effort.

Completing step 5

After another half hour, I wrote another ~14-line algorithm that processed every coordinate in my 2D grid, determining its Manhattan Distance to each target coordinate, and setting either the symbol of the closest coordinate, or a . to indicate a tie for closest targets

All coordinates marked according to their closest targets

The last bit of work is:

  • Filtering out characters that touch the edge of the visible grid, since they go on forever
  • Tallying the counts of each character
  • Determine the largest tally
  • Cross my fingers that it's the correct answer

Filtering, counting, hoping

Determine all symbols that occupy the edge of the visible grid, since they go on forever
Generate a subset of symbols, excluding the ones identified just now
Create a dictionary that will store keys for each symbol in the subset, and tallies for each occurrence as values
Count each instance
Return the largest count
Enter fullscreen mode Exit fullscreen mode

The results:

  • It worked on the example input!
  • It worked on my puzzle input!

Largest infinite area successfully identified

Part 2

  1. Could it be that easy?
  2. Yes, it could!

Could it be that easy?

  • My algorithm already calculates the Manhattan Distances from each target coordinate...for each cell in the framed grid
  • For Part 1, I checked for the smallest number among those distances
  • For Part 2, I just need to add them together and check whether the sum is less than 10000
  • If it is, I'll mark the cell with a #
  • Else, I'll mark the cell with a .
  • That will hopefully reveal the region

Yes, it could!

Viola!

Region revealed!

I did it!!

  • I solved both parts!
  • I made a simulator that helped me solve each part!

Top comments (0)