Go: Project Euler 70-79

problem70.go

package main

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

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

type ratio struct {
	num int
	den int
}

func (x ratio) float64() float64 {
	return float64(x.num) / float64(x.den)
}

func (x ratio) isPermutation() (answer bool) {
	a, b := x.num, x.den
	as, bs := []int{}, []int{}
	for a > 0 {
		as = append(as, a%10)
		a /= 10
	}
	for b > 0 {
		bs = append(bs, b%10)
		b /= 10
	}
	if len(as) != len(bs) {
		return
	}
	sort.Ints(as)
	sort.Ints(bs)
	for i, v := range as {
		if v != bs[i] {
			return
		}
	}
	return true
}

type rationals []ratio

func (xs rationals) max() (answer int) {
	min := math.MaxFloat64
	for _, x := range xs {
		y := x.float64()
		if y > min {
			continue
		}
		answer, min = x.num, y

	}
	return
}

func find(max int) (answer rationals, ok bool) {
	ps := primes(max)
	limit := 1e7 / ps[len(ps)-1]
	for i := 0; i < len(ps); i++ {
		if i < limit {
			continue
		}
		for j := i; j < len(ps); j++ {
			if j < limit {
				continue
			}
			n := ps[i] * ps[j]
			if n <= limit {
				continue
			}
			if n >= 1e7 {
				break
			}
			r := ratio{n, (ps[i] - 1) * (ps[j] - 1)}
			if !r.isPermutation() {
				continue
			}
			answer = append(answer, r)
			ok = true
		}
	}
	return
}

func problem70() (answer int) {
	n := int(math.Sqrt(1e7)) * 2
	for n < 1e7 {
		if res, ok := find(n); ok {
			return res.max()
		}
		n *= 2
	}
	return
}

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

problem71

package main

import (
	"fmt"
	"time"
)

func problem71() int {
	return 2 + ((1000000-5)/7)*3
}

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

problem72.go

package main

import (
	"fmt"
	"time"
)

type number struct {
	n int
	d int
	s []int
}

func newNumber(x int) *number {
	if x <= 1 {
		return &number{n: 0, d: 0}
	}
	return &number{n: x, d: x}
}

func (n *number) div(p int) {
	if n.d%p == 0 {
		for n.d%p == 0 {
			n.d /= p
		}
		n.s = append(n.s, p)
	}
}

func (x number) phi() (answer int64) {
	if x.n <= 1 {
		return 0
	}
	if x.n == x.d {
		return int64(x.n) - 1
	}
	ratio := [2]int64{int64(x.n), 1}
	for i := range x.s {
		p := int64(x.s[i])
		ratio[0] *= p - 1
		ratio[1] *= p
	}
	return ratio[0] / ratio[1]
}

type numbers []*number

func newNumbers(max int) (answer numbers) {
	answer = make(numbers, max+1)
	for i := range answer {
		answer[i] = newNumber(i)
	}
	for p := 2; 2*p <= max; p++ {
		if answer[p].n == answer[p].d {
			for i := 2; p*i <= max; i++ {
				answer[p*i].div(p)
			}
		}
	}
	return
}

func problem72() (answer int64) {
	xs := newNumbers(1000000)
	for i := range xs {
		answer += int64(xs[i].phi())
	}
	return
}

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

problem73.go

package main

import (
	"fmt"
	"time"
)

type ratio [2]int

func add(x, y ratio) (answer ratio) {
	answer[0] = x[0] + y[0]
	answer[1] = x[1] + y[1]
	return
}

func solve(left, right ratio) (answer int) {
	next := add(left, right)
	if next[1] > 12000 {
		return 0
	}
	answer = 1 + solve(left, next) + solve(next, right)
	return
}

func problem73() int {
	return solve(ratio{1, 3}, ratio{1, 2})
}

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

problem74.go

package main

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

