Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

Ovid
  (email not shown publicly)
http://publius-ovidius.livejournal.com/
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Journal of Ovid (2709)

Sunday June 08, 2008
11:47 AM

New Scientist Enigmas

[ #36624 ]

Every week, New Scientist has an "Enigma" puzzle. I've always thought they should be easy to solve with programming, so this week I decided to try it. Here's this week's puzzle:

Using each of the digits 1 to 9, find a 3-digit positive integer divisible by 7 whose reverse is an integer also divisible by 7, a 3-digit positive integer divisible by 9 whose reverse is an integer also divisible by 9, and a 3-digit positive integer divisible by 11 whose reverse is an integer also divisible by 11.

What are the smallest and largest of your six integers?

So basically you want all three digit numbers not containing zero. When you are examining candidates, the numbers should use "each" of the digits, not just "any". My program is still getting too many results. Either I'm missing something fundamental or their is an ambiguity in the spec.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • You get one pair each for 7 and 11, but two pairs for 9, right? Same here.
    • 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 :)

    • 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!

    • Ok, the ambiguity is in the part of the solution they don't ask for. So their actual question has a unique answer.
      • I think you're seeing something I don't, then, because I have no idea what your first sentence meant :)

    • OK, now I get your results :(

  • #!/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";
    }
    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?
    • 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

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

  • i don't really think there is ambiguity. i got 3 different sets of numbers, but all of them have the same min/max numbers.

    you can check my code at: http://www.depesz.com/ovid.pl [depesz.com]

    of course i could have made mistake, but the numbers "look" right to me.
    • I get the same sets of numbers, but what does "six integers" mean in this context?

      • i think this is just an mistake on the side of new scientist.
      • You have three three-digit numbers, and their reverses. That makes six by my counting...
        • 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.

          • 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.
  • Find a, b, c, d, e, f, g, h, and i where

    (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 == 0

    and where there exists an invertible function between the variables a..i to the numbers 1..9.
  • There are a total of 24 solutions to the puzzle. These 24 solutions are comprised of 10 unique integers. If you do not consider the reverse of an integer unique, there are 5 unique integers. No matter which way you slice this - there is no way to get to "six integers" unless the spec is incomplete.
    • 24 solutions? how did get them? can you show them?
        • 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.

  • I wrote a brute-force solution. My one little trick: next if $nine =~ qr/[$seven]/; A three digit number makes a fine character class inside of a regex when making sure that you're not reusing a digit.
    --

    --
    xoa

    • Hey, it's nice to see how different languages tackle the problem. Thanks!

          • 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:

            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