# Advent of Code 2022 - Day 8

This one has been quite the ride. Struggled at first to find a good data format to suite the problem. I really like how that turned out by separating the map data from coordinates to look at when counting. Part 2 also was imo not well defined. It took me a while to figure out I don’t need to subtract smaller trees behind larger trees anymore.

Solution
``````defmodule Day8 do
defstruct map: nil, size: nil

def parse(text) do
lines = text |> String.split("\n") |> Enum.reject(&(&1 == ""))

{map, _} =
lines
|> Enum.with_index()
|> Enum.flat_map_reduce(0, fn {line, y}, next ->
line
|> String.split("", trim: true)
|> Enum.with_index()
|> Enum.map_reduce(next, fn {height, x}, next ->
item = {{x, y}, %{id: next, height: String.to_integer(height)}}
{item, next + 1}
end)
end)

map = Map.new(map)

keys = Map.keys(map)
size_x = keys |> Enum.map(fn {x, _} -> x end) |> Enum.max()
size_y = keys |> Enum.map(fn {_, y} -> y end) |> Enum.max()

%__MODULE__{map: map, size: %{x: size_x, y: size_y}}
end

def count_visible_from_outside(text) do
data = parse(text)

from_left_keys =
for y <- 0..data.size.y//1 do
for x <- 0..data.size.x//1, do: {x, y}
end

from_right_keys =
for y <- 0..data.size.y//1 do
for x <- data.size.x..0//-1, do: {x, y}
end

from_top_keys =
for x <- 0..data.size.x//1 do
for y <- 0..data.size.y//1, do: {x, y}
end

from_bottom_keys =
for x <- 0..data.size.x//1 do
for y <- data.size.y..0//-1, do: {x, y}
end

[
from_left_keys,
from_right_keys,
from_top_keys,
from_bottom_keys
]
|> Enum.flat_map(& &1)
|> Enum.flat_map(&count_visible_line(data.map, &1))
|> Enum.uniq()
|> Enum.count()
end

defp count_visible_line(map, line) do
{_, trees} =
line
|> Enum.map(fn coordinate -> Map.fetch!(map, coordinate) end)
|> Enum.reduce({-1, []}, fn
%{height: tree_height} = tree, {line_of_sight, visible}
when tree_height > line_of_sight ->
{tree_height, [tree | visible]}

_, acc ->
acc
end)

trees
end

def count_visible_from_tree_house(text) do
data = parse(text)

for y <- 0..data.size.y//1, x <- 0..data.size.x//1 do
tree = Map.fetch!(data.map, {x, y})
to_left = for x <- (x - 1)..0//-1, do: {x, y}
to_right = for x <- (x + 1)..data.size.x//1, do: {x, y}
to_top = for y <- (y - 1)..0//-1, do: {x, y}
to_bottom = for y <- (y + 1)..data.size.y//1, do: {x, y}

[
to_top,
to_left,
to_right,
to_bottom
]
|> Enum.map(fn line ->
data.map |> count_visible_line_treehouse(line, tree.height)
end)
|> Enum.reduce(&Kernel.*/2)
end
|> Enum.max()
end

defp count_visible_line_treehouse(map, line, limit) do
line
|> Enum.map(fn coordinate -> Map.fetch!(map, coordinate) end)
|> Enum.reduce_while(0, fn
tree, num when tree.height >= limit -> {:halt, num + 1}
_, num -> {:cont, num + 1}
end)
end
end
``````
2 Likes

Yeah, part 2 was not very well defined. I made the same “mistake” as you with not counting smaller trees behind taller ones… quite annoying.

Something I keep having use for in these problems where you have to walk around in a matrix is to use a list of “vectors” instead of hardcoding the movements.
This is for part 2, made a more “clever”/convoluted solution for part 1… but I had no use for in part 2.

``````defmodule VisibilityChecker do
def max_visibility(grid) do
heights = for {rows, y} <- Enum.with_index(grid),
{h, x} <- Enum.with_index(rows), into: %{} do
{{x, y}, h}
end

heights
|> Stream.map(&elem(&1, 0))
|> Stream.map(&score(&1, heights))
|> Enum.max()
end

@directions [{-1, 0},{1, 0},{0, -1},{0, 1},]
defp score(pos, heights) do
for dir <- @directions, reduce: 1 do
score -> score * visible(heights, pos, dir, heights[pos], 0)
end
end

