Reservoir Research

Advent of Code 2018 Day 17

Try the scan renderer to see your puzzle input's veins of clay

Task: Solve for X where...

Part 1

X = the number of tiles the water can reach within the range of y values in my scan

Example input

x=495, y=2..7
y=7, x=495..501
x=501, y=3..7
x=498, y=2..4
x=506, y=1..2
x=498, y=10..13
x=504, y=10..13
y=13, x=498..504

It represents:

• A two-dimensional scan of a vertical slice of the ground nearby
• x represents the distance to the right
• y represents the distance down
• The scan identifies which square meters are clay
• There is also a spring of water near the surface at x=500, y=0

Part 1

1. What a novel puzzle!
2. Excitement and anticipated disappointment
3. Crafting a regular expression
4. Helper function: create range from min-max
5. Combining regex and range to generate coordinates of veins of clay
6. Creating the 2D scan from the newly-generated coordinate list
7. Creating a simulator to reveal the scan
8. Giving up, as anticipated

What a novel puzzle!

Familiar concepts:

• It is another 2D area
• Comprised of a handful of tile types
• With one coordinate acting as a quasi-starting spot

New concept:

• The crux of the puzzle is an unending stream emanating from the starting spot
• The 2D area must simulate gravity and physics

Excitement and anticipated disappointment

I'm excited to make a simulator that renders the 2D scan using my puzzle input.

I anticipate not solving either part of this puzzle:

• Definitely not with an algorithm
• And likely not manually
• I foresee the 2D scan to be so vast and complex that I won't have the patience to draw the eventual state with water flowing into each reservoir

Crafting a regular expression

I need to match these sorts of statements:

x=322, y=33..38
y=1437, x=389..403
x=502, y=72..82
y=944, x=505..511
x=359, y=100..120
y=1264, x=570..581

The pattern appears to be:

[x|y]=\d+, [x|y]=\d+..\d+

• Single x or y point
• Followed by x or y range
• It seems like the range is always increasing

The data I need is:

Option A:
x: int
y:
 min: int
 max: int

Option B:
y: int
x:
 min: int
 max: int

Time to use regexr.com to play, test and troubleshoot!

Wow, I was spot-on - just needed my capture groups:

/([x|y])=(\d+), ([x|y])=(\d+)\.\.(\d+)/g

Helper function: create range from min-max

• I made this function in several prior exercises
• I looked up my code
• Then I looked up how others solved it
• I wasn't far off from the most eloquent solution, in my opinion

Function range
Accept two parameters:
  1. Minimum integer
  2. Maximum integer

Create an array
  Where the length is equal to the the maximum number minus the minimum number, plus 1
  Set the value of each item equal to the index of the item plus the minimum number

Example:

range(5,10)

New array of length: 10 - 5 + 1 = 6
[?,?,?,?,?,?]

For each item, value = index + minimum
[0 + 5, 1 + 5, 2 + 5, 3 + 5, 4 + 5, 5 + 5]

Result:
[5,6,7,8,9,10]

Combining regex and range to generate coordinates of veins of clay

So many applications of programming fundamentals:

• Reading a file's contents
• Splitting a string into an array at each instance of a particular character
• Matching substrings based on a regular expression featuring captured groups
• Extracting only the needed items from the array resulting from iterating through each matched substring's captured groups
• Using a switch statement to conditionally perform certain operations based on the contents of one piece of data
• Mutating in-place each value in an array into an array, then flattening that array such that what I'm left with is each inner array

All of this in order to convert input like this:

x=495, y=2..7
y=7, x=495..501
x=501, y=3..7
x=498, y=2..4
x=506, y=1..2
x=498, y=10..13
x=504, y=10..13
y=13, x=498..504

Into coordinates like this:

