Old chestnut: divisible by two through 10 Jun 10, 2011

Tho' it be poor nodeform, shall I be the one to defend C? If I had a nickel for each one of these code nodes I've considered adding to, I'd probably have a dollar. Well, I got absolutely no noding done in May (sorry Cass! I'll get that one finished some day...) so here goes:

#include <stdio.h>

int search(long n, int digits, int count)
{
	int d, m;
	if (count > 8 || n % (10 - count) == 0) {
		for (d = 0, m = 0x200; m; d++, m >>= 1)
			if (m & digits) search(n * 10 + d, ~m & digits, count - 1);
		if (!count) printf("%ld\n", n);
	}
}

int main(int argc, char ** argv)
{
	search(0, 0x3ff, 10);
}

This code was derived from William42's second (more elegant) solution, above. It does the exact same thing as his non-deterministic Prolog magic, but without any fancy tricks like arrays. On a side note, /dev/joe's solution, being analytical, is of course the most elegant one here.

search() uses four ints and a long (because any pandigital above 4293567810 will overflow an unsigned int). n is the string of digits, built up from the left. No divisibility tests are performed if we have fewer than two digits (count > 8). Once we've run out of bits (!count), we know we've passed all the divisibility tests and that n holds the answer (printf(...)).

0x3ff is ten ones in binary. The highest bit represents the digit 'zero', and the next 'one', 'two', and so on to the lowest bit which represents 'nine'. The for loop searches the bits of digits using m as a mask, recursing on digits which have not been used yet (~m & digits is digits with the bit at m unset).

search() is called 4136 times, which is several orders of magnitude below the brute force time of ten factorial (3628800). Python brute force: 15.7 seconds. Python version of this code: .034 seconds. This code: .003 seconds.

If you want to get crazy about memory usage (and who doesn't?), digits and m could be typed as short, and count and d as char. Additionally, count could be eliminated by employing some form of bit counting on digits, as it is always equal to the number of bits set in digits.

For completeness, here's the python version:

def search(n, digits):
    if len(digits) > 8 or n % (10 - len(digits)) == 0:
        for d in digits:
            search(n * 10 + d, [x for x in digits if x != d])
        if not digits: print n

search(0, range(10))

That was a terrible node. I'm going back to poetry(?).

‌

Old chestnut: divisible by two through 10

all writing, chronological
next: dasopoesis
previous: This was my mountain. You call it your valley.