Write a Program which takes ‘n’ non-zero Integer arguments where n>3.
You need to use n-1 arguments in the same order to have the result as the nth argument by applying any of the arithmetic operators [ + , - , * , / ].
Assume all the operators will have same precedence.

Example 1:
Given n = 5 numbers are
1 2 3 4 20
Solution has to be provided in such a way that output should be as below
1 * 2 + 3 * 4 = 20

John dev wrote:Assume all the operators will have same precedence.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828

28

posted

1

I never saw that. I still think it is difficult.

Chan Ag
Bartender

Joined: Sep 06, 2012
Posts: 1049

15

posted

0

And there may be more than one solution for a particular input and a desired output.

A not so nice solution could be to come up with all combinations, and do a computeResult on these combinations. If there are additional qualities associated with the sequence in which the numbers are arranged, we could restrict all combinations to a subset, by doing a progressive computeResult of sorts so we could eliminate few cases.

While coming up with all combinations and doing a computeResult may not be so complex, a progressive computeResult seems way too complex.

Edit : I just re read the question and realized where I was wrong. n can be greater than 5 and the operators can repeat- so it's not a combination problem. Well, too many cases to consider. Too complex and CPU intensive ( I think so as there are many cases possible ) puzzle I think.

John dev wrote:Write a Program which takes ‘n’ non-zero Integer arguments where n>3.
You need to use n-1 arguments in the same order to have the result as the nth argument by applying any of the arithmetic operators [ + , - , * , / ]. Assume all the operators will have same precedence.

Sounds like one of the more advanced Project Euler problems, or possibly a Java version of those Vorderman 'Countdown' questions.

Oddly enough, I used to be quite good at those, but I couldn't explain the exact mechanics to you: I tend to just "see" them. I suspect there are heuristics you could use that might help you to eliminate unlikely or impossible combinations (for example, non-integral divisions), but beyond that I have no idea.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here

Winston Gutkowski wrote:Sounds like one of the more advanced Project Euler problems, or possibly a Java version of those Vorderman 'Countdown' questions.

For this one, I'd just (to begin with) try a brute-force search. I don't think it would be that bad. You've got 4^(n-2) cases to check, so if n is large it's not going to be fast. If the upper bound on n is no more than, say, 12, you might be OK.

Brute force would mean 4 to the power n-1 combinations. To try to get a greedy approach would probably improve the time yet I wonder how it will look like.

The good thing about this problem is that it does not ask for all possible solutions, this meaning that a*a*..*a + b*b*..*b is just an useful solution as b*b*..*b + a*a*..*a.

Firstly given n-1 numbers , we can assume that any solution could be written like a number of + and - on a number p (p <= n - 1) operands , where each operand is an expression containing only * and / and input numbers.
However , what would be the criteria on which to choose the best current solution ?

John dev wrote:
Write a Program which takes ‘n’ non-zero Integer arguments where n>3.
You need to use n-1 arguments in the same order to have the result as the nth argument by applying any of the arithmetic operators [ + , - , * , / ].
Assume all the operators will have same precedence.

Example 1:
Given n = 5 numbers are
1 2 3 4 20
Solution has to be provided in such a way that output should be as below
1 * 2 + 3 * 4 = 20

Campbell Ritchie wrote:I never saw that. I still think it is difficult.

Actually, I think the bit that's more important is the "You need to use n-1 arguments in the same order to have the [same] result as the nth argument" bit (which, I must admit, I missed when I posted previously). That reduces the number of possibilities enormously - and also, I suspect, improves the possibility for heuristics that will eliminate many combinations of operators.

Myke Enriq wrote:Brute force would mean 4 to the power n-1 combinations.
(...)

John dev wrote:
Write a Program which takes ‘n’ non-zero Integer arguments where n>3.
You need to use n-1 arguments in the same order to have the result as the nth argument by applying any of the arithmetic operators [ + , - , * , / ].
Assume all the operators will have same precedence.

Example 1:
Given n = 5 numbers are
1 2 3 4 20
Solution has to be provided in such a way that output should be as below
1 * 2 + 3 * 4 = 20

Brute force would mean 4 to the power n-2 permutations. The operators go in between n-1 numbers, and their order is significant.

If the programming language is not specified, you are much better off using a language that supports something like the 'eval' construct found in your most primitive shells.

"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery

I would make a function that takes an array of ints and returns either the string with all the right operators that work or null. The recursion "don't recurse" condition is when n=2.

canMake(8 8) would return "8=8"
canMake(4 7) would return null

