Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!

# Java puzzle

John dev
Greenhorn
Posts: 1

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

Chan Ag
Rancher
Posts: 1089
14
Welcome to the ranch, John Dev.

So what do we get for solving that puzzle?

Chan.

fred rosenberger
lowercase baba
Bartender
Posts: 12185
34
• 1
People here will help you write it, but nobody is going to do it for you.

Campbell Ritchie
Sheriff
Posts: 49788
69
Are you really supposed to find which operators will give the final result? That is bl**d* difficult. 1 × 2 + 3 × 4 ≠ 20

And welcome to the Ranch

Stuart A. Burkett
Ranch Hand
Posts: 679
Campbell Ritchie wrote: 1 × 2 + 3 × 4 ≠ 20

It is if you
John dev wrote:Assume all the operators will have same precedence.

Campbell Ritchie
Sheriff
Posts: 49788
69
• 1
I never saw that. I still think it is difficult.

Chan Ag
Rancher
Posts: 1089
14
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.

Winston Gutkowski
Bartender
Posts: 10504
64
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

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

Here's a related - much harder, I think - Project Euler problem: http://projecteuler.net/problem=93.

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.

Myke Enriq
Ranch Hand
Posts: 115
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

Winston Gutkowski
Bartender
Posts: 10504
64
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.

What they are though? Only The Shadow knows...

Winston

Anand Hariharan
Rancher
Posts: 272
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.

Ryan McGuire
Ranch Hand
Posts: 1072
4
Might I suggest a recursive solution?

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.

Piet Souris
Rancher
Posts: 1319
29
Nice recursion!

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
Posts: 1072
4
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
Posts: 1072
4
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.

Andrew Samii
Greenhorn
Posts: 5
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.

aleks Maleks
Greenhorn
Posts: 1
thanks it works

Ryan McGuire
Ranch Hand
Posts: 1072
4
aleks Maleks wrote:thanks it works

Cool!

Does this one work?

1 3 9 6 2