A series of solutions to the snake_case problem posed by @jackc's at ACR 2016.

snake_case.ex

# From the ACR 2016 coding challenge.

defmodule SnakeCase do

  @doc """
  Brute force, single process.
  """
  def single do
    range = 0..round(:math.pow(2, 20))
    count = Enum.count(range, fn x -> check_one_bits(x) == 10 end)

    IO.puts "Total paths for brute force, single process: #{count}"
  end

  @doc """
  Brute force, multi-process.
  """
  def multi do
    Agent.start_link(fn -> 0 end, name: __MODULE__)
    ranges = Enum.chunk(0..round(:math.pow(2, 20)), 262144)
    tasks = Enum.map ranges, fn range ->
      Task.async(fn -> subrange(range) end)
    end
    for task <- tasks, do: Task.await(task)

    Agent.get(__MODULE__, fn count -> IO.puts "Total paths for brute force, multi-process: #{count}" end)
  end

  defp subrange(range) do
    count = Enum.count(range, fn x -> check_one_bits(x) == 10 end)
    Agent.update(__MODULE__, fn(n) -> n + count end)
  end

  # Last run on multi: .69s
  # Last run on single: .83s
  # Thanks to @utkarshkukreti on the Elixir Slack channel!
  defp check_one_bits(x) do
    count_one_bits(:binary.encode_unsigned(x), 0)
  end

  def count_one_bits(<<>>, acc), do: acc
  def count_one_bits(<<n::1, rest :: bitstring>>, acc), do: count_one_bits(rest, acc + n)

  # Other implementations converted to Elixir:
  # https://rossta.net/blog/ancient-city-snake-case.html

  @doc """
  Iterative solution.
  """
  def count_paths do
    IO.puts "Total paths for count_paths: #{_count_paths(10, 10)}"
  end

  defp _count_paths(0, _), do: 1
  defp _count_paths(_, 0), do: 1
  defp _count_paths(h, w), do: _count_paths(h-1, w) + _count_paths(h, w-1)

  @doc """
  Factorial paths.
  """
  def factorial_paths do
    IO.puts "Total paths for factorial_paths: #{_factorial_paths(10, 10)}"
  end

  defp _factorial_paths(h, w) do
    Enum.reduce((h+w)..(h+1), fn(x, acc) -> x * acc end) / Enum.reduce(w..1, fn(x, acc) -> x * acc end)
    |> round
  end

  @doc """
  Pascal Triangle solution.
  """
  def pascal do
    IO.puts "Total paths for pascal: #{_pascal_paths(10, 10)}"
  end

  defp _pascal_paths(h, w) do
    # Build the first row:
    row = for _ <- 1..(w+1), do: 1

    # Process ALL the other rows:
    row
    |> _pascal_row(h)
    |> List.last
  end

  defp _pascal_row(row, h), do: _pascal_row(row, h, 0)
  defp _pascal_row(row, h, num) when num < h, do: Enum.reduce(row, [], &_pascal_acc/2) |> _pascal_row(h, num+1)
  defp _pascal_row(row, h, num), do: row

  defp _pascal_acc(x, []), do: [x]
  defp _pascal_acc(x, acc), do: acc ++ [x + List.last(acc)]

end

IO.inspect :timer.tc fn -> SnakeCase.single end
IO.inspect :timer.tc fn -> SnakeCase.pascal end
IO.inspect :timer.tc fn -> SnakeCase.multi end
IO.inspect :timer.tc fn -> SnakeCase.factorial_paths end
IO.inspect :timer.tc fn -> SnakeCase.count_paths end

Very slow. Multiprocess version is as fast as the single process Ruby version on mine, but it might be the string processing that's the issue.

Pinged the Elixir Slack channel and several guys came back with responses. Thanks so much, gents!

• utkarshkukreti
• micmus
• Martin Svalin