Advent of Code 2020 - Day 3

Part 1: Basic modulo wrap

Part 2: In the Functional style:

part_2 =
  Enum.reduce([1, 3, 5, 7], 1, &(&2 * travel(input, &1)))
  |> (fn x -> x * travel2(input) end).() 

where ‘travel’ traverses the map with slope -1 / n, and ‘travel2’ uses slope -2.

Full solution @ Github

https://gitlab.com/NobbZ/aoc_ex/-/blob/master/lib/y2020/d03.ex

Better late than never!

There’s plenty of overlap in my solution, but didn’t see the exact one, so figured I’d share. (Brand new to Elixir, Advent of code has been a great way to practice.)

1. Assume input is an enumerable of strings (e.g. file stream)
2. Calculates the width (assumes all rows are uniform)
3. Stream every down’th row
4. Stream an index, which represents the number of times you’ve moved right (i.e. each row visited)
5. Count the number of times the String at rem(right * idx, with) is #

Idea was to stream the file and only aggregate at the count step, as to not use intermediate lists

defmodule Advent.Y2020.D03 do
  @spec part_one(rows :: Enumerable.t(String.t())) :: integer
  def part_one(rows) do
    count_trees(rows, 3, 1)
  end

  @spec part_two(rows :: Enumerable.t(String.t()), strategies :: Enumerable.t({integer, integer})) ::
          integer
  def part_two(rows, strategies) do
    Enum.reduce(strategies, 1, fn {right, down}, product ->
      product * count_trees(rows, right, down)
    end)
  end

  defp count_trees(rows, right, down) do
    # Assumes all rows are uniform in width
    width = rows |> Enum.at(0) |> String.length()

    rows
    |> Stream.take_every(down)
    |> Stream.with_index()
    |> Enum.count(fn {row, idx} ->
      "#" == String.at(row, rem(right * idx, width))
    end)
  end
end

And here my Erlang solution, part 2 with skipping down gave me some troubles first too

-module(day3).
-export([run/0]).

run()->
    Lines = load_file("day3input.txt"),
    {part1(Lines), part2(Lines)}.

% Part 1 %
part1(Lines)->
    count_trees(Lines, 0, 0).

count_trees([H | T], Pos, Count)->
    case string:slice(H, Pos, 1) of
        "." -> count_trees(T, (Pos + 3) rem length(H), Count);
        "#" -> count_trees(T, (Pos + 3) rem length(H), Count + 1)
    end;
count_trees([], _, Count) ->
    Count.

% Part 2 %
part2(Lines)->
    C1 = count_trees(Lines, 0, 0, 1, 1),
    C2 = count_trees(Lines, 0, 0, 3, 1),
    C3 = count_trees(Lines, 0, 0, 5, 1),
    C4 = count_trees(Lines, 0, 0, 7, 1),
    C5 = count_trees(Lines, 0, 0, 1, 2),
    {C1, C2, C3, C4, C5, C1*C2*C3*C4*C5}.

count_trees([H | T], Pos, Count, Right, Down)->
    case string:slice(H, Pos, 1) of
        "." -> count_trees(nthtail(Down-1, T), (Pos + Right) rem length(H), Count, Right, Down);
        "#" -> count_trees(nthtail(Down-1, T), (Pos + Right) rem length(H), Count + 1, Right, Down)
    end;
count_trees([], _, Count,_,_) ->
    Count.

nthtail(_, [])->[];
nthtail(N, L)-> lists:nthtail(N, L).

% Helper %
load_file(Filename)->
    {ok, Binary} = file:read_file(Filename),
    StringContent = unicode:characters_to_list(Binary),
    [ Line || Line <- string:tokens(StringContent, "\n")].

Even it was fun, I’m not shure whether I’ll progress, as my time is quite limited atm.

Wow, some really interesting solutions here. Mine is a fairly basic recursive approach that relies on processing the input into a list of strings. It is brittle because if the strings are of unequal length it would fail. I also hardcoded the string length in the rem/2 call, which I could have avoided by introducing another module attribute like @line_length or something.

defmodule Day3 do
  @input File.stream!("lib/input") |> Enum.into([])
  @finish Kernel.length(@input)

  def progress(_, y, _, _, trees) when y >= @finish do
    trees
  end

  def progress(x, y, run, rise, trees) do
    case @input
         |> Enum.at(y)
         |> String.at(rem(x, 31)) do
      "#" -> progress(x + run, y + rise, run, rise, trees + 1)
      _ -> progress(x + run, y + rise, run, rise, trees)
    end
  end
end

(Day3.progress(0, 0, 1, 1, 0) * Day3.progress(0, 0, 3, 1, 0) * Day3.progress(0, 0, 5, 1, 0) *
   Day3.progress(0, 0, 7, 1, 0) * Day3.progress(0, 0, 1, 2, 0))
|> IO.inspect()

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

Yay! I learned it in Day 1

I used it to create a stream that lazily yields k-element combinations of a given list, just like Ruby’s Array#combination without a block.

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

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

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

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

https://github.com/al2o3cr/advent-of-code-2020/blob/main/day3/part1.exs

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.