canMake(1 2 3 4 20) would make the following calls:
- canMake(1 2 3 16), checking to see if there's any way 1, 2 and 3 and be combined to make 16, so that 1 ? 2 ? 3 + 4 = 20 works.
- canMake(1 2 3 24), checking to see if there's any way 1, 2 and 3 and be combined to make 24, so that 1 ? 2 ? 3 - 4 = 20 works.
- canMake(1 2 3 5), checking to see if there's any way 1, 2 and 3 and be combined to make 5, so that 1 ? 2 ? 3 * 4 = 20 works.
- canMake(1 2 3 80), checking to see if there's any way 1, 2 and 3 and be combined to make 80, so that 1 ? 2 ? 3 / 4 = 20 works.

Of course those calls to canMake() would also make additional calls, etc.

(Don't forget to check for divition by 0 before making some of the recursive calls.)

This still counts as "brute force" since we still check all 4 ^ (n-2) possibilities (unless a solution is found early). However, the recursive version of the code would be a little bit clearer and easier to program than other ways of doing it, IMO.

It reminds me of a television program many years ago. It was called "des chiffres et des lettres" (in Dutch "cijfers en letters")
where the two candidates were given four digits and had to try to make a given number, in the exact way the OP described.
The candidate who came nearest got the points. That number was a random number, so a solution was not always possible.

Problem here is, I think, the division. You must use doubles (integer division would not work, of course) and so you could introduce
rounding errors. Therefore you must use rounding in the two parameter "canMake".

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012

3

posted

0

Piet Souris wrote:Nice recursion!

Thank you.

Problem here is, I think, the division. You must use doubles (integer division would not work, of course) and so you could introduce
rounding errors. Therefore you must use rounding in the two parameter "canMake".

That's a good point. Should 7/4 equal 1, 2 or 1.75? The OP stated that the numbers are integers to start with, so I assumed integer math. i.e. 7/4=1. I suppose it could be programmed any way we want, as long as precision isn't lost.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012

3

posted

0

Piet Souris wrote:Problem here is, I think, the division. You must use doubles (integer division would not work, of course) and so you could introduce
rounding errors. Therefore you must use rounding in the two parameter "canMake".

...or use arguments that don't lose precision when you do integer division. e.g. Apache Fractions.

So I decided to do some stats on this after I finished the actual puzzle bit.

I set up a random generator to get n numbers, and do an arbitrary operation (+,-,/,*) on those n numbers. (I realized after running it a while, my program was giving me different results than these, even though they both totaled up correctly, which means that for the majority of numbers, if there's one answer, there's likely more.)

I then set up a second list of n numbers, intentionally incorrectly (filled them in with 1's, and set the last number to n+1), to see what the worst case scenario was like.

My algorithm is just recursively brute forcing the thing, so this is useful to have a baseline of any improvements I do. The only 'shortcut' I had was to halt the path if dividing by zero.

I had the program report back to me every 5 numbers, so 5,10,15 and 20, which is where I stopped. I had it report back for both the good list and the bad list the total time up to that point (as well as the individual times per number), the number of cycles through the recursion as well as the number of cycles where it actually did some work in the recursive function (rather than being short circuited by the dividing by zero).

No surprise on the intentionally bad list - very exponential

Mildly surprising on the good list - I thought it would be more like the good one, but to a lesser extent, but it does seem to be pretty much random on how it's going to go

Details...
At n=5, both the good list and the broken list were at 0ms, and had gone through the recursive loop 71 and 362 times respectively.
At n=10, the good list had a total time of 2 and 3ms. 17122/293315 iterations, respectively.
At n=15, good list took 62ms, the bad took 4 times longer at 2123ms. Good was 16% more efficient at this time.
At n=18, good was only taking 656ms- bad took 109019ms, so half a second vs 1.5 minutes. I knew finding a path was much more efficient, but there must be a lot of good routes to get to the end there if there's that much of a time difference. The bad list is 62% slower.
At n=19, good took 109203, a huge jump, bad jumping to 517168.
n=20 is currently running. Since the brute force method will take 16 times longer than last time, I'm not going to wait for the bad to be done.

Number of elements

Time to find a solution(ms)

Worst case scenario

1

0

0

2

0

0

3

0

0

4

0

1

5

0

00

6

0

3

7

13

25

8

6

12

9

2

3

10

5

11

11

1

37

12

5

164

13

114

520

14

62

2123

15

110

6710

16

0

33705

17

656

109019

18

109203

517168

19

190

...

When I tried running just the good test, to see how far I could go before it started crapping out, I waited for 15 minutes at n=21...that random behavior plays so much into it that I'm just playing the odds that it won't take a long time.

Anyway, this is a completely useless post, I was just bored.