Project Euler #24 in Go - Answer: [2 7 8 3 9 1 5 4 6 0]

euler24_brute.go

package main

import (
	"fmt"
)

const Max = 10
const Index = 1000000

func main() {
	numbers := make([]byte, 0, Max)
	for i := 0; i < Max; i++ {
		numbers = append(numbers, byte(i))
	}

	result = make(chan [Max]byte, 1)
	index = 0
	perm(numbers, 0, len(numbers))
	if len(result) > 0 {
		fmt.Println(<-result)
	}
}

var index int
var result chan [Max]byte

func perm(numbers []byte, lo, hi int) {
	if index > Index {
		return
	}
	if hi-lo < 2 {
		if index++; index == Index {
			var p [Max]byte
			copy(p[:], numbers)
			result <- p
		}
		return
	}
	for i := 1; i < hi-lo+1; i++ {
		rotateR(numbers, lo, lo+i)
		perm(numbers, lo+1, hi)
		rotateL(numbers, lo, lo+i)
	}
}

func rotateL(numbers []byte, lo, hi int) {
	for i := lo + 1; i < hi; i++ {
		numbers[i-1], numbers[i] = numbers[i], numbers[i-1]
	}
}

func rotateR(numbers []byte, lo, hi int) {
	for i := hi - 1; i > lo; i-- {
		numbers[i-1], numbers[i] = numbers[i], numbers[i-1]
	}
}

euler24_fast.go

package main

import (
	"fmt"
)

const Max = 10
const Index = 1000000

func main() {
	digits := make([]byte, 0, Max)
	for i := byte(0); i < Max; i++ {
		digits = append(digits, i)
	}

	rem := Index - 1
	res := make([]byte, 0, Max)
	for i := Max - 1; i >= 0; i-- {
		f := fact(i)
		quo := rem / f
		rem = rem % f
		res = append(res, digits[quo])
		digits = append(digits[:quo], digits[quo+1:]...)
	}
	fmt.Println(res)
}

func fact(n int) int {
	if n < 2 {
		return 1
	}
	return n * fact(n-1)
}