Go: Project Euler 30-39

problem30.go

package main

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

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

func maxDigits() (answer int) {
	answer = 1
	for pow(9, 5)*answer > pow(10, answer) {
		answer++
	}
	return
}

var MAXDIGITS = maxDigits()

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) value() (answer int) {
	if x.eq(digits{1}) {
		return
	}
	answer = x.sumFifth()
	y := newDigits(answer)
	sort.Ints(y)
	if !x.eq(y) {
		answer = 0
	}
	return
}

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

func (x digits) nexts() (answer []digits) {
	if len(x) >= MAXDIGITS {
		return
	}
	last := 0
	if len(x) > 0 {
		last = x[len(x)-1]
	}
	for i := last; i <= 9; i++ {
		d := make(digits, len(x)+1)
		copy(d, x)
		d[len(d)-1] = i
		answer = append(answer, d)
	}
	return
}

type tree struct {
	digits
	leaves []*tree
}

func newTree(d digits) (t *tree) {
	t = &tree{digits: d}
	for _, v := range d.nexts() {
		t.leaves = append(t.leaves, newTree(v))
	}
	return
}

func (t tree) sum() (answer int) {
	answer += t.value()
	for _, v := range t.leaves {
		answer += v.sum()
	}
	return
}

func problem30() int {
	t := newTree(digits{})
	return t.sum()
}

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

problem31.go

package main

import (
	"fmt"
	"time"
)

func problem31() (answer int) {
	answer = 2
	s := [][2]int{
		{2, 2},
		{5, 5},
		{10, 10},
		{20, 20},
		{50, 50},
		{100, 100},
	}
	for len(s) > 0 {
		last := len(s) - 1
		top := s[last]
		s = s[:last]
		if top[0] > 200 {
			continue
		}
		answer++
		switch {
		case top[1] == 100:
			s = append(s, [2]int{top[0] + 100, 100})
		case top[1] == 50:
			s = append(s, [][2]int{
				{top[0] + 50, 50},
				{top[0] + 100, 100},
			}...)
		case top[1] == 20:
			s = append(s, [][2]int{
				{top[0] + 20, 20},
				{top[0] + 50, 50},
				{top[0] + 100, 100},
			}...)
		case top[1] == 10:
			s = append(s, [][2]int{
				{top[0] + 10, 10},
				{top[0] + 20, 20},
				{top[0] + 50, 50},
				{top[0] + 100, 100},
			}...)
		case top[1] == 5:
			s = append(s, [][2]int{
				{top[0] + 5, 5},
				{top[0] + 10, 10},
				{top[0] + 20, 20},
				{top[0] + 50, 50},
				{top[0] + 100, 100},
			}...)
		case top[1] == 2:
			s = append(s, [][2]int{
				{top[0] + 2, 2},
				{top[0] + 5, 5},
				{top[0] + 10, 10},
				{top[0] + 20, 20},
				{top[0] + 50, 50},
				{top[0] + 100, 100},
			}...)
		}
	}
	return
}

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

problem32.go

package main

import (
	"fmt"
	"time"
)

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) 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) value() (a, b int) {
	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() {
		a = 0
	}
	if !append(x, newDigits(b)...).isPandigital() {
		b = 0
	}
	return
}

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

func fiveDigits() (answer []digits) {
	s := []digits{digits{}}
	for len(s) > 0 {
		top := s[0]
		s = s[1:]
		if len(top) == 5 {
			answer = append(answer, top)
			continue
		}
		s = append(top.nexts(), s...)
	}
	return
}

func problem32() (answer int) {
	m := make(map[int]bool)
	for _, v := range fiveDigits() {
		a, b := v.value()
		m[a] = true
		m[b] = true
	}
	for i := range m {
		answer += i
	}
	return answer
}

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

problem33.go

package main

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

func curiousFraction(n, d int64) (answer *big.Rat, ok bool) {
	answer = big.NewRat(n, d)
	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) {
		ok = true
	}
	return
}

func problem33() *big.Int {
	answer := big.NewRat(1, 1)
	for n := int64(10); n <= 98; n++ {
		for d := n + 1; d <= 99; d++ {
			if r, ok := curiousFraction(n, d); ok {
				answer.Mul(answer, r)
			}
		}
	}
	return answer.Denom()
}

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

problem34.go

package main

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

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))
}

func maxDigits() (n int) {
	for n = 1; fact(9)*n >= pow(10, n); n++ {
		continue
	}
	return
}

var MAXDIGITS = maxDigits()

type digits []int

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

