 # tylus's solution

## to Pythagorean Triplet in the Lua Track

Published at May 06 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
``````

and such that,

``````a < b < c
``````

For example,

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

Given an input integer N, find all Pythagorean triplets for which `a + b + c = N`.

For example, with N = 1000, there is exactly one Pythagorean triplet for which `a + b + c = 1000`: `{200, 375, 425}`.

## 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 < b 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)``````
``````return function(n)
local a
local b
local c
local triplets = {}

for a = 1, n / 2 - 1 do       -- VI
for b = a, n - a do         -- II
c = n - a - b             -- III
if a * a + b * b == c * c then
table.insert(triplets, {a, b, c})
end
end
end
return triplets
end

-- Reducing the size of the problem:
-- I        a * a + b * b = c * c
-- II       a + b + c = n
-- => III   c = n - a - b
-- IV       A triple where a == b is accepted, but
--          a + b is the same as b + a, so we can
-- => V     skip all triplets where a < b.
--          Also, from I follows c > b + a, so we can use:
-- => VI    a = 1 .. n / 2 - 1

-- Fun fact: using x * x the test takes 11s, with x^2 it takes 17s for me.``````