programming challenge...

[Fat Tone]

Hi all

My son sometimes plays this little maths game, and now wants to write a program to do it.
Looking at it I can see there's a number of methods of attack, and thought some of you guys would like to try to come up with an elegant solution.

Here's the game:

You take a dice and roll it 3 (or maybe 4) times and see how many results you can come up with using some or all of those numbers and the standard +,-, * and / operators. You usually start looking for the result 1 and work up.

E.g. if you roll 2,3,5 you can get

1 = 3-2 or (5/(3-2)) if you want to look for other ways
2 = 2
3 = 3
4 = 5-(3-2)
5 = 5
6 = 2*3 or 5+3-2
7 = 5+2
etc etc


Enjoy.

Cheers,

T.

[Umfriend]

I would go for a brute force route: calculate all possible outcomes, order them by outcome and voila!

[VJ]

I agree with umfriend...

I wonder if something recursive could provide for an elegant solution: for
two numbers x and y, the options are x+y, x*y, x-y, y-x, x/y, y/x, x or y. The
recursion could be that y is be the result of a similar computation, and
so forth.
The main reason I'd go for a recursive strategy, is that this would make
it easier to keep the number of throws as a variable, which might be more
difficult in a pure brute force approach. (and I have a soft spot for
recursive things )


Jörg

[Fat Tone]

...add w and z and possible brace positions and there's more to this than first appears!

[VJ]

There are 3 dice in this example: x,w,z, where y is the result of
another combination between (w,z). This implies brackets around that
portion.
Perhaps some permution of x,w,z in the calls would yield all the options?
It would be at the expense of doubling some results. though...
(I just glanced at the problem )

But yes, it could be a tricky one...


Jörg

[cjolley]

Very tricky.
Though the brace problem would be solved by the recursion itself.
For example, what do you do about negative results? eg for a > b and one result is b - a?
And what about avoiding div by zero in the combinations?

In fact, I hate you.
This is going to be like one of those terrible songs you can't get out of your head all day.
And I have work to do.


PS. already thinking
if a > b then recurse(a, b, 0) else recurse(b, a, 0)

It's going to be a long day...

[VJ]

I guess negative intermediate results are OK, but negative end results are not.

[Umfriend]

Which could be sorted once you sort the results by value and ignore smaller than 1. I assume all _valid_ results must be positive integers (forgot what the name of that collection is in English, "Natural numbers Larger than one" or N+?

[Umfriend]

I would, BTW, start with finding the function N=f(x) where x is the number of dices one is allowed to throw and N is the number of possible (non-unique) results. Once you have that, the rest follows easily (assuming you go for brute force that is).

[cjolley]

This seems to be a subset (a harder one) for the Subset Sum Problem

You could probably earn a Turing award for an elegant, general solution.

[Umfriend]

I considered it but decided to make myself some lasagna instead.

[FatBastard]

Here is a smallish Algorithm that will do the trick

let TA be the throw array. { i.e 2, 4 ,5 ,6 or 1 ,2 ,3 or 1 , 2,3 ,4, 5, 6 etc...}
let SA be the available math operands array. { i.e +-*\ or +- or \+* etc ...)
let n be the size of the TA array.
1. Let LIST _Sperm_ be all possible permutations of a n - 1 sized array (SA') made from items in SA and n number of parenthesis (). { Max number of parenthesis is the number of digits in TA }
Permutation rules:
1.1 disqualify permutations that start with ')'.
1.2 disqualify permutations with an uneven number of '(' ')'

2. Let LIST _Tperm_ be all possible permutations of TA
3. for each pair of _Sperm_ and _Tperm_ Items: print equation { i.e 2 + 1 - 5 \ 6 } then print the calculation result
print one item from _Tperm _ and one from _Sperm_ by those rules:
3.1 peek the first Item in _Sperm_. if its '(' print it.
3.1.1 if not print an Item from _Tperm_
3.2 If u printed an Item from _Sperm_, peek next. if its '(' print it. { i.e +( -( (( }
3.2.3 if not print an Item from _Tperm_

/* way I c it what you don't want is results like this 6(+4) and so on, so I guess 3.x rules cover it
If I missed one, lemme know ;-) */

4. LOOP: for each Item I in TA, take out I. go back to 1.

5. take out one Item of TA
5.1 IF Items in TA remain go to 1. else exit

[cjolley]

Only on MURC would someone write code with an object called LIST_Sperm.

[FatBastard]

Now, I know my character is not gonna be questioned by Mr "I use a guy with an exposed ass, bending over for an Avatar"

[Umfriend]

Never been good at this but I don;t think it is complete yet FB. Step 4; _which_ item do you take out and don't forget, if you take out item n-1, you need to put it back because you also need TA less item n-2.

Moreover, I guess you'll need to build SA each time because it is dependent on the number of elements of the version of TA you are processing and you need to ensure that the braces are put in nicely (can;t have opening braces and no closing braces because it believes it has finished with the number of elements in TA it is working on).

A good step would be, I guess, to first find how many versions of TA you'd need to run.