Go: Project Euler 90-99

problem90.go

package main

import (
	"fmt"
	"time"
)

type digits []int

func (xs digits) nexts() (answer []digits) {
	init := 0
	if len(xs) > 0 {
		init = xs[len(xs)-1] + 1
	}
	for n := init; n <= 9; n++ {
		ys := make(digits, len(xs)+1)
		copy(ys, xs)
		ys[len(ys)-1] = n
		answer = append(answer, ys)
	}
	return
}

func (xs digits) cube() (answer cube) {
	answer = cube(xs)
	if xs[len(xs)-1] == 9 {
		for _, n := range xs {
			if n == 6 {
				return
			}
		}
		answer = append(answer, 6)
		return
	}
	for _, n := range xs {
		if n == 6 {
			answer = append(answer, 9)
		}
	}
	return
}

type cube []int

func newCubes() (answer []cube) {
	stack := []digits{digits{}}
	for len(stack) > 0 {
		last := len(stack) - 1
		top := stack[last]
		stack = stack[:last]
		if len(top) == 6 {
			answer = append(answer, top.cube())
			continue
		}
		stack = append(stack, top.nexts()...)
	}
	return
}

func member(n int, xs []int) bool {
	for _, x := range xs {
		if x == n {
			return true
		}
	}
	return false
}

func isAnswer(xs, ys cube) bool {
	squares := [][2]int{
		[2]int{0, 1},
		[2]int{0, 4},
		[2]int{0, 9},
		[2]int{1, 6},
		[2]int{2, 5},
		[2]int{3, 6},
		[2]int{4, 9},
		[2]int{6, 4},
		[2]int{8, 1},
	}
	for _, arr := range squares {
		if !((member(arr[0], xs) && member(arr[1], ys)) ||
			(member(arr[0], ys) && member(arr[1], xs))) {
			return false
		}
	}
	return true
}

func problem90() (answer int) {
	xs := newCubes()
	for i := 0; i < len(xs); i++ {
		for j := i; j < len(xs); j++ {
			if isAnswer(xs[i], xs[j]) {
				answer++
			}
		}
	}
	return
}

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

problem92.go

package main

import (
	"fmt"
	"time"
)

func isAnswer(n int) (answer bool) {
	for {
		if n == 89 {
			return true
		}
		if n == 1 {
			return false
		}
		x := 0
		for n > 0 {
			d := n%10
			x += d*d
			n /= 10
		}
		n = x
	}
	return
}

func lower() (answer []bool) {
	answer = make([]bool, 1e3)
	for n := 2; n < 1e3; n++ {
		if isAnswer(n) {
			answer[n] = true
		}
	}
	return
}

type digits []int

func (xs digits) num() (answer int) {
	for _, x := range xs {
		answer += x*x
	}
	return
}

func (xs digits) allZero() (answer bool) {
	for _, x := range xs {
		if x != 0 {
			return
		}
	}
	return true
}

func (xs digits) count() (answer int) {
	if xs.allZero() {
		return
	}
	answer = 1
	m := map[int]int{}
	for _, v := range xs {
		m[v]++
	}
	if _, ok := m[0]; ok {
		answer *= len(xs) - m[0]
		for n := len(xs)-1; n > 1; n-- {
			answer *= n
		}
	} else {
		for n := len(xs); n > 1; n-- {
			answer *= n
		}
	}
	for _, i := range m {
		for i > 1 {
			answer /= i
			i--
		}
	}
	return
}

func (xs digits) nexts() (answer []digits) {
	for n := xs[len(xs)-1]; n <= 9; n++ {
		ys := make(digits, len(xs)+1)
		copy(ys, xs)
		ys[len(ys)-1] = n
		answer = append(answer, ys)
	}
	return
}

func upper() (answer []digits) {
	s := make([]digits, 10)
	for i, _ := range s {
		s[i] = digits{i}
	}
	for len(s) > 0 {
		top := s[0]
		s = s[1:]
		if len(top) == 7 {
			answer = append(answer, top)
			continue
		}
		if len(top) >= 4 {
			answer = append(answer, top)
		}
		s = append(top.nexts(), s...)
	}
	return
}

func problem92() (answer int) {
	answer = 1e7 - 1
	xs := lower()
	for i, ok := range xs {
		if i == 0 {
			continue
		}
		if !ok {
			answer--
		}
	}
	for _, d := range upper() {
		if !xs[d.num()] {
			answer -= d.count()
		}
	}
	return
}

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

problem95.go

package main

import (
	"fmt"
	"time"
)

const max = 1000000

type sumFactors []int

func newSumFactors() (answer sumFactors) {
	answer = make(sumFactors, max+1)
	for n := 1; n <= max/2; n++ {
		for p := 2; n*p <= max; p++ {
			answer[n*p] += n
		}
	}
	return
}

func (xs sumFactors) chainLength(n int) (answer int) {
	chain := map[int]bool{n: true}
	i := xs[n]
	for {
		if i < n || i > max {
			return 0
		}
		if i == n {
			return len(chain)
		}
		if chain[i] {
			return 0
		}
		chain[i] = true
		i = xs[i]
	}
	return
}

func problem95() (answer int) {
	xs, length := newSumFactors(), 0
	for i := range xs {
		n := xs.chainLength(i)
		if n > length {
			answer, length = i, n
		}
	}
	return
}

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

problem97.go

package main

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

func problem97() (answer *big.Int) {
	d := big.NewInt(0).Exp(big.NewInt(10), big.NewInt(10), nil)
	e := big.NewInt(0).Exp(big.NewInt(2), big.NewInt(7830457), d)
	answer = big.NewInt(28433)
	answer.Mul(answer, e).Add(answer, big.NewInt(1)).Rem(answer, d)
	return
}

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

problem99

package main

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

func problem99() (answer int) {
	b, _ := ioutil.ReadFile("base_exp.txt")
	xs := strings.Fields(string(b))
	max := float64(0)
	for i, x := range xs {
		ys := strings.Split(x, ",")
		a, _ := strconv.Atoi(ys[0])
		b, _ := strconv.Atoi(ys[1])
		n := math.Log10(float64(a)) * float64(b)
		if n > max {
			answer, max = i+1, n
		}
	}
	return
}

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