Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Recursion without lists

Reply
Thread Tools

Recursion without lists

 
 
Simon Andrews
Guest
Posts: n/a
 
      03-01-2010
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]} == {
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);

}
 
Reply With Quote
 
 
 
 
Jürgen Exner
Guest
Posts: n/a
 
      03-01-2010
Simon Andrews <(E-Mail Removed)> 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?

Onehundredtwentythreemillionfourhundredfiftysixtho usandsevenhundredeightynine
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
 
Reply With Quote
 
 
 
 
Jens Thoms Toerring
Guest
Posts: n/a
 
      03-01-2010
Simon Andrews <(E-Mail Removed)> 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://www.velocityreviews.com/forums/(E-Mail Removed)
\__________________________ http://toerring.de
 
Reply With Quote
 
Dr.Ruud
Guest
Posts: n/a
 
      03-01-2010
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
 
Reply With Quote
 
Dr.Ruud
Guest
Posts: n/a
 
      03-01-2010
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
 
Reply With Quote
 
Jens Thoms Toerring
Guest
Posts: n/a
 
      03-01-2010
Dr.Ruud <(E-Mail Removed)> 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 ___ (E-Mail Removed)
\__________________________ http://toerring.de
 
Reply With Quote
 
sln@netherlands.com
Guest
Posts: n/a
 
      03-02-2010
On 1 Mar 2010 21:57:02 GMT, (E-Mail Removed) (Jens Thoms Toerring) wrote:

>Dr.Ruud <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
va_arg... recursion: changing arguments and the using recursion jononanon@googlemail.com C Programming 8 04-26-2012 08:37 PM
Variadic Templates – Recursion – Initializer Lists. Kenshin C++ 0 12-09-2009 12:38 PM
postorder traversal of binary search tree without recursion nishit.gupta@st.com C Programming 9 04-20-2007 03:50 PM
List of lists of lists of lists... =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==?= Python 5 05-15-2006 11:47 AM
recursion and linked lists John Salerno Python 3 04-07-2006 08:37 AM



Advertisments