17
\$\begingroup\$

There are popular check digit algorithms such as Luhn and then there are good ones, for example the Damm algorithm. The only possible reason behind the popularity of algorithms such as Luhn is that there exist code golfed implementations of them. This means that we as a community have the power to change the world by providing golfed implementations of better algorithms.

So this challenge is to change the world by writing a function or a complete program in your language of choice that calculates a check digit using the Damm algorithm. The answer with the smallest number of characters (not bytes) will be chosen as a winner in a few weeks. Note that all helping functions and the declaration of the operation table must be included in the character count. In case of a tie the most popular answer will be chosen.

This algorithm revolves around an operation table that must be a weakly totally anti-symmetric quasigroup of order 10. The operation table that can be found in the Wikipedia article about the Damm algorithm is the one which is to be used in this challenge. For completeness sake I will reproduce it below:

    |   0   1   2   3   4   5   6   7   8   9
----+----------------------------------------
0   |   0   3   1   7   5   9   8   6   4   2
1   |   7   0   9   2   1   5   4   8   6   3
2   |   4   2   0   6   8   7   1   3   5   9
3   |   1   7   5   0   9   8   3   4   2   6
4   |   6   1   2   3   0   4   5   9   7   8
5   |   3   6   7   4   2   0   9   5   8   1
6   |   5   8   6   9   7   2   0   1   3   4
7   |   8   9   4   5   3   6   2   0   1   7
8   |   9   4   3   8   6   1   7   2   0   5
9   |   2   5   8   1   4   3   6   7   9   0

In short (for details see the Wikipedia article) the algorithm works as follows:

  1. You start with a list of digits to be processed and an interim digit which is set to 0.
  2. For every digit in the list you calculate a new interim digit by using the digit as the column index and the previous interim digit as the row index.
  3. The final interim digit is the check digit. If you are validating a number that already has an added check digit the final interim digit is 0 if the number is valid.

Your program or function must accept a string that can contain any characters except null, but it should only concern itself with the digits in the string. It must either print (if a program) or return (if a function) the original string with the calculated check digit appended. If you chose to write a program the program may either accept the input as an argument or as standard input. If the input string is empty or doesn't contain any digits you must return or append a zero.

Some examples:

Input       |   Output
------------+-------------
42          |   427
427         |   4270
2 to 2      |   2 to 29
23 42 76-   |   23 42 76-5
-           |   -0
\$\endgroup\$
  • \$\begingroup\$ I look forward to seeing the Piet entries claiming the win. \$\endgroup\$ – Alchymist Apr 1 '15 at 15:15
3
\$\begingroup\$

Pyth, 49 characters

+z`u@sm>+0jCdT_6"Ľ򒉲򭉟񶯆𐱩򐞆󰆂򕟐򑽌򵋏󇋽򯴆󚙈𱑂񞑼쵥񪨶"+*TGvH:z"\D"k0

Contains god knows what characters, so here's a Python3 program to generate the above program accurately on your machine:

N = 317598642709215486342068713591750983426612304597836742095815869720134894536201794386172052581436790
M = 1000000
l = []
while N:
    l.insert(0, N % M)
    N //= M

n = "".join(chr(c) for c in l)

s = '+z`u@sm>+0jCdT_6"' + n + '"+*TGvH:z"\D"k0'

with open("golf.pyth", "wb") as f:
    f.write(s.encode("utf-8"))

print("Program length is {} characters.".format(len(s)))

Explanation:

