Advent of Code - Day 14

Learning Questions & Discussions Coding Challenges
,
1

Note: This topic is to talk about Day 14 of the Advent of Code.

For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.

2

Here is my solution. It takes about 50s to finish. The long running time is because I’m dynamically building an array of about 20M elements. I resorted to using ets for this, as that works faster than using plain maps. I also briefly experimented with :array and procdict, but had no luck.

Assuming there’s no smarter algorithm, and that I didn’t make some terrible mistake, it seems that this is an example of where Erlang/Elixir are simply not performant enough. If we were able to preallocate a mutable array, this would finish much faster.

2 Likes
3

Here is my solution.

It takes less than 3 seconds on my computer.

I store the recipes in a binary, appending to it using the binary syntax. An append operation to a binary is specially optimized by Erlang’s runtime system, in that it will allocate extra storage when appending so that the next append operation will be cheaper. See the section about constructing binaries in the Efficiency Guide.

6 Likes
4

Oh, using binaries is a wonderful idea! I have to adapt my code.

1 Like
5

Here’s my Day 14 solution:

I wrote pretty code then uglied it up for speed. I’m unsatisfied with where I ended up, needing about five minutes for part two.

Watch the process here (for 14 days):

2 Likes
6

Anyone here would know why my code is so slow? It times out after 60 seconds.

defmodule Day14 do
  def next_ten(iterations) when is_integer(iterations) do
    {tuple, _index1, _index2} = Day14.generate(iterations + 10)

    tuple
    |> Tuple.to_list
    |> Enum.slice(iterations, 10)
    |> Enum.join("")
  end

  def generate(iterations) when is_integer(iterations) do
    Day14.generate({{3,7}, 0, 1, iterations})
  end

  def generate({tuple, index1, index2, 0}) do
    {tuple, index1, index2}
  end

  def generate({tuple, index1, index2, iterations}) do
    elven_digits = Integer.digits(elem(tuple, index1) + elem(tuple, index2))

    tuple = Day14.append_digits_to_tuple(tuple, elven_digits)

    Day14.generate({
      tuple,
      Day14.calculate_new_index(tuple, index1),
      Day14.calculate_new_index(tuple, index2),
      iterations - 1
    })
  end

  def append_digits_to_tuple(accumulator, [head | tail]) do
    append_digits_to_tuple(Tuple.append(accumulator, head), tail)
  end

  def append_digits_to_tuple(accumulator, []) do
    accumulator
  end

  def calculate_new_index(tuple, index) do
    len       = tuple_size(tuple)
    new_index = elem(tuple, index) + 1 + index

    if new_index >= len do
      rem(new_index, len)
    else
      new_index
    end
  end
end

Day14.next_ten(880751)

Any help would be greatly appreciated! Cheers!

7

My guess is that you’re spending a lot of time in Tuple.append. Day 14 requires a lot of iterations, and modifying a tuple involves copying it, which is then going to be pretty slow.

It’s somewhat tricky to get a sensible running time here. I’ve tried with various approaches, and the best I was able to come up was around 50 seconds using ETS. However, there is a way to reduce the running time to a few seconds, as explained by @bjorng earlier in this thread.

1 Like