Advent of Code 2021 - Day 5

bjorng · December 5, 2021, 5:35am

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

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

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

bjorng · December 5, 2021, 5:36am

Here is my solution:

github.com

bjorng/advent-of-code-2021/blob/6ca39045ed4cef5c81d45a76f1590d0098e6b5c4/day05/lib/day05.ex

defmodule Day05 do
  def part1(input) do
    parse(input)
    |> Enum.reduce(%{}, fn {first, second}, acc ->
      line_part1(first, second)
      |> Enum.reduce(acc, fn coordinate, acc ->
        Map.update(acc, coordinate, 1, &(&1 + 1))
      end)
    end)
    |> Enum.count(fn {_, value} -> value >= 2 end)
  end

  def part2(input) do
    parse(input)
    |> Enum.reduce(%{}, fn {first, second}, acc ->
      line_part2(first, second)
      |> Enum.reduce(acc, fn coordinate, acc ->
        Map.update(acc, coordinate, 1, &(&1 + 1))
      end)
    end)

This file has been truncated. show original

princemaple · December 5, 2021, 5:42am

github.com

princemaple/aoc/blob/main/2021/day5.exs

# Title: Day5

# ── Untitled ──

data =
  "input"
  |> IO.getn(1_000_000)
  |> String.split(["\n", "\r\n"], trim: true)
  |> Enum.map(fn line ->
    line
    |> String.split(" -> ")
    |> Enum.map(&(&1 |> String.split(",") |> Enum.map(fn n -> String.to_integer(n) end)))
  end)

defmodule P1 do
  def calc(data) do
    data
    |> Enum.filter(fn [[x1, y1], [x2, y2]] -> x1 == x2 or y1 == y2 end)
    |> Enum.map(fn [[x1, y1], [x2, y2]] ->
      if x1 == x2 do

This file has been truncated. show original

stevensonmt · December 5, 2021, 5:51am

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.

github.com

stevensonmt/advent_of_code/blob/ace53043d4d95ffdb60f0d47c396f87a6f5562a2/2021/day5/lib/day5.ex

defmodule Day5 do
  @moduledoc false

  # input file processed to list of list of tuple pairs
  @input "input.txt"
         |> File.read!()
         |> String.trim()
         |> String.split("\n")
         |> Enum.map(&String.split(&1, "->"))
         |> Enum.map(
           &Enum.map(&1, fn pair ->
             [n, m] = String.split(String.trim(pair), ",")
             {String.to_integer(n), String.to_integer(m)}
           end)
         )

  @spec count_overlaps(bool) :: %{{integer, integer} => integer}
  def count_overlaps(part1?) do
    @input
    |> Enum.reduce(%{}, fn [{x1, y1}, {x2, y2}], acc ->

This file has been truncated. show original

APB9785 · December 5, 2021, 5:53am

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

epilgrim · December 5, 2021, 6:42am

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

epilgrim · December 5, 2021, 6:44am

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

code-shoily · December 5, 2021, 6:51am

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

defmodule AdventOfCode.Y2021.Day05 do
  use AdventOfCode.Helpers.InputReader, year: 2021, day: 5

  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

weego · December 5, 2021, 7:43am

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

Malian · December 5, 2021, 8:03am

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....
``

ruslandoga · December 5, 2021, 8:09am

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...

factoryd · December 5, 2021, 8:12am

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.

github.com

trbngr/advent_of_code/blob/main/lib/2021/5.ex

defmodule Y2021.D5 do
  use AOC, day: 5, year: 2021

  def p1 do
    p1(input_stream() |> Enum.to_list())
  end

  def p1(input) do
    run_input(input)
  end

  def p2 do
    p2(input_stream() |> Enum.to_list())
  end

  def p2(input) do
    run_input(input, :inc_diagonals)
  end

  defp run_input(input, opt \\ nil) do

This file has been truncated. show original

qhwa · December 5, 2021, 8:12am

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

wasi0013 · December 5, 2021, 9:12am

My naive solution: y2021/day_05.ex

zevv · December 5, 2021, 11:28am

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

Klohto · December 5, 2021, 11:48am

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!

egze · December 5, 2021, 1:24pm

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

camilleryr · December 5, 2021, 1:47pm

@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

bengtson · December 5, 2021, 1:53pm

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

ramuuns · December 5, 2021, 2:46pm

Another highly functional tail-recursive approach from me:

github.com

ramuuns/aoc/blob/master/2021/day-05.exs

defmodule Day5 do

  def run(mode) do
    start = :erlang.system_time(:microsecond)

    data = read_input(mode)

    data |> part1() |> IO.puts()
    data |> part2() |> IO.puts()
    finish = :erlang.system_time(:microsecond)
    "took #{finish - start}μs" |> IO.puts()
  end

  def read_input(:test) 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

This file has been truncated. show original

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