+z`                                     Output the input followed by a
                                        stringified...
   u                         :z"\D"k0   Reduction starting with 0 of digits
                                        in input...
    @                  +*TGvH           Indexing ... by 10*prev + int(next).
     sm         "ZALGO"                 Sum all digits created by ... over the
                                        unicode garbage.
       >+0     6                        Prepend 0 if needed to...
          jCdT_                         Codepoint converted to sequence of
                                        digits.
\$\endgroup\$
3
\$\begingroup\$

CJam, 54 characters

q_o{A,s&},{~0"끼´慜䪝膞䝮芜㮜ꡞ靓渏縰蒆㣉倔쵶"2G#bAb+A/T==:T;}/T

There is one unprintable character in there, so you might want to use the permalink below.

Test it here.

Explanation

The interim digit is being tracked in T, which CJam initialises to 0.

q_o                                  "Read STDIN, duplicate it and print it.";
   {A,s&},                           "Filter out all non-digit characters.";
          {                     }/   "For each digit character.";
           ~                         "Eval to get the digit itself.";
            0                        "Push a zero.";
             "..."2G#b               "Push that long string and interpret the character
                                      codes as the digits of a base-2^16 number.";
                      Ab+            "Get base-10 digits and prepend the 0.";
                         A/          "Split into rows of 10.";
                           T=        "Select row based on interim digit.";
                             =       "Select column based on current digit.";
                              :T;    "Store in T and discard.";
                                   T "Push the interim digit to be printed.";
\$\endgroup\$
3
\$\begingroup\$

Python 3, 149 141 138 characters

import re
l=""
for c in"ĽᝢႮ⏿ዿၮ∉᜝Ꮺൢ៫Njẜ᳼╭᛭ᰡඡᆸߡⓞ᠜ȍ῏᪆":l+="%04d"%ord(c)
def D(b):
 a="0"
 for i in re.sub("\D","",b):a=l[int(a+i)]
 return b+a

Examples:

 Input | Output
-------+--------
    42 | 427
   427 | 4270
2 to 2 | 2 to 29
   123 | 1234
  1234 | 12340
     - | -0

Thanks to @MegaTom and @Sieg for helping to remove a total of 11 characters

\$\endgroup\$
  • 2
    \$\begingroup\$ 10*int(a)+int(i) is int(a+i), is it not? \$\endgroup\$ – MegaTom Mar 30 '15 at 17:01
  • \$\begingroup\$ Good point! Thank you, that saves 5 chars. \$\endgroup\$ – monopole Mar 30 '15 at 21:16
  • 1
    \$\begingroup\$ For followed by a single statement doesn't need a newline in between. (-3) \$\endgroup\$ – seequ Mar 31 '15 at 19:35
2
\$\begingroup\$

Ruby, 149 characters

i="0";t="0#{'2uleblnnz0nbpv3kqkaufbjqebm57jdj6ubaba1mc2fyucqff69tbllrcvw393li'.to_i 36}";puts(gets.chomp.each_char{|c|i=(c=~/\d/?t[(i+c).to_i]:i)}+i)

Tested on repl.it

\$\endgroup\$
2
\$\begingroup\$

J, 117 bytes

Contains only printable ascii. (I had a hard time with J and unicode.) Generates the transition table from the permutation-indices of the rows.

3 :'y,":(((_4(87)&#:inv\40-~a.i.''(3/3+wGf*Dl:(zaW+Hhw*(1p+;~.,y>m-<MZ)JCs'')A.i.10){~<@,~)/|.0,(#~10>])(1":i.10)i.y'

Usage:

   damm=.3 :'y,":(((_4(87)&#:inv\40-~a.i.''(3/3+wGf*Dl:(zaW+Hhw*(1p+;~.,y>m-<MZ)JCs'')A.i.10){~<@,~)/|.0,(#~10>])(1":i.10)i.y'

   damm '23 42 76-'
23 42 76-5

   damm ''
0

Try it online here.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 131 characters

import Data.Char
f n=n++(show$foldl(\x y->read[('0':(show.ord=<<"౧⚈ક×ዿၮ∉ɏᵕₖ᧔İɕSʢ凞㷽ᰡ衎텴䘗↩倭῏᪆"))!!(x*10+y)])0[read[i]|i<-n,isDigit i])

Test run:

> mapM_ (putStrLn.f) ["42", "427", "2 to 2", "23 42 76-", "-"]
427
4270
2 to 29
23 42 76-5
-0
\$\endgroup\$
0
\$\begingroup\$

k, 36 characters

/ declare quasi-group  
M:"H"$'"0317598642709215486342068713591750983426612304597836742095815869720134894536201794386172052581436790"

/ declare function
  f:{x,$0{M y+10*x}/"H"$'x@&x in .Q.n}

/ get length of function
  #$f
36

/ execute function against test input
  .q.show f@'{x!x}("42";"427";"2 to 2";"23 42 76-";,"-")
"42"       | "427"
"427"      | "4270"
"2 to 2"   | "2 to 29"
"23 42 76-"| "23 42 76-5"
,"-"       | "-0"

q, 40 characters (equivalent implementation to k)

 f:{x,string 0{M y+10*x}/"H"$'x inter .Q.n}
\$\endgroup\$
  • 1
    \$\begingroup\$ I must say I admire the use of a questionable loop-hole in the rules, but I really do must clarify the rules to enforce the inclusion of the declaration of the quasi-group and the declaration of any kind of helping function in the character count. \$\endgroup\$ – Fors Apr 2 '15 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.