[
  [ 2, 495 ],  [ 3, 495 ],  [ 4, 495 ],
  [ 5, 495 ],  [ 6, 495 ],  [ 7, 495 ],
  [ 7, 495 ],  [ 7, 496 ],  [ 7, 497 ],
  [ 7, 498 ],  [ 7, 499 ],  [ 7, 500 ],
  [ 7, 501 ],  [ 3, 501 ],  [ 4, 501 ],
  [ 5, 501 ],  [ 6, 501 ],  [ 7, 501 ],
  [ 2, 498 ],  [ 3, 498 ],  [ 4, 498 ],
  [ 1, 506 ],  [ 2, 506 ],  [ 10, 498 ],
  [ 11, 498 ], [ 12, 498 ], [ 13, 498 ],
  [ 10, 504 ], [ 11, 504 ], [ 12, 504 ],
  [ 13, 504 ], [ 13, 498 ], [ 13, 499 ],
  [ 13, 500 ], [ 13, 501 ], [ 13, 502 ],
  [ 13, 503 ], [ 13, 504 ]
]

Creating the 2D scan from the newly-generated coordinate list

Now, I must use the coordinate list above to create a multi-dimensional array that could be stringified to resemble this:

......+.......
............#.
.#..#.......#.
.#..#..#......
.#..#..#......
.#.....#......
.#.....#......
.#######......
..............
..............
....#.....#...
....#.....#...
....#.....#...
....#######...

My algorithm to get from point A to B:

Create an empty array, grid

For each coordinate
  If there is not a value at the index referenced by the number in the first position in the coordinate
    Store an empty array at that position in grid, creating empty spaces for any non-existent positions between points
  Store the character '#' as the value in the position referenced by the number in the second position in the coordinate in the nested array at the position referenced by the number in the first position in the coordinate

Calculate max, the highest-value position that a `#` occupies among all nested arrays:
  Filter grid to only include arrays (no empty slots)
  Change each array to become its length
  Return the highest value from all of the numbers
Calculate min, the lowest-value position that a `#` occupies among all nested arrays:
  Filter grid to only include arrays (no empty slots)
  If the array includes a '#'
    Return the index of the first '#'
  Else
    Return max
  Return the lowest value from all of the numbers

Update grid to the result of the following operations:
  Create a new array from grid, where:
    If the element has a value, leave it unchanged
    Else, store an empty array
  For each array in the new grid array
    Set each array's length to one greater than max (creating empty slots where necessary)
    Create a new array from the current array, where:
      If the element has a value, leave it unchanged
      Else, store the character '.'
    If it is the first array
      Update the character at location 500 to a '+'
    Return only the characters from locations one less than min, to the end of each array

While writing this algorithm, I learned some valuable knowledge about working with empty slots in arrays:

• Targeting those values is tricky
• I thought I could use map() to change them into arrays
• But that didn't work

Instead, I needed to use Array.from() with a function that checks for truthy/falsy values, like this:

Array.from(array, item => item || 0)

• This will copy all truthy values in an array
• And will replace all falsy values with 0
• Empty slots are falsy values in JavaScript

That was a fun exercise!

I wonder how it will work on my puzzle input.

Creating a simulator to reveal the scan

• This was no trouble at all
• The tougher part was saving an image of the ridiculously tall scan

The scan of ground using my puzzle input:

• You'll need to click on the image
• Then click again to zoom in

A pan of that image:

Giving up, as anticipated

• It took me this long just to reveal the scanned ground
• The area is massive, so I'm definitely not about to attempt this puzzle through manual efforts
• I have no idea how I would solve it algorithmically
• So, this is where my time with the puzzle ends

Celebrating my accomplishments

• I generated an ASCII image of the scanned area!
• To do that, I practiced some fundamental programming methods and discovered new 'hacks' for dealing with empty array values

Bummers:

• I didn't solve Part 1
• Heck, I didn't even attempt to solve Part 1...aside from parsing the input and seeing the map

In conclusion:

• I accomplished what I set out to do
• I failed to accomplish the task I anticipated struggling at
• I still really enjoyed my time with this puzzle