Top Coder Challenge: it adds up / countdown!

Question

See here: https://www.youtube.com/watch?v=pfa3MHLLSWI

You are given one number N, 6 numbers chosen randomly in the following set : 1,2,3,4,5,6,7,8,9,25,50,75,100.

The goal is to use the numbers & operators (+-×/) to be as close as possible as N. You cant repeat the numbers and each step has to produce integers.

See https://www.youtube.com/watch?v=h9vH7YGotQc
With [1,6,2,9,7,7],945 answer is
(7*2+1)*7*9=945
With [1,2,3,4,5,6],999 =>2*4*5*6*(1+3)=960 (999 not doable)

Write a program solving this game and giving a solution.

Answer 1

6! = 720 possible number positions
4^5 = 1024 possible operations

Answer 2

I've finished my first version, it barely runs :) plus I'll be optimizing it

this is by backtracking

https://code.sololearn.com/WqsZ5ifZ0c37/?ref=app

Answer 3

Also look at this as a way to get rid of () : https://en.wikipedia.org/wiki/Reverse_Polish_notation

As well as this research paper (fairly recent) on the number of options to evaluate : https://arxiv.org/pdf/1502.05450.pdf

Solution implementing the depth first method : https://code.sololearn.com/ccQZXwI4XcH7/#py

Answer 4

I'm building my own one :), based on: http://www.jlabstudio.com/webgl/ejemplos/cifrasyletras/

Answer 5

Now i have ! Congrats you won. Can be a good exercice to try to make the code more compact by using arrays of functions. Regarding the complexity i think this complexity is intrinsically high. Unless you find a smart way to deal with operator priority (lile only testing solutions where they are in non decreasing priority order since the numbers will take any position - this would be still exponential but quicker by a factor of 50).

Answer 6

English example

https://www.youtube.com/watch?v=X1jwjiEQG9Y

Answer 7

Agree but a brute force solution even with some redundancies would win the challenge so far ! In this case finding the way to quickly do the brutal method is already a good coding exercise (using functionnal programming). And since the problem is of limited size by definition the asymptotic complexity for very large sizes is less important than how it runs for n=6.

Answer 8

Thanks to you. Your solution led me to look for complexity analysis. Funny to see so few references.

Answer 9

You cant repeat the numbers and each step has to produce integer numbers.

Answer 10

Other test examples : #[100,10,7,5,7,75],232
#[8,75,1,10,9,3],747
#[2,6,1,8,5,9],265
#[2,5,10,75,50,8],417
#[3,100,8,8,10,6],683

Answer 11

@moby The challenge is to make a programml finding the solution given the target and the authorized numbers.

Answer 12

Hey good 1st step anyways ;-)

Answer 13

Hope so ! You kook like one of the few taking more complex challenges here ;-)

Answer 14

Try to find the calculations(+ - * /) you have to do in the given number to find the target.

Now code a program doing this automatically when given a set of numbers and a target

Answer 15

Just looked at the code from my laptop - looks much more readable. Less the case from a mobile phone !

Answer 16

You never give up ! Good one.

Answer 17

Btw you did not select a winner for range extraction...