func permutation(xs []int) (answer [][]int) {
	if len(xs) == 0 {
		answer = append(answer, xs)
		return
	}
	for _, x := range xs {
		ys := []int{}
		for _, v := range xs {
			if v != x {
				ys = append(ys, v)
			}
		}
		for _, y := range permutation(ys) {
			zs := make([]int, len(xs))
			zs[0] = x
			copy(zs[1:], y)
			answer = append(answer, zs)
		}
	}
	return
}

func perms(n int) [][]int {
	xs := make([]int, n)
	for i := range xs {
		xs[i] = i
	}
	return permutation(xs)
}

type num int

func (x num) next() (answer num) {
	for x > 0 {
		answer += num(math.Gamma(float64(x%10) + 1))
		x /= 10
	}
	return
}

func (x num) loopLength() int {
	mp := make(map[num]bool)
	mp[x] = true
	for {
		y := x.next()
		if mp[y] {
			break
		}
		mp[y] = true
		x = y
	}
	return len(mp)
}

func (x num) nextNumbers() (answer numbers) {
	for n := num(0); n <= x%10; n++ {
		answer = append(answer, 10*x+n)
	}
	return
}

func (x num) digits() (answer []num) {
	for x > 0 {
		answer = append(answer, x%10)
		x /= 10
	}
	return
}

func (x num) count() (answer int) {
	xs := x.digits()
	mp := make(map[string]bool)
	for _, ps := range perms(len(xs)) {
		ys := make([]num, len(xs))
		for i := range ys {
			ys[i] = xs[ps[i]]
		}
		if ys[0] != 0 {
			mp[fmt.Sprint(ys)] = true
		}
	}
	return len(mp)
}

type numbers []num

func newNumbers() (answer numbers) {
	stack := numbers{1, 2, 3, 4, 5, 6, 7, 8, 9}
	for len(stack) > 0 {
		last := len(stack) - 1
		top := stack[last]
		answer = append(answer, top)
		stack = stack[:last]
		if top < 100000 {
			stack = append(stack, top.nextNumbers()...)
		}
	}
	return
}

func problem74() (answer int) {
	for _, x := range newNumbers() {
		n := x.loopLength()
		if n == 60 {
			answer += x.count()
		}
	}
	return
}

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

problem75.go

package main

import (
	"fmt"
	"time"
)

const LIMIT = 1500000

type triples [3]int

