Go/goroutine: Project Euler 30-39

problem30.go

package main

import (
	"fmt"
	"math"
	"runtime"
	"sort"
	"time"
)

func init() {
	runtime.GOMAXPROCS(10)
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

type digits []int

func newDigits(n int) (answer digits) {
	for n > 0 {
		answer = append(answer, n%10)
		n /= 10
	}
	return
}

func (x digits) eq(y digits) bool {
	if len(x) != len(y) {
		return false
	}
	for i := range x {
		if x[i] != y[i] {
			return false
		}
	}
	return true
}

func (x digits) sumFifth() (answer int) {
	for _, v := range x {
		answer += pow(v, 5)
	}
	return
}

func (x digits) value() (answer int) {
	if x.eq(digits{1}) {
		return
	}
	n := x.sumFifth()
	y := newDigits(n)
	sort.Ints(y)
	if x.eq(y) {
		return n
	}
	return
}

func sum(n, max int) (answer int) {
	s := []digits{{n}}
	for len(s) > 0 {
		last := len(s) - 1
		top := s[last]
		s = s[:last]
		answer += top.value()
		if len(top) == max {
			continue
		}
		for n := 9; n >= top[len(top)-1]; n-- {
			x := make(digits, len(top)+1)
			copy(x, top)
			x[len(x)-1] = n
			s = append(s, x)
		}
	}
	return
}

type queue struct {
	ch   chan int
	size int
}

func newQueue() queue {
	max := 1
	for pow(9, 5)*max > pow(10, max) {
		max++
	}
	ch := make(chan int, 10)
	for m := 9; m >= 0; m-- {
		go func(n int) {
			ch <- sum(n, max)
		}(m)
	}
	return queue{ch, 10}
}

func problem30() {
	sum := 0
	for q := newQueue(); q.size > 0; q.size-- {
		sum += <-q.ch
	}
	fmt.Println(sum)
}

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

problem32.go

package main

import (
	"fmt"
	"runtime"
	"time"
)

func init() {
	runtime.GOMAXPROCS(9)
}

type digits []int

func newDigits(n int) (answer digits) {
	for n > 0 {
		answer = append(answer, n%10)
		n /= 10
	}
	return
}

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

func (x digits) nexts() (answer []digits) {
	for n := 1; n <= 9; n++ {
		if !x.member(n) {
			y := make(digits, len(x)+1)
			copy(y, x)
			y[len(y)-1] = n
			answer = append(answer, y)
		}
	}
	return
}

func (x digits) isPandigital() bool {
	memo := make([]int, 10)
	for _, v := range x {
		if v == 0 || memo[v] != 0 {
			return false
		}
		memo[v]++
	}
	return true
}

func (x digits) result() (answer []res) {
	a := x[0] * (1000*x[1] + 100*x[2] + 10*x[3] + x[4])
	b := (10*x[0] + x[1]) * (100*x[2] + 10*x[3] + x[4])
	if append(x, newDigits(a)...).isPandigital() {
		answer = append(answer, res{a, true})
	}
	if append(x, newDigits(b)...).isPandigital() {
		answer = append(answer, res{b, true})
	}
	return
}

type res struct {
	num int
	ok bool
}

func answers(n int) (answer []int) {
	s := []digits{{n}}
	for len(s) > 0 {
		last := len(s) - 1
		top := s[last]
		s = s[:last]
		if len(top) == 5 {
			for _, v := range top.result() {
				if v.ok {
					answer = append(answer, v.num)
				}
			}
			continue
		}
		s = append(s, top.nexts()...)
	}
	return
}

type queue struct {
	ch   chan []int
	size int
}

func newQueue() queue {
	ch := make(chan []int, 9)
	for n := 1; n <= 9; n++ {
		go func(m int) {
			ch <- answers(m)
		}(n)
	}
	return queue{ch, 9}
}

func problem32() {
	mp := make(map[int]bool)
	for q := newQueue(); q.size > 0; q.size-- {
		for _, n := range <-q.ch {
			mp[n] = true
		}
	}
	answer := 0
	for n := range mp {
		answer += n
	}
	fmt.Println(answer)
}

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

problem33.go

package main

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

func init() {
	runtime.GOMAXPROCS(90)
}

func curiousFraction(n, d int64) (answer bool) {
	n1, n2, d1, d2 := n/10, n%10, d/10, d%10
	if (n1 == d2 && n2*d == d1*n) || (n2 == d1 && n1*d == d2*n) {
		return true
	}
	return
}

func mulFraction(n int64) *big.Rat {
	answer := big.NewRat(1, 1)
	for d := n + 1; d <= 99; d++ {
		if curiousFraction(n, d) {
			answer.Mul(answer, big.NewRat(n, d))
		}
	}
	return answer
}

type queue struct {
	ch   chan *big.Rat
	size int
}

func newQueue() queue {
	ch, ps := make(chan *big.Rat, 90), 0
	for n := int64(10); n < 99; n++ {
		go func(num int64) {
			ch <- mulFraction(num)
		}(n)
		ps++
	}
	return queue{ch, ps}
}

func problem33() {
	answer := big.NewRat(1, 1)
	for q := newQueue(); q.size > 0; q.size-- {
		answer.Mul(answer, <-q.ch)
	}
	fmt.Println(answer.Denom())
}

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

problem34.go

package main

import (
	"fmt"
	"math"
	"runtime"
	"sort"
	"time"
)

func init() {
	runtime.GOMAXPROCS(10)
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

func fact(n int) (answer int) {
	return int(math.Gamma(float64(n) + 1))
}

type digits []int

func newDigits(n int) (answer digits) {
	for n > 0 {
		answer = append(answer, n%10)
		n /= 10
	}
	return
}

func (d digits) eq(d1 digits) (answer bool) {
	if len(d) != len(d1) {
		return
	}
	for i := range d {
		if d[i] != d1[i] {
			return
		}
	}
	return true
}

func (x digits) value() (answer int) {
	for _, v := range x {
		answer += fact(v)
	}
	y := newDigits(answer)
	sort.Ints(y)
	if y.eq(x) {
		return
	}
	return 0
}

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

func sum(n, max int) (answer int) {
	s := []digits{{n}}
	for len(s) > 0 {
		last := len(s) - 1
		top := s[last]
		s = s[:last]
		answer += top.value()
		if len(top) == max {
			continue
		}
		s = append(s, top.nexts()...)
	}
	return
}

type queue struct {
	ch   chan int
	size int
}

func newQueue() queue {
	max := 1
	for fact(9)*max >= pow(10, max) {
		max++
	}
	ch, ps := make(chan int, 10), 0
	for i := 0; i <= 9; i++ {
		go func(n int) {
			ch <- sum(n, max)
		}(i)
		ps++
	}
	return queue{ch, ps}
}

func problem34() {
	answer := -3
	for q := newQueue(); q.size > 0; q.size-- {
		answer += <-q.ch
	}
	fmt.Println(answer)
}

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