Project Euler Problem 62

problem62.go

// Solves problem 62 by iterating over all ints in increasing order
// and storing each in a map keyed by the lexigraphically-sorted
// cube of that number's digits. Repeat until storing an int results
// in the map key having five values associated with it.
//
// https://projecteuler.net/problem=62
//
// It turns out big ints weren't necessary to solve the problem,
// but re-writing numerics code from regular to big numbers is
// a huge PITA, so it's better to start with math/big if you think
// you may need to go there.

package main

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

type ByDigit []uint8

func (bs ByDigit) Less(i, j int) bool { return bs[i] < bs[j] }
func (bs ByDigit) Len() int           { return len(bs) }
func (bs ByDigit) Swap(i, j int)      { bs[i], bs[j] = bs[j], bs[i] }

func Int2Key(x *big.Int) string {
	bs := []uint8(x.Text(10))
	sort.Sort(ByDigit(bs))
	t := string(bs)
	return t
}

var (
	kZero = big.NewInt(0)
	kOne = big.NewInt(1)
	kThree = big.NewInt(3)
)

var cache = make(map[string][]*big.Int)

func main() {
	i := big.NewInt(0) // Don't use kZero b/c i is not a constant.
	for {
		x := &big.Int{} 
		x.Exp(i, kThree, kZero)
		key := Int2Key(x)
		value := &big.Int{}
		value.Set(i)
		cache[key] = append(cache[key], value)
		if len(cache[key]) == 5 {
			winner := cache[key][0]
			winner.Exp(winner, kThree, kZero)
			fmt.Printf("Winner: %v", winner)
			break
		}
		i.Add(i, kOne)
	}
}