func (x digits) nexts() (answer []digits) {
	if len(x) >= MAXDIGITS {
		return
	}
	min := 0
	if len(x) > 0 {
		min = x[len(x)-1]
	}
	for i := min; i <= 9; i++ {
		d := make(digits, len(x)+1)
		copy(d, x)
		d[len(d)-1] = i
		answer = append(answer, d)
	}
	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) {
		answer = 0
	}
	return
}

func problem34() (answer int) {
	answer -= 3
	stack := []digits{digits{}}
	for len(stack) > 0 {
		last := len(stack) - 1
		top := stack[last]
		answer += top.value()
		stack = append(stack[:last], top.nexts()...)
	}
	return
}

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

problem35.go

package main

import (
	"fmt"
	"time"
)

func isPrime(num int) (answer bool) {
	switch {
	case num < 2:
		return
	case num == 2:
		return true
	case num%2 == 0:
		return
	}
	for p := 3; p*p <= num; p += 2 {
		if num%p == 0 {
			return
		}
	}
	return true
}

type digits []int

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

func (d digits) toInt() (answer int) {
	for _, v := range d {
		answer = 10*answer + v
	}
	return
}

func (d digits) isPrime() (answer bool) {
	answer = isPrime(d.toInt())
	return
}

func (d digits) rotate() (answer []digits) {
	for i := range d {
		answer = append(answer, append(d[i:], d[:i]...))
	}
	return
}

func (d digits) isCircularPrimes() (answer bool) {
	xs := d.rotate()
	for _, x := range xs {
		if !x.isPrime() {
			return
		}
	}
	return true
}

func (d digits) nexts() (answer []digits) {
	candidate := []int{1, 3, 7, 9}
	for _, v := range candidate {
		next := append(newDigits(v), d...)
		answer = append(answer, next)
	}
	return
}

type tree struct {
	digits
	lazy   []func() *tree
}

func newTree(d digits) *tree {
	t := new(tree)
	t.digits = d
	nexts := d.nexts()
	for i := range nexts {
		next := nexts[i]
		f := func() *tree {
			return newTree(next)
		}
		t.lazy = append(t.lazy, f)
	}
	return t
}

func (t tree) count() (answer int) {
	if len(t.digits) > 2 && t.isCircularPrimes() {
		answer++
	}
	if len(t.digits) < 6 {
		for _, f := range t.lazy {
			answer += f().count()
		}
	}
	return
}

func problem35() int {
	d := newDigits(0)
	t := newTree(d)
	return t.count() + 13
}

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

problem36.go

package main

import (
	"fmt"
	"time"
)

type digits []int

func (d digits) candidates() (answer []int) {
	answer = []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	if len(d) == 0 {
		answer = []int{1, 3, 5, 7, 9}
	}
	return
}

func (d digits) nexts() (answer []digits) {
	arr := d.candidates()
	for i := range arr {
		answer = append(answer, append([]int{arr[i]}, d...))
	}
	return
}

func (d digits) toInt() (answer int) {
	for i := range d {
		answer = 10*answer + d[i]
	}
	return
}

func (d digits) addReverse() (a, b digits) {
	for i := len(d) - 1; i >= 0; i-- {
		a = append(a, d[i])
		if i > 0 {
			b = append(b, d[i])
		}
	}
	a = append(a, d...)
	b = append(b, d...)
	return
}

type bin []int

func newBin(n int) (answer bin) {
	for n > 0 {
		answer = append([]int{n % 2}, answer...)
		n /= 2
	}
	return
}

func (b bin) isPalindrom() (answer bool) {
	for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
		if b[i] != b[j] {
			return
		}
	}
	return true
}

type tree struct {
	digits
	lazy   []func() *tree
}

func newTree(d digits) (t *tree) {
	t = new(tree)
	t.digits = d
	nexts := t.nexts()
	for i := range nexts {
		next := nexts[i]
		f := func() *tree {
			return newTree(next)
		}
		t.lazy = append(t.lazy, f)
	}
	return
}

func (t tree) sum() (answer int) {
	d1, d2 := t.addReverse()
	n1, n2 := d1.toInt(), d2.toInt()
	b1, b2 := newBin(n1), newBin(n2)
	if b1.isPalindrom() {
		answer += n1
	}
	if b2.isPalindrom() {
		answer += n2
	}
	if len(t.digits) < 3 {
		for i := range t.lazy {
			f := t.lazy[i]
			answer += f().sum()
		}
	}
	return
}

func problem36() int {
	d := digits([]int{})
	t := newTree(d)
	return t.sum()
}

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

problem37.go

package main

