There's not much to this challenge. You get a two dimensional grid, you have to go over it and check things relative to each position. It's meant for imperative arrays, with nested loops, I guess...

At least I got to be clever about parsing an array without knowing it's dimensions in advance, and use the «generative array» Haskell trick. I have that going on for me...

## The Problem

We are given a two dimensional array. Each position holds a single integer, to be interpreted as elevation for that position.

The example input looks like this

``````    30373\n
25512\n
65332\n
33549\n
35390\n
``````

For each position `(row,col)`, one most consider the other positions sharing the same row or column. A position is visible if the elevation at said position is greater than the elevations of all other positions towards any edge, either row-wise left or right, or column-wise top or bottom. Naturally, this makes edge positions automatically visible.

Quite boring.

## Main Program

The main program is pretty much the same as Day 1.

## Arrays in a functional setting

The «array mentality» is strongly tied to plain iteration and the need to know «the size of things». It's one of the first things an imperative programmer learns, and one of the hardest things to forget when you change paradigms. Using lists as if they were arrays is a terrible idea.

Haskell has a full set of Arrays. With polymorphic dimensions and a rich API to move around. This rarely ever comes up when teaching introductory courses, because they are not «general purpose». Pure arrays are meant to be written once and read as many times as needed; modifying any position on a pure array means copying the whole thing.

This problem is amenable for solving with pure arrays:

1. Parse the input in one pass and load it into a pure array.

2. Go over the positions of the new array and create a new array computing the desired result per position. This would be the boring «nested loop» part.

3. Collapse the array to compute the solution.

We can do this without knowing the dimensions in advance, and never needing them for the «nested loops». This will hopefully show how Haskell arrays are nicer than your run of the mill imperative arrays.

## Parsing the input array

We'll be using Haskell's standard library `Data.Array`. This library provide «pure arrays», meant to be loaded once and read many times -- `O(1)` time for reads, if you must know. The basic way to create a pure array is with, well

``````    array :: Ix i => (i, i) -> [(i, e)] -> Array i e
``````

where `i` is any type that can be used as an array index. As you can imagine, you can use `Int` for indexing, so

``````    array :: (Int,Int) -> [(Int, e)] -> Array Int e
``````

will help you create a one-dimensional array from lower to upper bounds, storing elements of type `e`. The second argument is supposed to be a list with all the elements to be stored in the array. The order respective to the index doesn't matter, as `array` will place them correctly before «freezing» the grid.

One can use tuples `(Int,Int)` to create two-dimensional arrays. The astute reader should've figured by now that arrays indexes can start and end on whatever number you need, or even be `Char`, or `String`, or any `Enum`. Maybe this will come up in future challenges, but for this one, tuples it is.

Going back to how to use `array`, we will need to provide the dimensions of the array as second argument. And each element of the list must also carry correct row and column information, for each to be placed correctly. As usual, I will not cheat by looking at the actual input and hardcoding dimensions, but try to do it «en passant».

### The Array we need

We would like to use `array` instantiated as

``````    array :: ((Int,Int),(Int,Int))   -- Two dimensions
-> [((Int,Int), Int)]      -- Each position holds an Int
-> Array (Int,Int) Int
``````

which means our top-level parser should produce

``````    [((Int,Int), Int)]
``````

to feed as second argument to `array`. As for the first argument, the only thing we know for sure is

``````    ((0,0),(?,?))
``````

If we build the list with proper row and column position for each element, we can figure the maximum coordinate to provide as second argument. The trick is, precisely, computing proper row and column positions for each element...

### Implicit counters

We don't need a stateful parser like on Day 7, but you're free to try. A plain `Parser` will do.

Parsing a single row is straightforward using `Parsec` combinators and `Applicative`:

``````    parseRow :: Parser [Int]
parseRow = many1 (digitToInt <\$> digit) <* newline
``````

Just grab one digit at a time and collect them as a list. Notice the use of `(<*)` to run both parsers in sequence, but keeping what the first one returns. Now, we still don't know how many `Int`'s we collected.

We set on to parse the full matrix. Of course it's just a matter of using `parseRow` as many times as possible, until we hit the end of input (`eof`). Here's the trick:

