codewars/go/kyu5/some_egyptian_fractions/k.go

package kata

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

func normalizeRational(s string) (n, d int) {
	sl := strings.Split(s, ".")
	n, _ = strconv.Atoi(sl[0])
	if len(sl) == 1 {
		return n, 1
	}

	var f float64
	fmt.Sscanf(s, "%f", &f)
	fd := math.Pow10(len(sl[1]))
	n = int(f * fd)
	d = int(fd)
	g := gcd(n, d)
	return n / g, d / g
}

func toFraction(s string) (n, d int) {
	sl := strings.Split(s, "/")
	n, d = normalizeRational(sl[0])
	if len(sl) == 1 {
		return
	}
	n2, d2 := normalizeRational(sl[1])
	n, d = n * d2, d * n2
	g := gcd(n, d)
	return n / g, d / g
}

// gcd from runtime/proc.go
// (c) Go Authors - MIT License
func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func fib(divs chan<- int, a, b int) {
	if a == 1 || a == 0 {
		divs <- b
		close(divs)
		return
	}

	// Smallest n larger than b/a or equal to it.
	r := int(math.Ceil(float64(b) / float64(a)))
	divs <- r

	n := a*r - b
	d := r * b
	g := gcd(n, d)
	n /= g
	d /= g
	fib(divs, n, d)
}

func Decompose(s string) []string {
	n, d := toFraction(s)
	res := []string{}
	// Handle degenerate cases first.
	// Just 0.
	if n == 0 {
		return res
	}
	// Larger than 1: start by floor(ratio).
	if n/d >= 1 {
		first := n / d
		res = append(res, fmt.Sprintf("%d", first))
		if n%d == 0 {
			return res
		}
		n -= first * d
	}

	// Now code can assume n != 0.
	divs := make(chan int)
	fmt.Println(s, n, d)
	go fib(divs, n, d)
	for div := range divs {
		res = append(res, fmt.Sprintf("1/%d", div))
	}
	return res
}