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/1to handle the repeating horizontal values -
Enum.take_every/2to 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.
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:
- Used elixir scripts for everything (no modules/functions)
- 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])
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
