summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-27 16:17:24 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-27 16:17:24 +0200
commit39d4afd6d12ba6dd043763f1e65dde5fd8b99497 (patch)
tree3e9c5ed5217425f0bfed3562373a897e09ae4948
parentc872165aeb1bd3eadda5b354809bb3eab833f887 (diff)
Solve triplets
-rw-r--r--go/pythagorean-triplet/pythagorean_triplet.go42
1 files changed, 40 insertions, 2 deletions
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
+}