import (
	"fmt"
	"time"
)

func isPrime(n int64) (answer bool) {
	switch {
	case n < 2:
		return
	case n == 2:
		return true
	case n%2 == 0:
		return
	}
	for p := int64(3); p*p <= n; p += 2 {
		if n%p == 0 {
			return
		}
	}
	return true
}

type digits []int64

func newDigits(n int64) (answer digits) {
	for n > 0 {
		answer = append([]int64{n % 10}, answer...)
		n /= 10
	}
	return
}

func (d digits) int64() (answer int64) {
	for _, v := range d {
		answer = 10*answer + v
	}
	return
}

func (d digits) isPrime() (answer bool) {
	answer = isPrime(d.int64())
	return
}

func (d digits) candidates() (answer digits) {
	if len(d) == 0 {
		return []int64{2, 3, 5, 7}
	}
	return []int64{1, 3, 7, 9}
}

func (d digits) nexts() (answer []digits) {
	xs := d.candidates()
	for _, v := range xs {
		next := make([]int64, len(d)+1)
		copy(next, d)
		next[len(next)-1] = v
		if digits(next).isPrime() {
			answer = append(answer, next)
		}
	}
	return
}

func (d digits) tails() (answer []digits) {
	for i := range d {
		answer = append(answer, d[i:])
	}
	return
}

func (d digits) isAnswer() (answer bool) {
	if len(d) < 2 {
		return
	}
	tails := d.tails()
	for _, v := range tails {
		if !v.isPrime() {
			return
		}
	}
	return true
}

type tree struct {
	digits
	leaves []*tree
}

func newTree(d digits) (t *tree) {
	t = new(tree)
	t.digits = d
	nexts := t.nexts()
	for _, v := range nexts {
		t.leaves = append(t.leaves, newTree(v))
	}
	return
}

func (t tree) sum() (answer int64) {
	if t.digits.isAnswer() {
		answer += t.digits.int64()
	}
	for i := range t.leaves {
		answer += t.leaves[i].sum()
	}
	return
}

func problem37() int64 {
	d := newDigits(0)
	t := newTree(d)
	return t.sum()
}

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

problem38.go

package main

import (
	"fmt"
	"sort"
	"time"
)

type digits []int

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

func (x digits) int() (answer int) {
	for i := len(x)-1; i >= 0; i-- {
		answer = 10*answer + x[i]
	}
	return
}

func (x digits) isPandigital() bool {
	if len(x) != 9 {
		return false
	}
	y := make(digits, len(x))
	copy(y, x)
	sort.Ints(y)
	for i, v := range y {
		if i+1 != v {
			return false
		}
	}
	return true
}

func (x digits) multi(n int) (answer digits) {
	answer = make(digits, len(x))
	carry := 0
	for i, v := range x {
		carry += v*n
		answer[i] = carry % 10
		carry /= 10
	}
	for carry > 0 {
		answer = append(answer, carry%10)
		carry /= 10
	}
	return
}

func newConcatProd(n int) (answer digits) {
	d, m := newDigits(n), 1
	for len(answer) < 9 {
		answer = append(d.multi(m), answer...)
		m++
	}
	return
}

func problem38() (answer int) {
	for i := 1; i <= 9876; i++ {
		d := newConcatProd(i)
		if d.isPandigital() {
			n := d.int()
			if n > answer {
				answer = n
			}
		}
	}
	return
}

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

problem39.go

package main

import (
	"fmt"
	"time"
)

type triples [3]int

func (xs triples) nexts() []triples {
	a, b, c := xs[0], xs[1], xs[2]
	return []triples{
		{a - 2*b + 2*c, 2*a - b + 2*c, 2*a - 2*b + 3*c},
		{a + 2*b + 2*c, 2*a + b + 2*c, 2*a + 2*b + 3*c},
		{-a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c},
	}
}

func (xs triples) length() (answer int) {
	for _, x := range xs {
		answer += x
	}
	return
}

func primitives() (answer []int) {
	stack := []triples{{3, 4, 5}}
	for len(stack) > 0 {
		last := len(stack) - 1
		top := stack[last]
		stack = stack[:last]
		if top.length() > 1000 {
			continue
		}
		answer = append(answer, top.length())
		stack = append(stack, top.nexts()...)
	}
	return
}

func problem39() (answer int) {
	m := map[int]int{}
	for _, v := range primitives() {
		for n := 1; v*n <= 1000; n++ {
			m[v*n]++
		}
	}
	count := 0
	for i, v := range m {
		if v > count {
			count, answer = v, i
		}
	}
	return
}

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