From 39d4afd6d12ba6dd043763f1e65dde5fd8b99497 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sat, 27 Aug 2016 16:17:24 +0200 Subject: Solve triplets --- go/pythagorean-triplet/pythagorean_triplet.go | 42 +++++++++++++++++++++++++-- 1 file changed, 40 insertions(+), 2 deletions(-) (limited to 'go/pythagorean-triplet/pythagorean_triplet.go') diff --git a/go/pythagorean-triplet/pythagorean_triplet.go b/go/pythagorean-triplet/pythagorean_triplet.go index 8a6a9cd..967ffe3 100644 --- a/go/pythagorean-triplet/pythagorean_triplet.go +++ b/go/pythagorean-triplet/pythagorean_triplet.go @@ -2,5 +2,43 @@ package pythagorean type Triplet [3]int -func Range(min, max int) []Triplet { return nil } -func Sum(p int) []Triplet { return nil } +func (t Triplet) Sum() int { + return t[0] + t[1] + t[2] +} + +// Range calculates Triptets in range [min:max] in N(O^2) +// stolen on http://stackoverflow.com/questions/575117/generating-unique-ordered-pythagorean-triplets +func Range(min, max int) []Triplet { + var t []Triplet + for a := min; a <= max; a++ { + aa := a * a + b := a + 1 + c := b + 1 + for c <= max { + cc := aa + b*b + for c*c < cc { + c++ + } + if c*c == cc && c <= max { + t = append(t, Triplet{a, b, c}) + } + b++ + } + } + return t +} + +func Sum(p int) []Triplet { + var t []Triplet + // the tricky part + // since we have 3 summands we expect + // the upper bound to be no more then p/2 + // the lower bound is more vague and is set on p/10 + // needs proof and more testing + for _, v := range Range(p/10, p/2) { + if v.Sum() == p { + t = append(t, v) + } + } + return t +} -- cgit v1.2.3