Monday, July 21, 2008

Cedric's coding challenge

Although I came late to the party at Cedric's coding challenge, this is the kind of problem I just can't resist taking at least a little dip into. The idea is to generate all numbers up to a maximum that do not have any repeated digits.

My initial thought was that the pattern of digits for an n-digit number should be the same, you just need to recode the values. I.e. given 3 digits a, b and c from which you should generate all 3-digit sequences without repeated digits, then generating the 2-digit suffixes ac and ca after choosing b as the first digit is the same as choosing a as the first digit, generating bc and cb and then recoding a->b, b->a and c->c.

Anyway, I soon realized that I couldn't come up with an efficient recoding algorithm and also that generating the suffixes didn't cost much more than an iteration over a pre-generated suffix list. So I basically ended up with the same algorithm as crazybob and Jonathan Hawkes improvement. Happily, my implementation was a bit faster still than both of theirs, 30% faster than Bob's and 20% faster than Jonathan's in Bob's way of counting and when measured like Jonathn does it, mine is 65% faster than Bob's and 30% faster than Jonathan's. Here it is:

/**
* Finds base 10 numbers whose digits don't repeat. Solution to Cedric's coding
* challenge: http://beust.com/weblog/archives/000491.html
*
*
@author Torbjorn Gannholm
*/

public class NonRepeatingDigits {
private final long max;
private final int base;
private final Listener listener;
private final Digit head;

/**
* Finds all numbers with non-repeating digits in the supplied base up to max.
*
@param base The base, e.g. octal (8), decimal (10), hexadecimal (16).
*
@param max Upper bound for returned values.
*
@param listener Listener to receive valid numbers.
*/

public NonRepeatingDigits(int base, long max, Listener listener) {
this.base = base;
this.max = max;
this.listener = listener;
head =
new Digit(base);
}

public void run() {
// One digit numbers.
for (Digit current = head.next.next;
current !=
null;
current = current.next) {
int value = current.value;
if (value > max) return;
listener.hear(value);
}
// Pick first digit (non-zero), then find the rest of the number.
for (int digitsAfterFirst = 1;
digitsAfterFirst < base;
digitsAfterFirst++) {
for (Digit previous = head.next, current = head.next.next;
current !=
null;
// Restore removed digit to sequence.
previous.next = current, previous = current, current = current.next) {
// Remove chosen digit from sequence.
previous.next = current.next;
if (followingDigits(digitsAfterFirst, current.value * base)) return;
}
}
}

/** A digit, part of a linked list of all digits in a base.
* (Shamelessly paraphrased from crazybob) */

private static class Digit {
private Digit next;
private final int value;

/** Constructs a non-digit that acts as the head for the list, and the
* digits in the list. */

Digit(
int base) {
value = -
1;
next =
new Digit(base, 0);
}

/** Constructs the real sequence of digits */
private Digit(int base, int value) {
this.value = value;
if (++value < base) {
next =
new Digit(base, value);
}
}
}

/**
* Recursively generates digits after the first of a valid number.
*
@param remaining Number of digits left to generate.
*
@param prefixValue Value of previous digits.
*
@return true when values generated are greater than max.
*/

private boolean followingDigits(int remaining, int prefixValue) {
if (remaining > 1) {
for (Digit prev = head , current = head.next;
current !=
null;
// Restore removed digit to sequence.
prev.next = current, prev = current, current = current.next) {
// Remove chosen digit from allowable digits.
prev.next = current.next;
if(followingDigits(remaining - 1,
(prefixValue + current.value) * base))
return true;
}
}
else {
for (Digit current = head.next; current != null; current = current.next) {
int value = prefixValue + current.value;
if (value > max) return true;
listener.hear(value);
}
}
return false;
}
}