Go: Project Euler 50-59

problem50.go

package main

import (
	"fmt"
	"time"
)

const MAX = 1000000

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

func next_prime(n int) int {
	if n%2 == 0 {
		n--
	}
	for {
		n += 2
		if is_prime(n) {
			break
		}
	}
	return n
}

type primes struct {
	primes []int
	sum    int
}

func newPrimes() (p primes) {
	n := 2
	p.primes = append(p.primes, n)
	p.sum = n
	for {
		n = next_prime(n)
		if p.sum+n >= MAX {
			break
		}
		p.primes = append(p.primes, n)
		p.sum += n
	}
	return
}

func (p primes) next() (x primes) {
	x.primes = make([]int, len(p.primes)-1)
	copy(x.primes, p.primes[1:])
	x.sum = p.sum - p.primes[0]
	for {
		n := next_prime(x.primes[len(x.primes)-1])
		if x.sum+n >= MAX {
			break
		}
		x.primes, x.sum = append(x.primes, n), x.sum+n
	}
	return
}

func (p primes) answer() (xs []int) {
	xs = append(xs, p.primes[0])
	for i := 1; i < len(p.primes); i++ {
		n := p.primes[i]
		sum := xs[len(xs)-1] + n
		if sum >= MAX {
			break
		}
		xs = append(xs, sum)
	}
	return
}

func problem50() (answer int) {
	p := newPrimes()
	s := p.answer()
	for {
		p = p.next()
		if len(p.primes) < len(s) {
			break
		}
		tmp := p.answer()
		if len(tmp) > len(s) {
			s = tmp
		}
	}
	return s[len(s)-1]
}

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

problem51.go

package main

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

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

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 digits []int

func newDigits(n int) (answer digits) {
	answer = make(digits, int(math.Log10(float64(n)))+1)
	for i := range answer {
		answer[i] = n % 10
		n /= 10
	}
	return
}

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

func (xs digits) isPrime() bool {
	return isPrime(xs.int())
}

func (xs digits) indices(n int) (answer indices) {
	for i, x := range xs {
		if x == n {
			answer = append(answer, i)
		}
	}
	return
}

func (xs digits) expand(ix indices) (answer []digits) {
	for n := 0; n <= 9; n++ {
		ys := make(digits, len(xs))
		copy(ys, xs)
		for _, i := range ix {
			ys[i] = n
		}
		answer = append(answer, ys)
	}
	return
}

func (xs digits) isAnswer() bool {
	for n := 0; n <= 2; n++ {
		ys := xs.indices(n)
		for _, v := range ys.powerSet() {
			counter := 0
			for _, w := range xs.expand(v) {
				if w[len(w)-1] == 0 {
					continue
				}
				if w.isPrime() {
					counter++
				}
			}
			if counter >= 8 {
				return true
			}
		}
	}
	return false
}

type indices []int

func (xs indices) powerSet() (answer []indices) {
	for i := 0; i < len(xs)-2; i++ {
		for j := i + 1; j < len(xs)-1; j++ {
			for k := j + 1; k < len(xs); k++ {
				answer = append(answer, indices{xs[i], xs[j], xs[k]})
			}
		}
	}
	return
}

func primes() (out chan digits) {
	out = make(chan digits)
	go func() {
		for n := 56003 + 2; ; n += 2 {
			if isPrime(n) {
				out <- newDigits(n)
			}
		}
	}()
	return
}

func answer(in chan digits) (out chan int) {
	out = make(chan int)
	go func() {
		for d := range in {
			if d.isAnswer() {
				out <- d.int()
			}
		}
	}()
	return
}

func problem51() {
	fmt.Println(<-answer(primes()))
}

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

problem52.go

package main

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

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

type num int

func (n num) key() string {
	xs := strings.Split(strconv.Itoa(int(n)), "")
	sort.Strings(xs)
	return strings.Join(xs, "")
}

func (n num) isAnswer() bool {
	ch := make(chan bool, 5)
	for i := 2; i <= 6; i++ {
		go func(x int) {
			ch <- n.key() == (n * num(x)).key()
		}(i)
	}
	for i := 1; i <= 5; i++ {
		if !<-ch {
			return false
		}
	}
	return true
}

func (n num) len() int {
	return int(math.Log10(float64(n))) + 1
}

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

func (n num) next() (x num) {
	x = n + num(3)
	y := x * num(6)
	if length := x.len(); length == y.len() {
		return
	} else {
		return num(10).pow(length) + num(2)
	}
	return
}

func problem52() {
	answer := num(3)
	for !answer.isAnswer() {
		answer = answer.next()
	}
	fmt.Println(answer)
}

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

problem53.go

package main

import (
	"fmt"
	"time"
)

const limit = 1000000

func add(a, b int) int {
	x := a + b
	if x <= limit {
		return x
	}
	return limit + 1
}

type pascal []int

