From 6a5bafe3d99c26e78c4ce240eb54a917259a9861 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sun, 28 Aug 2016 00:23:47 +0200 Subject: Solve palindrome --- go/palindrome-products/README.md | 24 ++++++ go/palindrome-products/palindrome_products.go | 53 ++++++++++++ go/palindrome-products/palindrome_products_test.go | 98 ++++++++++++++++++++++ 3 files changed, 175 insertions(+) create mode 100644 go/palindrome-products/README.md create mode 100644 go/palindrome-products/palindrome_products.go create mode 100644 go/palindrome-products/palindrome_products_test.go (limited to 'go/palindrome-products') 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) + } + } +} -- cgit v1.2.3