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
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
Top comments (0)