problem 71 in go

1 files changed, 105 insertions, 0 deletions

diff --git a/go/071-ordered_fractions.go b/go/071-ordered_fractions.go
new file mode 100644
index 0000000..c93f796
--- /dev/null
+++ b/go/071-ordered_fractions.go
@@ -0,0 +1,105 @@
+/*
+* Ordered fractions
+* Problem 71
+*
+* Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1,
+* it is called a reduced proper fraction.
+* If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we
+* get:
+* 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5,
+* 5/6, 6/7, 7/8
+* It can be seen that 2/5 is the fraction immediately to the left of 3/7.
+* By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of
+* size, find the numerator of the fraction immediately to the left of 3/7.
+ */
+
+package main
+
+import (
+	"fmt"
+	"sort"
+)
+
+const MAX_DENOMINATOR = 1_000_000
+
+// from: https://www.101computing.net/hcf-and-lcm-algorithms/
+func hcf(a, b int) int {
+	var t int
+	if a < b {
+		t = a
+		a = b
+		b = t
+	}
+	for b > 0 {
+		t = b
+		b = a % b
+		a = t
+	}
+	return a
+}
+
+func hasCommonFactor(a, b int) bool {
+	return hcf(a, b) != 1
+}
+
+type Fraction struct {
+	N int
+	D int
+}
+
+func (f1 Fraction) isLower(f2 Fraction) bool {
+		ni_common := f1.N * f2.D
+		nj_common := f2.N * f1.D
+		return ni_common < nj_common
+}
+
+var targetFraction = Fraction {N: 3, D: 7}
+
+func main() {
+	fractions := make([]Fraction, 0, MAX_DENOMINATOR)
+	fractions = append(fractions, targetFraction)
+
+	for d := 1; d <= MAX_DENOMINATOR; d++ {
+		lo := 1
+		hi := d
+		n := (hi + lo) / 2
+		var f Fraction
+		for lo < hi {
+			factor := hcf(n, d)
+			f = Fraction{
+				N: n / factor,
+				D: d / factor,
+			}
+			if f.isLower(targetFraction) {
+				lo = n + 1
+			} else {
+				hi = n
+			}
+			n = (hi + lo) / 2
+		}
+		fractions = append(fractions, f)
+		// in case we're at the fraction just one above the target fraction
+		f.N--
+		fractions = append(fractions, f)
+	}
+
+	sort.Slice(fractions, func (i, j int) bool {
+		return fractions[i].isLower(fractions[j])
+	})
+
+	new_fractions := make([]Fraction, 0, len(fractions))
+	for i := 0; i < len(fractions); {
+		new_fractions = append(new_fractions, fractions[i])
+		curr := fractions[i]
+		for i < len(fractions) && curr.N == fractions[i].N && curr.D == fractions[i].D {
+			i++
+		}
+	}
+
+	for i, f := range new_fractions {
+		if f.N == targetFraction.N && f.D == targetFraction.D {
+			fmt.Printf("to the left of %d/%d is %d/%d\n", f.N, f.D, new_fractions[i - 1].N, new_fractions[i - 1].D)
+			fmt.Printf("answer %d\n", new_fractions[i - 1].N)
+		}
+	}
+}