Go: Project Euler 60-69

problem60.go

package main

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

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

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

func join(m, n int) int {
	return int(math.Pow(10, math.Floor(math.Log10(float64(n)))+1))*m + n
}

func joinable(m, n int) bool {
	return isPrime(join(m, n)) && isPrime(join(n, m))
}

func p1() (out chan int) {
	out = make(chan int)
	go func() {
		for n := 3; ; n += 2 {
			if isPrime(n) {
				out <- n
			}
		}
	}()
	return
}

func p2(in chan int) (out chan []int) {
	out = make(chan []int)
	go func() {
		slice := []int{}
		for p := range in {
			for _, v := range slice {
				if joinable(v, p) {
					out <- []int{v, p}
				}
			}
			slice = append(slice, p)
		}
	}()
	return
}

func pn(in chan []int) (out chan []int) {
	out = make(chan []int)
	go func() {
		mp := make(map[string][]int)
		for xs := range in {
			head := xs[:len(xs)-1]
			key := fmt.Sprint(head)
			last := xs[len(xs)-1]
			for _, v := range mp[key] {
				if joinable(v, last) {
					ys := make([]int, len(xs)+1)
					copy(ys, head)
					ys[len(ys)-2] = v
					ys[len(ys)-1] = last
					out <- ys
				}
			}
			mp[key] = append(mp[key], last)
		}
	}()
	return
}

func problem60() {
	answer := 0
	for _, v := range <-pn(pn(pn(p2(p1())))) {
		answer += v
	}
	fmt.Println(answer)
}

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

problem61.go

package main

import (
	"fmt"
	"graph"
	"time"
)

func pn(p, n int) int {
	return n * (n*(p-2) - (p - 4)) / 2
}

type vertex int

func (v vertex) Label() string {
	return fmt.Sprint(v)
}

type edge struct {
	from int
	to   int
	poly int
}

func (e edge) From() string {
	return fmt.Sprint(e.from)
}

func (e edge) To() string {
	return fmt.Sprint(e.to)
}

func makeGraph() graph.Graph {
	g := graph.New()
	for i := 10; i < 100; i++ {
		g.AddVertex(vertex(i))
	}
	for p := 3; p <= 8; p++ {
		n := 0
		for {
			n++
			x := pn(p, n)
			if x < 1e3 {
				continue
			}
			if x >= 1e4 {
				break
			}
			a, b := x/100, x%100
			g.AddEdge(edge{a, b, p})
		}
	}
	return g
}

type edges []edge

func (xs edges) isAnswer() bool {
	return xs[0].from == xs[len(xs)-1].to
}

func (xs edges) member(e edge) (answer bool) {
	for _, x := range xs {
		if x.poly == e.poly {
			return true
		}
	}
	return
}

func (xs edges) nexts(g graph.Graph) (answer []edges) {
	for _, e := range g.OutEdges(xs[len(xs)-1].To()) {
		x := e.(edge)
		if xs.member(x) {
			continue
		}
		ys := make(edges, len(xs)+1)
		copy(ys, xs)
		ys[len(ys)-1] = x
		answer = append(answer, ys)
	}
	return
}

func (xs edges) sum() (answer int) {
	for _, x := range xs {
		answer += 100*x.from + x.to
	}
	return
}

func find(g graph.Graph) (answer edges) {
	xs := g.Edges()
	s := make([]edges, len(xs))
	for i, x := range xs {
		s[i] = edges{x.(edge)}
	}
	for len(s) > 0 {
		last := len(s) - 1
		top := s[last]
		s = s[:last]
		if len(top) == 6 {
			if top.isAnswer() {
				return top
			}
			continue
		}
		s = append(s, top.nexts(g)...)
	}
	return
}

func problem61() int {
	return find(makeGraph()).sum()
}

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

problem62.go

package main

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

type num float64

func (x num) cube() (key string, n num) {
	n = num(math.Pow(float64(x), 3))
	xs := strings.Split(fmt.Sprint(int64(n)), "")
	sort.Strings(xs)
	key = strings.Join(xs, "")
	return
}

type table map[string][]num

func (xss table) find(key string) (answer int, ok bool) {
	if len(xss[key]) >= 5 {
		return len(key), true
	}
	return
}

func (xss table) result(length int) (answer num) {
	for key, xs := range xss {
		if len(key) != length || len(xss[key]) < 5 {
			continue
		}
		if answer == 0 {
			answer = xs[0]
			continue
		}
		if answer < xs[0] {
			continue
		}
		answer = xs[0]
	}
	return
}

func solve(n num, length int, t table) num {
	key, cube := n.cube()
	if length > 0 && len(key) > length {
		return t.result(length)
	}
	t[key] = append(t[key], cube)
	if x, ok := t.find(key); ok {
		length = x
	}
	return solve(n+1, length, t)
}

