# Advent of Code 2020 - Day 3

This topic is about Day 3 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
`39276-eeb74f9a`

1 Like

Might not be the most efficient solution, but fairly straightforward:

Day 3 Notes

• Took a bit longer than it should to build the data structure, then got hung up for several minutes on a row vs. col mixup when accessing it (forgot that I need to `get_in(map, [y, x]`) instead of `[x, y]`).
• Still pretty straightforward, my initial solution worked as expected for both parts (once I got it implemented properly). Part 2 did not add a new twist this time, which was unusual. (Unless of course, you assumed that you would always move down by oneâ€¦)
2 Likes

Me the same. Iâ€™m struggling with iterating through a range with a specific step.

Hereâ€™s my solution:

``````#!/usr/bin/env elixir

field = "./day3.txt"
|> File.stream!([], :line)
|> Enum.map(&String.trim/1)

width = IO.iodata_length(hd(field))
height = length(field)
field = field
|> Stream.with_index()
|> Stream.map(fn{row, i}->{i, row}end)
|> Map.new()

get_trees = fn({right, down})->
(0..height-1)
|> Stream.chunk_every(down, down, :discard)
|> Stream.map(&hd/1)
|> Enum.reduce({0, {0, 0}}, fn(_, {trees, {i, j}})->
row = field[i]
trees = if :binary.at(row, j) == ?#, do: trees + 1, else: trees
{trees, {i + down, rem(j + right, width)}}
end)
|> elem(0)
end

# Part 1
IO.puts get_trees.({3, 1})

# Part 2
[{1, 1}, {3, 1}, {5, 1}, {7, 1}, {1, 2}]
|> Enum.map(get_trees)
|> Enum.reduce(&*/2)
|> IO.inspect()
``````

I used:

• `Stream.cycle/1` to handle the repeating horizontal values
• `Enum.take_every/2` to handle skipping the downward slope.
• The input wasnâ€™t very long, so I just brute forced the horizontal value with `Enum.at/2`.
``````  def slope(v_x, v_y) do
{_, trees} =
File.read!("input")
|> String.trim()
|> String.split("\n")
|> Enum.take_every(v_y)
|> Enum.map(&String.to_charlist/1)
|> Enum.reduce({0, 0}, fn row, {x, trees} ->
trees =
case Stream.cycle(row) |> Enum.at(x) do
?# -> trees + 1
?. -> trees
end

{x + v_x, trees}
end)

trees
end
``````
5 Likes

Love the idea of `Stream.cycle` with `Enum.at`.

I see Iâ€™m not the first one to find the `Stream.cycle` function
My version:

``````defmodule Aoc2020.Day03 do
def part1(input) do
count_trees(input, {3, 1})
end

def part2(input) do
slopes = [
{1, 1},
{3, 1},
{5, 1},
{7, 1},
{1, 2}
]

for slope <- slopes, reduce: 1 do
product -> product * count_trees(input, slope)
end
end

def count_trees(input, {dx, dy}) do
input
|> Stream.take_every(dy)
|> Stream.map(&Stream.cycle/1)
|> Enum.reduce({0, 0}, fn
row, {trees, shift} ->
row
|> Stream.drop(shift)
|> Enum.at(0)
|> case do
?. ->
{trees, shift + dx}

?# ->
{trees + 1, shift + dx}
end
end)
|> elem(0)
end

def input_stream(path) do
File.stream!(path)
|> Stream.map(&parse/1)
end

defp parse(line) do
line
|> String.trim()
|> String.to_charlist()
end
end

input = Aoc2020.Day03.input_stream("input.txt")

input
|> Aoc2020.Day03.part1()
|> IO.inspect(label: "part1")

input
|> Aoc2020.Day03.part2()
|> IO.inspect(label: "part2")
``````
4 Likes

`Stream.take_every/2`! Thatâ€™s what Iâ€™m looking for!

Whatâ€™s the benefit of `Stream.drop(shift) |> Enum.at(0)` over just `Enum.at(shift)`?

