Go: Project Euler 80-89

problem80.go

package main

import (
	"fmt"
	"math"
	"math/big"
	"strings"
	"time"
)

type irrational struct {
	num *big.Int
	min *big.Int
	mid *big.Int
	max *big.Int
}

func newIrrational(n int) (x *irrational, ok bool) {
	if i := int(math.Sqrt(float64(n))); i*i == n {
		return
	}
	ok = true
	x = new(irrational)
	x.num = new(big.Int).Mul(
		big.NewInt(int64(n)),
		new(big.Int).Exp(big.NewInt(10), big.NewInt(202), nil),
	)
	x.min = big.NewInt(0)
	x.mid = new(big.Int).Div(x.num, big.NewInt(2))
	x.max = new(big.Int).Set(x.num)
	x.sqrt()
	return
}

func (x *irrational) sqrt() {
	t := new(big.Int)
	for {
		if x.min.Cmp(x.mid) == 0 {
			break
		}
		if t.Add(x.mid, big.NewInt(1)).Cmp(x.max) == 0 {
			break
		}
		if t.Mul(x.mid, x.mid).Cmp(x.num) == -1 {
			x.min.Set(x.mid)
		} else {
			x.max.Set(x.mid)
		}
		x.mid.Add(x.min, x.max).Div(x.mid, big.NewInt(2))
	}
}

func (x *irrational) sum() (answer int) {
	s := strings.Split(x.mid.String(), "")
	for i := 0; i < 100; i++ {
		var n int
		fmt.Sscan(s[i], &n, "%d")
		answer += n
	}
	return
}

func problem80() (answer int) {
	for n := 2; n <= 100; n++ {
		if x, ok := newIrrational(n); ok {
			answer += x.sum()
		}
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem80())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem87.go

package main

import (
	"fmt"
	"math"
	"time"
)

type primes []bool

func newPrimes(n int) (answer primes) {
	answer = make(primes, n+1)
	answer[2] = true
	for i := 3; i <= n; i += 2 {
		answer[i] = true
	}
	for i := 3; i*i <= n; i += 2 {
		for j := i; i*j <= n; j += 2 {
			answer[i*j] = false
		}
	}
	return
}

func (p primes) next(n int) (answer int) {
	answer = n + 2
	switch {
	case n == 2:
		answer = 3
		return
	case answer >= len(p):
		return
	case p[answer]:
		return
	default:
		return p.next(answer)
	}
	return
}

func problem87() int {
	max := 50000000
	ps := newPrimes(int(math.Sqrt(float64(max))))
	mp := make(map[int]bool)
	a := 2
	for {
		x := a * a
		if x >= max {
			break
		}
		b := 2
		for {
			y := x + b*b*b
			if y >= max {
				break
			}
			c := 2
			for {
				z := y + c*c*c*c
				if z >= max {
					break
				}
				mp[z] = true
				c = ps.next(c)
			}
			b = ps.next(b)
		}
		a = ps.next(a)
	}
	return len(mp)
}

func main() {
	start := time.Now()
	fmt.Println(problem87())
	end := time.Now()
	fmt.Println(end.Sub(start).Seconds())
}

problem89.go

package main

import (
	"fmt"
	"io/ioutil"
	"strings"
	"time"
)

func roman2int(s string) (answer int) {
	xs := make([]int, len(s))
	for i, c := range strings.Split(s, "") {
		switch {
		case c == "M":
			xs[i] = 1000
		case c == "D":
			xs[i] = 500
		case c == "C":
			xs[i] = 100
		case c == "L":
			xs[i] = 50
		case c == "X":
			xs[i] = 10
		case c == "V":
			xs[i] = 5
		case c == "I":
			xs[i] = 1
		}
	}
	for i := 0; i < len(xs)-1; i++ {
		if xs[i] < xs[i+1] {
			answer += xs[i+1] - xs[i]
			xs[i+1] = 0
			i++
		} else {
			answer += xs[i]
		}
	}
	answer += xs[len(xs)-1]
	return
}

func int2roman(n int) (answer string) {
	for n >= 1000 {
		answer = strings.Join([]string{answer, "M"}, "")
		n -= 1000
	}
	if n >= 900 {
		answer = strings.Join([]string{answer, "CM"}, "")
		n -= 900
	}
	if n >= 500 {
		answer = strings.Join([]string{answer, "D"}, "")
		n -= 500
	}
	if n >= 400 {
		answer = strings.Join([]string{answer, "CD"}, "")
		n -= 400
	}
	for n >= 100 {
		answer = strings.Join([]string{answer, "C"}, "")
		n -= 100
	}
	if n >= 90 {
		answer = strings.Join([]string{answer, "XC"}, "")
		n -= 90
	}
	if n >= 50 {
		answer = strings.Join([]string{answer, "L"}, "")
		n -= 50
	}
	if n >= 40 {
		answer = strings.Join([]string{answer, "XL"}, "")
		n -= 40
	}
	for n >= 10 {
		answer = strings.Join([]string{answer, "X"}, "")
		n -= 10
	}
	if n == 9 {
		answer = strings.Join([]string{answer, "IX"}, "")
		return
	}
	if n >= 5 {
		answer = strings.Join([]string{answer, "V"}, "")
		n -= 5
	}
	if n == 4 {
		answer = strings.Join([]string{answer, "IV"}, "")
		n -= 4
	}
	for n > 0 {
		answer = strings.Join([]string{answer, "I"}, "")
		n--
	}
	return
}

func problem89() (answer int) {
	bs, _ := ioutil.ReadFile("roman.txt")
	xs := strings.Split(string(bs), "\r\n")
	for _, x := range xs {
		answer += len(x) - len(int2roman(roman2int(x)))
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem89())
	fmt.Println(time.Now().Sub(start).Seconds())
}