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.
https://github.com/trbngr/advent_of_code/blob/main/lib/2021/5.ex
factoryd
qhwa
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
1
wasi0013
zevv
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
File.read!("data/05.txt")
|> 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
0
Klohto
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 = Kino.Input.textarea("Please paste your input file:")
```
## Input
```elixir
coordinates =
Kino.Input.read(input)
|> 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
egze
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
camilleryr
@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
import Advent2021
@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
bengtson
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"
|> File.read!()
|> 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
0
ramuuns
Another highly functional tail-recursive approach from me:
https://github.com/ramuuns/aoc/blob/master/2021/day-05.exs
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
0
mruoss
My approach in a nutshell: convert lines to list of points and find points that occur more than once in the (flattened) list of points.
Part 1: ignore diagonals
Part 2: include diagonals
defmodule AOC2021.Day05.Solver do
def solve(stream, :first), do: solve(stream, fn _ -> [] end)
def solve(stream, :second), do: solve(stream, fn [x1, y1, x2, y2] -> Enum.zip(x1..x2, y1..y2) end)
def solve(stream, get_diagonal) do
stream
|> Stream.map(&String.trim/1)
|> Stream.map(&String.split(&1, [" -> ", ","]))
|> Stream.map(fn line -> Enum.map(line, &String.to_integer/1) end)
|> Stream.flat_map(fn
[x, y1, x, y2] -> Enum.map(y1..y2, fn y -> {x, y} end)
[x1, y, x2, y] -> Enum.map(x1..x2, fn x -> {x, y} end)
diagonal_line -> get_diagonal.(diagonal_line)
end)
|> Enum.group_by(&Function.identity/1)
|> Enum.count(fn {_, val} -> Enum.count(val) >= 2 end)
end
end
1