This was a fun one. I build a map of `%{{x :: non_neg_integer, y :: non_neg_integer} => type :: :tree | :space}` from the input. For the horizontal repeating I simply used `rem(x, max_x)` to preprocess the coordinates before checking the map. For building the path through the map I used `Stream.unfold` to build a stream of types at the coordinates following the trajectory from the start.

2 Likes

One benefit is that you get to write one more line of lovely Elixir code

I think it is better without that `Stream.drop` though, so I have removed tit from my final version on GitHub.

2 Likes

Interesting indeed. Instead of `fold` like mine and many other contendersâ€™ code, you `unfold`. Thatâ€™s a new angle of looking at the problem.

Yeah, I feel `Stream.unfold` is overlooked quite often. Itâ€™s a really great api for places where one would use `while` in other languages. My solution in particular feels quite declarative even, given it deals at least as much with start, trajectory and moving as it does with actually figuring out if thereâ€™s a tree at the coordinate and counting them.

1 Like

I also went immediately for `Stream.unfold`:

``````defmodule AdventOfCode.Day03 do
def part1(input) do
input
|> String.trim()
|> String.split("\n")
|> walk_map(3, 1)
|> Enum.count(& &1)
end

def part2(input) do
rows =
input
|> String.trim()
|> String.split("\n")

slope_1 = rows |> walk_map(1, 1) |> Enum.count(& &1)
slope_2 = rows |> walk_map(3, 1) |> Enum.count(& &1)
slope_3 = rows |> walk_map(5, 1) |> Enum.count(& &1)
slope_4 = rows |> walk_map(7, 1) |> Enum.count(& &1)
slope_5 = rows |> walk_map(1, 2) |> Enum.count(& &1)

slope_1 * slope_2 * slope_3 * slope_4 * slope_5
end

def walk_map(rows, right, down) do
Stream.unfold({0, 0}, fn {x, y} ->
case rows |> Enum.at(y) |> get_x_position(x) do
"." -> {false, {x + right, y + down}}
"#" -> {true, {x + right, y + down}}
nil -> nil
end
end)
end

defp get_x_position(nil, _), do: nil

defp get_x_position(row, position) do
if position >= String.length(row) do
get_x_position(row, rem(position, String.length(row)))
else
String.at(row, position)
end
end
end
``````

Precomputed the grid as a `map`, then I also compute the path coordinates and just check the grid if it has trees on these coordinates.

GitHub link

``````defmodule Aoc.Y2020.D3 do
use Aoc.Boilerplate,
transform: fn raw ->
grid =
raw
|> String.split("\n", trim: true)
|> Enum.with_index()
|> Enum.flat_map(fn {line, index} ->
line
|> String.split("", trim: true)
|> Enum.with_index()
|> Enum.map(fn {char, char_index} ->
{{index, char_index}, char}
end)
end)
|> Enum.into(%{})

width =
raw
|> String.split("\n")
|> Enum.at(0)
|> String.split("", trim: true)
|> Enum.count()

height =
raw
|> String.split("\n", trim: true)
|> Enum.count()

%{width: width, height: height, grid: grid}
end

@part_1_operations [{3, 1}]
@part_2_operations [[{1, 1}], [{3, 1}], [{5, 1}], [{7, 1}], [{1, 2}]]

@doc """
Receives input in form of `%{width: 31, height: 323, grid: %{{0,0} => ".", {0,1} => "#"}, ...}`
"""
def part1(input \\ processed()) do
@part_1_operations
|> Stream.cycle()
|> Enum.take(input.height)
|> count_trees(input)
end

def part2(input \\ processed()) do
@part_2_operations
|> Enum.map(fn ops ->
ops
|> Stream.cycle()
|> Enum.take(input.height)
|> count_trees(input)
end)
|> Enum.reduce(&(&1 * &2))
end

defp count_trees(moves, input) do
moves
|> Enum.reduce({0, {0, 0}}, fn {move_right, move_down}, {trees, {current_row, current_column}} ->
row = current_row + move_down
column = Integer.mod(current_column + move_right, input.width)

case Map.get(input.grid, {row, column}, ".") do
"." -> {trees, {row, column}}
"#" -> {trees + 1, {row, column}}
end
end)
|> elem(0)
end
end
``````
1 Like

