Re: A little arithmetic puzzle

--- Jasvir Nagra <[email protected]> wrote: > 
> The list has been fairly quiet of late so I thought I would share the
> following simple little puzzle I heard recently.
> 
> Using the numbers 1,5,6,7 exactly once and using any of addition,
> subtraction, division and/or multiplication zero or more times form an
> expression that evaluates to 21.  You may use brackets.
> 
> So  1 + 5 * (7 - 6) = 6  fr'instance
> and 1 * 5 + 6 * 7   = 47
> 
> but the puzzle needs 21.
> 
> Yes, you must use every number at least once.
> No, you may not repeat any number.
> No, you may not use powers just +-/*.
> No, you may not concatenate numbers together.
> 
> The puzzle is sufficiently simple that it can be solved with a pencil
> and paper (although I think its not quite trivial and took me a couple
> of hours).  The Fun offcourse is in getting perl to solve it.

Easy, the fastest method is to use stack based notation (RPN).  This
completely avoids the need for those pesky brackets.  The stack is
arranged into each of the permutations, and then the operators applied
in each permutation.  There is only 24 permutations of the numbers, and
64 permutations of the operators, combined there is 1536 different
expressions.  We need to select only those evaluating to 21.

Of course, the problem was specified arithmetically so a conversion from
RPN to an arithmetic expression is required also.  I haven’t, as I am most
familiar with RPN expressions thanks to Hewlett Packard.  It isn’t much
work anyway.

My program is verbose in output, showing each stack arrangement it tries.
With respect to time, it manages 2.2 seconds on an AMD K6-2 450Mhz,
including all that listing of tries.  My program isn't particularly
efficient.

I must say I cheated a little, the problem is VERY similar to a problem
described with the solution.  (British TV’s Channel 4 Countdown programme).

#!/usr/bin/perl -w

use strict;

use Math::RPN;
use List::Permutor;

my @numbers     = qw(1 5 6 7); # All used once.
my @operators   = qw(+ - / *); # Any used three times.

my @solutions;

# Permutate the number sequence
my $perm = new List::Permutor(@numbers);
while (my @number_sequence = $perm->next) {

    # Permutate the operator sequence
    for my $first (@operators) {
        for my $second (@operators) {
            for my $third (@operators) {

                # Construct stack (with ops) to evaluate
                my @stack = (@number_sequence, $first, $second, $third);

                # Evaulate avoiding pesky divide by zero
                my $result = 0; # Set to 0 if divide by zero
                eval {
                    $result = rpn(@stack);
                };

                # Push onto solutions
                print "@stack evaluates to " . $result . "\n";
                push @solutions, [@stack] if $result == 21;
            }
        }
    }
}

for (@solutions) {
    my @solution = @{ $_ };
    print "Solution: @solution\n";
}

__END__

Jonathan Paton

=====
#!perl
$J=' 'x25 ;for (qq< 1+10 9+14 5-10 50-9 7+13 2-18 6+13
17+6 02+1 2-10 00+4 00+8 3-13 3+12 01-5 2-10 01+1 03+4
00+4 00+8 1-21 01+1 00+5 01-7 >=~/ \S\S \S\S /gx) {m/(
\d+) (.+) /x,, vec$ J,$p +=$2 ,8,= $c+= +$1} warn $J,,

________________________________________________________________________
Want to chat instantly with your online friends?  Get the FREE Yahoo!
Messenger http://uk.messenger.yahoo.com/