Announcement

Collapse
No announcement yet.

programming challenge...

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • programming challenge...

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

  • #2
    I would go for a brute force route: calculate all possible outcomes, order them by outcome and voila!
    Join MURCs Distributed Computing effort for Rosetta@Home and help fight Alzheimers, Cancer, Mad Cow disease and rising oil prices.
    [...]the pervading principle and abiding test of good breeding is the requirement of a substantial and patent waste of time. - Veblen

    Comment


    • #3
      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
      pixar
      Dream as if you'll live forever. Live as if you'll die tomorrow. (James Dean)

      Comment


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

        Comment


        • #5
          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
          pixar
          Dream as if you'll live forever. Live as if you'll die tomorrow. (James Dean)

          Comment


          • #6
            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...
            Chuck
            秋音的爸爸

            Comment


            • #7
              I guess negative intermediate results are OK, but negative end results are not.
              pixar
              Dream as if you'll live forever. Live as if you'll die tomorrow. (James Dean)

              Comment


              • #8
                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+?
                Join MURCs Distributed Computing effort for Rosetta@Home and help fight Alzheimers, Cancer, Mad Cow disease and rising oil prices.
                [...]the pervading principle and abiding test of good breeding is the requirement of a substantial and patent waste of time. - Veblen

                Comment


                • #9
                  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).
                  Join MURCs Distributed Computing effort for Rosetta@Home and help fight Alzheimers, Cancer, Mad Cow disease and rising oil prices.
                  [...]the pervading principle and abiding test of good breeding is the requirement of a substantial and patent waste of time. - Veblen

                  Comment


                  • #10
                    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.
                    Chuck
                    秋音的爸爸

                    Comment


                    • #11
                      I considered it but decided to make myself some lasagna instead.
                      Join MURCs Distributed Computing effort for Rosetta@Home and help fight Alzheimers, Cancer, Mad Cow disease and rising oil prices.
                      [...]the pervading principle and abiding test of good breeding is the requirement of a substantial and patent waste of time. - Veblen

                      Comment


                      • #12
                        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
                        Last edited by FatBastard; 2 August 2007, 07:41. Reason: cjcolly comments
                        Originally posted by Gurm
                        .. some very fair skinned women just have a nasty brown crack no matter what...

                        Comment


                        • #13
                          Only on MURC would someone write code with an object called LIST_Sperm.
                          Chuck
                          秋音的爸爸

                          Comment


                          • #14
                            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"
                            Originally posted by Gurm
                            .. some very fair skinned women just have a nasty brown crack no matter what...

                            Comment


                            • #15
                              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.
                              Join MURCs Distributed Computing effort for Rosetta@Home and help fight Alzheimers, Cancer, Mad Cow disease and rising oil prices.
                              [...]the pervading principle and abiding test of good breeding is the requirement of a substantial and patent waste of time. - Veblen

                              Comment

                              Working...
                              X