4
\$\begingroup\$

I've the following problem:

Print all valid phone numbers of length n subject to following constraints:
1.If a number contains a 4, it should start with 4
2.No two consecutive digits can be same
3.Three digits (e.g. 7,2,9) will be entirely disallowed, take as input

Here's my solution:

public static void ans(int length, int d1, int d2, int d3) {
    StringBuffer numbers = new StringBuffer();

    for(int i = 0; i < 10 ;i++) {
        if(i != d1 && i != d2 && i != d3) {
            numbers.append(i);
        }
    }
    printNumbers("", numbers.toString(), length);
}

public static void printNumbers(String soFar, String remaining, int length) {
    if(soFar.length() == length) {
        boolean four = false;
        boolean sameAdjDigits = false;

        for(int i = 1; i < soFar.length(); i++) {
            if(soFar.charAt(i-1) == soFar.charAt(i)) sameAdjDigits = true;
            if(soFar.charAt(i) == '4') four = true;
        }

        if(!sameAdjDigits) {
            if(!four || (four && soFar.charAt(0) == '4'))
                System.out.print(soFar + " ");
        }

        return;
    }

    if(soFar.length() < length) {
        for(int i = 0; i < remaining.length(); i++) {
            String newSoFar = soFar + remaining.charAt(i);
            String newRemaining = remaining.substring(0, i) + remaining.substring(i+1);
            printNumbers(newSoFar, newRemaining, length);
        }
    }
}

I ran some tests on this code and checked all the printed values. It worked for length 1 and 2. However, I couldn't verify for length > 2 because there were too many numbers.

Can anyone verify if my code runs a correct result? Is there any part of the code that can be improved?

\$\endgroup\$
8
\$\begingroup\$

Nitpicks

