advent_of_code_2022_day_8.nim

import std/sequtils, std/strutils, std/sets, std/sugar, std/strformat, std/tables, std/algorithm

proc countVisible*(input: seq[seq[int]]): int =
    runnableExamples:
        let input = @[@[2, 2, 1, 2],
                      @[2, 1, 3, 2],
                      @[2, 2, 5, 2]]

        assert countVisible(input) == 11

    # first pass from upper-left to lower-right
    var visibleFromUpperLeft = initHashSet[(int, int)]()
    var yMaxCols = input[0]

    for y in 1..<input.len-1:
        var xMax = input[y][0]

        for x in 1..<input[y].len-1:
            var height = input[y][x]
            var isVisible = false

            if height > xMax:
                xMax = height
                isVisible = true

            if height > yMaxCols[x]:
                yMaxCols[x] = height
                isVisible = true
            
            if isVisible:
                visibleFromUpperLeft.incl((x, y))

    # second pass from lower-right to upper-left
    var visibleFromLowerRight = initHashSet[(int, int)]()
    yMaxCols = input[^1]

    for y in countdown(input.len-2, 1):
        var xMax = input[y][^1]

        for x in countdown(input[y].len-2, 1):
            var height = input[y][x]
            var isVisible = false

            if height > xMax:
                xMax = height
                isVisible = true

            if height > yMaxCols[x]:
                yMaxCols[x] = height
                isVisible = true

            if isVisible:
                visibleFromLowerRight.incl((x, y))

    (visibleFromLowerRight + visibleFromUpperLeft).card + (2 * input.len) + (2 * (input[0].len - 2))

proc maxScenicScoreBad*(input: seq[seq[int]]): int =
    runnableExamples:
        let input = @[@[2, 2, 3, 2],
                      @[2, 1, 1, 2],
                      @[2, 2, 5, 2],
                      @[1, 1, 1, 1]]

        assert maxScenicScoreBad(input) == 4

    # first pass from upper-left to lower-right
    var scoresFromUpperLeft = newTable[(int, int), int]()
    var yMaxCols = input[0]
    var yScores = 1.repeat(input[0].len)

    for y in 1..<input.len-1:
        var xMax = input[y][0]
        var xScore = 1

        for x in 1..<input[y].len-1:
            var height = input[y][x]

            if height <= xMax:
                scoresFromUpperLeft[(x, y)] = 1
                xMax = height
                xScore.inc
            else:
                scoresFromUpperLeft[(x, y)] = xScore
                xScore = 1

            if height <= yMaxCols[x]:
                scoresFromUpperLeft[(x, y)] *= 1
                yMaxCols[x] = height
                yScores[x].inc
            else:
                scoresFromUpperLeft[(x, y)] *= yScores[x]
                yScores[x] = 1

    # second pass from lower-right to upper-left
    var scoresFromLowerRight = newTable[(int, int), int]()
    yMaxCols = input[^1]
    yScores = 1.repeat(input[0].len)

    for y in countdown(input.len-2, 1):
        var xMax = input[y][^1]
        var xScore = 1

        for x in countdown(input[y].len-2, 1):
            var height = input[y][x]

            if height <= xMax:
                scoresFromLowerRight[(x, y)] = 1
                xMax = height
                xScore.inc
            else:
                scoresFromLowerRight[(x, y)] = xScore
                xScore = 1

            if height <= yMaxCols[x]:
                scoresFromLowerRight[(x, y)] *= 1
                yMaxCols[x] = height
                yScores[x].inc
            else:
                scoresFromLowerRight[(x, y)] *= yScores[x]
                yScores[x] = 1

    result = 0
    for x in 1..<input[0].len-1:
        for y in 1..<input.len-1:
            var score = scoresFromLowerRight[(x, y)] * scoresFromUpperLeft[(x, y)]
            if score > result:
                result = score

let input = collect: 
    for row in "day-8/input.txt".lines:
        row.mapIt(parseInt($it))


proc getScore(height: int, path: seq[int]): int =
    for h in path:
        result.inc
        if height <= h:
            break

proc maxScenicScoreNaive*(input: seq[seq[int]]): int =
    runnableExamples:
        let input = @[@[2, 2, 3, 2],
                      @[2, 1, 1, 2],
                      @[2, 2, 5, 2],
                      @[1, 1, 1, 1]]

        assert maxScenicScoreNaive(input) == 4

    for y in 1..<input.len-1:
        for x in 1..<input[y].len-1:
            let height = input[y][x]

            let scoreLeft = getScore(height, (0..<x).mapIt(input[y][it]).reversed)
            let scoreRight = getScore(height, (x+1..<input[y].len).mapIt(input[y][it]))
            let scoreUp = getScore(height, (0..<y).mapIt(input[it][x]).reversed)
            let scoreDown = getScore(height, (y+1..<input.len).mapIt(input[it][x]))
            let score = scoreLeft * scoreRight * scoreUp * scoreDown

            if score > result:
                result = score

echo fmt"Visible trees count: {countVisible(input)}"
echo fmt"Max scenic score (smartass, incorrect version): {maxScenicScoreBad(input)}"
echo fmt"Max scenic score (naive, correct version): {maxScenicScoreNaive(input)}"