about summary refs log tree commit diff
path: root/users/wpcarro/assessments/semiprimes
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2021-12-13T22·51+0300
committerVincent Ambo <mail@tazj.in>2021-12-13T23·15+0300
commit019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch)
tree76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/assessments/semiprimes
parent464bbcb15c09813172c79820bcf526bb10cf4208 (diff)
parent6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff)
subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226
git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789
Diffstat (limited to 'users/wpcarro/assessments/semiprimes')
-rw-r--r--users/wpcarro/assessments/semiprimes/.gitignore1
-rw-r--r--users/wpcarro/assessments/semiprimes/README.md44
-rw-r--r--users/wpcarro/assessments/semiprimes/default.nix1
-rw-r--r--users/wpcarro/assessments/semiprimes/server/.formatter.exs4
-rw-r--r--users/wpcarro/assessments/semiprimes/server/.gitignore24
-rw-r--r--users/wpcarro/assessments/semiprimes/server/lib/app.ex8
-rw-r--r--users/wpcarro/assessments/semiprimes/server/lib/cache.ex41
-rw-r--r--users/wpcarro/assessments/semiprimes/server/lib/extras.ex22
-rw-r--r--users/wpcarro/assessments/semiprimes/server/lib/math.ex26
-rw-r--r--users/wpcarro/assessments/semiprimes/server/lib/router.ex86
-rw-r--r--users/wpcarro/assessments/semiprimes/server/lib/server.ex33
-rw-r--r--users/wpcarro/assessments/semiprimes/server/lib/sup.ex23
-rw-r--r--users/wpcarro/assessments/semiprimes/server/mix.exs32
-rw-r--r--users/wpcarro/assessments/semiprimes/server/mix.lock14
-rw-r--r--users/wpcarro/assessments/semiprimes/server/test/extras_test.exs18
-rw-r--r--users/wpcarro/assessments/semiprimes/server/test/math_test.exs30
-rw-r--r--users/wpcarro/assessments/semiprimes/server/test/server_test.exs34
-rw-r--r--users/wpcarro/assessments/semiprimes/server/test/test_helper.exs1
18 files changed, 442 insertions, 0 deletions
diff --git a/users/wpcarro/assessments/semiprimes/.gitignore b/users/wpcarro/assessments/semiprimes/.gitignore
new file mode 100644
index 000000000000..b5b25bd64822
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/.gitignore
@@ -0,0 +1 @@
+default.nix
diff --git a/users/wpcarro/assessments/semiprimes/README.md b/users/wpcarro/assessments/semiprimes/README.md
new file mode 100644
index 000000000000..7d5a15482ab3
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/README.md
@@ -0,0 +1,44 @@
+# Semiprimes Service
+
+## Introduction
+
+A **composite** is a number containing at least two prime factors. For example:
+
+```
+15 = 3 × 5
+9 = 3 × 3
+12 = 2 × 2 × 3
+```
+
+There are ten composites below thirty containing precisely two, not necessarily
+distinct, prime factors: `4, 6, 9, 10, 14, 15, 21, 22, 25, 26`. Let’s call such
+numbers *Semiprimes*.
+
+## Task
+
+- Write a module which provides a function to tell whether a given number, `N`,
+  is a semiprime. `N` will be less than 100,000
+- Please implement an API (RESTful or GraphQL) to factor a given number into two
+  prime numbers if it’s a semiprime, otherwise, return an error message.
+
+## Stretch Goals
+
+- Handle the invalid inputs.
+- Support batch requests: i.e. users could provide 100 numbers, and the API
+  return the answer for all.
+- Considering this module will be used by a long running service, could you
+  optimize it to give answers faster?
+
+## Usage
+
+To run the application you'll need to have `elixir` installed. Assuming `elixir`
+is already installed, consult the following steps to start the application:
+
+```shell
+$ cd server
+$ mix deps.get
+$ iex -S mix
+```
+
+Now open a web browser and visit `http://localhost:8080`!
+
diff --git a/users/wpcarro/assessments/semiprimes/default.nix b/users/wpcarro/assessments/semiprimes/default.nix
new file mode 100644
index 000000000000..29452eac250c
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/default.nix
@@ -0,0 +1 @@
+# stubbed
diff --git a/users/wpcarro/assessments/semiprimes/server/.formatter.exs b/users/wpcarro/assessments/semiprimes/server/.formatter.exs
new file mode 100644
index 000000000000..d2cda26eddc9
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/.formatter.exs
@@ -0,0 +1,4 @@
+# Used by "mix format"
+[
+  inputs: ["{mix,.formatter}.exs", "{config,lib,test}/**/*.{ex,exs}"]
+]
diff --git a/users/wpcarro/assessments/semiprimes/server/.gitignore b/users/wpcarro/assessments/semiprimes/server/.gitignore
new file mode 100644
index 000000000000..db9704a85ff6
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/.gitignore
@@ -0,0 +1,24 @@
+# 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 third-party dependencies like ExDoc output generated docs.
+/doc/
+
+# Ignore .fetch files in case you like to edit your project deps locally.
+/.fetch
+
+# 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
+
+# Ignore package tarball (built via "mix hex.build").
+server-*.tar
+
diff --git a/users/wpcarro/assessments/semiprimes/server/lib/app.ex b/users/wpcarro/assessments/semiprimes/server/lib/app.ex
new file mode 100644
index 000000000000..7a6fa5ea248d
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/lib/app.ex
@@ -0,0 +1,8 @@
+defmodule App do
+  use Application
+
+  @impl true
+  def start(_type, _args) do
+    Sup.start_link()
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/lib/cache.ex b/users/wpcarro/assessments/semiprimes/server/lib/cache.ex
new file mode 100644
index 000000000000..cd064cc1ae4b
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/lib/cache.ex
@@ -0,0 +1,41 @@
+defmodule Cache do
+  @moduledoc """
+  Cache is an in-memory key-value store.
+  """
+  use Agent
+
+  @doc """
+  Inititalize the key-value store.
+  """
+  def start_link(_) do
+    Agent.start_link(fn -> %{} end, name: __MODULE__)
+  end
+
+  @doc """
+  Attempt to return the value stored at `key`
+  """
+  def get(key) do
+    Agent.get(__MODULE__, &Map.get(&1, key))
+  end
+
+  @doc """
+  Write the `value` under the `key`. Last writer wins.
+  """
+  def put(key, value) do
+    Agent.update(__MODULE__, &Map.put(&1, key, value))
+  end
+
+  @doc """
+  List the contents of the cache. Useful for debugging purposes.
+  """
+  def list() do
+    Agent.get(__MODULE__, & &1)
+  end
+
+  @doc """
+  Invalidate the entire cache.
+  """
+  def clear() do
+    Agent.update(__MODULE__, fn _ -> %{} end)
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/lib/extras.ex b/users/wpcarro/assessments/semiprimes/server/lib/extras.ex
new file mode 100644
index 000000000000..f0c2ea4b9e21
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/lib/extras.ex
@@ -0,0 +1,22 @@
+defmodule Extras do
+  @moduledoc """
+  Hosts utility functions intended to supplement the standard library.
+  """
+
+  @doc """
+  Return an ascending range starting at `a` and ending at `b` (exclusive).
+
+  ## Examples
+
+      iex> Extras.range(2, 5)
+      [2, 3, 4]
+
+  """
+  def range(a, b) do
+    if b <= a do
+      []
+    else
+      [a] ++ range(a + 1, b)
+    end
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/lib/math.ex b/users/wpcarro/assessments/semiprimes/server/lib/math.ex
new file mode 100644
index 000000000000..8a33be475389
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/lib/math.ex
@@ -0,0 +1,26 @@
+defmodule Math do
+  @moduledoc """
+  Math utilities.
+  """
+  alias Extras
+
+  @doc """
+  Returns the prime factors for `n`.
+
+  ## Examples
+
+      iex> Math.factor(15)
+      [3, 5]
+
+  """
+  def factor(1), do: []
+
+  def factor(n) do
+    Extras.range(2, n - 1)
+    |> Enum.find(&(rem(n, &1) == 0))
+    |> case do
+      nil -> [n]
+      x -> [x | factor(div(n, x))]
+    end
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/lib/router.ex b/users/wpcarro/assessments/semiprimes/server/lib/router.ex
new file mode 100644
index 000000000000..cb55520920de
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/lib/router.ex
@@ -0,0 +1,86 @@
+defmodule Router do
+  use Plug.Router
+  use Plug.Debugger
+  require Logger
+
+  plug(Plug.Logger, log: :debug)
+  plug(Plug.Parsers, parsers: [:urlencoded])
+  plug(:match)
+  plug(:dispatch)
+
+  @usage """
+  Usage: Try querying some of the following endpoints...
+    GET /
+    GET /help
+    GET /semiprime?number=<integer>
+    GET /semiprimes?numbers=<comma-separated-integers>
+  """
+
+  get "/" do
+    send_resp(conn, 200, "Welcome to Semiprimes Service!\n\n#{@usage}")
+  end
+
+  get "/help" do
+    send_resp(conn, 200, @usage)
+  end
+
+  get "/semiprime" do
+    case conn |> Map.get(:query_params) |> Map.get("number") do
+      nil ->
+        send_resp(conn, 400, "You must pass an integer as a query parameter. #{@usage}")
+
+      val ->
+        case Integer.parse(val) do
+          {n, ""} ->
+            send_resp(conn, 200, semiprime_response(n))
+
+          _ ->
+            send_resp(conn, 400, "We could not parse the number you provided.\n\n#{@usage}")
+        end
+    end
+  end
+
+  get "/semiprimes" do
+    case conn |> Map.get(:query_params) |> Map.get("numbers") do
+      nil ->
+        send_resp(
+          conn,
+          400,
+          "You must pass a comma-separated list of integers as a query parameter.\n\n#{@usage}"
+        )
+
+      xs ->
+        response =
+          xs
+          |> String.split(",")
+          |> Stream.map(&Integer.parse/1)
+          |> Stream.filter(fn
+            {n, ""} -> true
+            _ -> false
+          end)
+          |> Stream.map(fn {n, ""} -> semiprime_response(n) end)
+          |> Enum.join("\n")
+
+        send_resp(conn, 200, response)
+    end
+  end
+
+  match _ do
+    send_resp(conn, 404, "Not found.")
+  end
+
+  ################################################################################
+  # Utils
+  ################################################################################
+
+  defp semiprime_response(n) do
+    case Server.semiprime(n) do
+      nil ->
+        "#{n} is not a semiprime. Try another number!"
+
+      {hit_or_miss, factors} ->
+        response = "#{n} is a semiprime! Its factors are #{Enum.join(factors, " and ")}."
+        "Cache #{Atom.to_string(hit_or_miss)} - #{response}"
+    end
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/lib/server.ex b/users/wpcarro/assessments/semiprimes/server/lib/server.ex
new file mode 100644
index 000000000000..7ab5e905b5a0
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/lib/server.ex
@@ -0,0 +1,33 @@
+defmodule Server do
+  @moduledoc """
+  Documentation for `Server`.
+  """
+
+  @doc """
+  If `n` contains exactly two prime factors, return those prime factors;
+  otherwise, return nothing.
+  """
+  def semiprime(n) do
+    case Cache.get(n) do
+      nil ->
+        case do_semiprime(n) do
+          nil ->
+            nil
+
+          res ->
+            Cache.put(n, res)
+            {:miss, res}
+        end
+
+      hit ->
+        {:hit, hit}
+    end
+  end
+
+  defp do_semiprime(n) do
+    case Math.factor(n) do
+      [_, _] = res -> res
+      _ -> nil
+    end
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/lib/sup.ex b/users/wpcarro/assessments/semiprimes/server/lib/sup.ex
new file mode 100644
index 000000000000..13a6ab374ff6
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/lib/sup.ex
@@ -0,0 +1,23 @@
+defmodule Sup do
+  @moduledoc """
+  Top-level supervisor for our OTP application. For now, this supervisor starts
+  and monitors our cache.
+  """
+
+  use Supervisor
+  alias Plug.Adapters.Cowboy
+
+  def start_link(opts \\ []) do
+    Supervisor.start_link(__MODULE__, :ok, opts)
+  end
+
+  @impl true
+  def init(:ok) do
+    children = [
+      Cache,
+      Cowboy.child_spec(scheme: :http, plug: Router, options: [port: 8000])
+    ]
+
+    Supervisor.init(children, strategy: :one_for_one)
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/mix.exs b/users/wpcarro/assessments/semiprimes/server/mix.exs
new file mode 100644
index 000000000000..9062f927e7a8
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/mix.exs
@@ -0,0 +1,32 @@
+defmodule Server.MixProject do
+  use Mix.Project
+
+  def project do
+    [
+      app: :server,
+      version: "0.1.0",
+      elixir: "~> 1.10",
+      start_permanent: Mix.env() == :prod,
+      deps: deps()
+    ]
+  end
+
+  # Run "mix help compile.app" to learn about applications.
+  def application do
+    [
+      extra_applications: [:logger],
+      mod: {App, []}
+    ]
+  end
+
+  # Run "mix help deps" to learn about dependencies.
+  defp deps do
+    [
+      {:cortex, "~> 0.1", only: [:dev, :test]},
+      {:plug_cowboy, "~> 2.4.1"},
+      {:cowboy, "~> 2.8.0"},
+      {:plug, "~> 1.11.0"},
+      {:poison, "~> 4.0.1"}
+    ]
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/mix.lock b/users/wpcarro/assessments/semiprimes/server/mix.lock
new file mode 100644
index 000000000000..2ae7efbb3fb6
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/mix.lock
@@ -0,0 +1,14 @@
+%{
+  "cortex": {:hex, :cortex, "0.6.0", "8094830fae266eb0ae34d1a58983c0c49484341f5044fb4dfb81746647bd2993", [:mix], [{:file_system, "~> 0.2", [hex: :file_system, repo: "hexpm", optional: false]}], "hexpm", "d0ef5a2b1269626149118684dc4ea77dbfbc67017f4b4065b71dcefa26cfcc49"},
+  "cowboy": {:hex, :cowboy, "2.8.0", "f3dc62e35797ecd9ac1b50db74611193c29815401e53bac9a5c0577bd7bc667d", [:rebar3], [{:cowlib, "~> 2.9.1", [hex: :cowlib, repo: "hexpm", optional: false]}, {:ranch, "~> 1.7.1", [hex: :ranch, repo: "hexpm", optional: false]}], "hexpm", "4643e4fba74ac96d4d152c75803de6fad0b3fa5df354c71afdd6cbeeb15fac8a"},
+  "cowboy_telemetry": {:hex, :cowboy_telemetry, "0.3.1", "ebd1a1d7aff97f27c66654e78ece187abdc646992714164380d8a041eda16754", [:rebar3], [{:cowboy, "~> 2.7", [hex: :cowboy, repo: "hexpm", optional: false]}, {:telemetry, "~> 0.4", [hex: :telemetry, repo: "hexpm", optional: false]}], "hexpm", "3a6efd3366130eab84ca372cbd4a7d3c3a97bdfcfb4911233b035d117063f0af"},
+  "cowlib": {:hex, :cowlib, "2.9.1", "61a6c7c50cf07fdd24b2f45b89500bb93b6686579b069a89f88cb211e1125c78", [:rebar3], [], "hexpm", "e4175dc240a70d996156160891e1c62238ede1729e45740bdd38064dad476170"},
+  "file_system": {:hex, :file_system, "0.2.10", "fb082005a9cd1711c05b5248710f8826b02d7d1784e7c3451f9c1231d4fc162d", [:mix], [], "hexpm", "41195edbfb562a593726eda3b3e8b103a309b733ad25f3d642ba49696bf715dc"},
+  "mime": {:hex, :mime, "1.5.0", "203ef35ef3389aae6d361918bf3f952fa17a09e8e43b5aa592b93eba05d0fb8d", [:mix], [], "hexpm", "55a94c0f552249fc1a3dd9cd2d3ab9de9d3c89b559c2bd01121f824834f24746"},
+  "plug": {:hex, :plug, "1.11.0", "f17217525597628298998bc3baed9f8ea1fa3f1160aa9871aee6df47a6e4d38e", [:mix], [{:mime, "~> 1.0", [hex: :mime, repo: "hexpm", optional: false]}, {:plug_crypto, "~> 1.1.1 or ~> 1.2", [hex: :plug_crypto, repo: "hexpm", optional: false]}, {:telemetry, "~> 0.4", [hex: :telemetry, repo: "hexpm", optional: false]}], "hexpm", "2d9c633f0499f9dc5c2fd069161af4e2e7756890b81adcbb2ceaa074e8308876"},
+  "plug_cowboy": {:hex, :plug_cowboy, "2.4.1", "779ba386c0915027f22e14a48919a9545714f849505fa15af2631a0d298abf0f", [:mix], [{:cowboy, "~> 2.7", [hex: :cowboy, repo: "hexpm", optional: false]}, {:cowboy_telemetry, "~> 0.3", [hex: :cowboy_telemetry, repo: "hexpm", optional: false]}, {:plug, "~> 1.7", [hex: :plug, repo: "hexpm", optional: false]}, {:telemetry, "~> 0.4", [hex: :telemetry, repo: "hexpm", optional: false]}], "hexpm", "d72113b6dff7b37a7d9b2a5b68892808e3a9a752f2bf7e503240945385b70507"},
+  "plug_crypto": {:hex, :plug_crypto, "1.2.0", "1cb20793aa63a6c619dd18bb33d7a3aa94818e5fd39ad357051a67f26dfa2df6", [:mix], [], "hexpm", "a48b538ae8bf381ffac344520755f3007cc10bd8e90b240af98ea29b69683fc2"},
+  "poison": {:hex, :poison, "4.0.1", "bcb755a16fac91cad79bfe9fc3585bb07b9331e50cfe3420a24bcc2d735709ae", [:mix], [], "hexpm", "ba8836feea4b394bb718a161fc59a288fe0109b5006d6bdf97b6badfcf6f0f25"},
+  "ranch": {:hex, :ranch, "1.7.1", "6b1fab51b49196860b733a49c07604465a47bdb78aa10c1c16a3d199f7f8c881", [:rebar3], [], "hexpm", "451d8527787df716d99dc36162fca05934915db0b6141bbdac2ea8d3c7afc7d7"},
+  "telemetry": {:hex, :telemetry, "0.4.2", "2808c992455e08d6177322f14d3bdb6b625fbcfd233a73505870d8738a2f4599", [:rebar3], [], "hexpm", "2d1419bd9dda6a206d7b5852179511722e2b18812310d304620c7bd92a13fcef"},
+}
diff --git a/users/wpcarro/assessments/semiprimes/server/test/extras_test.exs b/users/wpcarro/assessments/semiprimes/server/test/extras_test.exs
new file mode 100644
index 000000000000..67d0b8875cae
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/test/extras_test.exs
@@ -0,0 +1,18 @@
+defmodule ExtrasTest do
+  use ExUnit.Case
+  doctest Extras
+
+  describe "range" do
+    test "returns an empty list for descending sequences" do
+      assert Extras.range(0, -2) == []
+    end
+
+    test "returns an empty list for non-ascending sequences" do
+      assert Extras.range(8, 8) == []
+    end
+
+    test "returns an exclusive range" do
+      assert Extras.range(3, 6) == [3, 4, 5]
+    end
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/test/math_test.exs b/users/wpcarro/assessments/semiprimes/server/test/math_test.exs
new file mode 100644
index 000000000000..c7186c824a8c
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/test/math_test.exs
@@ -0,0 +1,30 @@
+defmodule MathTest do
+  use ExUnit.Case
+  doctest Math
+
+  describe "factor" do
+    test "returns the prime factors for an input" do
+      [
+        {15, [3, 5]},
+        {12, [2, 2, 3]},
+        {9, [3, 3]},
+        {21, [3, 7]}
+      ]
+      |> Enum.map(fn {input, expected} ->
+        assert Math.factor(input) == expected
+      end)
+    end
+
+    test "handles large numbers" do
+      assert Math.factor(104_023) == [17, 29, 211]
+    end
+
+    test "returns an empty list for 1" do
+      assert Math.factor(1) == []
+    end
+
+    test "returns the prime number itself when the input is prime" do
+      assert Math.factor(7) == [7]
+    end
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/test/server_test.exs b/users/wpcarro/assessments/semiprimes/server/test/server_test.exs
new file mode 100644
index 000000000000..08d559734b5a
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/test/server_test.exs
@@ -0,0 +1,34 @@
+defmodule ServerTest do
+  use ExUnit.Case
+  doctest Server
+
+  describe "semiprime" do
+    test "returns the factors when the number is semiprime" do
+      Cache.clear()
+      # Semiprimes below 30
+      [
+        {4, [2, 2]},
+        {6, [2, 3]},
+        {9, [3, 3]},
+        {10, [2, 5]},
+        {14, [2, 7]},
+        {15, [3, 5]},
+        {21, [3, 7]},
+        {22, [2, 11]},
+        {25, [5, 5]},
+        {26, [2, 13]}
+      ]
+      |> Enum.each(fn {input, expected} ->
+        assert Server.semiprime(input) == {:miss, expected}
+      end)
+    end
+
+    test "returns nothing when the number is a composite number" do
+      # Composite numbers below 30
+      [1, 2, 3, 5, 7, 8, 11, 12, 13, 16, 17, 18, 19, 20, 23, 24, 27, 28, 29]
+      |> Enum.each(fn x ->
+        assert Server.semiprime(x) == nil
+      end)
+    end
+  end
+end
diff --git a/users/wpcarro/assessments/semiprimes/server/test/test_helper.exs b/users/wpcarro/assessments/semiprimes/server/test/test_helper.exs
new file mode 100644
index 000000000000..869559e709ea
--- /dev/null
+++ b/users/wpcarro/assessments/semiprimes/server/test/test_helper.exs
@@ -0,0 +1 @@
+ExUnit.start()