Luhn Algorithm
Easy credit card number validation
Luhn Algorithm is a formula for checksumming credit card numbers. It won’t tell you whether the right card number was entered nor whether the card can Auth, but it will tell you whether the number is a valid card number. So it’s a useful input validation to verify someone didn’t typo their card or simply send you garbage data.
I once used Luhn in a SaaS security scanner product to narrow down lists of potentially leaked credit card numbers in cloud storage. I think that might be the less common use case.
Wikipedia describes the formula like this…
From the rightmost digit (excluding the check digit) and moving left, double the value of every second digit. The check digit is neither doubled nor included in this calculation; the first digit doubled is the digit located immediately left of the check digit. If the result of this doubling operation is greater than 9 (e.g., 8 × 2 = 16), then add the digits of the result (e.g., 16: 1 + 6 = 7, 18: 1 + 8 = 9) or, alternatively, the same final result can be found by subtracting 9 from that result (e.g., 16: 16 − 9 = 7, 18: 18 − 9 = 9).
Take the sum of all the digits.
If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; otherwise it is not valid.
Lets take a shot at what that might look like in range-v3-land.
LOOK AT THOSE PIPES THOUGH. Okay. Get it together.
Starting from line eleven. First things first. Let’s iterate that string and generate a list of digits. Transform calls the to_int lambda from line two. So let’s dig into that as well.
Why do we subtract 48 from each character? Well… On the ASCII table 48 is the value for ‘0'. So 48 + 1 = 49 = ‘1’. 48 + 2 = 50 = ‘2’. And so on up to 9. Conversely, ‘2’ AKA 50 MINUS 48 = 2. Like the actual number 2. Not the encoded text. Since we’re only concerned with single digit numbers in this formula, this applies to Unicode as well. std::stoul would still be better, but this was more fun, right?
So now we have our list of digits. Let’s look at line twelve. Remember how we were supposed to start from the right hand side. Do you have time for that? No. Just reverse the whole list. IDGAF. Pipe the list into views::reverse and move on with your life.
Line thirteen. You also recall that the instructions for odd and even digits were different. You could use digits | views::stride(2) and digits | views::drop(1) | views::stride(2) to get discrete lists of odd and even digits. Sounds ugly. Instead call views::enumerate to zip each value up with its index and mod 2 that index later.
Line fourteen. Our intrepid hero Transform is back. But whats this? It calls a lambda which accepts a tuple, feeds it to a ternary, and then captures yet another lambda. Do you really want an explanation of the ugliest part of this whole file? F$&%! Okay. Here we go.
- Line six is the key to piping zip into transform. Burn it into your brain for later.
- index % 2 == 0 lets us know whether we’re an odd or even digit. Not the digit itself, but you get the idea: where the digit lies in the card number.
- Multiply every even digit by 2. Then hit it with that digit summing lambda.
- n / 10 + n % 10 saves you from actually turning 8 * 2 = 16 into a string, then turning the digits back into the numbers 1 & 6, only to add them up and get 7. Isn’t that neat? I guess. I need a margarita.
- You finally made it to line sixteen. Accumulate sums our list. Why can’t you pipe into accumulate? You just can’t. Get over it. Why are you so demanding?
- Is the sum divisible by 10? Yes? Good. Does this remind you of RTN checksums? It should.
I’m done. Let’s all get drinks when quarantine is lifted. Maybe someone can also explain to me the actual time complexity of this solution. I don’t have a clue.
