Luhn Algorithm in JavaScript, Python, & Clojure: Part 1

The Big Man Himself: Hans Peter Luhn

Over the past few months many of my friends at university have asked me for programming advice ranging from small questions about CS101 problem sets to asking for help on technical interview questions. Due to the fact that I’m unemployed and have become incredibly efficient at acing my online community college courses over the past few months, I agreed to help. One question that appeared multiple times across a wide variety of CS101-type courses was the famous Luhn algorithm implementation.

The Luhn algorithm is a simple checksum formula used mainly at this point to check if people enter their credit card number in right as it’s not too cryptographically secure. In fact, checksum algorithms by themselves are actually just used to detect errors in the transmission of data rather than actually verify the authenticity of data. For those interested in how data actually gets secured today, check out Bruce Schneier’s books or my new favorite, Serious Cryptography, by Jean-Philippe Aumasson.

Alright, for those who just want to submit their PSet in time, here are the steps to this formula.

Given a sequence of digits:

1. Double every second digit, starting from the right.
2. If doubling the digit results in a number greater than 9, subtract 9 from the product
3. Find the sum all of the digits
4. If the sum is evenly divisible by 10, then the sequence / card number is valid.

I want to approach this problem in a few ways using a couple different languages as per the title of this article in order to really illustrate what each language offers in terms of benefits while at the same time showing you how to think computationally beyond the box of a specific programming language.

The Imperative Approach in JavaScript

First I want to approach this problem imperatively (mostly) using JavaScript. This won’t give us the most “elegant” solution, but it will give us a solid foothold in tackling this problem. Before that though, let’s establish our two baseline test-cases. I encourage you to add more test-cases, especially edge cases that can break your program. I’m just using these for the sake of simplicity and brevity.

isValid("4539148803436467") // true
isValid("8273123273520569") // false

Now let’s implement the first version of our isValid() function, which will accomplish the goals of the algorithm stated above. First let’s setup our function and initialize the array we will use to store our digits before finding the sum of them.

const isValid = n => {
  const arr = []
}

Next let’s setup a for-loop to iterate through each digit in our “number,” which by the way is actually a string due to the fact that this data would most likely be received through user input.

const isValid = n => {
  const arr = [];
  for (let i = 0; i < n.length; i++) {
    // do something to the digits and add them each to arr
  }
  // return sum of arr
}

The first thing we need to do is determine whether the digit we are looking at is an odd or even digit, or in the context of the array, whether the index i is odd or even. We can test this using an if-else statement to separate the actions we need to take in the case of an odd or even digit by testing for evenness using the modulo operator.

const isValid = n => {
  const arr = [];
  for (let i = 0; i < n.length; i++) {
    if (i % 2 == 0) {
      // double digit according to formula and add to arr
    } else {
      // add digit to arr
    }
  }
  // return sum of arr
}

Now we need to create another if-else statement within our current if block in order to tackle the case of a doubled digit being larger than 9. Then if it is, we can subtract 9 from the digit and add it to the array. If the doubled digit is less than 10, we can simply add it the array. To add the digit to the array, we will use the push method as the const declaration makes arr a read only reference to the actual array, essentially making:

arr +=

Invalid. Now let’s just implement the second if-else expression.

const isValid = n => {
  const arr = [];
  for (let i = 0; i < n.length; i++) {
    if (i % 2 == 0) {
      if (card[i]*2 < 10) {
        arr.push(card[i]*2)
      } else {
        arr.push(card[i]*2-9)
      }
    } else {
      // add digit to arr
    }
  }
  // return sum of arr
}

It’s important to note that the reason I don’t have to explicitly convert each digit, which once again is really a character within a string, to a number is that JavaScript’s data type coercion does this for us. That being said, trusting JavaScript’s type coercion to always give you the values you want is a bad programming practice and can lead to some very disastrous outcomes. I’m just doing this to show an unique aspect of the language.

Now we just need to push each odd digit to the array. However, in this case if simply type:

else {
  arr.push(card[i])
}

JavaScript’s type coercion will actually not save us and a character / string will be pushed to the array instead of a number. To fix this, we need to explicitly convert the char to a number using the built in function parseInt().

This function takes two arguments, a string and a radix, or base. In this case, we are using the common base 10 system so we just need to type:

else {
  arr.push(parseInt(card[i],10))
}

At this point, your program should look pretty close to this:

const isValid = card => {
  const arr = []
  for (let i = 0; i < card.length; i++) {
    if (i % 2 == 0) {
      if (card[i]*2 < 10) {
        arr.push(card[i]*2);
      } else {
        arr.push(card[i]*2-9);
      }
    } else {
      arr.push(parseInt(card[i],10))
    }
  }
  // return sum of arr
}

Now we just need to find the sum of arr and return it. When many people first start learning JavaScript, they create a sum function that looks something like this:

function sumOfArr(arr) {
  var sum = 0;
  for (var i = 0; i < arr.length; i++) {
    sum += arr[i]
  }
  return sum
}

