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)]]

Code

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