My solution with streams keeping only 1 line of map in memory at any given time.

``````defmodule Event3 do
def run do
part1_ruleset = [{3, 1}]
part2_ruleset = [{1, 1}, {3, 1}, {5, 1}, {7, 1}, {1, 2}]
IO.puts("Test part1: #{solver("input/event3/test.txt", part1_ruleset)}")
IO.puts("Puzzle part1: #{solver("input/event3/puzzle.txt", part1_ruleset)}")
IO.puts("Test part2: #{solver("input/event3/test.txt", part2_ruleset)}")
IO.puts("Puzzle part2: #{solver("input/event3/puzzle.txt", part2_ruleset)}")
end

def solver(path, ruleset) do
accs = Enum.map(ruleset, &rule_to_acc/1)

input_stream(path)
|> Stream.drop(1)
|> Stream.transform(accs, &step_all/2)
|> Stream.take(-length(ruleset))
|> Stream.flat_map(& &1)
|> Enum.reduce(&(&1 * &2))
end

def input_stream(path), do: path |> File.stream!() |> Stream.map(&parse_input/1)

def parse_input(input), do: String.trim(input) |> String.graphemes() |> Enum.map(&(&1 == "#"))

def step_all(input, acc), do: Enum.map(acc, &step(input, &1)) |> Enum.unzip()

def step(input, {count, index, step, step_down, step_down}) do
width = length(input)
count = count + ((Enum.at(input, index) && 1) || 0)
{[count], {count, rem(index + step, width), step, step_down, 1}}
end

def step(_input, {count, index, step, step_down, down_counter}),
do: {[count], {count, index, step, step_down, down_counter + 1}}

def rule_to_acc({right, down}), do: {0, right, right, down, 1}
end

``````
3 Likes

My solution:

``````defmodule TreeMap do
defstruct ~w[map max_x max_y]a

def new(txt) when is_binary(txt) do
%__MODULE__{}
|> parse(txt)
end

def is_tree?(%__MODULE__{map: map, max_x: max_x, max_y: max_y} = _map, {x, y})
when y <= max_y do
map[y][rem(x, max_x + 1)] == "#"
end

def in_bounds?(%__MODULE__{max_y: max_y} = _map, {_x, y} = _coords) when y <= max_y, do: true

def in_bounds?(%__MODULE__{} = _map, _coords), do: false

defp parse(result, txt) do
{map, max_y, max_x} =
txt
|> String.split()
|> Enum.map(&String.trim/1)
|> Enum.reduce({%{}, 0, 0}, fn line, {result, y, _max_x} = _acc ->
line_as_map =
0..String.length(line)
|> Enum.zip(String.graphemes(line))
|> Enum.into(%{})

{Map.put(result, y, line_as_map), y + 1, String.length(line) - 1}
end)

%{result | map: map, max_y: max_y - 1, max_x: max_x}
end
end

map =
File.read!("day3.txt")
|> TreeMap.new()

slope1 = fn {x, y} ->
{x + 1, y + 1}
end

slope2 = fn {x, y} ->
{x + 3, y + 1}
end

slope3 = fn {x, y} ->
{x + 5, y + 1}
end

slope4 = fn {x, y} ->
{x + 7, y + 1}
end

slope5 = fn {x, y} ->
{x + 1, y + 2}
end

[slope1, slope2, slope3, slope4, slope5]
|> Enum.map(fn fun ->
Stream.iterate({0, 0}, fun)
|> Enum.take_while(&TreeMap.in_bounds?(map, &1))
|> Enum.map(fn coords ->
(TreeMap.is_tree?(map, coords) && 1) || 0
end)
|> Enum.sum()
end)
|> Enum.reduce(1, &*/2)
|> IO.puts()
``````

`Stream.transform` has a bit of a learning curve, but you can make it do basically anything that involves â€ślook at each element of this list, plus some information from previous iterations, and return some results and information for the next iterationâ€ť.

