in reply to
Re: Puzzle Time

in thread Puzzle Time

++LanX for an excellent answer (*way* faster than my brute force approach).

Allow me one nit-pick:

*9! = 362880 possible combinations are checked in a recursive function.*

Throwing in a counter shows that `sub append_digit` is actually called 986,410 times. Took me a while to work out why...

9! is the number of combinations if every number has exactly 9 digits. But we also allow numbers with 1, 2, ..., 8 digits. So the total number of combinations is:

`my $p = 9 + # 1 digit
(9 * 8) + # 2 digits
(9 * 8 * 7) + # 3 digits
(9 * 8 * 7 * 6) + # 4 digits
(9 * 8 * 7 * 6 * 5) + # 5 digits
(9 * 8 * 7 * 6 * 5 * 4) + # 6 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3) + # 7 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2) + # 8 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1); # 9 digits
say $p; # = 986,409
`

(That 1 extra sub call is the first one, when `@number` is empty.)

`:-)`

For anyone else trying to understand how this code works, here is my slightly-reworked version which outputs the results in the order found:

`my $calls = 0;
my $count = 0;
my @digits;
my @solutions;
append_digit();
print "count: $count\n", join("\n", @solutions), "\n";
print "recursive calls: ", $calls, "\n";
sub append_digit
{
++$calls;
my $number = join '', @digits;
if (@digits && ! grep { $number % $_ } @digits)
{
print "$count: $number\n" unless ++$count % 100;
push @solutions, $number;
}
for my $digit (1 .. 9)
{
next if $digit ~~ @digits;
push @digits, $digit;
append_digit();
pop @digits;
}
}
`

Hope that’s helpful!