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

What a novel puzzle!
Excitement and anticipated disappointment
Crafting a regular expression
Helper function: create range from min-max
Combining regex and range to generate coordinates of veins of clay
Creating the 2D scan from the newly-generated coordinate list
Creating a simulator to reveal the scan
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: