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

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

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

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

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

1 Like

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

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!

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