summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-28 00:23:47 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-28 00:23:47 +0200
commit6a5bafe3d99c26e78c4ce240eb54a917259a9861 (patch)
tree9f7be1a2c46e6bab9b3ae976379c91b45c56524a
parenta593ae4ca4e3af5c419461284c97a6cc91466d1b (diff)
Solve palindrome
-rw-r--r--go/palindrome-products/README.md24
-rw-r--r--go/palindrome-products/palindrome_products.go53
-rw-r--r--go/palindrome-products/palindrome_products_test.go98
3 files changed, 175 insertions, 0 deletions
diff --git a/go/palindrome-products/README.md b/go/palindrome-products/README.md
new file mode 100644
index 0000000..9c404da
--- /dev/null
+++ b/go/palindrome-products/README.md
@@ -0,0 +1,24 @@
+# Palindrome Products
+
+Write a program that can detect palindrome products in a given range.
+
+A palindromic number reads the same both ways. The largest palindrome
+made from the product of two 2-digit numbers is 9009 = 91 x 99.
+
+To run the tests simply run the command `go test` in the exercise directory.
+
+If the test suite contains benchmarks, you can run these with the `-bench`
+flag:
+
+ go test -bench .
+
+For more detailed info about the Go track see the [help
+page](http://exercism.io/languages/go).
+
+## Source
+
+Problem 4 at Project Euler [http://projecteuler.net/problem=4](http://projecteuler.net/problem=4)
+
+## Submitting Incomplete Problems
+It's possible to submit an incomplete solution so you can see how others have completed the exercise.
+
diff --git a/go/palindrome-products/palindrome_products.go b/go/palindrome-products/palindrome_products.go
new file mode 100644
index 0000000..42e7bc4
--- /dev/null
+++ b/go/palindrome-products/palindrome_products.go
@@ -0,0 +1,53 @@
+package palindrome
+
+import (
+ "errors"
+ "strconv"
+)
+
+type Product struct {
+ Product int
+ Factorizations [][2]int
+}
+
+func Products(fmin, fmax int) (pmin, pmax Product, err error) {
+ fail := func(s string) (Product, Product, error) {
+ return Product{}, Product{}, errors.New(s)
+ }
+ if fmin > fmax {
+ return fail("fmin > fmax...")
+ }
+
+ pmin.Product = fmax * fmax
+ pp := make(map[int][][2]int)
+
+ for i := fmin; i <= fmax; i++ {
+ for j := i; j <= fmax; j++ {
+ if v := i * j; isPalindrom(v) {
+ pp[v] = append(pp[v], [2]int{i, j})
+ if v < pmin.Product {
+ pmin.Product = v
+ }
+ if v > pmax.Product {
+ pmax.Product = v
+ }
+ }
+ }
+ }
+ if len(pp) == 0 {
+ return fail("No palindromes...")
+ }
+ pmin.Factorizations = pp[pmin.Product]
+ pmax.Factorizations = pp[pmax.Product]
+ return
+}
+
+func isPalindrom(n int) bool {
+ s := strconv.Itoa(n)
+ for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
+ if s[i] != s[j] {
+ return false
+ }
+ }
+ return true
+}
diff --git a/go/palindrome-products/palindrome_products_test.go b/go/palindrome-products/palindrome_products_test.go
new file mode 100644
index 0000000..49b70ca
--- /dev/null
+++ b/go/palindrome-products/palindrome_products_test.go
@@ -0,0 +1,98 @@
+package palindrome
+
+import (
+ "fmt"
+ "reflect"
+ "strings"
+ "testing"
+)
+
+// API to impliment:
+// type Product struct {
+// Product int // palindromic, of course
+// // list of all possible two-factor factorizations of Product, within
+// // given limits, in order
+// Factorizations [][2]int
+// }
+// func Products(fmin, fmax int) (pmin, pmax Product, error)
+
+var testData = []struct {
+ // input to Products(): range limits for factors of the palindrome
+ fmin, fmax int
+ // output from Products():
+ pmin, pmax Product // min and max palandromic products
+ errPrefix string // start of text if there is an error, "" otherwise
+}{
+ {1, 9,
+ Product{}, // zero value means don't bother to test it
+ Product{9, [][2]int{{1, 9}, {3, 3}}},
+ ""},
+ {10, 99,
+ Product{121, [][2]int{{11, 11}}},
+ Product{9009, [][2]int{{91, 99}}},
+ ""},
+ {100, 999,
+ Product{10201, [][2]int{{101, 101}}},
+ Product{906609, [][2]int{{913, 993}}},
+ ""},
+ {4, 10, Product{}, Product{}, "No palindromes"},
+ {10, 4, Product{}, Product{}, "fmin > fmax"},
+ /* bonus curiosities. (can a negative number be a palindrome?
+ // most say no
+ {-99, -10, Product{}, Product{}, "Negative limits"},
+ // but you can still get non-negative products from negative factors.
+ {-99, -10,
+ Product{121, [][2]int{{-11, -11}}},
+ Product{9009, [][2]int{{-99, -91}}},
+ ""},
+ {-2, 2,
+ Product{0, [][2]int{{-2, 0}, {-1, 0}, {0, 0}, {0, 1}, {0, 2}}},
+ Product{4, [][2]int{{-2, -2}, {2, 2}}},
+ ""},
+ // or you could reverse the *digits*, keeping the minus sign in place.
+ {-2, 2,
+ Product{-4, [][2]int{{-2, 2}}},
+ Product{4, [][2]int{{-2, -2}, {2, 2}}},
+ ""},
+ {
+ {0, (^uint(0))>>1, Product{}, Product{}, "This one's gonna overflow"},
+ */
+}
+
+func TestPalindromeProducts(t *testing.T) {
+ for _, test := range testData {
+ // common preamble for test failures
+ ret := fmt.Sprintf("Products(%d, %d) returned",
+ test.fmin, test.fmax)
+ // test
+ pmin, pmax, err := Products(test.fmin, test.fmax)
+ switch {
+ case err == nil:
+ if test.errPrefix > "" {
+ t.Fatalf(ret+" err = nil, want %q", test.errPrefix+"...")
+ }
+ case test.errPrefix == "":
+ t.Fatalf(ret+" err = %q, want nil", err)
+ case !strings.HasPrefix(err.Error(), test.errPrefix):
+ t.Fatalf(ret+" err = %q, want %q", err, test.errPrefix+"...")
+ default:
+ continue // correct error, no further tests for this test case
+ }
+ matchProd := func(ww string, rp, wp Product) {
+ if len(wp.Factorizations) > 0 && // option to skip test
+ !reflect.DeepEqual(rp, wp) {
+ t.Fatal(ret, ww, "=", rp, "want", wp)
+ }
+ }
+ matchProd("pmin", pmin, test.pmin)
+ matchProd("pmax", pmax, test.pmax)
+ }
+}
+
+func BenchmarkPalindromeProducts(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ for _, test := range testData {
+ Products(test.fmin, test.fmax)
+ }
+ }
+}