defp visible(heights, pos, direction, max_height, line_height) do
new_pos = translate(pos, direction)
case heights[new_pos] do
nil -> 0
tree_height when tree_height >= max_height -> 1
tree_height when tree_height >= line_height ->
1 + visible(heights, new_pos, direction, max_height, tree_height)
_ ->
1 + visible(heights, new_pos, direction, max_height, line_height)
end
end

defp translate({x, y}, {dx, dy}), do: {x + dx, y + dy}
end

# input is a list of lists with the three heights [ [ 1, 2], [ 3, 4 ]]
#
# 1 2
# 3 4
#
# would be
# [
#.  [ 1, 2 ],
#   [ 3, 4 ]
# ]
VisibilityChecker.max_visibility(input)
``````
1 Like

Loops in loops in loops My slowest answer to date this year. I avoided scanning out from every tree, but I did do 4 passes of the forest, and each of those passes does a lot of map lookups, so pretty slow I guess. By slow I mean 40ms.

Brute forcing it. Now off checking on the subreddit aoc to see how clever people do it

``````defmodule Day8 do
@width 99
@height 99

def boolean_to_integer(bool) do
if bool, do: 1, else: 0
end

def at(trees, x, y) do
index = y * @width + x
trees[index]
end

# precondition: the tree is not on the edge
def is_visible(trees, x, y) do
height = at(trees, x, y)

left = 0..(x - 1) |> Enum.all?(fn i -> at(trees, i, y) < height end)
right = (x + 1)..(@width - 1) |> Enum.all?(fn i -> at(trees, i, y) < height end)
up = 0..(y - 1) |> Enum.all?(fn i -> at(trees, x, i) < height end)
down = (y + 1)..(@height - 1) |> Enum.all?(fn i -> at(trees, x, i) < height end)
left or right or up or down
end

def count_visible(trees) do
edge = @width * 2 + (@height - 2) * 2

interior = Enum.sum(for i <- 1..(@width - 2), j <- 1..(@height - 2) do
boolean_to_integer(is_visible(trees, i, j))
end)

edge + interior
end

# precondition: the tree is not on the edge
def scenic_score(trees, x, y) do
height = at(trees, x, y)

left = (x - 1)..0
|> Enum.reduce_while(0, fn i, acc ->
h = at(trees, i, y)
if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
end)

right = (x + 1)..(@width - 1)
|>  Enum.reduce_while(0, fn i, acc ->
h = at(trees, i, y)
if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
end)

up = (y - 1)..0
|> Enum.reduce_while(0, fn j, acc ->
h = at(trees, x, j)
if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
end)

down =  (y + 1)..(@height - 1)
|>  Enum.reduce_while(0, fn j, acc ->
h = at(trees, x, j)
if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
end)

left * right * up * down
end

def find_best_scenic_score(trees) do
Enum.max(for i <- 1..(@width - 2), j <- 1..(@height - 2) do
scenic_score(trees, i, j)
end)
end

def start() do
trees = File.stream!("input08")
|> Stream.map(&String.trim/1)
|> Enum.join
|> String.graphemes
|> Enum.map(&String.to_integer/1)
|> Arrays.new

Day8.count_visible(trees) |> IO.puts
Day8.find_best_scenic_score(trees) |> IO.puts
end
end
``````

I used Maps of Maps for faster access

Part 1

``````visible? =
fn x, y, height, forest ->
#IO.inspect({x, y, height})
Enum.map(0..x-1, &(forest[&1][y])) |> Enum.all?(&(&1 < height)) or
Enum.map(x+1..98, &(forest[&1][y])) |> Enum.all?(&(&1 < height)) or
Enum.map(0..y-1, &(forest[x][&1])) |> Enum.all?(&(&1 < height)) or
Enum.map(y+1..98, &(forest[x][&1])) |> Enum.all?(&(&1 < height))
end

forest =
input
|> String.split("\n")
|> Enum.with_index()
|> Enum.reduce(%{}, fn {row, row_index}, acc ->
row =
String.codepoints(row)
|> Enum.with_index()
|> Enum.reduce(%{}, fn {tree_height, col_index}, acc ->
Map.put(acc, col_index, String.to_integer(tree_height))
end)

Map.put(acc, row_index, row)
end)

forest
|> Enum.reduce(0, fn {row, trees}, count_visible ->
count_visible +
Enum.reduce(trees, 0, fn {col, tree_height}, count_visible ->
cond do
row == 0 -> count_visible + 1
col == 0 -> count_visible + 1
row == 98 -> count_visible + 1
col == 98 -> count_visible + 1
true ->
if visible?.(row, col, forest[row][col], forest) do
count_visible + 1
else
count_visible
end
end
end)
end)
``````

