programming challenge...

[FatBastard]

Assumptions
1) For each set of dice throw there is one run of the program, which means there is one TA list. ( say 2,3,4,5,6)
2) the number of Items in SA is constant for each run. ( say +,-,*)

as for step 4: u use a nested loop. each Item is an array, so there are two arrays for each iteration of the interior loop , one array of _Tperm_ (i.e 2,3,4,6) and one of _Sperm_ (i.e +.-,*) there is only one way to print two such arrays:
The order is fixed (per given two arrays) so in our case 2+3-4*6.

No need to track which items you pool out, because once you decrease the number of Items in SA, you recalculate both lists of permutations

[TransformX]

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"

I think that's Commander Keen.

[cjolley]

I think that's Commander Keen.

Well yes


I'm still thinking about the pattern.

For example how do you prevent dice being used twice? eg f({a,b}, {b,c})

And throwing in - and / where order matters is just EVIL.

[FatBastard]

Well yes


I'm still thinking about the pattern.

For example how do you prevent dice being used twice? eg f({a,b}, {b,c})

And throwing in - and / where order matters is just EVIL.

Thats not a problem.
the solution will work if the array is 1,2,3,4,5 or 1,1,1,3,5 or 5,5,5,5,5 or 4,3,3,2,1

The is no reason if the array of of dice throws or just a made up sequence of numbers

the order does not matter, any order is just permutaion of the array. it will be calculated the
same as all the rest of the permutations of the same array

[cjolley]

I don't think the rules force you to use all the dice for each calculation, which complicates the problem.

For dice a, b c
If one array element is {a, b} and another {b, c} how do you prevent that pair from processing.

After all, you are not allowed to use the same dice twice or you could produce any number you wanted.


@FT Your family does this kind of thing for FUN!?

[FatBastard]

I'm sorry , I don't follow you.
the way I understand it, it does not matter if you throw one dice 4 times, or 4 dice 1 time.
at the end you get a sequence of numbers which are your input array.
each sequence of number constitutes one permutation of the input array, and so the order of the array when starting the program is meaningless.

Fat tone's example was "E.g. if you roll 2,3,5 you can get ....."
I say 2,3,5 or 5,3,2 or 3,5,2 will yield the same result.

maybe I don't understand your suggested added complexity

[cjolley]

Substitute the word roll for dice.

Re-worded the rule would be that you can not use the same roll twice in one game.

so, for a game of 4 rolls you will have rolls a, b, c, d

