ISBN missing number solver

Question

This is a programming contest question. Question as follows

Problem Definition

An ISBN (International Standard Book Number) is a ten digit code that uniquely identifies a book. The first 9 digits are used to represent the book and the 10th digit is used to ensure that the ISBN is correct. To validate the ISBN number, calculate a sum that is 10 times the first digit plus 9 times the second digit plus 8 times the third digit ... all the way until you add 1 times the last digit. If the sum is divisible by 11, then the 10 digit code is a valid ISBN number.

For example 1111456291 is a valid ISBN, because

10*1 + 9*1 + 8*1 + 7*1 + 6*4 + 5*5 + 4*6 + 3*2 + 2*9 + 1*1 = 132 which is divisible by 11.

Each of the first nine digits can take a value between 0 and 9. Sometimes it is necessary to make the last digit equal to ten. This is done by writing the last digit as X.

For example, 156881111X is a valid ISBN, because

10*1 + 9*5 + 8*6 + 7*8 + 6*8 + 5*1 + 4*1 + 3*1 + 2*1 + 1*10 = 231 which is divisible by 11.

You have to write a program to fill in the missing digit from a given ISBN number where the missing digit is represented as '?'. The missing digit should be a value between 0 and 9 or 'X' (X represents 10)

---

Input Format

ISBN Code (A single line with a ten digit ISBN number that contains '?' in a single position. The length of the input should be 10 characters.)

---

Output Format

• The output should contain the missing digit.

• For any malformed input print 'INVALID INPUT'

• If a suitable value for '?' cannot be found which makes the ISBN valid, then the text 'NO SOLUTION POSSIBLE' should be displayed as output.

---

Samples

---

Solution

import java.util.Scanner;

/**
 * @see https://gist.github.com/tintinmj/18510d388e4d316c215e
 * @author tintinmj
 */

public class ISBNcodeSolver {
    private static final String MISSING_NUMBER = "?";
    private static final String LAST_NUMBER_AS_X = "X";
    private static final int    ISBN_CODE_LENGTH = 10;
    private static final int    MULTIPLE_OF = 11;

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            String code = sc.nextLine();

            System.out.println(new ISBNcodeSolver().run(code));
        }
    }

    public String run(String input) {
        return findMissingCodeDigit(input);
    }

    /**
     * Used https://in.answers.yahoo.com/question/index?qid=20100922080144AAXCMdM answer technique
     * @param ISBNcodeWithOneDigitMissing the 10 digit ISBN code word with one digit missing
     * @return "INVALID INPUT" if does not obey the ISBN code rule with one number missing.
     * else returns "NO SOLUTION POSSIBLE" if no solution possible. otherwise returns the missing digit.
     */
    public String findMissingCodeDigit(String ISBNcodeWithOneDigitMissing) {

        if(!isValid(ISBNcodeWithOneDigitMissing)) {
            return "INVALID INPUT";
        }

        int sum = calculateSum(ISBNcodeWithOneDigitMissing);
        int missingNumberMultiple = findMissingNumberMultiple(ISBNcodeWithOneDigitMissing);

        // check whether (sum + multiple * x) is divisible by 11 or not.
        // where x is a value between 0 and 9.
        for (int i = 0; i <= 9; i++) {
            if ((sum + (missingNumberMultiple * i)) % MULTIPLE_OF == 0) {
                return String.valueOf(i);
            }
        }

        // ends with X so add 10.
        if (ISBNcodeWithOneDigitMissing.endsWith(LAST_NUMBER_AS_X) && (sum + 10) % MULTIPLE_OF == 0) {
            return LAST_NUMBER_AS_X;
        }

        return "NO SOLUTION POSSIBLE";
    }

    /**
     * 
     * @param input the <i>probable</i> ISBN code
     * @return true if 10 digit ISBN code with one digit missing. otherwise false
     */
    private boolean isValid(String input) {

        // ISBN code has to be a ten digit code
        if(input.length() != ISBN_CODE_LENGTH) {
            return false;
        }
        // post-condition : a 10 digit ISBN code

        // as per question only only one digit will be missing
        if (!isOnlyOneNumberMissing(input)) {
            return false;
        }
        // post-condition : a 10 digit ISBN code with one number missing

        // if there is "X" it should be at last
        if (input.contains(LAST_NUMBER_AS_X) && !input.endsWith(LAST_NUMBER_AS_X)) {
            return false;
        }
        // post-condition : a 10 digit ISBN code with one number missing
        //                  and may or may not have "X" at last


        // calculate no of digits in the code
        int noOfDigits = countDigitOccurence(input);
             // ISBN code like "12345?678X" then no of digits = 8
        if ( (input.endsWith(LAST_NUMBER_AS_X) && noOfDigits != ISBN_CODE_LENGTH - 2) ||
             // ISBN code like "12345?6789" then no of digits = 9
             (!input.endsWith(LAST_NUMBER_AS_X) && noOfDigits != ISBN_CODE_LENGTH - 1) ) {
            return false;
        }
        // post-condition : a 10 digit ISBN code with one number missing
        //                  and may or may not have "X" at last
        //                  if has "X" at last then has 8 digits
        //                  or doesn't have "X" at last then has 9 digits

        return true;
    }

    /**
     * The sum of the ISBN code. 
     * More info - http://en.wikipedia.org/wiki/International_Standard_Book_Number#ISBN-10_check_digit_calculation
     * @param ISBNcode
     * @return the sum as described in https://in.answers.yahoo.com/question/index?qid=20100922080144AAXCMdM
     */
    private int calculateSum(String ISBNcode) {
        int sum = 0;
        char[] codeAlphabets = ISBNcode.toCharArray();
        int multiple = 10;
        for (int i = 0; i < codeAlphabets.length; i++) {
            if (Character.isDigit(codeAlphabets[i])) {
                sum += multiple * Character.digit(codeAlphabets[i], 10);
            }
            multiple--;
        }

        if (ISBNcode.endsWith(LAST_NUMBER_AS_X)) {
            sum += 10;
        }

        return sum;
    }

    /**
     * The multiple of the missing number will be returned. 
     * Example : if the code is like "1234?67892" then the multiple will be "6".
     * @param ISBNcode
     * @return the multiple of the missing number
     */
    private int findMissingNumberMultiple(String ISBNcode) {
        return (ISBN_CODE_LENGTH - ISBNcode.indexOf(MISSING_NUMBER));
    }

    /**
     * 
     * @param input the ISBN code
     * @return true if only one number is missing otherwise false.
     */
    private boolean isOnlyOneNumberMissing(String input) {
        return countOccurence(input, MISSING_NUMBER) == 1;
    }

    /**
     * Described in http://stackoverflow.com/a/8910767/2350145
     * @param haystack the string to search in
     * @param needle the string to search for
     * @return 
     */
    private int countOccurence(String haystack, String needle) {
        int count = haystack.length() - haystack.replace(needle, "").length();
        return count;
    }

    /**
     * 
     * @param haystack the string to search in
     * @return number of digits in the haystack
     */
    private int countDigitOccurence(String haystack) {
        int count = haystack.length() - haystack.replaceAll("\\d", "").length();
        return count;
    }
}

