121 lines
2.9 KiB
Go
121 lines
2.9 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"time"
|
|
)
|
|
|
|
type result struct {
|
|
n int
|
|
nine [9]int
|
|
}
|
|
|
|
func indexOf(n int, s []int) int {
|
|
for i, j := range s {
|
|
if n == j {
|
|
return i
|
|
}
|
|
}
|
|
return -1
|
|
}
|
|
|
|
func bIndexOf(b bool, s []bool) int {
|
|
for i, j := range s {
|
|
if b == j {
|
|
return i
|
|
}
|
|
}
|
|
return -1
|
|
}
|
|
|
|
func toNumber(digits []int, removeDigit int) int {
|
|
digits2 := digits
|
|
if removeDigit != 0 {
|
|
digits2 = make([]int, len(digits))
|
|
copy(digits2, digits)
|
|
d := indexOf(removeDigit, digits2)
|
|
copy(digits2[d:], digits2[d+1:])
|
|
digits2[len(digits2)-1] = 0
|
|
digits2 = digits2[:len(digits2)-1]
|
|
}
|
|
res := digits2[0]
|
|
for i := 1; i < len(digits2); i++ {
|
|
res = res*10 + digits2[i]
|
|
}
|
|
return res
|
|
}
|
|
|
|
func nDigits(n int) []result {
|
|
var res []result
|
|
digits := make([]int, n)
|
|
var used [9]bool
|
|
for i := 0; i < n; i++ {
|
|
digits[i] = i + 1
|
|
used[i] = true
|
|
}
|
|
for {
|
|
var nine [9]int
|
|
for i := 0; i < len(used); i++ {
|
|
if used[i] {
|
|
nine[i] = toNumber(digits, i+1)
|
|
}
|
|
}
|
|
res = append(res, result{toNumber(digits, 0), nine})
|
|
found := false
|
|
for i := n - 1; i >= 0; i-- {
|
|
d := digits[i]
|
|
if !used[d-1] {
|
|
panic("something went wrong with 'used' array")
|
|
}
|
|
used[d-1] = false
|
|
for j := d; j < 9; j++ {
|
|
if !used[j] {
|
|
used[j] = true
|
|
digits[i] = j + 1
|
|
for k := i + 1; k < n; k++ {
|
|
digits[k] = bIndexOf(false, used[:]) + 1
|
|
used[digits[k]-1] = true
|
|
}
|
|
found = true
|
|
break
|
|
}
|
|
}
|
|
if found {
|
|
break
|
|
}
|
|
}
|
|
if !found {
|
|
break
|
|
}
|
|
}
|
|
return res
|
|
}
|
|
|
|
func main() {
|
|
start := time.Now()
|
|
for n := 2; n <= 5; n++ {
|
|
rs := nDigits(n)
|
|
count := 0
|
|
var omitted [9]int
|
|
for i := 0; i < len(rs)-1; i++ {
|
|
xn, rn := rs[i].n, rs[i].nine
|
|
for j := i + 1; j < len(rs); j++ {
|
|
xd, rd := rs[j].n, rs[j].nine
|
|
for k := 0; k < 9; k++ {
|
|
yn, yd := rn[k], rd[k]
|
|
if yn != 0 && yd != 0 &&
|
|
float64(xn)/float64(xd) == float64(yn)/float64(yd) {
|
|
count++
|
|
omitted[k]++
|
|
if count <= 12 {
|
|
fmt.Printf("%d/%d => %d/%d (removed %d)\n", xn, xd, yn, yd, k+1)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
fmt.Printf("%d-digit fractions found:%d, omitted %v\n\n", n, count, omitted)
|
|
}
|
|
fmt.Printf("Took %s\n", time.Since(start))
|
|
}
|