In the 1950's, Hans Peter Luhn invented a method for checking the validity of IDnumbers. This method (known as the Luhn Algorithm or the Luhn Formula) is still used today for a number of different purposes, including all major credit card numbers and Social Insurance Numbers.
Here's how the Luhn Algorithm works when checking for a valid ID number:
Example 1: Validate 42395 Step 1 9 * 2 = 18, 1 + 8 = 9. 2 * 2 = 4. 4 + 9 = 13 Step 2 13 + 4 + 3 + 5= 25 Step 3 25 is not divisible by 10. Not valid. Example 2: Validate 35436 Step 1 3 * 2 = 6. 5 * 2 = 10. 1 + 0 = 1. 1+6 = 7 Step 2 7 + 3 + 4 + 6 = 20. Step 3 20 is divisible by 10. Valid.
The last digit of every number is the "check digit" and the rest of it is the base number. So in the first example above, 4239 is the base number and 5 is the check digit. When generating card numbers or other ID numbers, you first generate the base number without the final digit, then you figure out what the check digit has to be to make the whole ID number valid.
DATA21.txt (DATA22.txt for the second try) will contain 5 test cases. Each test case consists of a batch of 5 base numbers (1 to 100 digits each) on one line, each separated by a single space character. Your job is to compute the check digit for each base number in the batch and then output the result as a single 5-digit number.
|
Sample Input 389796 4565280784 8451692334 46 465949539 97699 7392253 54011409 8073542288 303142477 334 349839 12593962 02497993 9468 53173 2901524 2493367526 39094 83530 08080532 5023002 57849 9853641952 027179 |
Sample Output 48336 36757 31920 15686 88201 |
import java.io.File;
import java.util.ArrayList;
import java.util.Scanner;
public class Problem_2_The_Luhn_Algorithm {
public static boolean isValid(String base, String checkDigit) {
String s = base + checkDigit;
s = s.trim();
int total = 0;
// every other digit (starting from the right)
for (int i = s.length() - 2; i > -1; i -= 2) {
// that digit multiplied by 2
int x2 = Integer.parseInt(s.substring(i, i + 1)) * 2;
String doubled = String.valueOf(x2);
int sumOfDigits = 0;
if (doubled.length() == 2) {
// add both the digits
sumOfDigits = Integer.parseInt(doubled.substring(0,1)) + Integer.parseInt(doubled.substring(1));
} else if (doubled.length() == 1) {
// add the only digit
sumOfDigits = Integer.parseInt(doubled.substring(0));
}
// every iteration, add the sum of the digits to the total sum
total += sumOfDigits;
}
// add each of the other, not doubled, numbers to the sum
for (int i = s.length() - 1; i > -1; i -= 2) {
total += Integer.parseInt(s.substring(i, i + 1));
}
// valid if divisible by 10
if (total % 10 == 0) {
return true;
}
return false;
}
public static void main(String[] args) {
try {
ArrayList<String> list = new ArrayList<String>();
// read in the file to the ArrayList
Scanner file = new Scanner(new File("C:\\Users\\Mike\\Desktop\\problem_2_the_luhn_algorithm_DATA20.txt"));
while (file.hasNextLine()) {
list.add(file.nextLine());
}
for (String batch : list) { // batch is each line in the file
for (String base : batch.split("\\s+")) { // bases are the set of numbers in each batch separated by spacing
for (int i = 0; i < 10; i++) { // test if any digit from 0-9 is the check digit for the base
if (isValid(base, String.valueOf(i))) {
System.out.print(i);
break;
}
}
}
System.out.println();
}
} catch (Exception e) {
e.printStackTrace();
System.out.println("Exception");
}
}
}
Using their sample input:
389796 4565280784 8451692334 46 465949539 97699 7392253 54011409 8073542288 303142477 334 349839 12593962 02497993 9468 53173 2901524 2493367526 39094 83530 08080532 5023002 57849 9853641952 027179
And the output to that is:
48336 36757 31920 15686 88201DOWNLOAD as .txt
And that is exactly the expected output.
Using their first judging test input:
7044181395 6603 1149 720 049 603719 1809506204 72734 499510461 8790253589 757255897243485455292885310420322639313299358 0 643408739942 20586359865268333532044434925724662371237164769802648038576778321544110002109578621172135 5821688228863062013258548037363773 2469793881003789061245610131524356377412622712343820091510288116404979337319194601471 89839637677668699048818178309338606310505949861618780311761237326807316179324941487543 776452768548177468981648255509573135289576139866 58511915319 0331073978953302088080731 538411152926826002478815038070400554497365872621963413994049565670333416508284051 13084277235331374242165800 8851246262509211469282463247708785759884121345784318290656 6077771782402297875594794327452078281058984724034566636869054610159210559631442297 4267664955595208453638026819017342705543720663566
And the output to that is:
65437 60714 00909 99258 92214DOWNLOAD as .txt
And that is exactly the expected output.
Using their second judging test input:
269 3617488232 66265 0808378 58389 6980183646 34985151 21715907 50 593 51714 61831931771302392087751710698879902223845222535258284566326469963046827525373353844809 7536567674170954154468288661027132851706376682383083715074533243219529319740757454 599192733281115568724425550252019063235009479975226 86871946439939344 3 040985800221031597620420480095977390809106817 58907416207236112605505506161901121120775135024703051299693473148536360 697632 519927550769875337 4200215782396016122413097103169231122724845312179825332594453 205884007297164175611789615319593104853936108172403521168565 339069794159121878991597533297626233158811175618497060215544018133388616690387681606437062808613659 0015315 47574689708386644908023872755958537154205307915459710501452856446
And the output to that is:
18048 69854 48516 43680 49351DOWNLOAD as .txt
And that is exactly the expected output.
Created: March 26, 2014
Last updated: June 15, 2014
Completed in full by: Michael Yaworski