• While parsing row `r`, we can assign precisely row `r` to every element.

• We can pair each element with its column position by taking enough elements from the infinite list `[0..]` by lettting lazy evaluation do its thing, e.g. using a `String` as the list of elements and assuming we're on row `42`, something like

``````  ghci> zip (zip (repeat 42) [0..]) "foo"
[((42,0),'f'),((42,1),'o'),((42,2),'o')]
``````
• After parsing row `r`, we continue parsing a matrix, but starting at row `r+1`. Recursion!

• Build the correct list of elements and their positions for row `r`, and place them in front of the list of lists for the rest of the matrix.

``````  parseMatrix :: Int -> Parser [((Int,Int),Int)]
parseMatrix r = (eof >> pure [])
<|> do ds <- parseRow
rs <- parseMatrix (succ r)
pure \$ zip (zip (repeat r) [0..]) ds ++ rs
``````

When we start parsing our matrix, we are on row `0`, therefore

``````    parseInput :: Parser [((Int,Int),Int)]
parseInput = parseMatrix 0
``````

We are now in a position to use `array` after parsing our input. You can think my use of `maximum` for figuring out the largest tuple is cheating, but turns out it is as expensive as carrying it in the parser. You can do the math, I won't check it.

``````    loadForest :: String -> Array (Int,Int) Int
Left _e -> undefined
Right l -> array ((0,0),maximum \$ map fst l) l
``````

Yes, we can load a two-dimensional array with proper row and column information without needing to know the length of each line or the input file in advance. As long as all lines have the same length, of course.

## Parametric polymorphism is the answer

The `Array` API provides operator `(!)` for efficiently reading the element at any particular position. We could use it with lots of recursion to simulate nested loops. That would be Ugly, Sad, and Not Declarative.

Here's the nifty trick, in the form of a polymorphic function:

``````    mkArray :: Ix i => (i -> e) -> (i,i) -> Array i e
mkArray f bs = array bs [ (i, f i) | i <- range bs ]
``````

Function `f` is able to compute the element that should go in a particular position. The second argument provides the bounds for the array. Using `Data.Array` `range` we cover all the array space for the particular bounds, feeding `f` to effectively create a new pure `Array`.

Now, all we need to do is come up with the proper `f` to compute the solution we are looking for based on the input array, and `mkArray` will build the answer array. Since `mkArray` is polymorphic, the answers could have different contents -- planning ahead for Part B, obviously.

## Solving Part A

As discussed before, for each position in the input array, we need to check all positions in the same row to the left, in the same row to the right, in the same column up, and in the same column down.

Solving Part A can be accomplished by creating a new array with the same shape, but holding `Bool` to state whether or not a position is visible.

`Array` functions tend to be very busy, on account of having to keep track of dimensions, bounds, and whatnot.

``````    visibleTrees :: Array (Int,Int) Int -> Array (Int,Int) Bool
visibleTrees forest = mkArray visible dimensions
where
dimensions                          = bounds forest
((minR,minC),(maxR,maxC))           = dimensions

visible (_,c) | c == 0 || c == maxC = True
visible (r,_) | r == 0 || r == maxR = True
visible (r,c)                       =
or [ and [ forest ! (rb,c) < forest ! (r,c) | rb <- [minR..pred r] ]
, and [ forest ! (ra,c) < forest ! (r,c) | ra <- [succ r..maxR] ]
, and [ forest ! (r,bc) < forest ! (r,c) | bc <- [minC..pred c] ]
, and [ forest ! (r,ac) < forest ! (r,c) | ac <- [succ c..maxC] ]
]
]
``````

Since we'll be using `mkArray` to build the solution array, we must compute the input array `dimensions` using `Array` API `bounds`. We use pattern-matching to extract `dimensions` parts, as we'll need them for the internal lookups.

Finally, we provide function `visible` that, given a particular position, decides whether or not it is visible over any direction:

• Any position sitting on a boundary row or column is visible, no other checks needed.

• For position `(r,c)` to be visible, it must be taller than all neighboring positions per direction (left, right, up, down) on at least one of them:o

