-
Notifications
You must be signed in to change notification settings - Fork 0
/
pythagoreanTriplet.go
146 lines (124 loc) · 3.12 KB
/
pythagoreanTriplet.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
package projecteuler
import "fmt"
// FibonacciBox is a representation of matrix | A B |
//
// | C D |,
//
// where A, B are coprime, and B, A, C, D is a generalized Fibonacci sequence,
// i.e. C = B + A, D = C +A. That implies the box can be generated from 2 numbers.
// Every box singularily represents a Pythagorean triplet:
// At = 2AC, Bt = BD, Ct = BC + AD
type FibonacciBox struct {
A, B, C, D int
}
// PythagoreanTriplet represents triplet for which A^2 + B^2 = C^2
type PythagoreanTriplet struct {
A, B, C int
}
func (triplet PythagoreanTriplet) Length() int {
return triplet.A + triplet.B + triplet.C
}
func (triplet PythagoreanTriplet) Multiply(k int) PythagoreanTriplet {
return PythagoreanTriplet{
A: k * triplet.A,
B: k * triplet.B,
C: k * triplet.C,
}
}
func (triplet PythagoreanTriplet) String() string {
return fmt.Sprintf("(%d, %d, %d)", triplet.A, triplet.B, triplet.C)
}
func (box FibonacciBox) Triplet() PythagoreanTriplet {
return PythagoreanTriplet{
A: 2 * box.A * box.C,
B: box.B * box.D,
C: box.B*box.C + box.A*box.D,
}
}
type FibonacciBoxTernaryTree struct {
Root *FibonacciBox
Child1 *FibonacciBoxTernaryTree
Child2 *FibonacciBoxTernaryTree
Child3 *FibonacciBoxTernaryTree
}
func NewFibonacciBoxTernaryTree(a, b, c, d int) FibonacciBoxTernaryTree {
return FibonacciBoxTernaryTree{
Root: &FibonacciBox{
A: a,
B: b,
C: c,
D: d,
},
}
}
func (tree *FibonacciBoxTernaryTree) Generate(limit int) {
one, two, three := tree.generateRootChildren()
oneTriplet := one.Triplet()
if oneTriplet.Length() <= limit {
childTree := FibonacciBoxTernaryTree{Root: one}
tree.Child1 = &childTree
tree.Child1.Generate(limit)
}
twoTriplet := two.Triplet()
if twoTriplet.Length() <= limit {
childTree := FibonacciBoxTernaryTree{Root: two}
tree.Child2 = &childTree
tree.Child2.Generate(limit)
}
threeTriplet := three.Triplet()
if threeTriplet.Length() <= limit {
childTree := FibonacciBoxTernaryTree{Root: three}
tree.Child3 = &childTree
tree.Child3.Generate(limit)
}
}
func (tree *FibonacciBoxTernaryTree) TripletSlice() []PythagoreanTriplet {
return tree.extractTriplets()
}
func (tree *FibonacciBoxTernaryTree) extractTriplets() []PythagoreanTriplet {
triplets := []PythagoreanTriplet{tree.Root.Triplet()}
if tree.Child1 != nil {
triplets = append(triplets, tree.Child1.extractTriplets()...)
}
if tree.Child2 != nil {
triplets = append(triplets, tree.Child2.extractTriplets()...)
}
if tree.Child3 != nil {
triplets = append(triplets, tree.Child3.extractTriplets()...)
}
return triplets
}
func (tree *FibonacciBoxTernaryTree) generateRootChildren() (one, two, three *FibonacciBox) {
// box | * b |
// | * d | generates boxes
// | * b | | b d | | d b |
// | d * |, | * * |, | * * |
o1 := FibonacciBox{
A: 0,
B: tree.Root.B,
C: tree.Root.D,
D: 0,
}
o1.A = o1.C - o1.B
o1.D = o1.A + o1.C
one = &o1
o2 := FibonacciBox{
A: tree.Root.B,
B: tree.Root.D,
C: 0,
D: 0,
}
o2.C = o2.A + o2.B
o2.D = o2.C + o2.A
two = &o2
o3 := FibonacciBox{
A: tree.Root.D,
B: tree.Root.B,
C: 0,
D: 0,
}
o3.C = o3.A + o3.B
o3.D = o3.C + o3.A
three = &o3
return
}