# Advent of Code 2021 - Day 5

This topic is about Day 5 of the Advent of Code 2021.

We have a private leaderboard (shared with users of Erlang Forums ):

The entry code is:
`370884-a6a71927`

Here is my solution:

This one was nicer to me. I like my approach for handling the lines, but I don’t like my approach to parsing the input. There has to be a pattern matching on binaries but it’s beyond me.

``````def part_1 do
@path
|> parse_input()
|> Enum.filter(fn line -> line_direction(line) in @orthogonal end)
|> plot_lines_to_map()
|> Enum.count(fn {_k, v} -> v > 1 end)
end
``````

Part 2 simply removes the `Enum.filter`
Full solution here

My solution

Today was significatively simpler than yesterday, but I had to remember my vector algebra To calculate the intermediate points, I used:

``````  def fill_points({x1,y1,x2,y2}) do
{dx, dy} = {x2 - x1, y2 - y1}
slope = {step(dx), step(dy)}
do_fill({x1, y1}, {x2, y2}, slope, [])
end

defp step(0), do: 0
defp step(x) when x > 0, do: 1
defp step(x) when x < 0, do: -1

defp do_fill(point, point, _slope, acc) do
[point | acc]
end

defp do_fill({x1, y1} = point, end_point, {dx, dy} = slope, acc) do
new_point = {x1 + dx, y1 + dy}
do_fill(new_point, end_point, slope, [point | acc])
end
``````
1 Like

maybe you will like my way of parsing the input?

``````      File.read!("day_5.txt")
|> String.split(["\n", ",", " -> "], trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(4)
|> Enum.map(&List.to_tuple/1)
``````

We can split the file in all the special content we have, and then just take numbers 4 at a time. No need to nest anything

2 Likes

This one was fun. Beautiful use of pipe and pattern:

``````defmodule AdventOfCode.Y2021.Day05 do

def run_1, do: input!() |> parse() |> overlaps(false)
def run_2, do: input!() |> parse() |> overlaps(true)
def parse(data), do: Enum.map(String.split(data, "\n"), &ranges/1)

defp ranges(line) do
~r/(\d+),(\d+) -> (\d+),(\d+)/
|> Regex.run(line, capture: :all_but_first)
|> Enum.map(&String.to_integer/1)
|> Enum.split(2)
end

defp overlaps(ranges, diagonal?) do
ranges
|> Enum.flat_map(&points_between(&1, diagonal?))
|> Enum.frequencies()
|> Enum.count(&(elem(&1, 1) >= 2))
end

defp points_between({from, to}, diagonal?) do
case {{from, to}, diagonal?} do
{{[same, a], [same, b]}, _} -> Enum.map(a..b, &{same, &1})
{{[a, same], [b, same]}, _} -> Enum.map(a..b, &{&1, same})
{range, true} -> diagonals(range)
_ -> []
end
end

defp diagonals({[a, b], [c, d]}),
do: Enum.map(0..abs(a - c), &{(a > c && a - &1) || a + &1, (b > d && b - &1) || b + &1})
end
``````

Feels regex is justified here, maybe?

``````defmodule Aoc2021.Vents do
def overlaps(coords) do
regex = ~r/(\d+),(\d+) -> (\d+),(\d+)/

coords
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
Regex.run(regex, line, capture: :all_but_first)
|> Enum.map(&String.to_integer/1)
|> then(fn [x1, y1, x2, y2] -> [{x1, y1}, {x2, y2}] end)
end)
|> Enum.flat_map(&expand/1)
|> Enum.frequencies()
|> Enum.count(fn {_key, val} -> val > 1 end)
end

defp expand([{x1, y1}, {x2, y2}]) do
cond do
x1 == x2 -> for y <- y1..y2, do: {x1, y}
y1 == y2 -> for x <- x1..x2, do: {x, y1}
abs(y1 - y2) == abs(x1 - x2) -> Enum.zip(x1..x2, y1..y2)
:otherwise -> []
end
end
end

``````

Here is my solution for part 1. For part two, removing the filter does the job.

``````expend_lines = fn
[{x, y1}, {x, y2}] ->
y = y1..y2
Enum.zip(List.duplicate(x, Enum.count(y)), y1..y2)

[{x1, y}, {x2, y}] ->
x = x1..x2
Enum.zip(x1..x2, List.duplicate(y, Enum.count(x)))

[{x1, y1}, {x2, y2}] ->
Enum.zip(x1..x2, y1..y2)
end

