I'm very satisfied for my solution today.
This problem fits very well with AdamsTowel matrixes.
You can see a video description of my solution at
(https://www.youtube.com/watch?v=tSTDJlICst8)
Some highlights of the solution:
(1)
(new=that.with(row=\row-1\) catch error Any _ void \add(new))
This is making a new coordinate and adding it to the list under construction. If the coordinate would be outside of the matrix, an error is raised and ignored.
(2)
sizes=I.List()( for i in Range(seeds.size())
\add(Match.Count()(for v in matrix \add(v==i+100I)))
)
Here we taint the seeds using a number much bigger than any height.
The number can be tracked back as the corresponding seed index.
(3)
GrowBasin={class method Void(mut Matrix matrix)=(
for c in matrix.coords() var h in matrix {
if h>=9I return void
return for ci in Near(c) if matrix.val(ci)>99I return h:=matrix.val(ci)
}
To grow a basin one step, we search for all the coordinates c of height h; if there is a ci near c that is tainted with a basin number, we taint the current height too.
Here is the full code.
reuse [L42.is/AdamsTowel]
Fs = Load:{reuse[L42.is/FileSystem]}
Matrix = Collection.matrix(I.List,row=100I, col=100I)
Coords = Collection.list(Matrix.Coord)
Split={class method S.List (S that)=\()(//should be in adamsTowel
for c in that.replace(S"" with=S",").split(S",")\add(c)
)}
Near={class method Coords (Matrix.Coord that)=Coords()((
(new=that.with(row=\row-1\) catch error Any _ void \add(new))
(new=that.with(row=\row+1\) catch error Any _ void \add(new))
(new=that.with(col=\col-1\) catch error Any _ void \add(new))
(new=that.with(col=\col+1\) catch error Any _ void \add(new))
))}
GrowBasin={class method Void(mut Matrix matrix)=(
for c in matrix.coords() var h in matrix {
if h>=9I return void
return for ci in Near(c) if matrix.val(ci)>99I return h:=matrix.val(ci)
}
)}
NeedsMore={class method Bool(read Matrix matrix) =
Match.Some()(for e in matrix \add(e<9I))
}
PopMax ={class method I (mut I.List that)=(
var i = 0I
var e = 0I
for ei in that, ii in Range(that.size()) if ei>e (
e:=ei, i:=ii
)
that.remove(i)
e
)}
MainPart2 = (
input = Fs.Real.#$of().read(\"input")
matrix = Matrix(\()(
for s in input.split(S.nl()) for si in Split(s) \add(I(string=si))
))
seeds = Coords()(for c in matrix.coords() h in matrix (
min = Match.All()(for ci in Near(c) \add(matrix.val(ci)>h))
if min \add(c)
))
for c in seeds, i in Range(seeds.size()) (matrix.set(c val=i+100I))
while NeedsMore(matrix=matrix) ( GrowBasin(matrix=matrix) )
sizes=I.List()( for i in Range(seeds.size())
\add(Match.Count()(for v in matrix \add(v==i+100I)))
)
v1=PopMax(sizes)
v2=PopMax(sizes)
v3=PopMax(sizes)
Debug(v1*v2*v3)//882942
)
Top comments (0)