diff options
Diffstat (limited to 'users/wpcarro/assessments/semiprimes')
17 files changed, 441 insertions, 0 deletions
diff --git a/users/wpcarro/assessments/semiprimes/.gitignore b/users/wpcarro/assessments/semiprimes/.gitignore new file mode 100644 index 0000000000..b5b25bd648 --- /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 0000000000..7d5a15482a --- /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/server/.formatter.exs b/users/wpcarro/assessments/semiprimes/server/.formatter.exs new file mode 100644 index 0000000000..d2cda26edd --- /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 0000000000..db9704a85f --- /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 0000000000..7a6fa5ea24 --- /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 0000000000..cd064cc1ae --- /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 0000000000..f0c2ea4b9e --- /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 0000000000..8a33be4753 --- /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 0000000000..cb55520920 --- /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 0000000000..7ab5e905b5 --- /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 0000000000..13a6ab374f --- /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 0000000000..9062f927e7 --- /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 0000000000..2ae7efbb3f --- /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 0000000000..67d0b8875c --- /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 0000000000..c7186c824a --- /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 0000000000..08d559734b --- /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 0000000000..869559e709 --- /dev/null +++ b/users/wpcarro/assessments/semiprimes/server/test/test_helper.exs @@ -0,0 +1 @@ +ExUnit.start() |