• Check all positions on a particular direction. Here's the only place we need to use `(!)` to look on the input `forest` and compare with the current position. Notice `and` is short-circuited: lists will be traversed in full only if reaching the edge is needed.

• Using short-circuited `or` also helps: worst case scenario is having to check all directions when the position is not visible.

To round up the solution for Part A, we use `elems` as provided by `Array` API. It simply lists all elements from any `Array`. The list will be in outer to inner dimension order. It doesn't matter for this particular problem. We reason as follows:

``````    ghci> :type loadForest
loadForest :: String -> Array (Int, Int) Int
visibleTrees . loadForest :: String -> Array (Int, Int) Bool
ghci> :type elems . visibleTrees . loadForest
elems . visibleTrees . loadForest :: String -> [Bool]
``````

We just need to count how many are `True`, so we write

``````    partA :: String -> Int
partA = length . filter id . elems . visibleTrees . loadForest
``````

We needed the `length` of things in the end --badum tss--

### Solving Part B

The approach for solving Part B is similar. For each position in the input array, we need to «spread out» checking all positions in the same row to the left, in the same row to the right, in the same column up, and in the same column down. On every direction we need to count how far we can go until we find the first element that is greater or equal to the one in the position, or the edge, whatever happens first. The «scenic value» for the position, is the product of how far can we go in each of the four directions.

Solving Part B can be accomplished by creating a new array with the same shape, but holding `Int` to hold the scenic value. Pretty much the same structure as before, just changing the auxiliary function `scenery` passed to `mkArray`.

``````    scenicScore :: Array (Int,Int) Int -> Array (Int,Int) Int
scenicScore forest = mkArray scenery dimensions
where
dimensions                          = bounds forest
((minR,minC),(maxR,maxC))           = dimensions

scenery (_,c) | c == 0 || c == maxC = 0
scenery (r,_) | r == 0 || r == maxR = 0
scenery (r,c)                       =
product [ length ((r,c) `seesOver` [(r,c') | c' <- reverse [minC..pred c]])
, length ((r,c) `seesOver` [(r,c') | c' <- [succ c..maxC]])
, length ((r,c) `seesOver` [(r',c) | r' <- reverse [minR..pred r]])
, length ((r,c) `seesOver` [(r',c) | r' <- [succ r..maxR]])
]

seesOver _    []        = []
seesOver origin (p:ps) = if forest ! origin > forest ! p
then p : seesOver origin ps
else [p]
``````

Again, list comprehensions to construct the list of positions to consider in each direction. This time we need to compute their `length` in order to count them, and compute their `product` to figure out the positions scenic value.

Ranges within list comprehensions should be processed from the position outwards, that's why for left and right we need to build them from smaller to larger, and then `reverse` them. Using `Enum` API would be an alternative.

Finally, I had to write `seesOver` because neither `dropWhile` nor `takeWhile` were good fits. Can you figure out why?

Solving Part B is just a matter of find out the element having the maximum product.

``````    partB :: String -> Int
partB = maximum . elems . scenicScore . loadForest
``````

That's it.

## Conclusion

Functional programmers rarely ever use arrays. Arrays aren't as good control structures as `Foldable`s are. The only way to process arrays is with external information (bounds, dimensions) and control (recursion). That doesn't compose.

We reach out to Arrays for a few problems, mostly those that fit dynamic programming or hardware-assisted numerical computation. `Array` is helpful for dynamic programming, particularly if you need to build each position in the array via a computation that involves previous positions (a technique known as «dovetailing»). It's also helpful when your input data is going to be pretty much immutable, and you're going to derive results by repeated reads, as in this challenge. It is not useful if you're trying to implement algorithms that try to change array positions.

There are just a few array-based algorithms for which an equivalent non-array solution has been found yet. For those, you might want to explore `Data.Array.ST` and `Data.Array.IO`. But before trying to replicate your array-based algorithm in Haskell using arrays, do some research to find out if it has already been solved. You'd be surprised.

As for this challenge, the input was an `Array`, and the intermediate solution was also and `Array`, built using higher-order functions while looking at arrays as if they were functions from the index domain into the element codomain. Because, they are.