My solution of part 2 is to calculate result backwards, memoization is then “for free”:

data = "data/10" |> File.read!() |> String.split() |> Enum.map(&String.to_integer/1)
data = Enum.sort([0 | data], :desc)

IO.puts(
  Enum.reduce(data, %{(hd(data) + 3) => 1}, fn i, memo ->
    Map.put(memo, i, Enum.sum(Enum.map(1..3, &Map.get(memo, i + &1, 0))))
  end)[0]
)

You can actually calculate the answer for part two without the need to run any of the possibilities - if you sort your input and reduce that to a list of the number of consecutive digits in a row ( [1, 2, 3, 6] -> [3, 1] or [1, 3, 4, 5, 8] -> [1, 3, 1]), you can then calculate the number of permutations each ‘block’ will cause and then just find the product of the list

Yes, morge challenging today, so I didn’t come up with a solution for part 2 yet
Couldn’t decide how I wanna solve it, and then run out of time before work…
Anyway: Heres my part 1 in Erlang:

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

run()->
    Input = lists:sort(load_file("day10input.txt")),
    {part1(Input), part2(Input)}.

part1(Input)-> 
    calc([0|Input], 0, 0).

calc([X,Y|T], Ones, Threes) ->
    case Y - X of
        1 -> calc([Y|T], Ones + 1, Threes);
        3 -> calc([Y|T], Ones, Threes + 1);
        _ -> calc([Y|T], Ones, Threes)
    end;
calc(_, Ones, Threes)->
    Ones * (Threes + 1).

part2(_)-> notimplemented.

load_file(Filename)->
    {ok, Binary} = file:read_file(Filename),
    StringContent = unicode:characters_to_list(Binary),
    [ element(1, string:to_integer(Line)) || Line <- string:split(StringContent, "\n", all)].

Thanks for mentioning that. I had part 2 working for the examples, but the full input timed out. Then I rebuild it using :digraph and recursively weighted the edges from the end. This again timed out for the puzzle input but not the examples. Turns out keeping track of the already checked vertexes made the test resolve in 0.1 sec.

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