Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

Re^3: Puzzle: What is the largest integer ... (not "a longest")

by fizbin (Chaplain)
on Oct 27, 2005 at 14:59 UTC ( #503363=note: print w/replies, xml ) Need Help??

in reply to Re^2: Puzzle: What is the largest integer ... (not "a longest")
in thread Puzzle: What is the largest integer whose digits are all different (and do not include 0) that is divisible by each of its individual digits?

Note that you can cut the time in half or there abouts by adding just two simple checks; this version of your program runs in 6.1 seconds on my machine - the original without the initial 9-digit loop takes 13 seconds on my machine:

use Algorithm::Loops qw( NextPermuteNum ); my @digs= (1..9); my @map; @map[1..9]= reverse 1..9; my $prev= 0; for my $len ( reverse 1..8 ) { do { my $num= substr( join( '', @map[ @digs ] ), 0, $len ); if( $num != $prev and $num !~ /[2468].*[13579]$/ and $num !~ / +5./) { for( $num =~ /./g, 0 ) { die "$num\n" if ! $_; last if 0 != $num % $_; } } $prev= $num; } while( NextPermuteNum(@digs) ); }

Note that all I've done is add two regex tests - that you don't have any even digits if the last digit is odd, and that you never have a 5 in any but the last position.

Reducing the search space is almost always a good idea.

@/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/; map{y/X_/\n /;print}map{pop@$_}@/for@/

Replies are listed 'Best First'.
Re^4: Puzzle: What is the largest integer ... (not "a longest")
by tye (Sage) on Oct 27, 2005 at 15:25 UTC

    You can make it even faster by just dropping 5 from the list, since including a 5 excludes all even digits and restricts the solution length to 5 digits (which we quickly prove is too short). You can also make it faster by more efficiently skipping the redundant permutations. That's the nature of quick hacks. (:

    - tye        

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (5)
As of 2022-08-09 02:24 GMT
Find Nodes?
    Voting Booth?

    No recent polls found