We could do something like that here in our program but let’s use something more efficient and cleaner. Let’s use the wonderful built-in array method reduce().

This function allows us to apply a callback function against an accumulator across each value of an array. The accumulator here represents our sum, with our callback function body adding the current value to the sum as it iterates through the array. What we wrote above can now be condensed down to:

arr.reduce( (prv, cur) => prv + cur)

If you’re still confused on reduce, take a look through this.

Now that we can find our sum we just need to check if it is divisible by 10 as per Luhn’s formula. We can do so using a modulo operator like this:

arr.reduce( (prv, cur) => prv + cur) % 10 === 0

To put it all together:

const isValid = card => {
  const arr = []
  for (let i = 0; i < card.length; i++) {
    if (i % 2 == 0) {
      if (card[i]*2 < 10) {
        arr.push(card[i]*2);
      } else {
        arr.push(card[i]*2-9);
      }
    } else {
      arr.push(parseInt(card[i],10))
    }
  }
  return arr.reduce( (prv, cur) => prv + cur) % 10 === 0;
}

This program works but I want to show you a more elegant and efficient solution that makes use of some more built-in array methods, a helper function, and different way of writing if-else statements.

The Functional(ish) Approach in JS

This is going to be our final result:

const calc = e => (e*2 < 10) ? e*2 : e*2-9;
const isValid = card => {
  return card.split("")
  .map( (e,i) => (i % 2 == 0) ? calc(e): parseInt(e))
  .reduce( (prv, cur) => prv + cur) % 10 == 0
}

This probably looks like gibberish for the most part and that’s okay right now. Before I go into the nitty gritty of explaining each block of code, I want to explain how I approached writing this solution over the first solution. The first thing I did here was notice the calculation required for even digits. It’s a somewhat complex calculation at least compared to the odd digit calculation, which simply just returns the digit to the array. While the helper function, calc(), wasn’t essential, especially given how small this problem is compared to the some more difficult programming problems and even code infrastructures you might work on later, building these habits of simplifying problems down to their essential required calculations is an excellent habit to start now.

Now as to the array methods used here, once again I used .reduce() to calculate the sum of the array but this time I created our array by actually splitting our string argument into an array of characters using .split(). I then applied the built-in array method .map() to iterate through our newly created array of characters, which is actually what .split() returns here, and perform the necessary calculations. The .map() function return a new array with the results of a callback function being applied across every element of the array. The callback function also takes more optional arguments beyond the required current value argument like the current index argument. The current index argument here is i while the current value argument is e. The functions .map() and .split() are essentially accomplishing the task of the for-loop in our first program in a more elegant solution by using the built-in array methods JavaScript gives us.

Finally, I used a ternary operator.

(test case) ? returnValueIfTrue : returnValueIfFalse

I used this in order to fill the role of our previous if-else statements. Left of the question marks represents our conditional test, while the left of the colon represents the if block and the right of the colon represents the else block. Despite these comparisons, the ternary operator is not the same thing as an if-else statement as is actually closer to the logical operators. In fact, the ternary operator is the only operator that takes three operands.

This code is okay, but in many ways it’s still inefficient. Before moving onto the final approach, take a second to try to implement a more efficient solution.

The Final JavaScript Approach

I want to take one more time to use JavaScript to solve this problem in order to illustrate how we can simplify our program even further. Once again I will show the final result as I did before and then explain my thought process:

const calc = e => (e*2 < 10) ? e*2 : e*2-9;
const bestValid = card => card.split("").reduce( (sum, cur, i) => {
  return i % 2 == 0 ? calc(cur): parseInt(cur) + sum
},0) % 10 == 0;

So what did I do that was different compared to our to previous versions of this program?

I combined the process of calculating the digits and summing them at the same time, overall making it more efficient and in my opinion, simpler to understand. The array uses the same .calc() helper function as before but I removed the .map() and instead performed the digit calculation during the summation process in .reduce(). One thing to note is that I put a zero after the end of our callback function within .reduce(). The reason for this is that .reduce() with just a callback function will return an error if the array it is being applied to is empty as it will not have any value to return. To deal with this case, I put a starting value of zero to prevent this potential bug.

This program is still not perfect. For instance, it doesn’t take into account of potential whitespace between groups of digits nor does properly notify a user if the input is incorrectly entered. In fact, it doesn’t even have a user input function at the moment as we’ve simply given our test cases within the arguments of isValid. However, this does not necessarily mean we need to create a gigantic function, but rather we simply need to create a separate input function that checks for whitespace and notifies the user in case of bad input along with another main function that can tie the input function and isValid function together.

Moving Forward

By creating small and pure functions with clear and specific purposes, we can start to approach problems like a functional programmer.

In the next part of this article, I want to go over how can solve this problem using Clojure, a truly functional programming language and really explain what that means beyond “little pure functions” and “lots of array methods.” Then we’ll take one more shot at this problem using Python and some its respective benefits, which include a wonderful piece of magic called list comprehensions.

Leave a comment if you find something confusing or even want to correct me on something. See you soon.