Part 2

``````visibility_count =
fn heights, height ->
heights
|> Enum.reduce_while(0, fn h, acc ->
if h >= height do
{:halt, acc + 1}
else
{:cont, acc + 1}
end
end)
end

score =
fn x, y, height, forest ->
l = Enum.map(0..x-1, &(forest[&1][y])) |> Enum.reverse() |> visibility_count.(height)
r = Enum.map(x+1..98, &(forest[&1][y])) |> visibility_count.(height)
t = Enum.map(0..y-1, &(forest[x][&1])) |> Enum.reverse() |> visibility_count.(height)
d = Enum.map(y+1..98, &(forest[x][&1])) |> visibility_count.(height)

l * r * t * d
end

forest
|> Enum.reduce(0, fn {row, trees}, max_score ->
new_score =
Enum.reduce(trees, 0, fn {col, tree_height}, max_score ->
cond do
row == 0 -> max_score
col == 0 -> max_score
row == 98 -> max_score
col == 98 -> max_score
true ->
new_score = score.(row, col, forest[row][col], forest)
if max_score < new_score do
new_score
else
max_score
end
end
end)

if max_score < new_score do
new_score
else
max_score
end
end)
``````

Done with Livebook

1 Like

Fun with index math. I started the first part with the assumption that visibility is increasing unlikely toward the center so I should go from the edges in. But I made a serious logic error thinking I could get away with just tracking the visibility of the previous row/column as a short hand, forgetting that if a height was equal then I would need to consider the one before that, and the one before that if it was equal…so it took much longer than it should have

After fixing that things went smoothly although I had to do way more debugging in the second part than any previous day. All in all I really enjoyed this one, surveying a matrix from the outside in and then inside out

There is an optimization you can do in part 1, as you know that once the tree height is 9 you can’t see anything behind that, so there so use checking.

Late to the party. Brute forced like others

2 Likes

Didn’t have a chance to do this before now. Just threw together the quickest brute force solution I could. I’m sure there’s a clever dynamic programming approach that I’m missing. I hate that I couldn’t come up with a more concise way of searching the four directions.

``````def parse(input) do
input
|> String.split()
|> Enum.with_index()
|> Enum.map(&parse_line/1)
|> List.flatten()
|> Enum.reduce(Map.new(), fn {value, key}, map -> Map.put(map, key, value) end)
end
``````

Maybe purely stylistic but in a previous year’s AOC thread someone pointed out to me that `Map.new/2` makes `Enum.reduce(Map.new(), ...` unnecessary. Just pipe the enumerable into `Map.new(fn {v, k} -> {k, v} end)`. Also I think `Enum.flat_map(&parse_line/1)` does the same thing in one line as your current `Enum.map(&parse_line/1) |> List.flatten()`

I’m still one day behind but here goes my day 8. I struggled at puzzle 2 getting my ranges right. Yup, and I had the same issue with counting the taller tree.

``````defmodule ExAOC2022.Day8 do
@input "./lib/day8_input.txt"

def puzzle1() do
lines = file_by_line(@input)
grid = Enum.map(lines, &(String.split(&1, "", trim: true)))

rows_num = length(lines)
cols_num = hd(grid) |> length

for i <- 0..rows_num-1, j <- 0..cols_num-1, reduce: 0 do
acc ->
if visible?(grid, i, j, rows_num, cols_num), do: acc + 1, else: acc
end
end

def puzzle2() do
lines = file_by_line(@input)
grid = Enum.map(lines, &(String.split(&1, "", trim: true)))

rows_num = length(lines)
cols_num = hd(grid) |> length

for i <- 1..rows_num-2, j <- 1..cols_num-2, reduce: 0 do
acc ->
score = scenic_score(grid, i, j, rows_num-1, cols_num-1)
if score > acc, do: score, else: acc
end
end

defp visible?(grid, x, y, max_x, max_y) do
v = val(grid, x, y)

cond do
# edge
x == 0 or y == 0 or x == (max_x - 1) or y == (max_y - 1) ->
true
# up
max_num_y(grid, x, 0, y-1) < v ->
true
# down
max_num_y(grid, x, y+1, max_y-1) < v ->
true
# left
max_num_x(grid, y, 0, x-1) < v ->
true
# right
max_num_x(grid, y, x+1, max_x-1) < v ->
true
true ->
false
end
end

