It’s Friday, and time again for a new Fragment: my weekly programming-related puzzle.
This Week’s Fragment
“I knew I couldn’t trust that guy!”, exclaimed Joe the Plumber, having just returned from selling left-handed monkey wrenches at the pipe fitters’ convention. “I sold a wrench to this guy, Pierre Lefebvre, who didn’t have enough cash, nor have his checkbook or credit card with him. So I had him write his account information for both on a sheet of paper and give it to me. The checking account information is bad (my bank says that the routing number, 374088048, is invalid), and the paper is torn such that I don’t have the last digit of the credit card number, just 4754 2700 7476 257.”
Inspector Lestrade took one look at the paper and responded, “I can tell you the correct checking number or credit card number, or both. Which would you like?”
How did Lestrade do it? Can you determine the correct numbers?
If you want to “play along”, post a solution as a comment or send it via email. To avoid “spoilers”, simply don’t expand comments for this post. For an extra challenge, try writing code to correct the numbers or at least prove that the numbers you chose were valid. Maybe one day a plumber will thank you.
Last Week’s Fragment – Solution
Last week’s puzzle was “borrowed” from a recent Car Talk puzzler; here’s the gist:
You have 13 bottles of wine, and have been tipped off that one of them is tainted with a deadly poison: so deadly that one drop can kill a person or large animal within 24 hours. With the help of four lab rats, how can you determine which one contains the fatal potion within one day?
The solution requires giving some rats wine from multiple bottles, and since the poison is so deadly, a little dab’ll do ya’ (or do in a rat). Joel proposed a “divide and conquer” or “binary search” approach, which is nice and elegant and does the job (it’s also the solution I first thought of when I heard this on Car Talk). But there’s only time for one round of testing, so you’ll have to throw all four rats at the problem at once.
Thinking in binary is the right approach. Number the bottles 1-13 and represent each number in binary: 0001 through 1101. Assign each of the four rats to one of the binary “positions”; let’s call them “A” in the one’s position, “B” in the two’s position, “C” in the four’s position, and “D” in the eight’s position. And dole out the wine based on the binary representation of each bottle number. For example, bottle number 1 goes to rat A, bottle 2 to rat B, bottle 3 (binary 0011) to rats A and B, and so on up to bottle 13 (binary 1101) given to rats A, C, and D. The rats that kill over will identify the bottle number.
Wayne posted this solution and should probably get a bottle of poisoned Quivira wine as a prize. Both Wayne and Joel noted that we could take on up to 16 bottles of wine with this solution, but I went with Car Talk’s lucky thirteen to keep it interesting.
The last digits of credit card numbers are just checksums of some sort. I can’t remember the particular algorithm, but it is easy to calculate what it should be. I suppose that the routing numbers are the same way, but I didn’t know that.
Many years ago, I encountered a web site that was trying to sell some sort of scam. I was curious as to what information they were trying to sell, so I pulled out my credit card and, knowing that the first seven digits were common to all credit cards issued by my bank, I put in those digits, then I put in some random digits after that, then I figured out the checksum. Sure enough, the web site accepted the credit card number and I was let through, first try. (I should not have done this because it likely means that some innocent person ended up with a fraudulent charge on their card and I bear the guilt of that. I really don’t know what I was thinking because I should have known better. Maybe I thought that it wouldn’t really work.) The moral of the story is that credit card numbers are pretty easy to guess. I suppose that’s why modern web sites ask for zip codes, expiration dates, etc.
Assuming that Pierre is actually an honest guy and its just a matter of a mistake or bad handwriting on the bank number and an unfortunate tear of the paper, here’s my solution:
The first two digits of the bank number, otherwise known as a routing (or routing transit) number, usually represent the number of the Federal Reserve District for the bank (01-12). For thrift institutions (S&Ls, etc) in those districts, add a ‘2’ to the first district (ie 21-32). Since there is no Fed District 37 (or 17), one of these first two digits (or both) is incorrect. A few other values are valid for the first two digits as described in the following article: http://en.wikipedia.org/wiki/Routing_number.
The routing number also uses a modulus check routine for verification.
Pierre’s routing number doesn’t pass the mod check routine. The mod check routine can be used to reverse calculate any single digit that is missing. Assuming the first digit is in error, one can calculate the correct digit value to force the routing number to pass the mod check, in Pierre’s case, a ‘5’. However, 57 is not a valid 2 digits for the beginning of the routing number. So let’s move on to the second digit. The second digit must be a ‘1’ to pass the mod check. ’31’ IS a valid beginning for the routing number. A quick internet search will find that the routing number 314088048 belongs to the Alamo Federal Credit Union in San Antonio, TX. If both beginning digits are erroneous, then the modulus check could not be used to determine a valid routing number. Only a single unknown digit can be calculated using the mod check routine. Even then you may end up with a 9 digit number that passes the mod check but is still not a valid routing number as in 574088048. If Pierre had changed the value of more than one digit, only through the use of a commercial product like DigiCor’s Rescue 5 could you determine the valid routing number.
A good article on credit card issuers and their modulus check is also at wikipedia. The issuer is the first 6 digits of the CC number (475427) and identifies Pierre’s card as a rebate card issued by METABANK. Unfortunately, the article doesn’t identify WHICH MetaBank. There are 5 banks in the US that go by that name. Three are in Iowa, one is in North Dakota, and one is in Cordova, TN. Hopefully, the inspector has access to the full issuer information associated with 475427 and isn’t relying on Wikipedia.
Credit cards use the Luhn modulus check (every other digit being multiplied by 2). The sum of the products must be evenly divisible by 10. More information here: http://en.wikipedia.org/wiki/Luhn_algorithm
Assuming Pierre’s card issuer uses the Luhn algorith, the missing digit is a ‘5’. Note that it might also be a ‘0’ if the ‘plus 5’ version of the algorithm is used.
Several implementations (user beware) of the Luhn algorithm in different languages are included in the Wikipedia.