Programming Contest 8 - Questions

[stuart]

As always, any questions relating to contest 8 please post here !!

Stuart

Are parenthesis allowed...

e.g.

1 + 2 + 3 * 4 = 15

1 + (2 + 3) * 4 = 21

This is important because if parens are not allowed then the solution to the contest is ubersimple, number of permutations is low n^x

foreach ($permutations as $permutation) {
if (eval($permutation) == $answer)) {
echo 'Solved'; break;
}
}

when parens get involved the number of permutations rises several orders of magnitude greater for each number in the input set. ni^x + ni^xn-1 ... or something like that...

the point is the contest is just a fight as to who can loop the fastest, and transfer the least amount of memory.

IIRC codewalkers.com tried a similar contest

http://codewalkers.com/contests/2003-11-03/

[stuart]

I was waiting for someone to ask that!!! ... I was going to add it to the contest page but totally forgot

Yes, parenthesis may be used in the puzzle so your script must account for this.

Also forgot to mention that the shortest solution will win over time!!! if more that one script finds the same shortest solution then the fastest will win!

Cheers,
Stuart

[Mr. Sketch]

What happens to extra decimal places after a divide or multiply? Round or trunc, and should it be done after each operation or wait until the end to do the final rounding/truncing:

ex:
17,7,2.42 or would it be 2.43 since the result of the divide is 2.4285714285714285714285714285714

[stuart]

Welcome back Mr. Sketch!!

Very good question indeed

I think a 'round' after each calculation is the only way.

For example if the number = 136.09456353622 you should round it, and end up with 136.09.

An other example would be 136.09510808928 should round to 136.1


Cheers

1. Is it always possible to find an exact solution for the numbers given to the script?
2. How is length measured? Is it a length of the 'result string' or the number of operators/operands used?

[stuart]

Yes, All lists will have an exact solution provided you use the rules specified in the posts above.

Length is measured by operators used!!

So, the list you provide can have up to 50 numbers in it and the last one will be the value the script is suppose to reach? This one is over my head I think...

[argonauta]

hi there

I was reading, and one conditions is that you MUST use each number at least once, and at most twice, right?

however, what if you give me 5 numbers, but the smallest solution would be using only 4 of them?

i mean, you give me:

a,b,c,d,e=>f

the best solution being:
a+b+c+d=f
but if i have to use all numbers then the solution would be presented as:
a+b+c+d+(e-e)=f

Which only adds one more operator to the solution, nothing else. Well, when the list gets bigger, you could try to find a better way to remove all non-used numbers via substraction, but this, by all means, would be already kinda useless???

anyway, i wanted to make sure: ALL and ALL numbers must be used, or we must use as few numbers as possible??????

[stuart]

Hi,

Yes, all numbers must be included at least once, but can be used twice!! the object of the game is to find the shortest solution using the rules above (and any other rules stated). In your example your second one would be valid. But you are correct, it may well be possible to find the solution without using all numbers in the list.... but that is cheating