97 lines
3.0 KiB
Nim
97 lines
3.0 KiB
Nim
# Copyright 2021 Christian Ulrich
|
|
#
|
|
# This program is free software: you can redistribute it and/or modify
|
|
# it under the terms of the GNU General Public License as published by
|
|
# the Free Software Foundation, either version 3 of the License, or
|
|
# (at your option) any later version.
|
|
#
|
|
# This program is distributed in the hope that it will be useful,
|
|
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
# GNU General Public License for more details.
|
|
#
|
|
# You should have received a copy of the GNU General Public License
|
|
# along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
|
|
# usage: ./part2 < input
|
|
|
|
import algorithm
|
|
import sequtils
|
|
|
|
proc lowPoints(heightMap: seq[string]): seq[tuple[x, y: int]] =
|
|
for y in 0 ..< heightMap.len():
|
|
for x in 0 ..< heightMap[y].len():
|
|
let
|
|
value = heightMap[y][x]
|
|
left = x == 0 or heightMap[y][x - 1] > value
|
|
right = x == heightMap[y].len() - 1 or heightMap[y][x + 1] > value
|
|
top = y == 0 or heightMap[y - 1][x] > value
|
|
bottom = y == heightMap.len() - 1 or heightMap[y + 1][x] > value
|
|
if left and right and top and bottom:
|
|
result.add((x, y))
|
|
|
|
proc horizontalRange(line: string, x: int): Slice[int] =
|
|
result = x .. x
|
|
while result.a != 0:
|
|
if line[result.a - 1] == '9':
|
|
break
|
|
result.a.dec()
|
|
while result.b != line.len() - 1:
|
|
if line[result.b + 1] == '9':
|
|
break
|
|
result.b.inc()
|
|
|
|
proc findRanges(line: string, prevRanges: seq[Slice[int]]): seq[Slice[int]] =
|
|
for range in prevRanges:
|
|
var x = range.a
|
|
while x <= range.b:
|
|
if line[x] != '9':
|
|
result.add(line.horizontalRange(x))
|
|
x = result[^1].b + 1
|
|
else:
|
|
x.inc()
|
|
result = result.deduplicate()
|
|
|
|
proc basinSize(heightMap: seq[string], pos: tuple[x, y: int]): int =
|
|
let hrange = heightMap[pos.y].horizontalRange(pos.x)
|
|
result = hrange.len()
|
|
var
|
|
y = pos.y
|
|
ranges = @[hrange]
|
|
while y != 0:
|
|
y.dec()
|
|
ranges = findRanges(heightMap[y], ranges)
|
|
result += ranges.foldl(a + b.len(), 0)
|
|
y = pos.y
|
|
ranges = @[hrange]
|
|
while y != heightMap.len() - 1:
|
|
y.inc()
|
|
ranges = findRanges(heightMap[y], ranges)
|
|
result += ranges.foldl(a + b.len(), 0)
|
|
|
|
proc biggestBasins(): int =
|
|
var heightMap = @[""]
|
|
if not readLine(stdin, heightMap[0]) or heightMap[0].len() == 0:
|
|
raise newException(ValueError, "invalid first line")
|
|
var line = ""
|
|
while readLine(stdin, line):
|
|
if line.len() != heightMap[0].len():
|
|
raise newException(ValueError, "invalid line")
|
|
heightMap.add(line)
|
|
let basinSizes = heightMap.lowPoints()
|
|
.mapIt(heightMap.basinSize(it))
|
|
.sorted(Descending)
|
|
if basinSizes.len() < 3:
|
|
raise newException(ValueError, "not enough basins")
|
|
result = basinSizes[0 .. 2].foldl(a * b)
|
|
|
|
proc main(): int =
|
|
try:
|
|
echo biggestBasins()
|
|
except Exception as error:
|
|
echo error.msg
|
|
result = -1
|
|
|
|
when isMainModule:
|
|
quit(main())
|