Advent of Code 2020 - Day 10

That is pretty elegant, kind of wish I’d thought of going backwards. I don’t think the direction is relevant for whether memoization is free or not though. We both just store the accumulated values in a map, and I go forwards. Anyway, the other solutions are faster :sunglasses:. And @camilleryr’s is faster than @Damirados’ Reddit “optimal” solution, although I don’t pretend to understand it! Very clever.

Name                 ips        average  deviation         median         99th %
camilleryr      105.88 K        9.44 μs    ±75.62%           9 μs          30 μs
reddit           32.58 K       30.69 μs    ±34.14%          28 μs          81 μs
adam             25.09 K       39.86 μs    ±24.96%          37 μs          91 μs
hallski          19.81 K       50.49 μs    ±27.17%          48 μs         126 μs
bossek           19.45 K       51.42 μs    ±27.12%          48 μs         121 μs
kwando           16.00 K       62.51 μs    ±30.45%          58 μs         158 μs

Comparison:
camilleryr      105.88 K
reddit           32.58 K - 3.25x slower +21.25 μs
adam             25.09 K - 4.22x slower +30.41 μs
hallski          19.81 K - 5.35x slower +41.05 μs
bossek           19.45 K - 5.44x slower +41.98 μs
kwando           16.00 K - 6.62x slower +53.07 μs

It would be interesting to see how the Agent answers do, but I’ve looked at this problem for long enough already!

2 Likes

Thanks for your notes! That ascii illustration made it really click what you were doing and also (sort of) how the tribonacci sequence comes into play.

1 Like

part1 and part2

O(n log n)

defmodule Advent.Day10 do

  def start(part \\ :part1, file \\ "/tmp/input.txt"), do:
    File.read!(file)
    |> String.split()
    |> Enum.map(&String.to_integer/1)
    |> Enum.sort()
    |> execute(part)

  defp execute(lst, :part1), do:
    lst
    |> Enum.reduce({0, %{3 => 1}}, fn o, {last, m} -> {o, Map.update(m, o - last, 1, fn x -> x + 1 end)} end)
    |> elem(1)
    |> print()

  defp execute(lst, :part2) do
    (lst ++ [List.last(lst) + 3])
    |> Enum.reduce(%{0 => 1}, fn o, acc -> acc |> Map.put(o, 0) |> update(o, -3) |> update(o, -2) |> update(o, -1) end)
    |> print(List.last(lst) + 3)
  end

  def update(acc, v, delta) do
    case acc[v + delta] do
      nil -> acc
      delta_v -> Map.update(acc, v, 1, fn x -> x + delta_v end)
    end
  end

  defp print(m), do: m[1] * m[3] # part1
  defp print(m, n), do: m[n] # part2

end

little improvement
dont need to add +1 element in list

...
  defp execute(lst, :part2) do
    lst
    |> Enum.reduce(%{0 => 1}, fn o, acc -> acc |> Map.put(o, 0) |> update(o, -3) |> update(o, -2) |> update(o, -1) end)
    |> print(List.last(lst))
  end
...

Using map for accumulated values is not necessary because I need at most 3 last added values:


It should be a bit faster… but also a bit uglier.

I didn’t figure out how to do part2, so here’s my part1:

defmodule Day10.Adapter do
  defstruct jolts: 0, input: nil

  def new(jolts) do
    %__MODULE__{jolts: jolts, input: (jolts - 3)..(jolts - 1)}
  end
end

defmodule Day10 do
  alias Day10.Adapter

  def readinput(fname \\ "10.input.txt") do
    File.read!(fname)
    |> String.split("\n", trim: true)
    |> Enum.map(&String.to_integer/1)
    |> Enum.sort()
    |> Enum.map(&Adapter.new/1)
  end

  def part1(adapters \\ readinput()) do
    chain(adapters)
  end

  # threecount starts with 1 to account for the last adapter <-> your device
  def chain(adapters, jolts \\ 0, onecount \\ 0, threecount \\ 1)

  def chain([], _jolts, onecount, threecount), do: onecount * threecount
    # do: {onecount, threecount, onecount * threecount}

  def chain(adapters, jolts, onecount, threecount) do
    # since the list is sorted, the adapter we want is always the first one
    {adapter, rest} = List.pop_at(adapters, 0)
    onecount = if adapter.jolts - jolts == 1, do: onecount + 1, else: onecount
    threecount = if adapter.jolts - jolts == 3, do: threecount + 1, else: threecount
    chain(rest, adapter.jolts, onecount, threecount)
  end
end

For part one, Enum.frequencies/1 is very useful.

1 Like

