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

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.