Codewars - Twice Linear - Optimisation issue

Learning Questions & Discussions Coding Challenges
1

Hi there,

i am new to elixir, so i solved some stuff on codewars.

i ran into this kata: https://www.codewars.com/kata/twice-linear/

I tried to solve storing the u in a list, and learned linked list are not a good idea to solve that thing :wink:
I could not get it working with tuples. I will push the solutions to github asap.

My fastest solution is based on a map cache, that is still to slow, i.e.

dotest(1000000, 54381286) # ~ 6-7 seconds
dotest(100000, 2911582) # ~ 300 ms

I get a timeout after 30 of 100 random tests…

def dbl_linear(n) do
    {_, un} = Enum.reduce(
      1..n,
      {%{0 => 1}, 1},
      fn (i, {u, un}) ->

        x = Integer.floor_div((un - 1), 2)
        y = Integer.floor_div((un - 1), 3)

        xx = binary(x, u, 0, i - 1)
        yy = binary(y, u, 0, i - 1)

        un = 1 + Kernel.min(2 * xx, 3 * yy)
        u = Map.put(
          u,
          i,
          un
        )

        {
          u,
          un
        }

      end
    )
    un
  end

  defp binary(0, _, _, _), do: 1
  defp binary(_, cache, lb, ub) when ub - lb <= 1 do
    %{^ub => un} = cache
    un
  end
  defp binary(un, cache, lb, ub) do
    mid = lb + (
      (ub - lb)
      >>> 1)

    %{^mid => mid_v} = cache

    if mid_v > un do
      binary(un, cache, lb, mid)
    else
      binary(un, cache, mid, ub)
    end
  end
2

Really?

Spoiler 
defmodule Twice do
  defp next_y(x),
    do: 2 * x + 1

  defp next_z(x),
    do: 3 * x + 1

  defp next(store, [], value, fun) do
    [x | source] = :lists.reverse([value | store])
    {[], source, fun.(x)}
  end

  defp next(store, [x | source], value, fun) do
    {[value | store], source, fun.(x)}
  end

  defp helper(0, value, _, _, _, _, _, _) do
    value
  end

  defp helper(index, _, y_store, y_source, y, z_store, z_source, z) when y < z do
    {ny_store, ny_source, ny} = next(y_store, y_source, y, &next_y/1)
    helper(index - 1, y, ny_store, ny_source, ny, [y | z_store], z_source, z)
  end

  defp helper(index, _, y_store, y_source, y, z_store, z_source, z) when y >= z do
    {nz_store, nz_source, nz} = next(z_store, z_source, z, &next_z/1)

    {ny_store, ny_source, ny} =
      if y > z do
        {[z | y_store], y_source, y}
      else
        next(y_store, y_source, y, &next_y/1)
      end

    helper(index - 1, z, ny_store, ny_source, ny, nz_store, nz_source, nz)
  end

  def dbl_linear(index),
    do: helper(index, 1, [], [], 3, [], [], 4)
end

IO.inspect(:timer.tc(Twice, :dbl_linear, [100_000]))   # {19802, 2911582}
IO.inspect(:timer.tc(Twice, :dbl_linear, [1_000_000])) # {212929, 54381286}

Refined version:

Spoiler 
defmodule Twice do
  defp next_y(x),
    do: 2 * x + 1

  defp next_z(x),
    do: 3 * x + 1

  defp next(store, [], fun) do
    [x | seq] = :lists.reverse(store)
    {[], seq, fun.(x), x}
  end

  defp next(store, [x | seq], fun) do
    {store, seq, fun.(x), x}
  end

  # 1.) The current value goes into y_store
  #     regardless of where it came from (y or z)
  # 2.) A value coming out of y_seq goes into z_store

  defp helper(0, value, _, _, _, _, _, _) do
    value
  end

  defp helper(index, _, y_store, y_seq, y, z_store, z_seq, z) when y < z do
    {ny_store, ny_seq, ny, x} = next([y | y_store], y_seq, &next_y/1)
    helper(index - 1, y, ny_store, ny_seq, ny, [x | z_store], z_seq, z)
  end

  defp helper(index, _, y_store, y_seq, y, z_store, z_seq, z) when y >= z do
    yy_store = [z | y_store]

    {ny_store, ny_seq, ny, zz_store} =
      if y > z do
        {yy_store, y_seq, y, z_store}
      else
        # skip over duplicate value
        {n_store, n_seq, n, x} = next(yy_store, y_seq, &next_y/1)
        {n_store, n_seq, n, [x | z_store]}
      end

    {nz_store, nz_seq, nz, _} = next(zz_store, z_seq, &next_z/1)

    helper(index - 1, z, ny_store, ny_seq, ny, nz_store, nz_seq, nz)
  end

  def dbl_linear(index),
    do: helper(index, 1, [], [], 3, [], [], 4)
end

IO.inspect(:timer.tc(Twice, :dbl_linear, [100_000]))   # {16420, 2911582}
IO.inspect(:timer.tc(Twice, :dbl_linear, [1_000_000])) # {185478, 54381286}
3 Likes
3

Using 2 lists instead of 2 index variables does the trick. I will refactor my solution according to that.

Thanks for your help, Peer! Much appreciated!