• Criticize on coding-style, magic-number scattering.
• Comment (mis)utilized?
• Coded under one class cause needed to be submit as one class.
• Candy or unicorn!

Answer 1

Overview

Your code is generally pretty good, but there are places where it can be edited.

Let's start off with...

private boolean isValid(String input) {
    if (input.length() != ISBN_CODE_LENGTH) {
        return false;
    }
    if (!isOnlyOneNumberMissing(input)) {
        return false;
    }
    if (input.contains(LAST_NUMBER_AS_X)
            && !input.endsWith(LAST_NUMBER_AS_X)) {
        return false;
    }
    int noOfDigits = countDigitOccurence(input);
    if ((input.endsWith(LAST_NUMBER_AS_X) && noOfDigits != ISBN_CODE_LENGTH - 2)
            ||
            (!input.endsWith(LAST_NUMBER_AS_X) && noOfDigits != ISBN_CODE_LENGTH - 1)) {
        return false;
    }
    return true;
}

private boolean isOnlyOneNumberMissing(String input) {
    return countOccurence(input, MISSING_NUMBER) == 1;
}

private int countOccurence(String haystack, String needle) {
    int count = haystack.length() - haystack.replace(needle, "").length();
    return count;
}

private int countDigitOccurence(String haystack) {
    int count = haystack.length() - haystack.replaceAll("\\d", "").length();
    return count;
}

All this code is inefficient and can make your head spin. It is better done using a regular expression:

private boolean isValid(String input) {
    return input.length() == ISBN_CODE_LENGTH
            && input.matches("\\d*\\" + MISSING_NUMBER + "\\d*X?");
}

This method simply checks if it is the right length first, and then checks if it matches "\\d*\\" + MISSING_NUMBER + "\\d*X?" (which is "\d*\?\d*X?"). This regex matches a String with any number of digits, followed by a "?", another set of digits, and finally a X, which is optional.

This part can also be edited:

private int calculateSum(String ISBNcode) {
    int sum = 0;
    char[] codeAlphabets = ISBNcode.toCharArray();
    int multiple = 10;
    for (int i = 0; i < codeAlphabets.length; i++) {
        if (Character.isDigit(codeAlphabets[i])) {
            sum += multiple * Character.digit(codeAlphabets[i], 10);
        }
        multiple--;
    }

    if (ISBNcode.endsWith(LAST_NUMBER_AS_X)) {
        sum += 10;
    }

    return sum;
}

Most important is:

if (ISBNcodeWithOneDigitMissing.endsWith(LAST_NUMBER_AS_X)
        && (sum + 10) % MULTIPLE_OF == 0) {
    return LAST_NUMBER_AS_X;
}

I think you meant:

