Advent of Code 2022 day 8

    Day 8 was much less effort than day 7 (this is becoming a trend).

    The two parts are quite different, and just distinct enough from the "obvious" solutions to make them a challenge.

    I represent the grid of trees as just a list of list of Trees. I could have used an Array (see the description of 2021 day 9 for more details), but this representation was sufficient for this task.

    Part 1

    The wrinkle for part 1 is that trees can be visible from more than one direction, but those trees only count once for the "visible trees" count. The solution is to augment each tree with a flag, showing if it's visible. Trees start of invisible. I can follow the rules of the puzzle to identify the trees that are visible, then count them.

    data Tree = Tree Int Bool -- height, isVisible
      deriving (Show, Eq)
    type Forest = [[Tree]]
    readTree :: Char -> Tree
    readTree h = Tree (read [h]) False
    isVisible :: Tree -> Bool
    isVisible (Tree _ v) = v
    treeHeight :: Tree -> Int
    treeHeight (Tree h _) = h

    The tricky part is to ensure that all the updates from earlier stages follow through to the later stages. I can set the visibility for a single row of trees with a fold, setting trees to visible if they are higher than the previously-highest seen tree. Note that this builds a new list of trees as the fold progresses.

    Setting visibility for several rows of trees means mapping setVisibility over all the rows.

    setVisibility :: [Tree] -> [Tree]
    setVisibility row = reverse $ snd $ foldl' vis (-1, []) row
      where vis (highest, tagged) (Tree height visible)
              | height > highest = (height, (Tree height True) : tagged)
              | otherwise = (highest, (Tree height visible) : tagged)
    setVisibilityOrient :: Forest -> Forest
    setVisibilityOrient = fmap setVisibility

    The hard part is finding the visibility of trees from all positions. I want to set the visibility from the current direction, then rotate the forest, then find the visibility of this changed, rotated, visibility-set forest, and do that four times.

    The combination of (fmap reverse) . transpose rotates the grid a quarter-turn. Applying the same process repeatedly is iterate. The glue that connects the part is to combine the visibility-setting and rotating in the function applied by iterate.

    setVisibilityForest :: Forest -> Forest
    setVisibilityForest forest = (!!4) $ iterate f forest
      where f = rotate . setVisibilityOrient
            rotate = (fmap reverse) . transpose 

    Finally, I can mash the lists together and count how many trees are visible.

    part1 :: Forest -> Int
    part1 = countVisible . setVisibilityForest
    countVisible :: Forest -> Int
    countVisible forest = length $ filter isVisible $ concat forest

    Part 2

    The main challenge of part 2 was spitting the forest into "tracks", sequences of trees radiating from a particular point.

    Given a forest and a particular row and column to start from, I can spilt the trees in the given row at the given column, to give the left and right tracks. I can transpose the forest, which allows me to easily split the given column at the given row. There's a bit of tidying up to remove the current tree and have the tracks in the correct order.

    tracks :: Forest -> Int -> Int -> [[Tree]]
    tracks forest row col = [reverse l, drop 1 r, reverse u, drop 1 d]
      where (l, r) = splitAt col (forest !! row)
            (u, d) = splitAt row ((transpose forest) !! col)

    After that, the number of visible trees on each track is given by taking trees until you find one that's not shorter than the starting point. That's normally what takeWhile does, but this problem needs the inclusion of the first failing element. That's captured in the new takeWhile1 function.

    viewDistance :: Int -> [Tree] -> Int
    viewDistance h trees = length $ takeWhile1 (< h) $ fmap treeHeight trees
    takeWhile1 :: (a -> Bool) -> [a] -> [a]
    takeWhile1 _ [] = []
    takeWhile1 f (x:xs) 
      | f x == True = x : (takeWhile1 f xs)
      | otherwise = [x]

    Finally, the scenic score of a location is found by multiplying the view distance of all four tracks.

    scenicScore :: Forest -> Int -> Int -> Int
    scenicScore forest row col = foldl' (*) 1 $ fmap (viewDistance h) directions
      where directions = tracks forest row col
            h = treeHeight $ (forest!!row)!!col

    I can find the best scenic score by finding the scenic score at every location and just keeping the maximum.

    part2 :: Forest -> Int
    part2 forest = maximum scores
      where nrows = length forest
            ncols = length $ head forest
            scores = [scenicScore forest r c | r <- [0 .. (nrows - 1)], c <- [0 .. (ncols - 1)]]


    You can get the code from my locally-hosted Git repo, or from Gitlab.

    Neil Smith

    Read more posts by this author.