summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-27 22:08:55 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-27 22:08:55 +0200
commita0698547385e2aa355c9a3c40ffdf1e0c04d63a8 (patch)
tree74b66654dd16b97890748f643508313997e0ad90
parentcd350a33c56dce01fad81fa5ebb2f1258d2f2455 (diff)
Solve luhn
-rw-r--r--go/luhn/README.md75
-rw-r--r--go/luhn/luhn.go42
-rw-r--r--go/luhn/luhn_test.go54
3 files changed, 171 insertions, 0 deletions
diff --git a/go/luhn/README.md b/go/luhn/README.md
new file mode 100644
index 0000000..ea6b72a
--- /dev/null
+++ b/go/luhn/README.md
@@ -0,0 +1,75 @@
+# Luhn
+
+Write a program that can take a number and determine whether or not it is valid per the Luhn formula.
+
+The Luhn formula is a simple checksum formula used to validate a variety
+of identification numbers, such as credit card numbers and Canadian
+Social Insurance Numbers.
+
+The formula verifies a number against its included check digit, which is
+usually appended to a partial number to generate the full number. This
+number must pass the following test:
+
+- Counting from rightmost digit (which is the check digit) and moving
+ left, double the value of every second digit.
+- For any digits that thus become 10 or more, subtract 9 from the
+ result.
+ - 1111 becomes 2121.
+ - 8763 becomes 7733 (from 2×6=12 → 12-9=3 and 2×8=16 → 16-9=7).
+- Add all these digits together.
+ - 1111 becomes 2121 sums as 2+1+2+1 to give a check digit of 6.
+ - 8763 becomes 7733, and 7+7+3+3 is 20.
+
+If the total ends in 0 (put another way, if the total modulus 10 is
+congruent to 0), then the number is valid according to the Luhn formula;
+else it is not valid. So, 1111 is not valid (as shown above, it comes
+out to 6), while 8763 is valid (as shown above, it comes out to 20).
+
+Write a program that, given a number
+
+- Can check if it is valid per the Luhn formula. This should treat, for
+ example, "2323 2005 7766 3554" as valid.
+- Can return the checksum, or the remainder from using the Luhn method.
+- Can add a check digit to make the number valid per the Luhn formula and
+ return the original number plus that digit. This should give "2323 2005 7766
+ 3554" in response to "2323 2005 7766 355".
+
+## About Checksums
+
+A checksum has to do with error-detection. There are a number of different
+ways in which a checksum could be calculated.
+
+When transmitting data, you might also send along a checksum that says how
+many bytes of data are being sent. That means that when the data arrives on
+the other side, you can count the bytes and compare it to the checksum. If
+these are different, then the data has been garbled in transmission.
+
+In the Luhn problem the final digit acts as a sanity check for all the prior
+digits. Running those prior digits through a particular algorithm should give
+you that final digit.
+
+It doesn't actually tell you if it's a real credit card number, only that it's
+a plausible one. It's the same thing with the bytes that get transmitted --
+you could have the right number of bytes and still have a garbled message. So
+checksums are a simple sanity-check, not a real in-depth verification of the
+authenticity of some data. It's often a cheap first pass, and can be used to
+quickly discard obviously invalid things.
+
+
+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
+
+The Luhn Algorithm on Wikipedia [http://en.wikipedia.org/wiki/Luhn_algorithm](http://en.wikipedia.org/wiki/Luhn_algorithm)
+
+## 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/luhn/luhn.go b/go/luhn/luhn.go
new file mode 100644
index 0000000..c8ba0ad
--- /dev/null
+++ b/go/luhn/luhn.go
@@ -0,0 +1,42 @@
+package luhn
+
+import "unicode"
+
+func normalize(s string) string {
+ var r []rune
+ for _, v := range s {
+ if unicode.IsNumber(v) {
+ r = append(r, v)
+ }
+ }
+ return string(r)
+}
+
+func chksum(s string) int {
+ var sum int
+ for i, v := range s {
+ n := int(v - '0')
+ if (len(s)-i)%2 == 0 {
+ n *= 2
+ if n > 9 {
+ n -= 9
+ }
+ }
+ sum += n
+ }
+ return sum
+}
+
+func Valid(s string) bool {
+ s = normalize(s)
+ if len(s) == 0 {
+ return false
+ }
+ return chksum(s)%10 == 0
+}
+
+func AddCheck(s string) string {
+ sum := chksum(normalize(s + "0"))
+ n := (10 - sum%10) % 10
+ return s + string('0'+n)
+}
diff --git a/go/luhn/luhn_test.go b/go/luhn/luhn_test.go
new file mode 100644
index 0000000..db7fc4a
--- /dev/null
+++ b/go/luhn/luhn_test.go
@@ -0,0 +1,54 @@
+package luhn
+
+import "testing"
+
+var validTests = []struct {
+ n string
+ ok bool
+}{
+ {"738", false},
+ {"8739567", true},
+ {"1111", false},
+ {"8763", true},
+ {" ", false},
+ {"", false},
+ {"2323 2005 7766 3554", true},
+}
+
+var addTests = []struct{ raw, luhn string }{
+ {"123", "1230"},
+ {"873956", "8739567"},
+ {"837263756", "8372637564"},
+ {"2323 2005 7766 355", "2323 2005 7766 3554"},
+ // bonus Unicode cases
+ // {"2323·2005·7766·355", "2323·2005·7766·3554"},
+ // {"123", "1230"},
+}
+
+func TestValid(t *testing.T) {
+ for _, test := range validTests {
+ if ok := Valid(test.n); ok != test.ok {
+ t.Fatalf("Valid(%s) = %t, want %t.", test.n, ok, test.ok)
+ }
+ }
+}
+
+func TestAddCheck(t *testing.T) {
+ for _, test := range addTests {
+ if luhn := AddCheck(test.raw); luhn != test.luhn {
+ t.Fatalf("AddCheck(%s) = %s, want %s.", test.raw, luhn, test.luhn)
+ }
+ }
+}
+
+func BenchmarkValid(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ Valid("2323 2005 7766 3554")
+ }
+}
+
+func BenchmarkAddCheck(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ AddCheck("2323 2005 7766 355")
+ }
+}