input
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
line
|> String.split([",", "->"], trim: true)
|> Enum.map(fn value -> String.trim(value) |> String.to_integer() end)
|> Enum.chunk_every(2)
|> Enum.map(&List.to_tuple/1)
end)
|> Enum.filter(fn [{x1, y1}, {x2, y2}] -> x1 == x2 or y1 == y2 end)
|> Enum.flat_map(expend_lines)
|> Enum.frequencies()
|> Enum.count(fn {_, count} -> count > 1 end)
``````

I also draw the board in order to debug, but I am not able to properly draw it neither in console neither in Live Book due to `\n` that are not “expended”.

“1.1…11.\n.111…2…\n…2.1.111.\n…1.2.2…\n.112313211\n…1.2…\n…1…1…\n.1…1…\n1…1.\n222111…”

Someone knows how I can show it like this?

``````1.1....11.
.111...2..
..2.1.111.
...1.2.2..
.112313211
...1.2....
..1...1...
.1.....1..
1.......1.
222111....
````````

`IO.puts` would work, I think:

``````iex(5)> input = "1.1...11.\n.111...2...\n...2.1.111.\n...1.2.2...\n.112313211\n...1.2...\n...1...1...\n.1...1...\n1...1.\n222111..."
iex(6)> IO.puts input
1.1...11.
.111...2...
...2.1.111.
...1.2.2...
.112313211
...1.2...
...1...1...
.1...1...
1...1.
222111...
``````
1 Like

Here’s my day 5 solution. After coding up a physical representation of the graph, I saw how slow it was. And it dawn on me that I don’t need a physical graph. Just the points touched.

Here’s my take:

``````defmodule Y2021.Day05 do
def p1 do
AOC.Input.stream("2021/day05.txt", &parse_seg/1)
|> Stream.filter(fn [x1, y1, x2, y2] -> x1 == x2 || y1 == y2 end)
|> count_overlap()
end

def p2 do
AOC.Input.stream("2021/day05.txt", &parse_seg/1)
|> count_overlap()
end

defp parse_seg(line) do
Regex.run(~r/(\d+),(\d+) -> (\d+),(\d+)/, line, capture: :all_but_first)
|> Enum.map(&String.to_integer/1)
end

defp count_overlap(segs) do
segs
|> Stream.flat_map(fn [x1, y1, x2, y2] ->
max_step = max(abs(x2 - x1), abs(y2 - y1))
dx = div(x2 - x1, max_step)
dy = div(y2 - y1, max_step)

Stream.iterate({x1, y1}, fn {x, y} -> {x + dx, y + dy} end)
|> Stream.take(max_step + 1)
|> Enum.to_list()
end)
|> Enum.frequencies()
|> Enum.count(fn {_, count} -> count > 1 end)
end
end
``````

full file

1 Like

My naive solution: y2021/day_05.ex

Both part 1 and 2, full program with no other dependencies. pretty happy with the nice pipeline in there!

``````  defp sgn(0) do 0 end
defp sgn(a) do div(abs(a), a) end

defp draw(x, y, xend, yend, dx, dy, map) do
map = Map.update(map, {x, y}, 1, &(&1+1))
case {x, y} do
{^xend, ^yend} -> map
_ -> draw(x+dx, y+dy, xend, yend, dx, dy, map)
end
end

defp draw([x1, y1, x2, y2], map) do
draw(x1, y1, x2, y2, sgn(x2-x1), sgn(y2-y1), map)
end

