From cee981b9b40676534e8ff6b690ac7f4b2c2064c8 Mon Sep 17 00:00:00 2001
From: David Kerkeslager <kerkeslager@gmail.com>
Date: Fri, 16 Dec 2016 23:19:43 -0500
Subject: [PATCH] Added a prime generation library written in Elixir

---
 elixir_primes/.gitignore           | 17 +++++++
 elixir_primes/README.md            | 23 +++++++++
 elixir_primes/config/config.exs    | 30 +++++++++++
 elixir_primes/lib/primes.ex        | 58 +++++++++++++++++++++
 elixir_primes/mix.exs              | 32 ++++++++++++
 elixir_primes/test/primes_test.exs | 82 ++++++++++++++++++++++++++++++
 elixir_primes/test/test_helper.exs |  1 +
 7 files changed, 243 insertions(+)
 create mode 100644 elixir_primes/.gitignore
 create mode 100644 elixir_primes/README.md
 create mode 100644 elixir_primes/config/config.exs
 create mode 100644 elixir_primes/lib/primes.ex
 create mode 100644 elixir_primes/mix.exs
 create mode 100644 elixir_primes/test/primes_test.exs
 create mode 100644 elixir_primes/test/test_helper.exs

diff --git a/elixir_primes/.gitignore b/elixir_primes/.gitignore
new file mode 100644
index 0000000..6e1db0f
--- /dev/null
+++ b/elixir_primes/.gitignore
@@ -0,0 +1,17 @@
+# The directory Mix will write compiled artifacts to.
+/_build
+
+# If you run "mix test --cover", coverage assets end up here.
+/cover
+
+# The directory Mix downloads your dependencies sources to.
+/deps
+
+# Where 3rd-party dependencies like ExDoc output generated docs.
+/doc
+
+# If the VM crashes, it generates a dump, let's ignore it too.
+erl_crash.dump
+
+# Also ignore archive artifacts (built via "mix archive.build").
+*.ez
diff --git a/elixir_primes/README.md b/elixir_primes/README.md
new file mode 100644
index 0000000..be7392f
--- /dev/null
+++ b/elixir_primes/README.md
@@ -0,0 +1,23 @@
+# Primes
+
+**TODO: Add description**
+
+## Installation
+
+If [available in Hex](https://hex.pm/docs/publish), the package can be installed as:
+
+  1. Add `primes` to your list of dependencies in `mix.exs`:
+
+    ```elixir
+    def deps do
+      [{:primes, "~> 0.1.0"}]
+    end
+    ```
+
+  2. Ensure `primes` is started before your application:
+
+    ```elixir
+    def application do
+      [applications: [:primes]]
+    end
+    ```
diff --git a/elixir_primes/config/config.exs b/elixir_primes/config/config.exs
new file mode 100644
index 0000000..ebb0ff7
--- /dev/null
+++ b/elixir_primes/config/config.exs
@@ -0,0 +1,30 @@
+# This file is responsible for configuring your application
+# and its dependencies with the aid of the Mix.Config module.
+use Mix.Config
+
+# This configuration is loaded before any dependency and is restricted
+# to this project. If another project depends on this project, this
+# file won't be loaded nor affect the parent project. For this reason,
+# if you want to provide default values for your application for
+# 3rd-party users, it should be done in your "mix.exs" file.
+
+# You can configure for your application as:
+#
+#     config :primes, key: :value
+#
+# And access this configuration in your application as:
+#
+#     Application.get_env(:primes, :key)
+#
+# Or configure a 3rd-party app:
+#
+#     config :logger, level: :info
+#
+
+# It is also possible to import configuration files, relative to this
+# directory. For example, you can emulate configuration per environment
+# by uncommenting the line below and defining dev.exs, test.exs and such.
+# Configuration from the imported file will override the ones defined
+# here (which is why it is important to import them last).
+#
+#     import_config "#{Mix.env}.exs"
diff --git a/elixir_primes/lib/primes.ex b/elixir_primes/lib/primes.ex
new file mode 100644
index 0000000..cab7035
--- /dev/null
+++ b/elixir_primes/lib/primes.ex
@@ -0,0 +1,58 @@
+defmodule SieveFilter do
+  def less_than?({a, _}, {b, _}) when a < b do true end
+  def less_than?({a, b}, {a, c}) when b < c do true end
+  def less_than?(_, _) do false end
+
+  def get_next({counter, prime}) do {counter + prime, prime} end
+end
+
+defmodule Sieve do
+  def run_item_through_sieve([{item, prime}|remaining_sieve], item) do
+    {matched, unmatched} = run_item_through_sieve(remaining_sieve, item)
+    {[{item, prime}|matched], unmatched}
+  end
+  def run_item_through_sieve(sieve, _) do {[], sieve} end
+
+  def merge(xs, []) do xs end
+  def merge([], ys) do ys end
+  def merge(xs, ys) do
+    [x|remaining_xs] = xs
+    [y|remaining_ys] = ys
+
+    if SieveFilter.less_than?(x, y) do
+      [x|merge(remaining_xs, ys)]
+    else
+      [y|merge(xs, remaining_ys)]
+    end
+  end
+
+  def get_next(sieve) do
+    Enum.map(sieve, &(SieveFilter.get_next(&1)))
+  end
+end
+
+defmodule Primes do
+  def transform(sieve, previous_item) do
+    item = previous_item + 1
+    {matched, unmatched} = Sieve.run_item_through_sieve(sieve, item)
+
+    case matched do
+      [] -> {Sieve.merge([{item * 2, item}], sieve), item}
+      _ -> transform(Sieve.merge(Sieve.get_next(matched), unmatched), item)
+    end
+  end
+
+  def generate(initial_state, initial_item, get_next) do
+    Stream.map(
+      Stream.iterate(
+        {initial_state, initial_item},
+        fn({previous_state, previous_item}) -> get_next.(previous_state, previous_item) end
+      ),
+      fn({_, item}) -> item end
+    )
+  end
+
+  def primes() do
+    Stream.drop(generate([], 1, &(transform(&1, &2))), 1)
+  end
+end
diff --git a/elixir_primes/mix.exs b/elixir_primes/mix.exs
new file mode 100644
index 0000000..0beb4d0
--- /dev/null
+++ b/elixir_primes/mix.exs
@@ -0,0 +1,32 @@
+defmodule Primes.Mixfile do
+  use Mix.Project
+
+  def project do
+    [app: :primes,
+     version: "0.1.0",
+     elixir: "~> 1.3",
+     build_embedded: Mix.env == :prod,
+     start_permanent: Mix.env == :prod,
+     deps: deps()]
+  end
+
+  # Configuration for the OTP application
+  #
+  # Type "mix help compile.app" for more information
+  def application do
+    [applications: [:logger]]
+  end
+
+  # Dependencies can be Hex packages:
+  #
+  #   {:mydep, "~> 0.3.0"}
+  #
+  # Or git/path repositories:
+  #
+  #   {:mydep, git: "https://github.com/elixir-lang/mydep.git", tag: "0.1.0"}
+  #
+  # Type "mix help deps" for more examples and options
+  defp deps do
+    []
+  end
+end
diff --git a/elixir_primes/test/primes_test.exs b/elixir_primes/test/primes_test.exs
new file mode 100644
index 0000000..b95c508
--- /dev/null
+++ b/elixir_primes/test/primes_test.exs
@@ -0,0 +1,82 @@
+defmodule SieveFilterTest do
+  use ExUnit.Case
+  doctest SieveFilter
+
+  test "less_than? compares the counter first" do
+    assert SieveFilter.less_than?({10, 5}, {12, 3})
+    assert not SieveFilter.less_than?({12, 3}, {10, 5})
+  end
+
+  test "less_than? compares the prime second" do
+    assert SieveFilter.less_than?({10, 2}, {10, 5})
+    assert not SieveFilter.less_than?({10, 5}, {10, 2})
+  end
+
+  test "get_next adds the prime to the counter" do
+    assert SieveFilter.get_next({21, 7}) == {28, 7}
+  end
+end
+
+defmodule SieveTest do
+  use ExUnit.Case
+  doctest SieveFilter
+
+  test "run_item_through_sieve returns empty list and all filters for prime" do
+    sieve = [{8, 2}, {9, 3}, {10, 5}]
+    {matched, unmatched} = Sieve.run_item_through_sieve(sieve, 7)
+
+    assert matched == []
+    assert unmatched == sieve
+  end
+
+  test "run_item_through_sieve returns matched and unmatched filters for composite" do
+    sieve = [{10, 2}, {10, 5}, {12, 3}, {14, 7}]
+    {matched, unmatched} = Sieve.run_item_through_sieve(sieve, 10)
+
+    assert matched == [{10, 2}, {10, 5}]
+    assert unmatched == [{12, 3}, {14, 7}]
+  end
+
+  test "merge merges sieves" do
+    sieve_a = [{12, 2}, {15, 5}]
+    sieve_b = [{12, 3}, {14, 7}]
+    merged = Sieve.merge(sieve_a, sieve_b)
+
+    assert merged == [{12, 2}, {12, 3}, {14, 7}, {15, 5}]
+  end
+
+  test "get_next updates filters" do
+    sieve = [{42, 2}, {42, 3}, {42, 7}]
+
+    assert Sieve.get_next(sieve) == [{44, 2}, {45, 3}, {49, 7}]
+  end
+end
+
+defmodule PrimesTest do
+  use ExUnit.Case
+  doctest Primes
+
+  test "transform updates sieve and next item" do
+    sieve = [{8, 2}, {9, 3}, {10, 5}, {14, 7}]
+    item = 7
+
+    {next_sieve, next_item} = Primes.transform(sieve, item)
+
+    assert next_sieve == [{12, 2}, {12, 3}, {14, 7}, {15, 5}, {22, 11}]
+    assert next_item == 11
+  end
+
+  test "generate iterates updating state and yielding items" do
+    fibonacci = Primes.generate(0, 1, fn(prev, curr) -> {curr, prev + curr} end)
+
+    assert Enum.take(fibonacci, 10) == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
+  end
+
+  test "primes generates primes" do
+    assert Enum.take(Primes.primes(), 10) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+  end
+
+  test "primes is fast" do
+    assert 1 == Enum.sum(Stream.take_while(Primes.primes(), &(&1 < 2_000_000)))
+  end
+end
diff --git a/elixir_primes/test/test_helper.exs b/elixir_primes/test/test_helper.exs
new file mode 100644
index 0000000..869559e
--- /dev/null
+++ b/elixir_primes/test/test_helper.exs
@@ -0,0 +1 @@
+ExUnit.start()
-- 
2.20.1