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

mudasobwa
I am happy to introduce the very α version of the new programming language compiled to BEAM. Welcome Cure. It has literally three kille...
New
marciok
Hi there! We created Gust: A task orchestrator inspired by Airflow. For those who have never heard about Aiflow, it’s a Python-based wor...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Dmk
Xamal is a deployment tool for Elixir apps that deploys native releases to bare metal servers over SSH. It’s a port of GitHub - basecamp/...
New
netoum
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
New
webofbits
With AI doing more of the implementation work, I’ve been wondering how much coding I should deliberately keep doing myself. My main conc...
#ai
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews