No such thing as a small change PerlMonks

### 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??

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

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://503363]
help
Chatterbox?
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
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?