if (ISBNcodeWithOneDigitMissing.endsWith(MISSING_NUMBER)
        && (sum + 10) % MULTIPLE_OF == 0) {
    return LAST_NUMBER_AS_X;
}

Next, the for loop. The if statement could only return true if:

a) It comes to the question mark; or
b) It reaches the end (where X is possible)

That pretty much means that the if will be useful only twice in ten times. You can change the for loop so that it can be changed into something less time-consuming (and since the length of the array is used multiple times, I add an int to hold the length):

int length = codeAlphabets.length;
for (int i = 0; i < length - (codeAlphabets[length - 1] == 'X' ? 1 : 0); i++)

Then change:

if (Character.isDigit(codeAlphabets[i]))

To:

if (codeAlphabets[i] != '?')

Which saves some time for the program.

Also:

private int findMissingNumberMultiple(String ISBNcode) {
    return (ISBN_CODE_LENGTH - ISBNcode.indexOf(MISSING_NUMBER));
}

The parentheses are optional:

private int findMissingNumberMultiple(String ISBNcode) {
    return ISBN_CODE_LENGTH - ISBNcode.indexOf(MISSING_NUMBER);
}

After all this editing...

Final code:

Note: Comments were removed, because while I was editing on Eclipse, it looked very messy with it.

import java.util.Scanner;

public class ISBNSolver {

    private static final String MISSING_NUMBER = "?";
    private static final String LAST_NUMBER_AS_X = "X";
    private static final int ISBN_CODE_LENGTH = 10;
    private static final int MULTIPLE_OF = 11;

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            String code = sc.nextLine();

            System.out.println(new ISBNSolver().run(code));
        }
    }

    public String run(String input) {
        return findMissingCodeDigit(input);
    }

    public String findMissingCodeDigit(String ISBNcodeWithOneDigitMissing) {

        if (!isValid(ISBNcodeWithOneDigitMissing)) {
            return "INVALID INPUT";
        }

        int sum = calculateSum(ISBNcodeWithOneDigitMissing);
        int missingNumberMultiple = findMissingNumberMultiple(ISBNcodeWithOneDigitMissing);

        for (int i = 0; i <= 9; i++) {
            if ((sum + (missingNumberMultiple * i)) % MULTIPLE_OF == 0) {
                return String.valueOf(i);
            }
        }

        if (ISBNcodeWithOneDigitMissing.endsWith(MISSING_NUMBER)
                && (sum + 10) % MULTIPLE_OF == 0) {
            return LAST_NUMBER_AS_X;
        }

        return "NO SOLUTION POSSIBLE";
    }

private boolean isValid(String input) {
    return input.length() == ISBN_CODE_LENGTH
            && input.matches("\\d*\\" + MISSING_NUMBER + "\\d*X?");
}

    private int calculateSum(String ISBNcode) {
        int sum = 0;
        char[] codeAlphabets = ISBNcode.toCharArray();
        int multiple = 10;
        int length = codeAlphabets.length;
        for (int i = 0; i < length - (codeAlphabets[length - 1] == 'X' ? 1 : 0); i++) {
            if (codeAlphabets[i] != '?') {
                sum += multiple * Character.digit(codeAlphabets[i], 10);
            }
            multiple--;
        }

        if (ISBNcode.endsWith(LAST_NUMBER_AS_X)) {
            sum += 10;
        }

        return sum;
    }

    private int findMissingNumberMultiple(String ISBNcode) {
        return ISBN_CODE_LENGTH - ISBNcode.indexOf(MISSING_NUMBER);
    }
}

Answer 2

You frequently pass around a string parameter named ISBNcodeWithOneDigitMissing (a.k.a. ISBNcode or input). At the same time, your ISBNcodeSolver class maintains no state.

Your naming is cumbersome. I think that DefectiveISBN10 would be a good class name.

I recommend reorganizing the code according to the following outline:

public class DefectiveISBN10 {

    public static class ISBNException extends Exception {
        public ISBNException(String s) {
            super(s);
        }
    }

    public static class InvalidInputException extends ISBNException {
        public InvalidInputException() {
            super("Invalid input");
        }
    }

    public static class NoSolutionPossibleException extends ISBNException {
        public NoSolutionPossibleException() {
            super("No solution possible");
        }
    }

    //////////////////////////////////////////////////////////////////////

    public DefectiveISBN10(String input) throws InvalidInputException {
        // Check length
        // Check regex
        // Convert string to int array
        // Locate the ? placeholder
        …
    }

    public char getMissingChar() throws NoSolutionPossibleException {
        …
    }

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            DefectiveISBN10 isbn = new DefectiveISBN10(sc.next());
            System.out.println(isbn.getMissingChar());
        } catch (NoSuchElementException noInput) {
            System.err.println("No input");
        } catch (ISBNException e) {
            System.out.println(e.getMessage());
        }
    }
}

Other than that, your solution seems strategically sound, especially with the simplifications that @MannyMeng introduced using the regular expression.