public static void ans(int length, int d1, int d2, int d3) {

Any time that I see numbered variables, I want to replace them with a collection. Since we know that there will be no duplicate values, I'd use a Set.

public static void generatePhoneNumbers(int length, Set<Character> disallowedDigits) {

Also, I find d an unclear name, so I switched to disallowedDigits which I find clearer.

I switched from int to Character as you are building a string. We could just as easily be working with the letters of the alphabet as with numeric digits.

StringBuffer numbers = new StringBuffer();

This seems an ideal place to use a StringBuilder.

StringBuilder digits = new StringBuilder();

I also changed the name to digits, as that tells me that we're talking about one digit at a time rather than multi-digit numbers.

            if(!four || (four && soFar.charAt(0) == '4'))

You could just as well write

            if( ! four || soFar.charAt(0) == '4' )

If the string begins with a 4, then we don't care if none of the rest have a 4.

Fulfilling the Problem Statement

        String newRemaining = remaining.substring(0, i) + remaining.substring(i+1);

This is actively wrong given your problem statement:

Print all valid phone numbers of length n subject to following constraints:
1. If a number contains a 4, it should start with 4
2. No two consecutive digits can be same
3. Three digits (e.g. 7,2,9) will be entirely disallowed, take as input

From #2, only consecutive digits can't be the same. So you should not be removing digits from your remaining String. Like length, that will be constant for all calls.

We can rewrite #1 to say: only numbers that start with 4 can contain 4. This effectively gives us different rules for 4 than other values. Since we're supposed to generate all numbers, I'd suggest that we generate all numbers starting with 4 separately from other numbers. Fortunately, #3 means that we already need a way to exclude digits from the set.

ans

Here's how I'd write the method that you called ans:

private final static char [] DIGITS = "0123456789".toCharArray();

public static void generate(int length, Set<Character> disallowedDigits) {
    Set<Character> allowedDigits = new TreeSet<Character>();

    for ( Character digit : DIGITS ) {
        if ( ! disallowedDigits.contains(digit) ) {
            allowedDigits.add(digit);
        }
    }

    if ( allowedDigits.contains('4') ) {
        printNumbers("4", allowedDigits, length);
        allowedDigits.remove('4');
    }

    for ( Character digit : allowedDigits ) {
        printNumbers("" + digit, allowedDigits, length);
    }
}

First, we define a constant to hold the possible digit values. Then we make a new Set that masks out the disallowedDigits. If 4 is allowed, then we generate all the numbers that start with 4 separately. Then we remove 4 from the allowedDigits, as it won't be allowed in any of the other numbers.

printNumbers

    if(soFar.length() == length) {
        boolean four = false;
        boolean sameAdjDigits = false;

        for(int i = 1; i < soFar.length(); i++) {
            if(soFar.charAt(i-1) == soFar.charAt(i)) sameAdjDigits = true;
            if(soFar.charAt(i) == '4') four = true;
        }

        if(!sameAdjDigits) {
            if(!four || (four && soFar.charAt(0) == '4'))
                System.out.print(soFar + " ");
        }

        return;
    }

This whole section of code is unnecessary, except for one line (the print). Instead of generating invalid strings and masking them out, just don't generate them in the first place. That will save all subsequent recursive calls down that path.

    if(soFar.length() < length) {
        for(int i = 0; i < allowedDigits.length(); i++) {
            String newSoFar = soFar + allowedDigits.charAt(i);
            String newRemaining = allowedDigits.substring(0, i) + allowedDigits.substring(i+1);
            printNumbers(newSoFar, newRemaining, length);
        }
    }

I switched to a Set to hold the digits that can be used, so this is going to be a bit different.

private static void printNumbers(String soFar, Set<Character> allowedDigits, int length) {
    int lengthSoFar = soFar.length();

    if ( lengthSoFar < length ) {
        Character last = soFar.charAt(lengthSoFar - 1);

        for ( Character digit : allowedDigits ) {
            if ( ! digit.equals(last) ) {
                printNumbers(soFar + digit, allowedDigits, length);
            }
        }
    } else {
        System.out.println(soFar);
    }
}

First, we already took care of 4 in our generate function. Here, it will either be in allowedDigits or it won't.

Second, we take care of the rule about consecutive digits by simply not starting the recursive generation in that case: if ( ! digit.equals(last) ) {.

I put each number on its own line. For all but trivial lengths, there are too many numbers to fit on a single line.

Note that soFar is the only parameter that changes from call to call.

Testing

This is a bit difficult. Because we print the numbers to standard output, we can't run normal unit tests on them. The simplest way to handle this is to direct the output to a file. Then we can search the file for values that should or shouldn't be there.

For example, we should never have any of the following sequences: 00, 11, 22, 33, 44, 55, 66, 77, 88, 99, 00. So search for those in the file. If they don't exist, then you know that rule is working.

Search for lines containing the disallowedDigits. There shouldn't be any.

Find all the lines in the file that contain a 4 and verify that 4 is the first digit of the number. On Linux, that might be written something like

fgrep '4' < phone_numbers.txt | cut -c1 | sort | uniq -c

If there are any values other than 4, then you can look them up more specifically.

Also search for a few values that you construct, e.g. for a length of 8 where 7, 2, and 9 are disallowed, 40134568 should be in the list. Also 86868686 should be there.

\$\endgroup\$
2
\$\begingroup\$

You use the value soFar.length() multiple times in the printNumbers() method, or to be more specific, 2 + soFar.length() times. You can easily avoid retrieving the value that many times by creating a variable to hold the value:

int length = soFar.length();

Then replace all the soFar.length() with length.

What does four exactly mean? Use a more specific and more detailed (but not too much) variable name, such as hasFour.

The return is completely unnecessary. Instead, use else-if:

public static void printNumbers(String soFar, String remaining, int length) {
    if(soFar.length() == length) {
        boolean four = false;
        boolean sameAdjDigits = false;

        for(int i = 1; i < soFar.length(); i++) {
            if(soFar.charAt(i-1) == soFar.charAt(i)) sameAdjDigits = true;
            if(soFar.charAt(i) == '4') four = true;
        }

        if(!sameAdjDigits) {
            if(!four || (four && soFar.charAt(0) == '4'))
                System.out.print(soFar + " ");
        }
    } else if(soFar.length() < length) {
        for(int i = 0; i < remaining.length(); i++) {
            String newSoFar = soFar + remaining.charAt(i);
            String newRemaining = remaining.substring(0, i) + remaining.substring(i+1);
            printNumbers(newSoFar, newRemaining, length);
        }
    }
}

Also, use braces for all if statements. Instead of:

if(soFar.charAt(i-1) == soFar.charAt(i)) sameAdjDigits = true;
if(soFar.charAt(i) == '4') four = true;

Do:

if(soFar.charAt(i-1) == soFar.charAt(i)) {
    sameAdjDigits = true;
}
if(soFar.charAt(i) == '4') {
    four = true;
}

It is more work, but if you don't, horrible bugs may occur.

Otherwise, your code is good.

\$\endgroup\$
  • \$\begingroup\$ IMO, there's nothing wrong with using the return; \$\endgroup\$ – Simon Forsberg Dec 26 '14 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.