func (xs triples) nexts() []triples {
	a, b, c := xs[0], xs[1], xs[2]
	return []triples{
		triples{a - 2*b + 2*c, 2*a - b + 2*c, 2*a - 2*b + 3*c},
		triples{a + 2*b + 2*c, 2*a + b + 2*c, 2*a + 2*b + 3*c},
		triples{-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{triples{3, 4, 5}}
	for len(stack) > 0 {
		last := len(stack) - 1
		top := stack[last]
		stack = stack[:last]
		length := top.length()
		if length >= LIMIT {
			continue
		}
		answer = append(answer, length)
		stack = append(stack, top.nexts()...)
	}
	return
}

func problem75() (answer int) {
	mp := map[int]int{}
	for _, p := range primitives() {
		for n := 1; p*n < LIMIT; n++ {
			mp[p*n]++
		}
	}
	for _, v := range mp {
		if v == 1 {
			answer++
		}
	}
	return
}

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

problem76.go

package main

import (
	"fmt"
	"time"
)

type partitions map[[2]int]int64

func (xs *partitions) count(m, n int) (answer int64) {
	if m < n {
		return
	}
	if m == n || n == 1 {
		return int64(1)
	}
	if x, ok := (*xs)[[2]int{m, n}]; ok {
		return x
	}
	for i := 1; i <= n; i++ {
		answer += xs.count(m-n, i)
	}
	(*xs)[[2]int{m, n}] = answer
	return
}

func problem76() (answer int64) {
	p := make(partitions)
	for n := 2; n <= 100; n++ {
		answer += p.count(100, n)
	}
	return
}

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

problem77.go

package main

import (
	"fmt"
	"time"
)

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

type nextPrimes map[int]int

func (xs *nextPrimes) next(n int) (answer int) {
	if x, ok := (*xs)[n]; ok {
		return x
	}
	answer = n + 1
	for !isPrime(answer) {
		answer++
	}
	(*xs)[n] = answer
	return
}

type primes []int

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

func newMakePrimes() func(int) primes {
	ps := nextPrimes{2: 3}
	f := func(n int) (answer primes) {
		p := 2
		for p <= n {
			answer = append(answer, p)
			p = ps.next(p)
		}
		return
	}
	return f
}

var makePrimes = newMakePrimes()

type num int

func (x num) partition() (answer int) {
	ps := makePrimes(int(x))
	stack := []primes{}
	for _, p := range ps {
		stack = append(stack, primes{p})
	}
	for len(stack) > 0 {
		last := len(stack) - 1
		top := stack[last]
		sum := top.sum()
		stack = stack[:last]
		if sum > int(x) {
			continue
		}
		if sum == int(x) {
			answer++
			continue
		}
		for _, p := range ps {
			if p > top[len(top)-1] {
				break
			}
			elem := make(primes, len(top)+1)
			copy(elem, top)
			elem[len(elem)-1] = p
			stack = append(stack, elem)
		}
	}
	return
}

func problem77() (answer num) {
	answer = 1
	for answer.partition() <= 5000 {
		answer++
	}
	return
}

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

problem78.go

package main

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

func pentagonal(n int) int {
	return n * (n*3 - 1) / 2
}

func seq(n int) (answer []int) {
	x := 0
	for {
		x++
		for _, y := range []int{1, -1} {
			m := pentagonal(x * y)
			if m > n {
				return
			}
			answer = append(answer, n-m)
		}
	}
	return
}

var partitionNumbers = map[int]*big.Int{0: big.NewInt(1), 1: big.NewInt(1)}

func partition(n int) (answer *big.Int) {
	if x, ok := partitionNumbers[n]; ok {
		return x
	}
	answer = big.NewInt(0)
	for i, y := range seq(n) {
		s := big.NewInt(1)
		if i/2%2 != 0 {
			s.Neg(s)
		}
		answer.Add(answer, s.Mul(s, partition(y)))
	}
	partitionNumbers[n] = answer
	return
}

func problem78() (answer interface{}) {
	d := big.NewInt(1e6)
	zero := big.NewInt(0)
	n := 1
	for {
		n++
		x := partition(n)
		x.Mod(x, d)
		if x.Cmp(zero) == 0 {
			answer = n
			break
		}
	}
	return
}

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

problem79.go

package main

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

func data() (answer [][]string) {
	bs, _ := ioutil.ReadFile("keylog.txt")
	xss := strings.Split(strings.TrimSpace(string(bs)), "\r\n")
	for _, xs := range xss {
		x := strings.Split(xs, "")
		a := []string{x[0], x[1]}
		b := []string{x[1], x[2]}
		answer = append(answer, a, b)
	}
	return
}

type vertex string

func (x vertex) Label() string {
	return string(x)
}

type edge struct {
	f string
	t string
}

func (x edge) From() string {
	return x.f
}

func (x edge) To() string {
	return x.t
}

func makeGraph() (g graph.Graph) {
	g = graph.New()
	for _, x := range data() {
		g.AddVertex(vertex(x[0]))
		g.AddVertex(vertex(x[1]))
		g.AddEdge(edge{x[0], x[1]})
	}
	return
}

func tsort(g graph.Graph) (answer []string) {
	for len(g) > 0 {
		for v := range g {
			if len(g.InEdges(v)) == 0 {
				answer = append(answer, v)
				g.DeleteVertex(v)
				break
			}
		}
	}
	return
}

func problem79() (answer string) {
	g := makeGraph()
	return strings.Join(tsort(g), "")
}

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