Avatar of davearonson

davearonson's solution

to Pythagorean Triplet in the Elixir Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

A Pythagorean triplet is a set of three natural numbers, {a, b, c}, for which,

a**2 + b**2 = c**2

For example,

3**2 + 4**2 = 9 + 16 = 25 = 5**2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product a * b * c.

Running tests

Execute the tests with:

$ elixir pythagorean_triplet_test.exs

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

For more detailed information about the Elixir track, please see the help page.

Source

Problem 9 at Project Euler http://projecteuler.net/problem=9

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

pythagorean_triplet_test.exs

if !System.get_env("EXERCISM_TEST_EXAMPLES") do
  Code.load_file("pythagorean_triplet.exs", __DIR__)
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule PythagoreanTripletTest do
  use ExUnit.Case

  # @tag :pending
  test "sum" do
    triplet = [3, 4, 5]
    assert Triplet.sum(triplet) == 12
  end

  @tag :pending
  test "product" do
    triplet = [3, 4, 5]
    assert Triplet.product(triplet) == 60
  end

  @tag :pending
  test "pythagorean" do
    triplet = [3, 4, 5]
    assert Triplet.pythagorean?(triplet)
  end

  @tag :pending
  test "not pythagorean" do
    triplet = [5, 6, 7]
    refute Triplet.pythagorean?(triplet)
  end

  @tag :pending
  test "triplets up to 10" do
    triplets = Triplet.generate(1, 10)
    assert Enum.map(triplets, &Triplet.product/1) == [60, 480]
  end

  @tag :pending
  test "triplets from 11 up to 20" do
    triplets = Triplet.generate(11, 20)
    assert Enum.map(triplets, &Triplet.product/1) == [3840]
  end

  @tag :pending
  test "triplets where sum is 180 and max factor is 100" do
    triplets = Triplet.generate(1, 100, 180)
    assert Enum.map(triplets, &Triplet.product/1) == [118_080, 168_480, 202_500]
  end
end
defmodule Triplet do

  @doc """
  Calculates sum of a given triplet of integers.
  """
  @spec sum([non_neg_integer]) :: non_neg_integer
  def sum(triplet) do
    triplet |> Enum.reduce(&+/2)
  end

  @doc """
  Calculates product of a given triplet of integers.
  """
  @spec product([non_neg_integer]) :: non_neg_integer
  def product(triplet) do
    triplet |> Enum.reduce(&*/2)
  end

  @doc """
  Determines if a given triplet is pythagorean. That is, do the squares of a and b add up to the square of c?
  """
  @spec pythagorean?([non_neg_integer]) :: boolean
  def pythagorean?([a, b, c]) do
    a * a + b * b == c * c
  end

  @doc """
  Generates a list of pythagorean triplets from a given min (or 1 if no min) to a given max.
  """
  @spec generate(non_neg_integer, non_neg_integer) :: [list(non_neg_integer)]
  def generate(min, max) do
    low = trunc(:math.sqrt(min * 2))  # inverse of min*min/2
    # not sure if this is high enough really; the math makes my head hurt
    high = max * :math.sqrt(2)
    # feed it only even current-numbers
    do_generate(min, low + rem(low, 2), max, high, [])
  end

  defp do_generate(_  , cur, _  , high, acc) when cur > high, do: acc
  defp do_generate(min, cur, max, high, acc) do
    # yeah, ++ is kinda slow... but to avoid this
    # we'd have to pass the acc all the way down,
    # and tack on each dicksonized factoring, yuck!
    do_generate(min, cur+2, max, high, acc ++ dicksons_triples(min, cur, max))
  end

  # triples generated with dickson's method; see
  # https://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples#Dickson.27s_method
  # method chosen because "All Pythagorean triples may be found by this method."
  # whereas other methods only find certain families.
  defp dicksons_triples(min, cur, max) do
    factorings(trunc(cur * cur / 2))
    |> Enum.map(&(dicksonize(cur, &1)))
    |> Enum.filter(&(all_within?(&1, min, max)))
  end

  defp factorings(num) do
    # this gives us no dups, and in sorted order
    (1..trunc(:math.sqrt(num)))
    |> Enum.filter(&(rem(num, &1)) == 0)
    |> Enum.map(&([&1, trunc(num/&1)]))
  end

  defp dicksonize(r, [s,t]) do
    [r+s, r+t, r+s+t]
  end

  defp all_within?([n|rest], min, max) do
    n <= max && n >= min && all_within?(rest, min, max)
  end
  defp all_within?([], _, _), do: true

  @doc """
  Generates a list of pythagorean triplets from a given min to a given max, whose values add up to a given sum.
  """
  @spec generate(non_neg_integer, non_neg_integer, non_neg_integer) :: [list(non_neg_integer)]
  def generate(min, max, sum) do
    generate(min, max) |> Enum.filter(&(Enum.sum(&1) == sum))
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?