Re:Maybe there is an ambiguity...
Ovid on 2008-06-08T17:48:13
I get more than that. They draw the prize next Wednesday, so I don't think it's fair to post code right now, but that's OK because mine is obviously buggy
:) Re:Maybe there is an ambiguity...
Ovid on 2008-06-08T17:54:29
Er, now that I stop to think about it, perhaps it's not fair for me to count a number and its reverse. D'oh!
Re:Maybe there is an ambiguity...
dakkar on 2008-06-08T18:02:48
Ok, the ambiguity is in the part of the solution they don't ask for. So their actual question has a unique answer.Re:Maybe there is an ambiguity...
Ovid on 2008-06-08T18:09:15
I think you're seeing something I don't, then, because I have no idea what your first sentence meant
:) Re:Maybe there is an ambiguity...
Ovid on 2008-06-08T18:04:53
OK, now I get your results
:(
That's my interpretation of the spec - but that's a hell of a lot more than six numbers as you say. Is that what you get?#!/usr/bin/env perl
my @candidate = grep { $_ % 10 } 101.. 999;
for my $N ( 7, 9, 11 ) {
print join( ', ',
grep { $_ % $N == 0 && reverse( $_ ) % $N == 0 } @candidate ),
"\n";
}
Re:Is this it?
Ovid on 2008-06-08T18:07:07
Nope, not even close
:) That tiny spec bears close rereading. For example, "using each of the digits 1 to 9" for 3-digit numbers means your first grep is off. my @candidates = grep { !/0/ } 111... 999; I also used &List::MoreUtils::uniq to pre-trim that list (since duplicate numbers are not allowed).
Basically, you'll need a three stage process (I think). First, generate your candidate list. Second, find all three digit numbers which satisfy the reverse divisor requirement. Then construct your final list of three triples.
And though I thought I had matched dakkar's results above, I actually have three numbers for 9
:( Re:Is this it?
dakkar on 2008-06-08T18:15:15
Argh! *three numbers*, not *two pairs*. Stupid typing-faster-than-reading...Re:Is this it?
rjbs on 2008-06-08T18:07:52
First, you need a "grep { $_ !~/0/ }" in there. Second, I think that your three numbers, concatenated, must use each of the digits only once all together. That is, a valid answer would be qw(123 456 789) if only those numbers divided properly. qw(123 331 882) is no good. Re:Is this it?
Ovid on 2008-06-08T18:13:12
That appears to be correct. You have to read the spec carefully. They ask you to use each of those numbers, not any. I got that wrong the first time.
Re:Is this it?
AndyArmstrong on 2008-06-08T18:52:01
Christ on a bike - I'm rubbish at reading specifications:)
Re:Maybe there isn't an ambiguity ...
Ovid on 2008-06-08T19:01:29
I get the same sets of numbers, but what does "six integers" mean in this context?
Re:Maybe there isn't an ambiguity ...
depesz on 2008-06-08T19:17:13
i think this is just an mistake on the side of new scientist.Re: six integers
mauzo on 2008-06-09T00:26:13
You have three three-digit numbers, and their reverses. That makes six by my counting...Re: six integers
Ovid on 2008-06-09T05:01:15
You have five three-digit numbers. One for 7, one for 11, but three for 9. If there was only one result for each of the three (which is what I was initially expecting), then six would make sense.
Re: six integers
depesz on 2008-06-09T05:17:46
I think this mistake doesn't really matter.
The request was:
"What are the smallest and largest of your six integers?"
even it we'll change it to "10 integers" the answer stays the same. i.e. the numbers i got for div/9 are neither min nor max.
(a * 10**2 + b * 10**1 + c * 10**0) % 7 == 0
(c * 10**2 + b * 10**1 + a * 10**0) % 7 == 0
(d * 10**2 + e * 10**1 + f * 10**0) % 9 == 0
(f * 10**2 + e * 10**1 + d * 10**0) % 9 == 0
(g * 10**2 + h * 10**1 + i * 10**0) % 11 == 0
(i * 10**2 + h * 10**1 + g * 10**0) % 11 == 0Re:I bet New Scientist publishes a correction
depesz on 2008-06-09T09:07:37
24 solutions? how did get them? can you show them?Re:I bet New Scientist publishes a correction
Limbic Region on 2008-06-09T12:24:02
Well, first the math
there is 1 solution for 7, with reverse = 2
there is 3 solutions for 9, with reverse = 6
there is 1 solution for 11, with reverse = 2
2 * 6 * 2 = 24
I used a bit more complicated code than I am about to show, but you should be able to see how I came up with the 24 solutionsfor my $a (1.. 9) {
for my $b (grep {!/$a/} 1 .. 9) {
for my $c (grep {!/$a|$b/ 1 .. 9) {
my $first = join '', $a, $b, $c;
next if $first % 7 || (scalar reverse $first) %7;
#....
print "$first $second $third"Re:I bet New Scientist publishes a correction
depesz on 2008-06-09T13:09:58
well, you said: 1 solution for 7, with reverse 2. actually - there are 2 solutions for 7 (4 with reverse).
and your code shows them.
also - you didn't take into consideration the fact that digits cannot be reused between numbers generated for various dividers.
Huh?
Limbic Region on 2008-06-09T13:24:43
With regards to the math: What I posted about 24 solutions comprised of 10 different integers was correct (as is my code). I made a mistake when I was explaining where I came up with the 24 solutions because I didn't have the code or the results in front of me. My apologies.
also - you didn't take into consideration the fact that digits cannot be reused between numbers generated for various dividers
I am not sure I understand.How is that allowing re-use?for my $a (1.. 9) { # 1 - 9
for my $b (grep {!/$a/} 1 .. 9) { # 1 - 9 not used in $a
for my $c (grep {!/$a|$b/} 1 .. 9) { # 1 - 9 not used in $a or $b
#...
for my $i (grep {!/$a|$b|$c|$d|$e|$f|$g|$h/} 1 .. 9) { # 1 - 9 not in any previous loop
In any event, that's not the code I used anyway. The code I used was some fancy C = N choose K iterators with a code ref passed in for combinations to skip. It would have been difficult to reproduce in the 10 minutes I allow myself in the morning to surf use.perlRe:I bet New Scientist publishes a correction
Smylers on 2008-06-09T10:28:37
I'm sure they won't publish a correction.
Note that the spec says to find a 3-digit number which satisfies the criteria, not the 3-digit number. That there are multiple such numbers, and you could've found a different one, doesn't violate the spec.
Once you've done what it says, you will have 3 3-digit numbers, plus their reverses. That's 6 integers.
Yes, other people could validly come up with a different set of 6 integers. So what? There's nothing in the spec prohibiting that! As others have noted, all that matters is the smallest and largest integers in that set — and all the possible sets of valid 6 integers have the same smallest and largest.
So, following their instructions does yield 6 integers. And the answer to the question they asked is unique.
That's really too bad
Limbic Region on 2008-06-09T12:31:52
I guess I won't be looking into New Scienties afterall
Having worked on interesting puzzles like this as long as I can remember, as well as knowing many people who have the same interest - this is the type of puzzle no one likes to work on.
A simple foot note that says: While multiple preliminary solutions are possible, the max and min will always be the same.
Would have gone a long way to making others and myself happier that our solutions were correct.
By the way - you have read into the spec.
Once you've done what it says, you will have 3 3-digit numbers, plus their reverses. That's 6 integers.
That's not what the spec has said, that's how you have interpreted it. That's probably the correct interpretation - but certainly not the only one.
I rather enjoy puzzles where the solution hinges upon realizing the spec doesn't say something the reader assumes it does - but it is painfully obvious once the solution is known.
In any event, I have no interest in getting New Scientist if the puzzles are presented consistently this way.Re:That's really too bad
Ovid on 2008-06-09T13:16:23
They're not usually this unclear. I think it's just a fluke, but I'd have to work through some others to be sure.
next if $nine =~ qr/[$seven]/;
Here is my solution in Python... my Perl is not strong enough yet
There are three sets of 6 numbers which satisfy the conditions. The min and max of those three sets is the same for all three, which can be the only answer to the problem.
I didn't find the wording ambiguous at all.
Re:My solution
Ovid on 2008-06-09T16:59:05
Hey, it's nice to see how different languages tackle the problem. Thanks!
Re:My solution
runrig on 2008-06-09T23:57:25
Cool! It's nice to compare strengths/weaknesses/(or just plain differences) of both languages. This syntax is terse and if it were perl (and the function were not clearly named), people would probably complain that it's confusing and unreadable:reverse_num = lambda n: int(str(n)[::-1])It's nice that you can slice a string (like substr() on steroids()), though not so nice that you have to cast the number as a string before you reverse it.
It's also nice that sets are built into the language, and "+" seems to "add" sets together. But for large sets, I wonder how efficient code like
set1 + set2 + set3 == big_setis (though it probably doesn't matter much for the nine digits we are dealing with here, and I think the smartmatch operator in perl 5.10 would at least accomplish the "==" part). In perl, we would probably use hashes, but I don't think there is a simple/elegant way to do the adding and difference of the sets like you have in your code.There is also no "yield" statement in perl, but we do have anonymous functions and closures, which could accomplish pretty much the same thing (and more).
No one else seems to be posting solutions yet, so I'll hold off for now
:-) Re:My solution
lost-theory on 2008-06-11T18:18:59
I probably wrote some things more tersely than other Python programmers would (e.g. the extended slice syntax [::-1] for reversing, which not many people use); if it were 'real' code I'd probably clean it up a bit. The lambda's are another thing I like using in my own code, but are not widely used in practice. I code in the same style when I'm working on Project Euler problems (get something that works first, then worry about 'ugly' hacks).
I don't mind casting the integer as a string before reversing... it's not a very common operation, and numbers and strings have different operations which apply to them (strings/iterables have len, sort, reverse,
...; ints/numbers have abs, pow, hex, ...), so the behavior seems pretty consistent (IMO). Sets might not be the most efficient thing to use, but now that they're built-in in Python they are super handy for easily solving many common list-related tasks (removing duplicates, diffing two lists, etc.).
depesz's code was quite interesting, if any other solutions (Perl or otherwise) exist I'd be happy to see them
:) Re:My solution
runrig on 2008-06-16T17:36:39
Here's my go:The "0" in the qr of the anonymous function seems redundant, but the code got uglier if I removed it (as to why, I'll leave that as an exercise).#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw(min max);
my @nlist = grep !(/0/ || /(.).*\1/ ), 123..987;
my %f;
for my $n ( qw( 7 9 11 ) ) {
$f{$n} = sub {
my $str = join('', @_);
my $re = qr/[0$str]/;
grep !( $_ % $n || reverse() % $n ||/$re/ ), @nlist;
};
}
my ($min, $max) = (1000, 0);
for my $d_7 ( $f{7}->() ) {
for my $d_9 ( $f{9}->($d_7) ) {
for my $d_11 ( $f{11}->($d_7, $d_9) ) {
print "$d_7 $d_9 $d_11\n";
my ($tmp_min, $tmp_max) = (min($d_7, $d_9, $d_11), max($d_7, $d_9, $d_11));
if ( $tmp_min <= $min and $tmp_max >= $max ) {
( $min, $max ) = ( $tmp_min, $tmp_max );
}
}
}
}
print "min: $min max: $max\n";Re:My solution
runrig on 2008-06-16T17:43:21
And just when I think I'm done...I realize the first part can be replaced with this:my %f;
for my $n ( qw( 7 9 11 ) ) {
my @nlist = grep !( $_ % $n || reverse() % $n ||/0/ || /(.).*\1/ ), 123..987;
$f{$n} = sub {
my $str = join('', @_);
my $re = qr/[0$str]/;
grep !/$re/, @nlist;
};
}Re:My solution
pudge on 2008-06-19T23:29:02
Unsurprisingly, we used a lot of the same elements, including
/(.).?\1/. I decided to recurse. Since these are all three-digit numbers, a simple (sort @nums)[0,-1] gives min and max, so as soon as we get a hit in 11 we have all the info we need. So yours could be shortened quite a bit further: Mine is here.for my $d_7 ( $f{7}->() ) {
for my $d_9 ( $f{9}->($d_7) ) {
for my $d_11 ( $f{11}->($d_7, $d_9) ) {
printf "min: %d, max: %d\n",
(sort(map { reverse($_)+0, $_ } $d_7, $d_9, $d_11))[0,-1];
exit;
}
}
}#!/usr/bin/perl
use warnings;
use strict;
my @six = map { $_, reverse($_)+0 } foo([grep { !/0/ && !/(.).?\1/ } 123..987], [7, 9, 11]);
printf "7: %d/%d, 9: %d/%d, 11:%d/%d\nAnswer: %d : %d\n", @six, (sort @six)[0, -1];
sub foo {
my($d, $n) = @_;
my $x = shift @$n;
for my $i (@$d) {
if (!($i % $x) && !(reverse($i) % $x)) {
if (@$n) {
my @t = foo([grep !/[$i]/, @$d], [@$n]);
return($i, @t) if @t;
} else {
return $i;
}
}
}
return;
}