Skip to content

Instantly share code, notes, and snippets.

@edw
Created July 11, 2020 12:18
Show Gist options
  • Save edw/3620d7459d74187d2523593e0545dfeb to your computer and use it in GitHub Desktop.
Save edw/3620d7459d74187d2523593e0545dfeb to your computer and use it in GitHub Desktop.
Project Euler Problem 62
// 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)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment