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.