func problem62() int64 {
	return int64(solve(345, -1, make(table)))
}

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

problem63.go

package main

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

func count(x float64) (answer int) {
	y := float64(1)
	for {
		n := Pow(x, y)
		digits := Trunc(Log10(n)) + 1
		if digits != y {
			break
		}
		answer++
		y++
	}
	return
}

func problem63() (answer int) {
	for n := float64(1); n < 10; n++ {
		answer += count(n)
	}
	return
}

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

problem67.go

package main

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

func max(x, y int) int {
	if x >=y {
		return x
	}
	return y
}

type nums []int

func (xs *nums) join(ys nums) {
	for i, _ := range *xs {
		(*xs)[i] += max(ys[i], ys[i+1])
	}
	return
}

func data() (answer []nums) {
	bs, _ := ioutil.ReadFile("triangle.txt")
	xs := strings.Split(strings.TrimSpace(string(bs)), "\n")
	for _, x := range xs {
		ys := nums{}
		for _, y := range strings.Fields(x) {
			n, _ := strconv.Atoi(y)
			ys = append(ys, n)
		}
		answer = append(answer, ys)
	}
	return
}

func problem67() (answer int) {
	xs := data()
	for i := len(xs)-2; i >= 0; i-- {
		xs[i].join(xs[i+1])
	}
	return xs[0][0]
}

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

problem68.go

package main

import (
	"fmt"
	"graph"
	"time"
)

type line []int

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

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

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

func (xs line) From() string {
	return fmt.Sprint(xs[1])
}

func (xs line) To() string {
	return fmt.Sprint(xs[2])
}

type sumMap map[int][]line

func newSumMap() (answer sumMap) {
	answer = make(sumMap)
	s := []line{}
	for i := 1; i <= 10; i++ {
		s = append(s, line{i})
	}
	for len(s) > 0 {
		top := s[0]
		s = s[1:]
		if len(top) == 3 {
			n := top.sum()
			answer[n] = append(answer[n], top)
			continue
		}
		s = append(top.nexts(), s...)
	}
	return
}

type vertex int

func (v vertex) Label() string {
	return fmt.Sprint(v)
}

func makeGraph(xs []line) (g graph.Graph) {
	g = graph.New()
	for n := 1; n <= 10; n++ {
		g.AddVertex(vertex(n))
	}
	for _, x := range xs {
		g.AddEdge(line(x))
	}
	return
}

type ring []line

func (r ring) isAnswer() bool {
	return r[0][1] == r[len(r)-1][2]
}

func (r ring) member(xs line) (answer bool) {
	if len(r) == 4 {
		xs = line{xs[0]}
	} else {
		xs = line{xs[0], xs[2]}
	}
	for _, ys := range r {
		for _, y := range ys {
			for _, x := range xs {
				if x == y {
					return true
				}
			}
		}
	}
	return
}

func (r ring) nexts(g graph.Graph) (answer []ring) {
	for _, e := range g.OutEdges(r[len(r)-1].To()) {
		line := e.(line)
		if r[0][0] > line[0] {
			continue
		}
		if r.member(line) {
			continue
		}
		xs := make(ring, len(r)+1)
		copy(xs, r)
		xs[len(xs)-1] = line
		answer = append(answer, xs)
	}
	return
}

func (r ring) flatten() (answer []int) {
	for _, line := range r {
		for _, n := range line {
			answer = append(answer, n)
		}
	}
	return
}

func (r ring) int64() (answer int64) {
	xs := r.flatten()
	for len(xs) > 0 {
		if xs[0] == 10 {
			xs = append([]int{1, 0}, xs[1:]...)
			continue
		}
		answer = 10*answer + int64(xs[0])
		xs = xs[1:]
	}
	return
}

func findRing(g graph.Graph) (answer []ring) {
	s := []ring{}
	for _, e := range g.Edges() {
		s = append(s, ring{e.(line)})
	}
	for len(s) > 0 {
		top := s[0]
		s = s[1:]
		if len(top) == 5 {
			if top.isAnswer() {
				answer = append(answer, top)
			}
			continue
		}
		s = append(top.nexts(g), s...)
	}
	return
}

func problem68() (answer int64) {
	rings := []ring{}
	for _, v := range newSumMap() {
		g := makeGraph(v)
		rings = append(rings, findRing(g)...)
	}
	for _, r := range rings {
		n := r.int64()
		if n > answer {
			answer = n
		}
	}
	return
}

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

problem69.go

package main

import (
	"fmt"
	"time"
)

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

func nextPrime(n int) int {
	n += 2
	for !isPrime(n) {
		n += 2
	}
	return n
}

func problem69() (answer int) {
	answer = 2
	for p := 3; answer*p <= 1000000; p = nextPrime(p) {
		answer *= p
	}
	return
}

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