def work(filt) do
|> String.split(~r/[^0-9]+/, trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(4, 4)
|> Enum.filter(filt)
|> Enum.reduce(%{}, &draw/2)
|> Enum.filter(fn {_, v} -> v >= 2 end)
|> Enum.count()
end

def run() do
[6311, 19929] = [ work(fn [x1,y1,x2,y2] -> x1==x2 or y1==y2 end), work(&(&1)) ]
end
``````

Wow, today was an absolute breeze (looking at you Day 4…)

• Learned about pairing Stream.cycle with Enum.zip
• Had to switch from Livebook native input (looks like it’s deprecated at `edge`) to Kino input
• Pattern matching makes this easy
• Just expanded all coordinates and counted frequencies bigger than 1
``````# Day 4

## Deps & preparation

```elixir
Mix.install([
{:kino, "~> 0.4.0"}
])

```

## Input

```elixir
coordinates =
|> String.split(["\n", ",", " -> "], trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.chunk_every(4)
```

## Part 1

```elixir
coordinates
|> Enum.reduce(
[],
fn
[x, y, x1, y1], map when y == y1 ->
Enum.zip(x..x1, Stream.cycle([y])) ++ map

[x, y, x1, y1], map when x == x1 ->
Enum.zip(Stream.cycle([x]), y..y1) ++ map

_, map ->
map
end
)
|> Enum.frequencies()
|> Enum.count(fn {_k, v} -> v > 1 end)
```

## Part 2

```elixir
coordinates
|> Enum.reduce(
[],
fn
[x, y, x1, y1], map when y == y1 ->
Enum.zip(x..x1, Stream.cycle([y])) ++ map

[x, y, x1, y1], map when x == x1 ->
Enum.zip(Stream.cycle([x]), y..y1) ++ map

[x, y, x1, y1], map ->
Enum.zip(x..x1, y..y1) ++ map
end
)
|> Enum.frequencies()
|> Enum.count(fn {_k, v} -> v > 1 end)
```
``````

EDIT: Updated with @epilgrim split approach, thanks!

1 Like

My solution: y2021/d5.ex

Wanted to use `NimbleParsec` just for fun ``````defmodule VentParser do
import NimbleParsec

coordinates =
integer(min: 1)
|> ignore(string(","))
|> integer(min: 1)

defparsec(:parse, coordinates |> ignore(string(" -> ")) |> concat(coordinates))
end
``````

@Klohto Cool use of `Enum.zip`, going to borrow it 1 Like

@Klohto - Ill one up your Stream.cycle / Enum.zip combo with a Stream.cycle / Stream.zip / Enum.take combo that works for horizontal, vertical, and 45deg diagonal lines all at the same time!

``````  @doc ~S"""
## Example

iex> build_line_segment({{0, 9}, {5, 9}})
[{0, 9}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}]

iex> build_line_segment({{0, 0}, {2, 2}})
[{0, 0}, {1, 1}, {2, 2}]
"""
def build_line_segment({{x1, y1}, {x2, y2}}) do
xs = x1..x2
ys = y1..y2

Stream.cycle(xs)
|> Stream.zip(Stream.cycle(ys))
|> Enum.take(max(Range.size(xs), Range.size(ys)))
end
``````

Here is the whole solutions

``````defmodule Day5 do

@doc ~S"""
--- Day 5: Hydrothermal Venture ---
You come across a field of hydrothermal vents on the ocean floor! These vents
constantly produce large, opaque clouds, so it would be best to avoid them if
possible.

They tend to form in lines; the submarine helpfully produces a list of nearby
lines of vents (your puzzle input) for you to review. For example:

#{test_input()}

Each line of vents is given as a line segment in the format x1,y1 -> x2,y2
where x1,y1 are the coordinates of one end the line segment and x2,y2 are the
coordinates of the other end. These line segments include the points at both
ends. In other words:

An entry like 1,1 -> 1,3 covers points 1,1, 1,2, and 1,3.
An entry like 9,7 -> 7,7 covers points 9,7, 8,7, and 7,7.
For now, only consider horizontal and vertical lines: lines where either x1 = x2 or y1 = y2.

So, the horizontal and vertical lines from the above list would produce the following diagram:

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

In this diagram, the top left corner is 0,0 and the bottom right corner is
9,9. Each position is shown as the number of lines which cover that point or
. if no line covers that point. The top-left pair of 1s, for example, comes
from 2,2 -> 2,1; the very bottom row is formed by the overlapping lines 0,9
-> 5,9 and 0,9 -> 2,9.

To avoid the most dangerous areas, you need to determine the number of points
where at least two lines overlap. In the above example, this is anywhere in
the diagram with a 2 or larger - a total of 5 points.

Consider only horizontal and vertical lines. At how many points do at least
two lines overlap?

## Example

iex> part_1(test_input())
5
"""
def_solution part_1(stream_input) do
do_solve(stream_input, &filter_lines/1)
end

defp filter_lines({{x, _y1}, {x, _y2}}), do: true
defp filter_lines({{_x1, y}, {_x2, y}}), do: true
defp filter_lines(_), do: false

@doc ~S"""
--- Part Two ---
Unfortunately, considering only horizontal and vertical lines doesn't give
you the full picture; you need to also consider diagonal lines.

Because of the limits of the hydrothermal vent mapping system, the lines in
your list will only ever be horizontal, vertical, or a diagonal line at
exactly 45 degrees. In other words:

An entry like 1,1 -> 3,3 covers points 1,1, 2,2, and 3,3.
An entry like 9,7 -> 7,9 covers points 9,7, 8,8, and 7,9.
Considering all lines from the above example would now produce the following diagram:

1.1....11.
.111...2..
..2.1.111.
...1.2.2..
.112313211
...1.2....
..1...1...
.1.....1..
1.......1.
222111....

You still need to determine the number of points where at least two lines
overlap. In the above example, this is still anywhere in the diagram with a 2
or larger - now a total of 12 points.

Consider all of the lines. At how many points do at least two lines overlap?

## Example

iex> part_2(test_input())
12
"""

def_solution part_2(stream_input) do
do_solve(stream_input)
end

defp do_solve(stream_input, filter \\ fn _ -> true end) do
stream_input
|> Stream.map(&line_to_points/1)
|> Stream.filter(&filter.(&1))
|> Stream.flat_map(&build_line_segment/1)
|> Enum.frequencies()
|> Enum.filter(fn {_point, frequency} -> frequency > 1 end)
|> Enum.count()
end

@doc ~S"""
## Example

iex> build_line_segment({{0, 9}, {5, 9}})
[{0, 9}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}]

iex> build_line_segment({{0, 0}, {2, 2}})
[{0, 0}, {1, 1}, {2, 2}]
"""
def build_line_segment({{x1, y1}, {x2, y2}}) do
xs = x1..x2
ys = y1..y2

Stream.cycle(xs)
|> Stream.zip(Stream.cycle(ys))
|> Enum.take(max(Range.size(xs), Range.size(ys)))
end

@doc ~S"""
## Example

iex> line_to_points("0,9 -> 5,9")
{{0, 9}, {5, 9}}
"""
def line_to_points(line) do
line
|> String.split([",", " -> "])
|> Enum.map(&String.to_integer/1)
|> then(fn [x1, y1, x2, y2] -> {{x1, y1}, {x2, y2}} end)
end

def test_input do
"""
0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2
"""
end
end
``````
1 Like

Was pretty much asleep when I wrote this solution but liked it when I woke up this morning. Concise but violates Elixir formatting rules.

``````defmodule Aoc.Day05 do
def part1, do: input() |> Enum.reject(fn [x1, y1, x2, y2] -> x1 != x2 and y1 != y2 end) |> part2()
def part2(), do: part2(input())
def part2(input), do: input |> Enum.reduce(%{}, &draw_line/2) |> Enum.filter(fn {_k, v} -> v > 1 end) |> Enum.count()

def draw_line([x, y1, x, y2], map), do: y1..y2 |> Enum.reduce(map, fn y, map2 -> Map.update(map2, {x,y}, 1, &(&1 + 1)) end)
def draw_line([x1, y, x2, y], map), do: x1..x2 |> Enum.reduce(map, fn x, map2 -> Map.update(map2, {x,y}, 1, &(&1 + 1)) end)
def draw_line([x1, y1, x2, y2], map), do: x1..x2 |> Enum.reduce(map, fn x, map2 -> Map.update(map2, {x, div(y2 - y1, x2 - x1) * (x - x1) + y1}, 1, &(&1 + 1)) end)

def input() do
"lib/day05/input.txt"
|> String.split("\n")
|> Enum.map(fn s -> String.split(s, [",", " -> "]) end)
|> Enum.map(fn l -> Enum.map(l, fn s -> String.to_integer(s) end) end)
end
end

``````

Another highly functional tail-recursive approach from me:

Edit: the following two paragraphs are my previous approach

Where the interesting part is that I’m using an accumulator that consists of two maps and a count, where the first map contains all the points that have at least one line pass through them, the second map, all the points that have at least two points pass through them, and the count is incremented whenever we add an element to the second map. Thus at the end we simply return the count.

This is slightly slower than using just one map and doing an if to see if we need to increment the counter, however the approach has the benefit of code elegance because we can outsource the checking if the map contains a point to the function guards, thus the function bodies become trivial.

Edit: And now the 2x faster approach

So a thought hit me - calling `Map.put/3` a lot is actually kind of slow - this is because what you do is you copy the old map and create a new one with the one new key added. A list however is fast (if you add an item at the head), because you only create the new element, put the old head as the next pointer, and return the pointer to this thing (as a simplification obviously). So how about I just create a huge list that has all of the points that are part of any of the lines, then sort that list, and look for patterns in this new list that look like `[x, x, y | tail ]` and count those.

To my slight surprise this was indeed 2x faster for the input data.

EDIT2: of course approach 1 is faster if the data grows much larger