Suggestions

[hissssst]

Hi, great library, clean approach! However, I have a couple of suggestions

1. Introduce memoization for find_all_solutions. While thinking about other problems, I've found that if next_state function can return the same result for two different inputs (that is if next_state is not bijection), a lot of solutions will be recomputed. It would be nice if this solver could store the %{state => next_state(state)} kind of map to avoid recomputations

2. find_all_solutions function is craving for parallelization.

3. Minor, it would be nice if you could remove examples from lib, so that they won't be loaded into runtime of the program which uses this dependency

[adonig]

Hi @hissssst!

Thank you for the feedback. I've pushed a feat/memoization branch. Maybe you can try whether this approach speeds things up for you? I tried with the Hamiltonian Path and a relatively large graph, but it just made things slower:

$ iex -S mix
Generated backfish app
Erlang/OTP 26 [erts-14.2.5] [source] [64-bit] [smp:20:20] [ds:20:20:10] [async-threads:1] [jit:ns]

Interactive Elixir (1.16.2) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> graph = Backfish.LargeGraph.generate_graph(25)
%{
  1 => [3, 4, 0],
  2 => [4, 5, 1],
  3 => [5, 6, 2],
  4 => [6, 7, 3],
  5 => [7, 8, 4],
  6 => [8, 9, 5],
  7 => [9, 10, 6],
  8 => ~c"\n\v\a",
  9 => ~c"\v\f\b",
  10 => ~c"\f\r\t",
  11 => [13, 14, 10],
  12 => [14, 15, 11],
  13 => [15, 16, 12],
  14 => [16, 17, 13],
  15 => [17, 18, 14],
  16 => [18, 19, 15],
  17 => [19, 20, 16],
  18 => [20, 21, 17],
  19 => [21, 22, 18],
  20 => [22, 23, 19],
  21 => [23, 24, 20],
  22 => [24, 25, 21],
  23 => [25, 1, 22],
  24 => [1, 2, 23],
  25 => [2, 3, 24]
}
iex(2)> {time, _} = :timer.tc(fn -> Backfish.find_all_solutions(Backfish.Examples.HamiltonianPath, [args: [graph: graph, start_node: 1], memoize: false]) end); IO.puts("Time: #{time / 1_000_000} seconds"); :ok
Time: 5.016542 seconds
:ok
iex(3)> {time, _} = :timer.tc(fn -> Backfish.find_all_solutions(Backfish.Examples.HamiltonianPath, [args: [graph: graph, start_node: 1], memoize: true]) end); IO.puts("Time: #{time / 1_000_000} seconds"); :ok
Time: 10.311358 seconds
:ok