The elves, with us in tow, have come across a fantastic grove of trees and for whatever reason they think it’s a great place (and time to build a tree house). They’ve mapped out the tree heights and want to find the best point that’s hidden from the outside but still has a great view.
Today’s solution isn’t going to be the most efficient but I still had fun solving it and further cleaning up my solutions from the mess I made racing the clock. I’ve also grown more comfortable with the basics of the language, enough so that I feel that I can start stepping out and exploring more of the features available with firmer footing under me.
Parsing
As we’ve already seen, AoC has a number of different input formats and today’s is no different. We’ve got a 2-d array represented in text as a column per character and a row per line, each element is an integer within the range of 0-9. Compared to some other days, this is fairly trivial and a good format to get comfortable with as it’ll surely appear again in the future of either this year or the next.
If you recall, on day 1 we made heavy use of split(separator:) to break apart lines and on day 6 we used Array(_: String) to convert a string to an array where each element is a character in the string. There’s a further trick to reduce our work which is that Strings implement iterators that return a String.Element, aka a Character, each time, meaning we can directly call map(_:) on strings, neat! We can tie these together along with Int(_: String) -> Int? to parse our input into a 2-d array that’s ready to go with minimal work, but we’ve got some snag. Firing up a REPL (swift repl) we see that there isn’t an Int(_: Character) initializer!
1> Int(Character("1"))
# whole bunch of messages like this:
Swift.FixedWidthInteger:3:23: note: candidate expects value of type 'String' for parameter #1 (got 'Character')
Well, that’s inconvenient. We could convert the Character to a String and then initialize an Int but that’s just straight up messy. Looking through the docs for Character however we see that there’s a helpful wholeNumberValue property, perfect.
typealias TreeHeight = Int
typealias TreeGridRow = [TreeHeight]
typealias TreeHeightGrid = [GridRow]
let trees: TreeHeightGrid = input.split(separator: "\n").map { line in
line.map { char in char.wholeNumberValue! }
}
We’re okay with failing if the character doesn’t parse into an integer since that means our input is malformed and we don’t want to continue, so we’ll take the easy route of force-unwrapping it. Ideally we’d probably want to make a nice error message, however, to help reduce the time taken to track down where failures are.
To make our code a little more expressive, we also define a few typealiases to make it clear that trees is a 2-d array of our tree heights. This is a little contrived but it’s something that really helps me remember what a specific data structure is storing, beyond the plain [[Int]].
A Tangent
Since we’re (or at least I am) getting more comfortable with the language, let’s try golfing this a tiny bit for fun and learn what we can!
I’ve glossed over these in previous days but Swift has implicitly args for its closures, called Shorthand Argument Names which means that our line.map(_:) can turn into:
let trees: TreeGrid = input.split(separator: "\n").map { line in
line.map { $0.wholeNumberValue! }
}
In this case though, it’s not too clear what $0 is immediately as we’re in a closure … wrapped in a closure. Not really ideal there, is it? I’m always on the fence about how much I like using shorthands in any language, since it does make the code a little harder to reason about so let’s keep digging.
As it turns out, we can get this even smaller. Swift also has Key-Path Expressions which allow us to reference a property or subscript on a value using a \.<name> pattern. In this case, swift knows that our map(_:) is getting called on a Character type so we can reference the Character’s wholeNumberValue property via \.wholeNumberValue. This will still return an optional, though, but thankfully the key-path support optional and force-unwrapping so our final parsing code can become:
let trees: TreeGrid = input.split(separator: "\n").map { $0.map(\.wholeNumberValue!) }
There are certainly more ways to golf this down further but I find this to be a good balance of extracting the data and being clean and seems like it’ll fit well with a lot of the AoC parsing problems if I go back and clean up old code!
Part One
Consider your map; how many trees are visible from outside the grid?
So we’ve got our tree height map all parsed out into a fancy 2-d array and now we’ve got to find which trees the elves shouldn’t build in, because those trees are visible from outside the grove. We’ve got a couple of options here for how we go about checking if a tree is visible or hidden but we’ll do the easy route and just check each tree individually. To do this we need to:
- Get our current tree’s height
- Get the trees above, below, left and right of our current tree
- Ensure that in all 4 directions there are trees equal to or greater in height than the current tree
We’ll need a few things to make this easier to work with, firstly a typealias for coordinates which we’ll store as a named-element tuple:
typealias Coords = (x: Int, y: Int)
And next up a struct container for some helpful functions for interacting with our map:
struct HeightMap {
let grid: TreeHeightGrid
let xBounds: Range<Int>
let yBounds: Range<Int>
init(_ grid: TreeHeightGrid) {
self.grid = grid
self.xBounds = 0..<grid.first!.count
self.yBounds = 0..<grid.count
}
func contains(_ coords: Coords) -> Bool { xBounds ~= coords.x && yBounds ~= coords.y }
func heightAt(_ coords: Coords) -> TreeHeight {
if !contains(coords) {
fatalError("Coords \(coords) are not within the maps coordinate space!")
}
return grid[coords.y][coords.x]
}
}
There’s a bit to break down here, we’re storing some bounds, and have a few helpers including one that gets the height of a tree if we have a set of coordinates.
When we initialize a new HeightMap, we’re also building two ranges which represent the bounds of our map. Using ranges here gets us two nice-to-haves: it’s easy to check if a coordinate calls within the map, and we can iterate over them to build lists of coordinates that are all within the map automatically. We’ll see this more in a minute.
Now, Ashby there’s a typo in contains(_:), you might say. What’s this ~= business? It’s actually a shortcut operator for contains(_:) that’s defined on Range! It’s not the most expressive but it does allow us to neatly condense our contains check for both dimensions into one line.
Finally, we’ve got a helper that does a bounds check before returning the height of the tree at a given set of coordinates. We’d probably want to make this a func heightAt(_ coords: Coords) throws -> TreeHeight and have a specific OutOfBounds error rather than just fatally erroring out and exiting if this was production code, but we shouldn’t hit any failures during our normal puzzle operations so it’s more of a ‘we did our math wrong’ debugging helper.
We know that we’re going to need a list of coordinates for all of the trees, so how can we programmatically build that? We’ll use our ranges from the bounds! Because I want to also cut down on how many trees we have to iterate through, we’ll actually make an interiorCoordinates property on our HeightMap struct:
var interiorCoords: [Coords] {
yBounds.dropFirst().dropLast().flatMap { y in
xBounds.dropFirst().dropLast().map { x in (x, y) }
}
}
The .dropFirst().dropLast() jazz will remove the perimeter trees and what we get back Wil be an array of just the interior trees coordinates. With this in place, we can start working on our solution to part one:
let baseVisible = (grid.xBounds.count * 2) + (grid.yBounds.count * 2) - 4
return grid
.interiorCoords
.reduce(baseVisible) { accumulator, coords in
let currentHeight = grid.heightAt(coords)
let isHidden = // ????
return accumulator + (isHidden ? 0 : 1)
}
We’ set up baseVisible using the count of all the trees along the perimeter as they’re already known to be visible. Because the 4 corners are included in both the xBounds and the yBounds ranges, however, we’ll over count the number of trees by 4, so we have to correct that.
Next, we reduce over the array of our interior coordinates, grab the height of the current tree and then decide if the tree is hidden or not. If it’s not hidden, we’ll add it to our accumulator.
Now things get fun. For each tree we need 4 arrays: trees above, below, left and right. Let’s work a little backwards here and start by scaffolding a radiateOutFrom() which will return these 4 arrays:
func radiateOutFrom(_ coords: Coords) -> [[Coords]] {}
And we can even fill in our // ???? in our solution code too:
let isHidden = grid.radiateOutFrom(coords)
.map { direction in direction.map { otherCoords in grid.heightAt(otherCoords) } }
.map { otherHeights in otherHeights.firstIndex { height in height >= currentHeight } }
.allSatisfy { $0 != nil }
We’ll grab an array of arrays of coordinates, representing the 4 directions, map those coordinates to the height and then look to see if every direction has a tree which meets the requirements of being equal to or greater than the current tree’s height. If the current tree is taller than any of its peers in any direction than our firstIndex(_:) will return a nil and we’ll fail our allSatisfy(_:)).
Let us fill in the blanks with this radiateOutFrom(_:) and start by making a small helper. We want something that we can give a “direction” vector to and it’ll return the list of coordinates, without our origin, till the edge of the map:
func moveAwayFrom(from coords: Coords, inDirection: Coords) -> [Coords] {
var steps: [Coords] = []
var currentStep = coords
var nextStep: Coords = (x: currentStep.x + inDirection.x, y: currentStep.y + inDirection.y)
while contains(nextStep) {
currentStep = nextStep
nextStep = (x: currentStep.x + inDirection.x, y: currentStep.y + inDirection.y)
steps.append(currentStep)
}
return steps
}
You could probably muck with stride() or zip here to make this a little more condensed, but the general gist is that we’ll add our direction vector to our coordinates, appending the new set of coordinates to a list for as long as we’re still on the map. Once an edge is hit, we’ll include the edge and then return the full array of coordinates.
With that, we just need to provide a “direction” vector for each of the directions, map over them and return the results:
func radiateOutFrom(_ coords: Coords) -> [[Coords]] {
return [ (0, -1), (0, 1), (-1, 0), (1, 0) ]
.map { direction in moveAwayFrom(from: coords, inDirection: direction) }
}
With that, our solution to part one should be done!
Part Two
Consider each tree on your map. What is the highest scenic score possible for any tree?
Naturally being well hidden shouldn’t preclude the tree house from having a great view. We’ll have to again iterate through the interior trees and this time, calculate the view score which consists of the distance to the first tree that is of equal or greater height all multiplied together for each direction. After we’ve done this, we’ll need to find the highest-ranking view score.
Our initial setup for the solution starts off the same as before, we iterate over the interior coordinates and then get our list of tree heights in the 4 directions. The only difference is that we’ll take the first index of the tree matching our criteria OR the total number of trees in that direction, ie the count of the directions array:
return grid
.interiorCoords
.map { coords in
let currentHeight = grid.heightAt(coords)
return grid.radiateOutFrom(coords)
.map { direction in direction.map { otherCoords in grid.heightAt(otherCoords) } }
.map { otherHeights in
let index = otherHeights.firstIndex { height in height >= currentHeight }?.advance(by: 1)
return index ?? otherHeights.count
}
.reduce(1, *)
}
.max() ?? 0
There’s one little trick in here, that advance(by: 1) which is the same as index + 1 but has the advantage of being optionally chainable. We’re doing this because, as we’ve seen the week before, we have to convert our 0-indexed problem space into a 1-indexed solution space for the puzzle to correctly validate.
And that’s it!
There’s some additional clean up that you could do. For example, I consolidated the index/advance/nil-coalescing into my radiateOutFrom function such that it’s signature looks like:
func radiateOutFrom(_ coords: Coords, tallerThan: TreeHeight) -> [(index: Int, count: Int)]
I’ll leave it as an exercise for the reader to figure out what other changes need to be made for each solution and whether or not this is a cleaner approach.
Until tomorrow!
-
Previous: Day 07