This solution transforms the file (one line at a time) into a stream of `{"..#", row#, col#}` tuples representing the path, then counts the ones that have a tree at the correct column.

The day2 version uses a neat property of `transform` - returning `[]` works like it does in `flat_map` and produces no output, so skipping rows (for the â€śdown 2 over 1â€ť) case is easy.

1 Like

I think my solution is similar to that of @LostKobrakai @egze, using `rem(position, length(line))` to map the large position into the small map.

The two novelties I can offer are:

1. Used elixir scripts for everything (no modules/functions)
2. Itâ€™s a one-pass solution going through all lines only once
``````#!/usr/bin/env elixir
require Integer

map = File.read!("3.csv")
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
String.to_charlist(line)
|> Enum.map(fn char -> char == ?# end)
end)
|> Enum.reduce(List.duplicate({0, 0}, 5), fn trees, slopes ->
Enum.with_index(slopes)
|> Enum.map(fn {{pos, count}, slope} ->
nextpos = case slope do
0 -> pos+1
1 -> pos+3
2 -> pos+5
3 -> pos+7
4 -> pos+0.5
end
if trunc(pos) == pos and Enum.at(trees, rem(trunc(pos), length(trees))) do
{nextpos, count + 1}
else
{nextpos, count}
end
end)
end)

result = Enum.map(map, fn {_pos, count} -> count end)
|> Enum.reduce(1, fn count, product -> count * product end)

:io.format("~p~n", [result])
``````

Git Repo

I clearly need to spend more time with the `Stream` module. I picked an easy way to do it:

``````defmodule Day03.Forest do
defstruct forest: [], width: 0, height: 0
end

defmodule Day03 do
alias Day03.Forest

def readinput() do
input =
File.stream!("3.input.txt")
|> Enum.map(fn line -> String.trim(line) |> String.graphemes() end)

%Forest{forest: input, height: length(input), width: length(Enum.at(input, 0))}
end

def part1(forest \\ readinput()) do
move(forest, 3, 1, 0, 0, 0)
end

def part2(forest \\ readinput()) do
[{1, 1}, {3, 1}, {5, 1}, {7, 1}, {1, 2}]
|> Enum.map(fn {right, down} ->
move(forest, right, down, 0, 0, 0)
end)
|> Enum.reduce(1, &*/2)
end

def move(forest, right, down, x, y, numtrees) do
newx = rem(x + right, forest.width)
newy = y + down

if newy >= forest.height do
numtrees + under(forest, x, y)
else
move(forest, right, down, newx, newy, numtrees + under(forest, x, y))
end
end

def under(forest, x, y) do
if Enum.at(forest.forest, y) |> Enum.at(x) == "#", do: 1, else: 0
end
end

``````

O(mn) solution

``````defmodule Advent.Day3b do
@doc """
right_down part 1 -> [{3, 1}]
right_down part 2 -> [{1, 1}, {3, 1}, {5, 1}, {7, 1}, {1, 2}]
"""
def start(right_down \\ [{3, 1}], file \\ "/tmp/input.txt"), do:
File.read!(file) |> String.split("\n") |> process_paths(right_down)

defp process_paths(path, right_down), do:
Enum.reduce(right_down, 1, fn {right, down}, acc ->
path |> find_bottom(right, down - 1) |> (fn trees -> acc * trees end).()
end)

def find_bottom([h|t], right, down), do: find_bottom(t, byte_size(h), right, right, down, down, 0)
def find_bottom(lst, _, _, _, _, _, acc) when lst in [[], [""]], do: acc
def find_bottom([h|t], line_length, position, right, 0, down, acc), do:
find_bottom(t, line_length, position + right, right, down, down, acc + is_tree(binary_part(h, rem(position, line_length), 1)))
def find_bottom([h|t], line_length, position, right, skip, down, acc), do:
find_bottom(t, line_length, position, right, skip - 1, down, acc)

def is_tree("#"), do: 1
def is_tree(_), do: 0

end
``````