and operators given as * (doesn't matter which one for this problem)

the permutations of a, b, c, d will include
{a, b, c}
{a, b}
..
{c}
{b, c}
..etc

while you want to process (a * b) * c
you do not want to process (a * b) * (b * c) because you would be using roll b twice.

Because n/n = 1 and for any number m there exists a number m + 1
so, if you can repeat the use of a single roll then you can produce any number

I would be very interested to see a brute force program for this problem in a real language for a game of even only three rolls.

[FatBastard]

OK, I think I got you
the () issue in my algorithm is not problem.
(+-)* or +(-)* or +(-*) are just permutations of the SA array { (,),+,-,* } in LIST _Sperm_

However, you changed the definition of the problem.
You are talking about sets of dice roll results {a,b,c,d} {a,b,c} {e,d,f}
you also introduced some new logic into how you can calculate permutations.
Its an interesting problem, but a different one then FT's.
gonna think about it for a while

[spadnos]

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.

This is sort of a combination of umfriend's and fatbastard's approaches.

the number of combinations of N rolls is N!, so 3 rolls gives 6 (3*2*1) orderings:
a b c
a c b
b a c
b c a
c a b
c b a

The number of orders of operations is harder (this may have been cjolley's point about not reusing a roll). With 3 rolls, it's easy, there are 3 possible orders of operations - using * to show some operation, not necessarily multiplication:
a * b * c
(a * b) * c
a * (b * c)
I'm not sure exactly how to calculate this number, but it may be something like doing the permutation calc on (N/2).
Hmmm. So there's the obvious no parentheses option, then there are N-1 options with two items in parentheses. Since no parens is equivalent to parens around the whole equation, I think the 1-paren set may just be the sum from 1 to N-1, which is (N-1)*N/2 (for the 3 case, this becomes 2*3/2 = 3, which fits so far )
The more generic case for evaluation order will then become some sum of sums (that's a tongue twister):

get_ev_orders(start, end)
  if (start=end) return 1
  count=0
  for i=start to end-1
    count = count+get_ev_orders(1,i)
    count = count+get_ev_orders(i+1,end)
  return count

I think that will give all combinations, including ones like these:
abcde
(abc)(de)
((ab)c)(de)
(a(bc))de)

There may need to be a separate loop though. I had started out with a nested loop, but realized that I needed to split the given set as many ways as possible, and allow each subset to also be split similarly.
I think this is the TPerm list fatbastard was talking about. I don't know how to evaluate that kind of double-sum for a closed-form expression (and it may not have a closed form equivalent).

After that, you have the operations themselves
This is easier, because there are only 4 operations (constant), and there are only N-1 locations for an operation to be placed. There is the option of adding a unary minus to the first operand, so there may be 2*(4N) ways to combine the operations.

So there are N! operand orderings, 8N possible arrangements of operators (including the leading unary minus), and an unknown, but presumably factorial or second-order factorial number of orders of operation to contend with

That's my story and I'm sticking to it

- Steve

[FatBastard]

Added comments to solution.

[cjolley]

I don't see how this solution handles the case of, for example, a roll of 1, 5, 6
Where one of the answers is 11 which is only reachable by leaving out the roll of 1.

Also, from FT's example a single dice roll counts as a hit, so in the above example it is not necessary to use 6-5 to reach a result of 1 because the roll of one in the group provides a direct solution.

So the number of possible combinations for 3 dice is 15 not 6

[FatBastard]

Please see steps 4 and 5.

after u r done calculating all possible answers for 1 5 6
you take out 6 and calculate all possible answerers 1 5
then you take out 5 and calculate all possible answers for 1 6
then you take out 1 and calculate all possible answers for 5 6 ( one of which is 11)
...
...

Added intermediate step to clarify.

[cjolley]

well, the general formula for how many permutations plus partial permutations are going to be available just from the rolls, not including operators or grouping:

n!/(n-1)! + n!/(n-2)! ... + n!/(n-n)!

that is going to get really big, really fast

PS Here is an algorithm for producing permutations.

[spadnos]

Ah. I had missed the option of using subsets of the numbers - duh.

- Steve

[cjolley]

Well, here is a permutation counter.
It's in Oracle pl/sql but should be pretty easy to translate into another lang.

sql>declare
  2     max_elements number := &max_elements;
  3     result number;
  4     function factoral(v_in number) return number
  5     is
  6        fac number := 1;
  7     begin
  8        for j in 1..v_in loop
  9           fac := fac * j;
 10        end loop;
 11        return fac;
 12     end factoral;
 13
 14     function count_perm(v_in number) return number
 15     is
 16        pri_fac number;
 17        sub_fac number;
 18        result number := 0;
 19     begin
 20        pri_fac := factoral(v_in);
 21        for i in 1..v_in loop
 22           sub_fac := factoral(v_in - i);
 23           result := result + pri_fac / sub_fac;
 24        end loop;
 25        return result;
 26     end count_perm;
 27
 28  begin
 29     for elements in 1..max_elements loop
 30        result := count_perm(elements);
 31        dbms_output.put_line('elements:'||to_char(elements)||'  permutations:'||to_char(result));
 32     end loop;
 33  end;
 34  /
Enter value for max_elements: 20
old   2:    max_elements number := &max_elements;
new   2:    max_elements number := 20;
elements:1  permutations:1
elements:2  permutations:4
elements:3  permutations:15
elements:4  permutations:64
elements:5  permutations:325
elements:6  permutations:1956
elements:7  permutations:13699
elements:8  permutations:109600
elements:9  permutations:986409
elements:10  permutations:9864100
elements:11  permutations:108505111
elements:12  permutations:1302061344
elements:13  permutations:16926797485
elements:14  permutations:236975164804
elements:15  permutations:3554627472075
elements:16  permutations:56874039553216
elements:17  permutations:966858672404689
elements:18  permutations:17403456103284420
elements:19  permutations:330665665962403999
elements:20  permutations:6613313319248080000

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.03
sql>