Yes! I saw that in someone else’s solution.

hey, sorry for answering quite late.
Here is the whole file, probably I missed something when pasting the code. You just need to do this to execute the task2:

iex -S mix
input = "lib/day10/input.txt"
Aoc2020.Day10.task2(input)

Let me know the results :hugs:

Sorry I deleted my benchmark file so I can’t compare them together, but here’s your result.

Name             ips        average  deviation         median         99th %
jkmrto       19.12 K       52.29 μs    ±22.18%          50 μs         115 μs

Should mention that I edited everyone’s solutions to make sure the file parsing was already done. The input to all the benchmarked solutions was a list of integers.

1 Like

Hello all,

Classify?

Part two looks like the problem “Triple Steps” (8.1 of Cracking The Code Interview), for which we have relation : x(n) = x(n-3) + x(n-2) + x(n-1) for i>3 : we can reach 4 from 1, 2, 3, x is the number of combinations.

Bottom up

This problem has as bottom up solution, that need to store only 3 values, O(n) it time and O(1) in space (it’s not in the book).

  # Number of combinations to reach step n, with moves of 1, 2, 3 steps.
  # Starts from ground (0) and first step is 1.
  def solve(n) do
    # memo holds {x(1), x(2), x(3)} where x is solve, it's the meat.
    memo = {1, 2, 4}
    4..n
    |> Enum.reduce(memo, fn _i, {n3, n2, n1} ->
      {n2, n1, n1 + n2 + n3}
    end)
    |> elem(2)
  end

The difference with the triple steps problem, beside names (step -> adapter, number -> joltage), is set of valid values as input : x(n) = x(n-3) + x(n-2) + x(n-1) if n in input else x(n) = 0 for i>3

We can adapt above solution:

  def combinations(input) do
    set = MapSet.new(input)

    # memo holds {x(1), x(2), x(3)}
    memo =
      case 1..3 |> Enum.map(fn i -> if Enum.member?(set, i), do: i, else: 0 end) do
        [1, 2, 3] -> {1, 2, 4}
        # others are derived
        [0, 2, 3] -> {0, 1, 2}
        [1, 0, 3] -> {1, 0, 2}
        [1, 2, 0] -> {1, 2, 0}
        [1, 0, 0] -> {1, 0, 0}
        [0, 2, 0] -> {0, 1, 0}
        [0, 0, 3] -> {0, 0, 1}
      end

    max = Enum.max(set)

    4..max
    |> Enum.reduce(memo, fn n, {xn3, xn2, xn1} ->
      if Enum.member?(set, n) do
        {xn2, xn1, xn3 + xn2 + xn1}
      else
        {xn2, xn1, 0}
      end
    end)
    |> elem(2)
  end

The meat of change is also in {x(1), x(2), x(3)}.
We have O(n) in time and O(n) in space (the set).

2 Likes

This one was a real bear for me. I think I’m not yet thinking in proper functional terms, when I see some of the short elegant solutions. Here’s mine:

defmodule Day10 do

  @input [
    # original array of numbers given, removed here for brevity
  ] |> Enum.sort

  @full_input @input ++ [List.last(@input) + 3]

  def part1() do
    jumps = count_jumps(@full_input, 0, %{})
    jumps[1] * jumps[3]
  end

  def part2() do
    find_ways_to_each([0|@full_input], %{0 => 1})[List.last(@full_input)]
  end

  defp count_jumps([next|rest], last, acc) do
    diff = next - last
    old = Map.get(acc, diff, 0)
    count_jumps(rest, next, Map.put(acc, diff, old + 1))
  end
  defp count_jumps([], _, acc), do: acc

  defp find_ways_to_each([here|rest], counts) do
    new_counts =
      rest
      |> Enum.take(3)
      |> Enum.filter(&(&1 <= here + 3))
      |> add_to_map(counts[here], counts)
    find_ways_to_each(rest, new_counts)
  end
  defp find_ways_to_each([], counts), do: counts

  defp add_to_map([target|rest], ways_here, counts) do
    add_to_map(rest, ways_here,
               Map.update(counts, target, ways_here, &(&1 + ways_here)))
  end
  defp add_to_map([], _, counts), do: counts
end

Similar approach.

What I did, actually, was to create a new array which contained the differences between numbers where 1-differenced numbers were the most important:
[(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19] turns into [1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3]

Now the times you can remodel two or more contiguous 1’s in the second array is your solution:

1, 1, 1 turns into [2, 1], [1, 2] and [3] (4 different ways)
1, 1 turns into [2] (2 different ways)
Now, 4*2 = 8
It gets tough when you have to remodel five or more contiguous 1’s