Posts Tagged ‘credit’

Programming Praxis – Credit Card Validation

April 8, 2011

In today’s Programming Praxis exercise our goal is to write to functions related to the Luhn credit card number verification algorithm: one to check if a number is valid and one to make a valid number from a given number by adding one digit. Let’s get started, shall we?

Some imports:

import Data.Char
import Data.List.HT
import Test.QuickCheck

For both functions we need to calculate the Luhn sum of a number, so let’s start with that. This one simply follows the description given in the exercise text. You could probably speed it up a bit by replacing the multiplication with a lookup table.

luhnSum :: Integral a => a -> a
luhnSum n = digitSum a + digitSum (show . (* 2) . digitToInt =<< b)
    where [a,b] = sliceHorizontal 2 . reverse $ show n
          digitSum = sum . map (fromIntegral . digitToInt)

Checking if a number is valid is trivial: just see if the Luhn sum is zero.

isValid :: Integral a => a -> Bool
isValid n = mod (luhnSum n) 10 == 0

Making a valid number means adding the complement of the Luhn sum of 10 times the number (to account for the digit that will be added on the end) to the end of the number. The outer modulo is to account for the case where the Luhn sum is zero.

makeValid :: Integral a => a -> a
makeValid n = 10*n + mod (10 - mod (luhnSum $ 10*n) 10) 10

Some testing to see if everthing is working properly:

prop_luhn :: Integer -> Property
prop_luhn n = n >= 0 ==> isValid (makeValid n)

main :: IO ()
main = do print $ isValid 0
          print $ isValid 34
          print $ isValid 117
          print $ isValid 49927398716
          print . not $ isValid 49927398715
          print $ makeValid 4992739871 == 49927398716
          quickCheck prop_luhn

Yup. Have fun committing credit card fraud 🙂

Programming Praxis – Google Code Jam Qualification Round Africa 2010

February 15, 2011

In today’s Programming Praxis exercise, our goal is to solve three Google Code Jam assignments. Let’s get started, shall we?

A quick import:

import Data.List

For the store credit exercise, we simply test all unique combinations of two items to see which add up to the correct total and return the first one.

storeCredit :: Num a => a -> [a] -> (Int, Int)
storeCredit c xs = head [ (i, j) | (i, a) <- zip [1..] xs
                        , (j, b) <- drop i $ zip [1..] xs, a + b == c]

Reversing the words in a sentence is trivial: make a list of words, reverse it and assemble them together again.

reverseWords :: String -> String
reverseWords = unwords . reverse . words

The T9 assignment is a bit more complicated. First, we find the correct sequence of digits for each character of the input. Then we add spaces between each consecutive group of identical digits, except between consecutive zeros.

t9 :: String -> String
t9 s = unwords =<< groupBy (\(a:_) (b:_) -> a == b && a > '0') (map f s)
    where f c = maybe "0" id . lookup c . concat $ zipWith zip
                    (words "abc def ghi jkl mno pqrs tuv wxyz")
                    [[replicate n d | n <- [1..]] | d <- ['2'..]]

Some tests to see if we made any mistakes:

main :: IO ()
main = do print $ storeCredit 100 [5,75,25] == (2,3)
          print $ storeCredit 200 [150,24,79,50,88,345,3] == (1,4)
          print $ storeCredit 8 [2,1,9,4,4,56,90,3] == (4,5)
          print $ reverseWords "this is a test" == "test a is this"
          print $ reverseWords "foobar" == "foobar"
          print $ reverseWords "all your base" == "base your all"
          print $ t9 "hi" == "44 444"
          print $ t9 "yes" == "999337777"
          print $ t9 "foo  bar" == "333666 6660022 2777"
          print $ t9 "hello world" == "4433555 555666096667775553"

Nope, looks like everything is working properly.