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

GenericJam
Edit: 2026 May 15 - This post is archived. Mob is alive!! Main docs: mob v0.7.11 — Documentation A bit of explanation for the slightly c...
New
garrison
Hobbes is a low-level distributed database for the Elixir programming language. Hobbes provides a simple, safe, and scalable storage lay...
New
budgie
A little off-topic, but I feel like people here have a good head on their shoulders. I used to be quite good at making software. Was luc...
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
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
mcass19
ExRatatui lets you cook up rich terminal UIs in Elixir, powered by Rust’s ratatui via Rustler NIFs. Build interactive terminal applicatio...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews