sprengerjo

sprengerjo

Hi there,

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

i ran into this kata: Twice linear | Codewars

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

Showing Posts 1 to 2

peerreynders

peerreynders

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}
sprengerjo

sprengerjo OP

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!

— All posts loaded —

Where Next? Top

Trending in Challenges Top

Other Trending Topics Top

dominicletz
Hey there, I haven’t seen a list of useful Elixir specific skills for the popular AI tools yet so I’m starting one here with my first. ...
New
raa-ziq
Hi everyone :waving_hand: I wanted to share something I’ve been building — NowBlind, a random chat app designed to help people discover ...
New
mudasobwa
I fully migrated to my own harness from Anthropic/Gemini and I think it’s time to share it. Welcome DSH, the DeepSeek Harness, fully writ...
New
KristerV
Hey. Is there anyone here who creates agents in their apps? Not talking about using agents, but creating them. I’m finding it pretty diff...
New
OndrejValenta
(I just needed to vent somewhere and LinkedIn is full of hope, or hype, I’m not sure which exactly) AI dream has many faces, but general...
New
kip
Localize is the next generation localisation library for Elixir. Think of it as ex_cldr version 3.0. The first version will be released ...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews