John dev

Greenhorn

Posts: 1

posted 4 years ago

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

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: 1090

14

posted 4 years ago

- 1

People here will help you write it, but nobody is going to do it for you.

You may want to read our HowToAskQuestionsOnJavaRanch FAQ.

You may want to read our HowToAskQuestionsOnJavaRanch FAQ.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Campbell Ritchie

Sheriff

Posts: 55351

157

Stuart A. Burkett

Ranch Hand

Posts: 679

Campbell Ritchie

Sheriff

Posts: 55351

157

Chan Ag

Rancher

Posts: 1090

14

posted 3 years ago

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.

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.

posted 3 years ago

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

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Matthew Brown

Bartender

Posts: 4568

9

posted 3 years ago

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

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

posted 3 years ago

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 ?

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

posted 3 years ago

Actually, I think the bit that's more important is the "You need to use n-1 arguments

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

Winston

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

Articles by Winston can be found here

posted 3 years ago

Brute force would mean 4 to the power

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.

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

Ryan McGuire

Ranch Hand

Posts: 1138

8

posted 3 years ago

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.

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: 1946

66

posted 3 years ago

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".

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: 1138

8

posted 3 years ago

Thank you.

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.

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: 1138

8

posted 3 years ago

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

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

posted 3 years ago

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.

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.

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.