func (p *pascal) next() {
	*p = append([]int{0}, *p...)
	for i := 0; i < len(*p)-1; i++ {
		(*p)[i] = add((*p)[i], (*p)[i+1])
	}
}

func problem53() (answer int) {
	for p := pascal([]int{1, 1}); p[1] <= 100; p.next() {
		for i := range p {
			if p[i] > limit {
				answer++
			}
		}
	}
	return
}

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

problem54.go

package main

import (
	"fmt"
	"io/ioutil"
	"runtime"
	"sort"
	"strings"
	"time"
)

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

const (
	Spade = iota
	Club
	Heart
	Diamond
)

const (
	HighCard = iota
	OnePair
	TwoPairs
	ThreeOfAKind
	Straight
	Flush
	FullHouse
	FourOfAKind
	StraightFlush
	RoyalFlush
)

type card struct {
	value int
	suit  int
}

func newCard(s string) (answer card) {
	switch {
	case s[0] == 'A':
		answer.value = 14
	case s[0] == 'K':
		answer.value = 13
	case s[0] == 'Q':
		answer.value = 12
	case s[0] == 'J':
		answer.value = 11
	case s[0] == 'T':
		answer.value = 10
	default:
		answer.value = int(s[0] - '0')
	}
	switch {
	case s[1] == 'S':
		answer.suit = Spade
	case s[1] == 'C':
		answer.suit = Club
	case s[1] == 'H':
		answer.suit = Heart
	case s[1] == 'D':
		answer.suit = Diamond
	}
	return
}

type values []int

func (xs values) isStraight() bool {
	for i, x := range xs {
		if x != xs[0]+i {
			return false
		}
	}
	return true
}

func (xs values) less(ys values) (answer bool) {
	for {
		x, y := xs[len(xs)-1], ys[len(ys)-1]
		switch {
		case x < y:
			return true
		case x > y:
			return false
		}
		for xs[len(xs)-1] == x {
			xs = xs[:len(xs)-1]
		}
		for ys[len(ys)-1] == y {
			ys = ys[:len(ys)-1]
		}
	}
	return
}

type hand []card

func (xs hand) isSameSuit() bool {
	for _, v := range xs[1:] {
		if v.suit != xs[0].suit {
			return false
		}
	}
	return true
}

func (xs hand) values() (answer values) {
	for _, x := range xs {
		answer = append(answer, x.value)
	}
	sort.Ints(answer)
	return
}

func (xs hand) rank() (rank, highestRank int, vs values) {
	vs = xs.values()
	isStraight := vs.isStraight()
	if xs.isSameSuit() {
		switch {
		case isStraight && vs[4] == 14:
			rank = RoyalFlush
			return
		case isStraight:
			rank = StraightFlush
			return
		default:
			rank = Flush
			return
		}
	}
	if isStraight {
		rank = Straight
		return
	}
	m := map[int]int{}
	for _, v := range vs {
		m[v]++
	}
	switch {
	case len(m) == 2:
		for v, n := range m {
			if n == 4 {
				highestRank = v
				rank = FourOfAKind
				return
			}
			if n == 3 {
				highestRank = v
				rank = FullHouse
				return
			}
		}
	case len(m) == 3:
		pair := []int{}
		for v, n := range m {
			if n == 3 {
				highestRank = v
				rank = ThreeOfAKind
				return
			}
			if n == 2 {
				pair = append(pair, v)
			}
		}
		rank = TwoPairs
		if pair[0] > pair[1] {
			highestRank = pair[0]
		} else {
			highestRank = pair[1]
		}
		return
	case len(m) == 4:
		for v, n := range m {
			if n == 2 {
				highestRank = v
				rank = OnePair
				return
			}
		}
	}
	rank = HighCard
	return
}

type play struct {
	player1 hand
	player2 hand
}

func newPlay(s string) (answer play) {
	for i, v := range strings.Fields(s) {
		if i < 5 {
			answer.player1 = append(answer.player1, newCard(v))
		} else {
			answer.player2 = append(answer.player2, newCard(v))
		}
	}
	return
}

func (x play) win() bool {
	r1, h1, v1 := x.player1.rank()
	r2, h2, v2 := x.player2.rank()
	switch {
	case r1 > r2:
		return true
	case r1 < r2:
		return false
	case h1 > h2:
		return true
	case h1 < h2:
		return false
	case !v1.less(v2):
		return true
	case v1.less(v2):
		return false
	}
	return false
}

func problem54() {
	bs, _ := ioutil.ReadFile("poker.txt")
	ss := strings.Split(strings.TrimSpace(string(bs)), "\n")
	ch := make(chan bool, len(ss))
	n := 0
	for _, s := range ss {
		n++
		go func(x string) {
			ch <- newPlay(x).win()
		}(s)
	}
	answer := 0
	for ; n > 0; n-- {
		if <-ch {
			answer++
		}
	}
	fmt.Println(answer)
}

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

problem55.go

package main

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

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

type digits []int

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

