Avatar of glennj

glennj's solution

to Pythagorean Triplet in the Lua Track

Published at Mar 11 2019 · 0 comments
Instructions
Test suite
Solution

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 the tests

To run the tests, run the command busted from within the exercise directory.

Further information

For more detailed information about the Lua track, including how to get help if you're having trouble, please visit the exercism.io Lua language 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_spec.lua

local triplets_with_sum = require('pythagorean-triplet')

describe('pythagorean-triplet', function()
  local function sort(triplets)
    table.sort(triplets, function(a, b) return a[1] < b[1] end)
    return triplets
  end

  describe('triplets_with_sum', function()
    it('finds triplets whose sum is 12', function()
      assert.same(
        { { 3, 4, 5 } },
        sort(triplets_with_sum(12))
      )
    end)

    it('finds triplets whose sum is 108', function()
      assert.same(
        { { 27, 36, 45 } },
        sort(triplets_with_sum(108))
      )
    end)

    it('finds triplets whose sum is 1000', function()
      assert.same(
        { { 200, 375, 425 } },
        sort(triplets_with_sum(1000))
      )
    end)

    it('finds no triplets whose sum is 1001', function()
      assert.same({}, triplets_with_sum(1001))
    end)

    it('finds triplets whose sum is 90', function()
      assert.same(
        {
          { 9, 40, 41 },
          { 15, 36, 39 },
        },
        sort(triplets_with_sum(90))
      )
    end)

    it('finds triplets whose sum is 840', function()
      assert.same(
        {
          { 40, 399, 401 },
          { 56, 390, 394 },
          { 105, 360, 375 },
          { 120, 350, 370 },
          { 140, 336, 364 },
          { 168, 315, 357 },
          { 210, 280, 350 },
          { 240, 252, 348 },
        },
        sort(triplets_with_sum(840))
      )
    end)

    it('finds triplets whose sum is a large number (30000)', function()
      assert.same(
        {
          { 1200, 14375, 14425 },
          { 1875, 14000, 14125 },
          { 5000, 12000, 13000 },
          { 6000, 11250, 12750 },
          { 7500, 10000, 12500 },
        },
        sort(triplets_with_sum(30000))
      )
    end)
  end)
end)
local is_pythagorean = function (a, b, c)
    return (a^2 + b^2) == c^2
end

local triplets_with_sum = function (sum)
    local triplets = {}
    -- smallest pyth.triangle is {3,4,5} so we can use
    -- that in the loop endpoints to save a bit of time.
    for c = sum - 7, 5, -1 do
        for b = c-1, 4, -1 do
            local a = math.sqrt(c^2 - b^2)
            if  math.tointeger(a) 
                and a < b 
                and a+b+c == sum 
                and is_pythagorean(a, b, c)
            then
                table.insert(triplets, {math.tointeger(a), b, c})
            end
        end
    end
    return triplets
end

return triplets_with_sum

Community comments

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

glennj's Reflection

A brute force solution. On my underpowered VM, the test suite took 184 seconds to complete.