Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Simple Math Puzzle...

by Daruma (Curate)
on May 10, 2003 at 07:10 UTC ( #257085=perlmeditation: print w/ replies, xml ) Need Help??

Greetings Monks!

Yesterday I was given a riddle over an instant messenger connection. "What 5 digit number am I thinking of?" It was a simple mathematical puzzle. Here are the conditions of the query...

What 5 digit number am I thinking of?

  • It has 2 prime digits.
  • Digit 3 is the highest number.
  • Digit 2 is lowest.
  • Digit 5 is between digit 2 and digit 1 and is half of digit 4.
  • There are no duplicates.
  • Digit 1 is 1 less than digit 3.
  • Digit 1 is higher than the sum of digits 4 and 5.

Well... I twiddled around with it a bit and found one answer using a good bit of guesswork. Then my IM prompter said she had two answers. At this point, I was hooked. I not only had to find three answers... I had to find all possible answers, and fast!

I whipped together a quick bit of code...
#!c:\perl\bin\perl.exe # # FILE: autoprime.pl # # Daruma # 09-MAY-2003 # # puzzle: What 5 digit number am I thinking of? # It has 2 prime digits. # Digit 3 is the highest number. # Digit 2 is lowest. # Digit 5 is between digit 2 and digit 1 and is half of digit 4. # There are no duplicates. # Digit 1 is 1 less than digit 3. # Digit 1 is higher than the sum of digits 4 and 5. use warnings; use strict; my $candidate; my @digits; my $flag; for ($candidate = 12345; $candidate <= 98765; $candidate++) { $flag = 0; check_prime($candidate); check_digit_3($candidate); check_digit_2($candidate); check_digit_5($candidate); #check_duplicates($candidate); # problem? check_digit_1($candidate); if ($flag < 1) { print "$candidate\n"; } } # subroutines sub check_prime { # The candidate number must have 2 prime digits my $candidate = shift; my @digits = split //,$candidate; my $prime_count = 0; foreach my $digit (@digits) { if ($digit =~ /(2|3|5|7)/) { $prime_count++ } } if ($prime_count != 2) { $flag++ } } sub check_digit_3 { # Digit 3 is the highest number. my $candidate = shift; my @digits = split //,$candidate; my $digit_3 = splice @digits,2,1; foreach my $digit (@digits) { if ($digit_3 < $digit) { $flag++ } } } sub check_digit_2 { # Digit 2 is lowest. my $candidate = shift; my @digits = split //,$candidate; my $digit_2 = splice @digits,1,1; foreach my $digit (@digits) { if ($digit_2 > $digit) { $flag++ } } } sub check_digit_5 { # Digit 5 is between digit 2 and digit 1 # and is half of digit 4. my $candidate = shift; my @digits = split //,$candidate; my $digit_5 = pop(@digits); my $digit_1 = shift(@digits); my $digit_2 = shift(@digits); my $digit_4 = pop(@digits); if ($digit_5 > $digit_1 and $digit_5 < $digit_2) {} # good elsif ($digit_5 < $digit_1 and $digit_5 > $digit_2) {} # also good else { $flag++ } if ($digit_5 != $digit_4 / 2) { $flag++ } } sub check_duplicates { # There are no duplicates. # Problems with this sub... my $candidate = shift; my @digits = split //,$candidate; foreach my $digit (@digits) { #shift(@digits); foreach my $check_digit (@digits) { if ($digit == $check_digit) { $flag++ } } } } sub check_digit_1 { # Digit 1 is 1 less than digit 3. # Digit 1 is higher than the sum of digits 4 and 5. my $candidate = shift; my @digits = split //,$candidate; my $sum_4_5 = $digits[3] + $digits[4]; if ($digits[0] != $digits[2] - 1 or $digits[0] <= $sum_4_5) { $flag+ ++ } }

I am quite sure there is a MUCH more efficient way to handle the problem, but this was a quick hack. Any suggestions, concerns, criticisms or witticisms are welcome, as always...

Daruma

Comment on Simple Math Puzzle...
Download Code
Re: Simple Math Puzzle...
by hossman (Prior) on May 10, 2003 at 07:48 UTC
    My first suggestion, would be to dump the "flag" variable, and change the methods so they return true if the test is "ok", then short circut out if any of the tests fail...
    for ($candidate = 12345; $candidate <= 98765; $candidate++) { if (check_prime($candidate) && check_digit_3($candidate) && check_digit_2($candidate) && check_digit_5($candidate) && #check_duplicates($candidate) && # problem? check_digit_1($candidate)) { print "$candidate\n"; } }
    ...so you don't waste time on tests that don't matter (because you allready know other tests don't work).
Re: Simple Math Puzzle...
by hossman (Prior) on May 10, 2003 at 07:59 UTC
    BTW, I just noticed...
    • Digit 3 is the highest number.
    • Digit 5 is ... half of digit 4.
    • Digit 1 is higher than the sum of digits 4 and 5.

    Which means assuming 3 is "9" (as big as it can be), then 1 can be at most "8", so 4 + 5 can be at most "7", so the biggest they can be are "4" and "2".

    So now you've got "8_942" as your max, and with the no duplicates rule (and the "2 is lowest" rule), that means you can stop your for loop at "83945".

    UPDATE: But wait, there's more!!!!!

    Using the same rules, we can increase the starting number of your for loop ... 4 and 5 have to be at least "2" and "1" (because of the half rule) which means 1 has to be at least "4", which gives you 4__21, so you can safely start your for loop at "40321".

Re: Simple Math Puzzle...(no code required?)
by BrowserUk (Pope) on May 10, 2003 at 09:33 UTC

    D(1,3,4,5) !=0 and D(1,2,4,5) != 9. D5 cannot be 0 (it would be lowest), D5 cannot be higher than 2 because d5(3) + d4(6) => d1(9) but d3 is hi +ghest. d5 must be 1|2, so d4 must be 2|4, so d1 must be > 3, so d3 must be > +4. D2 must be 0|1. Eliminate the impossible Digit 1 2 3 4 5 ----------------- 0 x 0 x x x 1 x 1 x x 1 2 x x x 2 2 3 x x x x x 4 4 x x 4 x 5 5 x 5 x x 6 6 x 6 x x 7 7 x 7 x x 8 8 x 8 x x 9 x x 9 x x Leaves us these choices. 4 0 5 2 1 5 1 6 4 2 6 7 7 8 8 9 d1+1 = d3 means this further reduces to 40521 50621 60721 70821 80921 * 70842 71842 80942 * 81942 *

    Eliminating those * that lack two prime digits leaves five+ six answers? (I think!)

    (40521, 50621, 60721, 70821, 70842+, 71842)

    + Corrected. Thanks to crenz.


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller

      I like the way how you showed to get the correct solutions; however, 70842 should be counted a solution as well -- it has two prime digits (2 and 7).

      The "two primes condition" follows from the fact that columns 4 and 5 have at most one prime, columns 2 has no prime, so there must be at least one prime in columns 1 and 3. But if digit 1 is 8, then digit 3 is 9, so no prime. This will directly create all solutions w/o any test, based on the implied order and your logic above:

      use strict; use warnings; for my $two (0..1) { for my $five (($two+1)..2) { for my $one ((3*$five+1)..7) { print "$one$two".($one+1).(2*$five)."$five\n"; } } }
Re: Simple Math Puzzle...
by hv (Parson) on May 10, 2003 at 12:43 UTC

    One initial note: "10234" would be a better starting point than "12345".

    For the problem sub check_duplicates(), if you're going to write it that way you need to allow for the fact that you'll get 5 mandatory matches, when you compare digit-1 to digit-1 etc: you can allow for that by subtracting 5 from $flag.

    Another approach is to use indices to iterate over the arrays so that you can avoid comparing a digit against itself:

    for my $i (0 .. $#digits) { for my $j (0 .. $#digits) { next if $i == $j; ++$flag if $digit[$i] == $digit[$j]; } }

    Another way to avoid it, since an equality check is symmetrical, is to iterate the inner loop only over the digits following the current outer digit:

    for my $i (0 .. $#digits) { for my $j ($i + 1 .. $#digits) { ++$flag if $digits[$i] == $digits[$j]; } }

    But I'd rather use a simple regexp:

    sub check_duplicates { my $candidate = shift; ++$flag if $candidate =~ /(.).*\1/; }

    For check_prime(), note that a character class (/[2357]/) is more efficient than an alternation (/2|3|5|7/), but for counting the number of occurrences of a class of characters tr/// is faster still:

    sub check_prime { my $candidate = shift; ++$flag if 2 != $candidate =~ tr/2357//; }

    As a general efficiency rule, duplicated effort is a red flag: rather than let each check subroutine split the candidate to an array, you could do it once in the main loop and pass a reference to the resulting array as a second argument to the relevant check subroutines.

    Note also that you can gain time by ordering the check subroutines so that the ones most likely to fail or quickest to check appear earlier (at least if you also follow others' advice and short-circuit on the first failure) - in this respect, I'd check for duplicates first, but I'd also be inclined to avoid checking all of (for example) 44000 .. 44999 by checking for where the first duplicate occurs:

    for (my $candidate = 10234; $candidate <= 98765; ++$candidate) { # we want to jump eg from 10992 to 11000 # note not 'next': we've already incremented if the s/// succeeds redo if $candidate =~ s{ ^ (.*? (.) .*? \2) (.*) }{ ($1 + 1) . ("0" x length($3)) }ex; ... }

    On another topic, you've done a good job of writing self-documenting code here, but I should mention that while I agree with other respondents about removing the use of $flag, I'd otherwise suggest renaming it - since it will have a true value if the candidate is not acceptable, I'd call it something like $bad or $fail and then finish the main loop with:

    print "$candidate\n" unless $bad;

    Hugo
Re: Simple Math Puzzle...
by EvdB (Deacon) on May 12, 2003 at 07:47 UTC

    I whipped up a brute force method which might be of interest as a reference.

    # Crude but effective hunter. use strict; my %primes = map { $_ => 1 } ( 2,3,5,7 ); for (10234..98765) { my @a = split //; # Digit 1 is 1 less than digit 3. next unless $a[0] == $a[2]-1; # Digit 1 is higher than the sum of digits 4 and 5. next unless $a[0] > $a[3]+$a[4]; my @sorted = sort @a; my $highest = pop @sorted; my $lowest = shift @sorted; # Digit 3 is the highest number. next unless $a[2] == $highest; # Digit 2 is lowest. next unless $a[1] == $lowest; # Digit 5 is between digit 2 and digit 1 and is half of digit 4. my ($low, $high) = sort ($a[0], $a[1]); next unless $a[4] < $high; next unless $a[4] > $low; next unless $a[4] == $a[3]/2; # It has 2 prime digits. my $p_count = 0; foreach (@a) { $p_count++ if $primes{ $_ }; } next unless $p_count == 2; # There are no duplicates. my %uniq = (); foreach (@a) { $uniq{$_} = 1; } next unless scalar( keys %uniq ) == 5; # All tests passed - print number. print @a, "\n"; }

    The results produced match those given above - so it must be right....

    -- tidiness is the memory loss of environmental mnemonics

Re: Simple Math Puzzle...
by jackdied (Monk) on May 13, 2003 at 07:06 UTC
    Before they discontinued it, Dr Dobbs "Dr Ecco's Omniheurst Corner" was great because they had these kinds of problems -- but they were too big to be brute forced!

    Brute force here is at worst 10^5. But since digit3 depends on digit1, and digit5 depends on digit4 there are only three 'loose' digits, or 10^3 possibilities.

    You could brute-froce the 1000 combinations on paper ;)

    -jack

    ps, you can find old Ecco columns by typing 'ecco' in the search box on ddj.

Re: Simple Math Puzzle...
by mtve (Chaplain) on May 15, 2003 at 07:01 UTC

    My quick hack

    #!perl -l $_=~('(.)'x5) && # (put our digits in $1..$5) y/2357//==2 && # It has 2 prime digits. "$1$2$4$5"!~/[$3-9]/ && # Digit 3 is the highest number. "$1$3$4$5"!~/[0-$2]/ && # Digit 2 is lowest. ($5>$2&$5<$1|$5>$1&$5<$2) && # Digit 5 is between digit 2 and digit 1 $5==$4/2 && # ... and is half of digit 4. !/(.).*\1/ && # There are no duplicates. $1==$3-1 && # Digit 1 is 1 less than digit 3. $1>$4+$5 && # Digit 1 is higher than the sum of digit +s 4 and 5. print for 0..9x5

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://257085]
Approved by Paladin
Front-paged by demerphq
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (6)
As of 2014-09-02 00:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (18 votes), past polls