defp scenic_score(grid, x, y, max_x, max_y) do
v = val(grid, x, y)
up_trees = Enum.map(y-1..0//-1, &val(grid, x, &1)) |> dist(v)
left_trees = Enum.map(x-1..0//-1, &val(grid, &1, y)) |> dist(v)
down_trees = Enum.map(y+1..max_y, &val(grid, x, &1)) |> dist(v)
right_trees = Enum.map(x+1..max_x, &val(grid, &1, y)) |> dist(v)

up_trees * down_trees * left_trees * right_trees
end

defp dist(trees, our_tree) do
Enum.reduce_while(trees, 0, fn tree, score ->
if tree >= our_tree, do: {:halt, score + 1}, else: {:cont, score + 1}
end)
end

defp max_num_y(grid, x, from, to), do:
Enum.map(from..to, &val(grid, x, &1)) |> Enum.max()

defp max_num_x(grid, y, from, to), do:
Enum.map(from..to, &val(grid, &1, y)) |> Enum.max()

defp int(s), do: String.to_integer(s)

defp val(grid, x, y) do
get_in(grid, [Access.at(y), Access.at(x)]) |> int
end

defp file_by_line(file) do
file
|> String.split(~r/\R/, trim: true)
end
end
``````

Way late with this, but I took the last Advent of Code as a means to learn Elixir a bit and this is what I came up with for the day 8 challenge.

``````defmodule Aoc2022.Day8 do
@moduledoc """
Documentation for `Day 8`.

--- Day 8: Treetop Tree House ---

"""

defmodule Tree do
defstruct height: nil, visible: false, score: 1
end

def process_input do
rows =
|> String.split("\r\n")

row_count = Enum.count(rows) - 1
cols = rows |> Enum.at(0) |> String.graphemes()
col_count = Enum.count(cols) - 1

trees =
rows
|> Enum.with_index()
|> Enum.map(fn {x, i} ->
t =
x
|> String.graphemes()
|> Enum.with_index()
|> Enum.reduce(%{}, fn {y, j}, acc ->
Map.put(acc, {i, j}, %Tree{height: String.to_integer(y), visible: false})
end)

t
end)
|> Enum.reduce(%{}, fn x, acc ->
Map.merge(acc, x)
end)

trees_with_visibility =
0..row_count
|> Enum.map(fn i ->
0..col_count
|> Enum.map(fn j ->
case {i, j} do
{0, _} ->
tree = Map.get(trees, {i, j})
%{{i, j} => %Tree{tree | visible: true}}

{_, 0} ->
tree = Map.get(trees, {i, j})
%{{i, j} => %Tree{tree | visible: true}}

{r, _} when r == row_count ->
tree = Map.get(trees, {i, j})
%{{i, j} => %Tree{tree | visible: true}}

{_, c} when c === col_count ->
tree = Map.get(trees, {i, j})
%{{i, j} => %Tree{tree | visible: true}}

{r, c} when r == row_count and c == col_count ->
tree = Map.get(trees, {i, j})
%{{i, j} => %Tree{tree | visible: true}}

{row, column} ->
%{height: current, visible: _v} = Map.get(trees, {i, j})

trees_left = traverse_x(trees, column - 1, 0, row)

visibility_score_left =
trees_left
|> visibility_score(current)

visible_left? =
trees_left
|> Enum.filter(fn x -> current <= x end)
|> Enum.empty?()

trees_right = traverse_x(trees, column + 1, col_count, row)

visibility_score_right =
trees_right
|> visibility_score(current)

visible_right? =
trees_right
|> Enum.filter(fn x -> current <= x end)
|> Enum.empty?()

trees_up = traverse_y(trees, row - 1, 0, column)

visibility_score_up =
trees_up
|> visibility_score(current)

visible_up? =
trees_up
|> Enum.filter(fn x -> current <= x end)
|> Enum.empty?()

trees_down = traverse_y(trees, row + 1, row_count, column)

visibility_score_down =
trees_down
|> visibility_score(current)

visible_down? =
trees_down
|> Enum.filter(fn x -> current <= x end)
|> Enum.empty?()

%{
{i, j} => %Tree{
height: current,
visible: visible_up? || visible_down? || visible_left? || visible_right?,
score:
visibility_score_down * visibility_score_left * visibility_score_right *
visibility_score_up
}
}
end
end)
end)
|> List.flatten()
|> Enum.reduce(%{}, fn w, acc ->
Map.merge(w, acc)
end)

visible_count =
trees_with_visibility
|> Enum.filter(fn {_, %{height: _, visible: v}} -> v end)
|> Enum.count()

highest_score =
trees_with_visibility
|> Enum.map(fn {_, %{score: s}} -> s end)
|> Enum.max()

{visible_count, highest_score}
end

defp traverse_x(trees, from, to, axis) do
from..to
|> Enum.map(fn x ->
%{height: u, visible: _v} = Map.get(trees, {axis, x})
u
end)
end

defp traverse_y(trees, from, to, axis) do
from..to
|> Enum.map(fn x ->
%{height: u, visible: _v} = Map.get(trees, {x, axis})
u
end)
end

defp visibility_score(trees, current) do
score =
trees
|> Enum.reduce_while(0, fn x, acc ->
if x >= current, do: {:halt, acc + 1}, else: {:cont, acc + 1}
end)

score
end
end

``````

A tiny bit of code review on the above - nothing major, mostly “here’s a shorter way to write the same ideas” tips.

• many `Enum` functions have a variant that lets you transform the input before doing their thing. For instance, `Enum.count/2` or `Enum.max_by/4`. There’s a minor performance benefit of using them since the intermediate list doesn’t need to be constructed, but IMO the readability gain is better.

• `Enum.map` + `List.flatten` == `Enum.flat_map`, only again the intermediate list doesn’t need to be constructed.

• Most code that uses `Enum.reduce` with an initial value of `%{}` will be clearer with `Map.new`. I say “most” because sometimes there’s code in the block passed to `reduce` that returns `acc` unchanged, which you can’t do with `Map.new`

• most of the time when you want one-line-at-a-time, `File.stream!` will save you some typing. By default, it already splits lines. There is also a theoretical memory-usage advantage since using `Stream` means you don’t need every line in memory at once, but it’s unlikely to be important.

• functions are basically free: make more of them. In my experience, if you’d use a phrase to name a piece of code when discussing it with a colleague, it should probably be a separate function. For instance, here’s the “read the file in” part from my day 8 solution:

``````  def read(filename) do
File.stream!(filename)
|> Stream.map(&String.trim/1)
|> Stream.with_index()
|> Stream.flat_map(&parse_line/1)
|> Map.new()
end

defp parse_line({line, row_index}) do
line
|> String.codepoints()
|> Enum.map(&String.to_integer/1)
|> Enum.with_index()
|> Enum.map(fn {h, col_index} -> {{row_index, col_index}, h} end)
end
``````

If you wanted `%Tree{}` structs like in your version, you’d change that very last statement of `parse_line` to build one out of `row_index` / `col_index` / `h` values.

Another guideline I find useful: repeat yourself, find the common parts, and then make THAT a function. For instance, you might notice this pattern (placeholders in `SHOUTING_CASE`):

``````trees_DIR = GET_TREES

visibility_score_DIR =
trees_DIR
|> visibility_score(current)

visible_DIR? =
trees_DIR
|> Enum.filter(fn x -> current <= x end)
|> Enum.empty?()
``````

This becomes a function:

``````defp visibility_of(trees, current) do
score = visibility_score(trees, current)

flag =
trees
|> Enum.filter(fn x -> current <= x end)
|> Enum.empty? # NOTE: consider using any? instead of filter + empty?

{score, flag}
end
``````

then the big branch of the case shortens to:

``````            {row, column} ->
%{height: current, visible: _v} = Map.get(trees, {i, j})

{visibility_score_left, visible_left?} =
trees
|> traverse_x(column - 1, 0, row)
|> visibility_of(current)

{visibility_score_right, visible_right?} =
trees
|> traverse_x(column + 1, col_count, row)
|> visibility_of(current)

{visibility_score_up, visible_up?} =
trees
|> traverse_y(row - 1, 0, column)
|> visibility_of(current)

{visibility_score_down, visible_down?} =
trees
|> traverse_y(row + 1, row_count, column)
|> visibility_of(current)

%{
{i, j} => %Tree{
height: current,
visible: visible_up? || visible_down? || visible_left? || visible_right?,
score:
visibility_score_down * visibility_score_left * visibility_score_right *
visibility_score_up
}
}
``````

Writing things this way makes it clearer that only the trees change between the four copies of the code.

2 Likes

Hi Matt!

Thanks for taking the time to analyze the code, these are very valuable suggestions which I’ll try to use in the future.

Elixir is indeed a special language, there is (almost) always a better and more elegant solution to a particular problem.