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 nitpick:
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 slightlyreworked 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!
Re^3: Puzzle Time by LanX (Chancellor) on Dec 23, 2012 at 15:25 UTC 
> Allow me one nitpick:
Yeah I noticed this, but was too tired to correct it. =)
Anyway my guess was wrong (9!+8!+7!+...) you got it right.
> (way faster than my brute force approach).
If it's about speed you can limit the $maxlevel, because the longest number can't have more than 7 digits:
 Evidently 0 is excluded!
 Any number this long includes even ciphers. So 5 is excluded!
But any number divisible by 5 and 2 must end with a 0
 An number from the remaining 8 digits would include 9 and 3, but the digit sum would be 40, which is impossible.¹
Even your approach with a brute force loop could compete when only considering 7 digits, cause you don't have the overhead of 1 million function calls.
¹) and therefor a 7 digit number excludes 4 to be divisible by 9.
 [reply] 
