 # Codewars - Twice Linear - Optimisation issue

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 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
``````

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

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!