Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Puzzle Time

by Athanasius (Abbot)
on Dec 23, 2012 at 10:21 UTC ( #1010086=note: print w/ replies, xml ) Need Help??


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!


Athanasius <°(((><contra mundum Iustus alius egestas vitae, eros Piratica,


Comment on Re^2: Puzzle Time
Select or Download Code
Re^3: Puzzle Time
by LanX (Canon) on Dec 23, 2012 at 15:25 UTC
    > Allow me one nit-pick:

    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:

    1. Evidently 0 is excluded!

    2. Any number this long includes even ciphers. So 5 is excluded! But any number divisible by 5 and 2 must end with a 0

    3. 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.

    Cheers Rolf

    ) and therefor a 7 digit number excludes 4 to be divisible by 9.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1010086]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (12)
As of 2015-07-06 21:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (83 votes), past polls