Thursday, August 29, 2013

Some nice, simple stuff - Problem 32 in Go.

After freeing up Go with my Shakespeare solution, I decided to solve another problem with it. This was just some nice simple programming, while getting to learn some more features of Go - I wouldn't mind getting another chance to use Go again. The problem was to find all numbers that are part of a 1-9 pandigital product (that is, a product P with X x Y = P such that the concatenation of the digits in X, Y, and P contains exactly the digits 1-9 occurring exactly once) - notably my upper bounds that I established are very rough and could be lowered, but nonetheless, this solution ran in about 1.5s on my computer.
package main

import "fmt"
import "sort"

func getDigits(x int) []int {
    d := []int{}
    for x > 0 {
        d = append(d, x % 10)
        x /= 10
    }
    return d
}

func pandigitalProduct(x int, y int) (bool, int) {
    prod   := x * y

    digits := []int{}
    digits  = append(digits, getDigits(x)...)
    digits  = append(digits, getDigits(y)...)
    digits  = append(digits, getDigits(prod)...)
    sort.Ints(digits)
    if len(digits) == 9 {
        for i, value := range digits {
            if value != i + 1 {
                return false, 0
            }
        }
        return true, prod
    }
    return false, 0
}
func contains(lst []int, x int) bool {
    for _, value := range lst {
        if value == x {
            return true
        }
    }
    return false
}
func main() {
    validProds := []int{}
    for i := 0; i < 10000; i += 1 {
        for j := i; j < 10000; j += 1 {
            isPandigital, product := pandigitalProduct(i, j)
            if isPandigital && !contains(validProds, product) {
                validProds = append(validProds, product)
            }
            if j * i > 100000 {
                break
            }
        }
    }
    sum := 0
    for _, num := range validProds {
        sum += num
    }
    fmt.Println(sum)
}

No comments:

Post a Comment