Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Puzzle Time

by LanX (Canon)
on Dec 23, 2012 at 03:47 UTC ( #1010072=note: print w/ replies, xml ) Need Help??


in reply to Puzzle Time

And the answer is: 548

(I suppose only positive numbers otherwise multiply it with 2)

The following is just a variation of the code I recently used:

(I love branch and bound! :)

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

#!perl use strict; use warnings; my @digits = 1..9; my @number; my $maxlevel=10; my %count_hash; my $count=0; append_digit(); print "count: $count\n"; print join "\n", sort { $a <=>$b } keys %count_hash; sub append_digit { my $level = scalar @number; my $number= join "", @number; if ( $level and ! grep {$number % $_} @number ) { $count++; print "$count: $number\n" unless $count %100; $count_hash{$number} = undef; } for my $digit (@digits) { return if $level > $maxlevel; # for testing only next if $digit ~~ @number; push @number, $digit; append_digit(); pop @number; } }
output

Cheers Rolf

╣) and of course their substrings from the start, thx Athanasius++ :)


Comment on Re: Puzzle Time
Select or Download Code
Re^2: Puzzle Time
by Anonymous Monk on Dec 23, 2012 at 04:28 UTC
    You are a legend, your help is greatly appreciated :)
Re^2: Puzzle Time
by Athanasius (Abbot) on Dec 23, 2012 at 10:21 UTC

    ++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.)

    :-)


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

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

Re^2: Puzzle Time
by ikegami (Pope) on Dec 24, 2012 at 06:41 UTC
    Your method of getting the next digit is expensive! Replace
    for my $digit (@digits) { next if $digit ~~ @number; push @number, $digit; append_digit(); pop @number; }
    with
    for my $pos (0..$#digits) { push @number, $digits[$pos]; local @digits = @digits[0..$pos-1, $pos+1..$#digits]; append_digit(); pop @number; }

    to cut down the time taken to 2/3 (6s from 9s).

    Also, there's reason to use a hash (outside of testing).

    Full code:

    #!perl use strict; use warnings; use 5.010; our @digits = 1..9; my @number; my @results; sub append_digit { my $number = join "", @number; push @results, $number if @number && !grep $number % $_, @number; for my $pos (0..$#digits) { push @number, $digits[$pos]; local @digits = @digits[0..$pos-1, $pos+1..$#digits]; append_digit(); pop @number; } } my $stime = time; append_digit(); my $etime = time; say $etime-$stime; say "count: " . (0+@results); #say for sort { $a <=> $b } @results;

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2015-07-05 09:33 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 (61 votes), past polls