ShareMyScreen/AdventOfCode/2022/14/RegolithReservoirJP
A problem that made me think, for sure. It looks like simple simulation, especially for part 1, but part 2 put me with my nose on the fact that my first idea was not efficient. I had a lovely time finding a recursive solution that beat the hell out of my one-potato two-potato approach that I started out with.
Entire Solution
i14=: freads '14.txt'
NB. Part 1: sand enters at 0 500, falls down as far as it can, if not, diagonal, left, otherwise right, otherwise stop
NB. parse input: one path per line (assume no - numbers), returning list of coordinates
par=: [: /:~@:(|."1)@~.@; <@([: ; 2 <@to/\ [:".;._1 '>',' -'-.~]);._2
NB. to, dyad, for range [x,y], also non-ordered x,y. Happens to work for (x0 y0) to (x1 y1) as well, as long as only 1 direction
to =: [: |: <. + i.@(+_1+2*0&<:)@-~
NB. offsets, w.r.t. sand unit, ordered by preference
OFS =: 3 2$1 0 1 _1 1 1
NB. Recursive approach: Pass list of known obstacles down, and have every level add their obstacles to it.
rec =: {{
LOW =: >./{."1 y NB. lowest point in map = highest row coord. used for detecting overflow.
MSG=: _1 _1 NB. coords used as special "message" to abort descent
NB. GO: recursive depth first search
NB. y: obstacle coords; x: pt;
NB. returns *new* obstacle coords (for use by lower ranked neighbors and upwards)
GO =: {{
if. LOW < {.x do. ,:MSG return. end. NB. if dropped to abbys: send "abort"
if. x e.!.0 y do. 0 2$0 return. end. NB. don't add if already in obstacles (y)
addpt=. 0 2$0 NB. newly found points
for_pt. x+"1 OFS do. NB. for reachable points, in order:
NB. find points below, consider points previously found by higher ranking moves: recurse
if. MSG -:{.res=.pt GO y,addpt do. NB. if _1 _1, we fell through: abort
res,addpt return. NB. pt NOT added!
else.
addpt=. addpt, res NB. accumulate & continue
end.
end.
x,addpt NB. All visited, point added and returned upward
}}
NB. not simply behead, as part 2 does not overflow
MSG -.~ 0 500 GO y
}}
part1=: #@rec@ par
NB. Part 2: there's an infinite floor at deepest -2. find how many units when sand reaches 500 0
NB. addfloor, takes coords, adds line wide enough to be "infinite" i.e. 0-1000
addfloor =: (, [: (] to/@,. (500 (+,-) >:)) 2 + >./@:({."1))
part2=: #@rec@addfloor@par
(part1;part2)i14
Data and parsing
The data is given in a rather obnoxious way this time, with each line defining points of a line.
tst=: {{)n
498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
}}
These lines for barriers stopping sand that falls from the position 0 500 into a space.
For seeing where sand will land, I need to know all positions on any of the lines. Which points are on which lines is irrelevant. A line between two points can be defined with a variation of the to verb of day 8:
to =: [: |: <. + i.@(+_1+2*0&<:)@-~
NB. day 8: <. + i.@(+_1+2*0&<:)@-~
It's a dyad, taking two pairs of coordinates and returning a list of coordinates between them. It being so similar to the one of day 8 is why I like J: often it just works. to works for lines that are horizontal, vertical and diagonal (45 degrees). I'll just hope that none will be diagonal under other angles (others get 0 padding on the shorter dimension).
The parsing can be written, again using cut for each line:
par=: [: /:~@:(|."1)@~.@; <@([: ; 2 <@to/\ [:".;._1 '>',' -'-.~]);._2
I remove the spaces and - as they are not needed, and keep the angle bracket to split the pairs of numbers. Applying to between each pair using infix, not forgetting boxing, as lines won't have the same length and we'd like to avoid padding with 0 0. Finally, I remove doubles (the ends of each internal segment of each line are duplicated), I switch x and y in order to have the first coordinate refer to rows, and the second to columns to keep my mental sanity. I hope sorting might prove efficient for the lookups I will do...
As a test, I wrote these verbs for visualising the field: mat converts a list of coordinates to a matrix that viewmat can take, and vis converts such matrix to literal, mainly to visualise examples on the test data:
mat=: (] 1:`(<"1@[)`]} 0 $~ >:@(>./))@(-"1 (0),<./@:({:"1))
NB. for quick vis of tst, e.g. vis (+&mat pour) par tst
vis=:{& '.o#@$'
vis (+&mat 0 500,]) par tst ......o... NB. <-- Starting position .......... .......... .......... ....#...## NB. <-- two obstacle lines ....#...#. ..###...#. ........#. ........#. #########.
This corresponds pretty much to the graph on the problem page. It's not perfect, as +&mat will fail if mat happens to generate matrices of different dimensions...
Part 1, first try
So part 1 asks for the amount of sand units that can be dropped before the first unit falls into abyss, where it passed all obstacles.
My initial try was simple enough, and worked well enough for part 1. It simply simulated pouring in every drop of sand, given the start position and the current list of obstacles, adding its final position to the list, unless it is _ _, which is returned when no obstacle could be found.
The pour verb uses the power conjunction to iterate on it's argument, the list of obstacles, until it no longer changes. The dropping verb performs the drop of a single grain of sand from the start till it stops, takes the list of obstacles and returns the stopping position. The result of dropping is only added if it is not the special value _ _. Afterwards, coordinates are sorted for dropping to be able to use them.
pour =: ([: \:~ dropping ,^:(_ _-.@-:[) ])^:_
dropping is an explicit verb for clarity; I could probably write a tacit one, but the problem is rather loopy for this. It takes a sorted list (highest first) of coordinates of obstacles, and loops whilst (i.e. skipping the first check) the point is not the same as the previous:
OFS =: 3 2$0 _1 0 1 _1 0 NB. offsets in order of preference, w.r.t. the obstacle in same col as current position
NB. expects y: sorted obstacle coords, hardcoded initial 0 500
dropping =: {{
pt =. prev=. 0 500 NB. initial pos
whilst. pt~:prev do. NB. whilst pt keeps moving
prev=. pt NB. keep track of position
NB. first val not in y of offset obstacle at col of pt
NB. sort down to allow negative behead on y
pt=. pt (] (] {~ #@[ i.&1@:= i:!.0) OFS +"1 i:!.0&:({:"1)~ { _ _,~]) y
NB. exclude higher points for further refinements (note: integrating with pt update does not perform better).
y=. y ([ {.~ [: >: (i:&1@:>:)&:({."1)) pt
end.
pt
}}
.
It does not simulate a sand unit's drop for every position, but takes a slightly optimised route: It finds the last (i.e. highest, since y is sorted) item of y (extended with _ _ so it's easy to select when no obstacle is found) that is in the same column as the current point, then adds the offsets the sand unit could go when it encountered an obstacle; adds those, and then checks for each of those positions which one is still free, and selects the first available, being the point itself if none is available, ending the loop. In case no obstacles are found in the first place, _ _ is selected as the basis for adding the offsets, which will stay infinite, causing dropping eventually to return _ _. Another optimisation is the trimming of y: As we're looking for obstacles below the current point, anything higher can be removed. As y is sorted this is simply a behead with the right index. This reduces the search space a lot.
Part 1's solution, the number of sand units that fall before they overrun, can be then written as the difference in tally between the obstacle list after pour and the original one:
part1 =: (-&# pour)@par
Part 2
Part two is a fun one: the assignment remains the same, but an infinite floor, 2 units below the lowest obstacle is to be added. Infinity is rather hard to work with when lists of obstacles are kept... After pondering a bit, I realised the sand can only ever fall in a 45 degree angle from its starting point 0 500. Adding to the result of par a floor that is wide enough to block this range at the lowest height is sufficient, and will cause the sand to pile up until it reaches the starting position.
addfloor =: (,~ [: (] to/@,. (500 (+,-) >:)) 2 + >./@:({."1))
NB. append ( range both ways by depth+1) depth of floor
Now, there will not be any falling through anymore, and we should break on a different criterion, namely the origin 0 500 being added to the list of items:
fill =: (] (\:~@,) dropping)^:(0 500 -.@-: {:)^:_
part2=: (-~&# fill)@addfloor@par
Intermediate version
Even though this works for part 1, it is rather slow, and it is unbearably slow for part 2 (170s on my phone). I set this problem apart, and returned to it after I had finished all problems in an attempt to speed up the slowest solutions I had.
The above solution "speeds up" things by a) looking up the first obstacle position encountered in the same column as the falling sand unit, and work from there; and b) by only looking up positions that are lower than the current sand unit.
I realised that while vertical falling was likely common, diagonal rolling down the slope created by predecessors was likely also very common, maybe even more, as the eventual result of part 2 looked pretty much like a pyramid with some holes. An intermediate attempt to make units also fast-forward when rolling down a 45 degree angle slope was faster (52s instead of 170s of the original): It involves actually two look-ups per diagonal stretch, as it has to verify whether obstacles are present on the same diagonal as the sand unit, and also has to verify where there are holes in the diagonal just below. Discussing it here in full would make this page too long, though.
One very important lesson I learned while coding this solution is something tucked away [too deep in Nuvoc]: Using verbs of the i. family on arrays of rank > 1 is FAR faster when using non-tolerant comparison (using !.0). As this solution used e. for looking up coordinate pairs in a matrix, this made an enormous difference.
Final recursive version
On a whim, I tried imagining it as a recursive problem, as every sand unit falls on the previous one, and the scheme gradually fills up. It turned out quite spectacular, both in simplicity as in speed.
As before, it uses the offsets ordered by preference, but this time with respect to the current sand unit considered, rather than the obstacle encountered:
OFS =: 3 2$1 0, 1 _1, 1 1 NB. straight down, left diagonal, right diagonal
The rec verb sets up two global nouns LOW and MSG and a global verb GO to do the actual recursion. All have to be globals, since J does not have lexical scoping, i.e. an inner verb defined in an outer verb cannot access any locals of the outer verb, like it can in languages that do have lexical scoping. While this has bothered me in the past, coming from Lua, writing array-oriented code largly removes the need, and J also has locales to help in avoiding clutter.
The GO verb takes a list of already known obstacles and recurses down by order of preference. This effectively tries to drop straight down until the first sand unit hits an obstacle, after which it adds that point to the list of discovered additional points addpt and uses that list to try and find other reachable points left and right down from the current position. As every point does so, and returns upward, this list of found points keeps growing, until the starting position is reached again on the way back. At this point, all occupied sand positions are known and returned.
For part 1, we won't get to that point though, as we know sand units will start falling through that will not find any obstacle any more. For this case, the LOW noun keeps the lowest known obstacle. If sand falls lower, it must be in free fall, and it's time to abort. In this case, GO returns a single point that cannot ever be produced, MSG, set to _1 _1, as message.
Once previous calls of GO find MSG, they return, without adding the current sand unit, because the one it should rest on already fell through. This way, this location will not be occupied by sand, all the way up the chain of previous invocations of GO on the call stack. As last action in rec, we just remove this MSG if present. Because part 2 does not (with hindsight) overflow, we cannot simply discard the head of the result, where MSG is guaranteed to be, but only if it overflowed.
rec =: {{
LOW =: >./{."1 y NB. lowest point in map = highest row coord. used for detecting overflow.
MSG=: _1 _1 NB. coords used as special "message" to abort descent
NB. GO: recursive depth first search
NB. y: obstacle coords; x: pt;
NB. returns *new* obstacle coords (for use by lower ranked neighbors and upwards)
GO =: {{
if. LOW < {.x do. ,:MSG return. end. NB. if dropped to abyss: send "abort"
if. x e.!.0 y do. 0 2$0 return. end. NB. don't add if already in obstacles (y)
addpt=. 0 2$0 NB. newly found points
for_pt. x+"1 OFS do. NB. for reachable points, in order:
NB. find points below, consider points previously found by higher ranking moves: recurse
if. MSG -:{.res=.pt GO y,addpt do. NB. if _1 _1, we fell through: abort
res,addpt return. NB. pt NOT added!
else.
addpt=. addpt, res NB. accumulate & continue
end.
end.
x,addpt NB. All visited, point added and returned upward
}}
NB. not simply behead, as part 2 does not overflow
MSG -.~ 0 500 GO y
}}
As rec only returns the additional points discovered, the solution verbs for part 1 and 2 are even simpler (with addfloor and par defined as before):
part1=: #@rec@ par
part2=: #@rec@addfloor@par
As an afterthought, I thought it would be nice to somehow visualise the addition sequence. As each point adds its obstacles in turn and the points are not reshuffled, the position of each point in the list can tell when it was added. To get a feeling for when points were added, I used the matord adverb which is similar to mat introduced above.
It takes on the left the additional points, and on the right all points, including the given obstacle points. It finds the indices of all points in the additional ones, causing the given obstacles to show as pure magenta, close the points added as last ones. All other points are coloured by their time of addition to the list, from blue to magenta. I first drafted matord as a verb, but then realised the background to offset the colour of empty spaces from the sand added as first needs to change depending on how many units are added. It seems setting it to about minus 10% of the total number of added sand units works well, i.e. _100 and _2000 for parts 1 and 2. (Note subtracting the minimum first is for making the verb show something sensible on the tst sample; doing it twice is not pretty, but effective enough).
matord =: {{ i.`(]-"1 <./@])`(m$~1+>./@(-"1 <./)@])} }}
viewmat (rec ([ _100 matord ,) ]) par i14 NB. See viewmat image part 1
viewmat (rec ([ _2000 matord ,) ]) addfloor par i14 NB. See viewmat image part 2