func (x *digits) isPalindrome() bool {
	d := *x
	for i, j := 0, len(d)-1; i < j; i, j = i+1, j-1 {
		if d[i] != d[j] {
			return false
		}
	}
	return true
}

func (d *digits) add(e digits) {
	carry := 0
	for i := range *d {
		x := 0
		if i < len(e) {
			x = e[i]
		}
		sum := (*d)[i] + x + carry
		(*d)[i], carry = sum%10, sum/10
	}
	for i := len(*d); i < len(e); i++ {
		sum := e[i] + carry
		*d = append(*d, sum%10)
		carry = sum / 10
	}
	if carry > 0 {
		*d = append(*d, carry)
	}
}

func (d *digits) addReverse() {
	rev := make([]int, len(*d))
	for i := range rev {
		rev[i] = (*d)[len(*d)-1-i]
	}
	(*d).add(rev)
}

func (d *digits) isLychrel() bool {
	p := *d
	p.addReverse()
	for i := 1; i <= 50; i++ {
		if p.isPalindrome() {
			return false
		}
		p.addReverse()
	}
	return true
}

func problem55() {
	ch := make(chan bool, 10000)
	for i := 1; i < 10000; i++ {
		go func(n int) {
			ch <- newDigits(n).isLychrel()
		}(i)
	}
	answer := 0
	for i := 1; i < 10000; i++ {
		if <-ch {
			answer++
		}
	}
	fmt.Println(answer)
}

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

problem56.go

package main

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

type num struct {
	a   int64
	b   int64
	max int64
}

func (x *num) pow() (answer *big.Int) {
	answer = new(big.Int)
	answer.Exp(big.NewInt((*x).a), big.NewInt((*x).b), nil)
	return
}

func (x *num) sumDigits() (answer int64) {
	n := (*x).pow()
	m := new(big.Int)
	one := big.NewInt(1)
	ten := big.NewInt(10)
	for n.Cmp(one) == 1 {
		n.DivMod(n, ten, m)
		answer += m.Int64()
	}
	return
}

func (x *num) next() {
	sum := x.sumDigits()
	digits := math.Log10(math.Pow(float64(x.a), float64(x.b)))
	switch {
	case digits < float64(x.max)/9:
		x.a--
	case sum > x.max:
		x.b--
		x.max = sum
	default:
		x.b--
	}
}

func problem56() int64 {
	x := num{99, 99, 0}
	for x.a > 0 {
		x.next()
	}
	return x.max
}

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

problem57.go

package main

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

func isAnswer(x *big.Rat) bool {
	return len(x.Num().String()) > len(x.Denom().String())
}

func problem57() (answer int) {
	x := big.NewRat(1,2)
	for i := 1; i <= 1000; i++ {
		r := big.NewRat(1,1)
		if isAnswer(r.Add(r,x)) {
			answer++
		}
		x.Add(x,big.NewRat(2,1)).Inv(x)
	}
	return
}

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

problem58.go

package main

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

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

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

type layer struct {
	length int
	prime  int
	total  int
}

func (x layer) isAnswer() bool {
	return 10*x.prime < x.total
}

func (x layer) next() (answer layer) {
	n := x.length + 2
	answer = layer{n, x.prime, x.total + 4}
	ch := make(chan bool, 3)
	for p, i, m := n*n, 1, n-1; i <= 3; i++ {
		go func(num int) {
			ch <- isPrime(num)
		}(p - i*m)
	}
	for i := 1; i <= 3; i++ {
		if <-ch {
			answer.prime++
		}
	}
	return
}

func problem58() {
	n := layer{1, 0, 1}
	n = n.next()
	for !n.isAnswer() {
		n = n.next()
	}
	fmt.Println(n.length)
}

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

problem59.go

package main

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

type key map[int]int

func (x key) max() (answer int) {
	count := 0
	for k, v := range x {
		if v > count {
			answer, count = k, v
		}
	}
	return
}

type nums []int

func (xs nums) key() (answer nums) {
	key0, key1, key2 := make(key), make(key), make(key)
	magic := int(' ')
	for i, x := range xs {
		switch {
		case i%3 == 0:
			key0[x]++
		case i%3 == 1:
			key1[x]++
		case i%3 == 2:
			key2[x]++
		}
	}
	answer = append(answer, key0.max()^magic)
	answer = append(answer, key1.max()^magic)
	answer = append(answer, key2.max()^magic)
	return
}

func (xs nums) decrypt() (answer nums) {
	answer = make(nums, len(xs))
	ys := xs.key()
	for i, x := range xs {
		answer[i] = x ^ ys[i%3]
	}
	return
}

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

func problem59() int {
	bs, _ := ioutil.ReadFile("cipher1.txt")
	ss := strings.Split(strings.TrimSpace(string(bs)), ",")
	ns := nums{}
	for _, s := range ss {
		n, _ := strconv.Atoi(s)
		ns = append(ns, n)
	}
	return ns.decrypt().sum()
}

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