Recursion without lists

Discussion in 'Perl Misc' started by Simon Andrews, Mar 1, 2010.

  1. In a discussion about interview questions the following problem came up:

    "Take the numbers 123456789. Insert between each number either a + * or
    nothing and find the two equations whose answer is 2002"

    Of course I had a go and managed to find a solution, but I'm not really
    happy with the way I did it. In particular I'm not wild about:

    1) Having to build the full set of symbols before performing the actual
    calculations. Is there a simple way to do this which only holds one
    equation in memory at a time?

    2) The use of eval. In this particular case it's probably the nicest
    way to do it, but is it really necessary?

    Any thoughts?

    Simon.

    #!perl
    use warnings;
    use strict;

    my @numbers = (1,2,3,4,5,6,7,8,9);
    my @symbols = ('','+','*');

    my $options = build_symbol_options([[]]);

    foreach my $option (@$options) {
    my $equation = '';
    for my $index(0..$#numbers-1) {
    $equation .= $numbers[$index];
    $equation .= $option->[$index];
    }
    $equation .= $numbers[$#numbers];

    my $answer = eval($equation);

    if ($answer == 2002) {
    print $equation," = 2002\n";
    }
    }


    sub build_symbol_options {

    my ($options) = @_;

    if (@{$options->[0]} == 8) {
    return $options;
    }

    my $new_options;

    foreach my $option (@$options) {
    foreach my $symbol (@symbols) {
    my @new_symbols = @$option;
    push @new_symbols,$symbol;
    push @$new_options, \@new_symbols;
    }
    }

    build_symbol_options($new_options);

    }
    Simon Andrews, Mar 1, 2010
    #1
    1. Advertising

  2. Simon Andrews <> wrote:
    >In a discussion about interview questions the following problem came up:
    >
    >"Take the numbers 123456789. Insert between each number either a + * or
    >nothing and find the two equations whose answer is 2002"


    Is this a test about guessing customer intentions from vague and
    actually meaningless or impossible specificiations?

    Onehundredtwentythreemillionfourhundredfiftysixthousandsevenhundredeightynine
    is only one number. Where is/are the other number(s) this task is
    talking about? How do you insert anything between a single element?

    There are no equal signs mentioned anywhere in that spec. Where do you
    get those "two equations" if you don't have an equal sign?

    What does some "answer" have to do with a (non-existing) equation?
    Equations don't have answers, at most they may have a solution or are
    true or false.

    jue
    Jürgen Exner, Mar 1, 2010
    #2
    1. Advertising

  3. Simon Andrews <> wrote:
    > In a discussion about interview questions the following problem came up:


    > "Take the numbers 123456789. Insert between each number either a + * or
    > nothing and find the two equations whose answer is 2002"


    > Of course I had a go and managed to find a solution, but I'm not really
    > happy with the way I did it. In particular I'm not wild about:


    > 1) Having to build the full set of symbols before performing the actual
    > calculations. Is there a simple way to do this which only holds one
    > equation in memory at a time?


    > 2) The use of eval. In this particular case it's probably the nicest
    > way to do it, but is it really necessary?


    Concerning your point 2) I have no better idea at the moment
    (or at least things would look quite a bit more complicated),
    but building the complete list of possible strings first and
    only then iterating over them can be avoided if you use re-
    cursion (and you can stop once you have the requested two
    solutions), e.g. like this:

    #!/usr/bin/perl

    use strict;
    use warnings;

    my $cnt = 0;
    add_op( '1', 2 );

    sub add_op {
    my ( $s, $n ) = @_;
    add_num( $s . $_, $n ) for ( '', '+', '*' );
    }

    sub add_num {
    my ( $s, $n ) = @_;
    if ( $n < 9 ) {
    add_op( $s . $n, $n + 1 );
    } elsif ( eval $s . $n == 2002 ) {
    print "$s$n = 2002\n";
    if ( ++$cnt == 2 ) {
    exit 0;
    }
    }
    }
    Regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
    Jens Thoms Toerring, Mar 1, 2010
    #3
  4. Simon Andrews

    Dr.Ruud Guest

    Simon Andrews wrote:

    > "Take the numbers 123456789. Insert between each number either a + * or
    > nothing and find the two equations whose answer is 2002"


    eval==2002 and print "$_ = 2002" while glob(join "{+,\\*,}", 1..9);

    --
    Ruud
    Dr.Ruud, Mar 1, 2010
    #4
  5. Simon Andrews

    Dr.Ruud Guest

    Dr.Ruud wrote:
    > Simon Andrews wrote:


    >> "Take the numbers 123456789. Insert between each number either a + *
    >> or nothing and find the two equations whose answer is 2002"

    >
    > eval==2002 and print "$_ = 2002" while glob(join "{+,\\*,}", 1..9);


    perl -wle '
    eval==$ARGV[0] and print "$_ = $ARGV[0]"
    while glob(join "{+,-,\\*,/,}", 1..9);
    ' 1962

    1+2-3+45*6*7+8*9 = 1962
    1+2*34*5*6-7-8*9 = 1962
    1+234*56/7+89 = 1962
    12*3*45/6*7+8*9 = 1962
    12*3/4*5*6*7+8*9 = 1962
    123*4*5+6-7*8*9 = 1962

    --
    Ruud
    Dr.Ruud, Mar 1, 2010
    #5
  6. Dr.Ruud <> wrote:
    > Simon Andrews wrote:


    > > "Take the numbers 123456789. Insert between each number either a + * or
    > > nothing and find the two equations whose answer is 2002"


    > eval==2002 and print "$_ = 2002" while glob(join "{+,\\*,}", 1..9);


    Nice! I never did imagine that you can use 'glob' like this. Things
    like that are the one of the reason why reading clpm is so useful;-)

    Best regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
    Jens Thoms Toerring, Mar 1, 2010
    #6
  7. Simon Andrews

    Guest

    On 1 Mar 2010 21:57:02 GMT, (Jens Thoms Toerring) wrote:

    >Dr.Ruud <> wrote:
    >> Simon Andrews wrote:

    >
    >> > "Take the numbers 123456789. Insert between each number either a + * or
    >> > nothing and find the two equations whose answer is 2002"

    >
    >> eval==2002 and print "$_ = 2002" while glob(join "{+,\\*,}", 1..9);

    >
    >Nice! I never did imagine that you can use 'glob' like this. Things
    >like that are the one of the reason why reading clpm is so useful;-)
    >
    > Best regards, Jens


    I tried that glob above but it didn't work on my machine.
    I read the docs for File::Glob, supposedly what CORE::Glob is since 5.6
    Here's what I think I understand about it:

    - glob() does recursive pattern expansion.

    - If wildcards are included, it will flesh out each
    pattern and try to match files, but if it can't,
    the pattern is not included in the result list.

    - If no wildcards are in the pattern it just returns
    the pattern.

    - Characters can be escaped with \, presumeably for metachars
    and for wildcard chars.

    - Among others metachars {} denote multiple patters and
    [] denote character class. Other metachars exist as recognised by
    globe \*?~

    Finally, on DOSISH machines, the \ is a valid directory separator
    so it cannot be used as a quoting character. This fact makes the
    \* in {+,-,\*,/} invalid and the \* instigates a dos substitution
    of the current expansion using a root plus wild card embedded into the
    current pattern. This fails since no such file is found, therefore
    the pre-expanded pattern is not included in the result list.

    So all the other combinations are valid, but not \* and
    doesen't work on windows.

    This takes a long time to expand on my machine. Probably because
    its trying to do the dos wildcard expansion.
    1{+,-,\*,/,}2{+,-,\*,/,}3{+,-,\*,/,}4{+,-,\*,/,}
    5{+,-,\*,/,}6{+,-,\*,/,}7{+,-,\*,/,}8{+,-,\*,/,}9


    -sln
    , Mar 2, 2010
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Salerno

    recursion and linked lists

    John Salerno, Apr 1, 2006, in forum: Python
    Replies:
    3
    Views:
    238
    Ed Singleton
    Apr 7, 2006
  2. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    384
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  3. Replies:
    9
    Views:
    4,866
  4. Kenshin
    Replies:
    0
    Views:
    281
    Kenshin
    Dec 9, 2009
  5. Replies:
    8
    Views:
    716
    John Reye
    Apr 26, 2012
Loading...

Share This Page