Re: Puzzle Time
by LanX (Saint) on Dec 23, 2012 at 03:47 UTC
|
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
¹) and of course their substrings from the start, thx Athanasius++ :) | [reply] [Watch: Dir/Any] [d/l] [select] |
|
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;
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
++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.)
:-)
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
> 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:
- 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] [Watch: Dir/Any] |
|
You are a legend, your help is greatly appreciated :)
| [reply] [Watch: Dir/Any] |
Re: Puzzle Time
by Athanasius (Archbishop) on Dec 23, 2012 at 03:39 UTC
|
First, some assumptions:
- Numbers means natural numbers
- Digits means digits in the decimal representation
- Divisible by a digit means divisible without remainder
- The digit 0 is excluded, since division by 0 is undefined
There are 9 different digits allowed, and any number having more than 9 digits will necessarily have some digits repeated. So, the upper bound is 987,654,321.
#! perl
use Modern::Perl;
my $count = 0;
OUTER:
for my $n (1 .. 987_654_321)
{
my %digits;
++$digits{$_} for split //, $n;
for (keys %digits)
{
next OUTER if ($_ == 0) || ($digits{$_} > 1) || ($n % $_);
}
printf "#%d is %d\n", ++$count, $n;
}
Hope that helps,
| [reply] [Watch: Dir/Any] [d/l] |
Re: Puzzle Time
by golux (Chaplain) on Dec 23, 2012 at 05:03 UTC
|
The solution by Athanasius is already very nice and succinct; it can find all 548 solutions twice as fast (31 seconds instead of 65) if the tests are performed for each digit rather than after all digits have been hashed:
#!/usr/bin/perl -w
use strict;
use warnings;
my $count = 0;
my $start = time;
OUTER:
for my $n (1 .. 987_654_321) {
my %digits;
map { next OUTER if !$_ or $digits{$_}++ or $n % $_ } split //, $n;
printf "#%d is %d\n", ++$count, $n;
($count == 548) and printf "Time: %d sec\n", time - $start;
}
say
substr+lc crypt(qw $i3 SI$),4,5
| [reply] [Watch: Dir/Any] [d/l] |
Re: Puzzle Time
by BrowserUk (Patriarch) on Dec 23, 2012 at 03:59 UTC
|
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
RIP Neil Armstrong
| [reply] [Watch: Dir/Any] [d/l] |
Re: Puzzle Time
by hdb (Monsignor) on Jun 25, 2013 at 14:58 UTC
|
Here are the answers for the number representations with bases 2 to 9 using brute force and Math::BaseCalc.
Base 2: 1
Base 3: 2
Base 4: 6
Base 5: 10
Base 6: 10
Base 7: 75
Base 8: 144
Base 9: 487
| [reply] [Watch: Dir/Any] [d/l] |
Re: Puzzle Time
by hdb (Monsignor) on Sep 20, 2013 at 08:02 UTC
|
| [reply] [Watch: Dir/Any] |
Re: Puzzle Time
by Anonymous Monk on Dec 23, 2012 at 02:57 UTC
|
| [reply] [Watch: Dir/Any] |