Java Code Pyramids :S



  • Hey there, long time reader, first time poster here..

    I'm a university student, and i've been tasked with implementing the game "Shut The Box" in java. 

    I'm currently stuck at detecting when a turn cannot be taken, without doing a big pyramid of fors and ifs..

    I have a boolean array covered[] representing the boxes 1 to 9  (covered[0] --> box 1 etc..) and an integer left which holds the total left to cover.

    I want to go through the array and check if any combo of the false entries can add up to left.. i know it's possible to do it quickly and easily, without the pyramid, but i seem to have the programmers version of writers block.. (i.e. i've been staring blankly at the screen for about an hour..)

    Any help is much appreciated, and i am a student so take it easy with "the real wtf is.." hehe
     



  • I don't think anyone is going to just give you the answer, but I bet we'd be happy to help you work through it.  Why don't you start with the code you have, and an outline of how the mighty pyramid will look if you go ahead with what you're doing.  Your first objective is to just get the assignment done, even if the result is ugly.  Afterward, you'll have time to think about a better way to do it.



  • I'm not sure I understand the problem, but a lookup table might be help simplify the logic: http://en.wikipedia.org/wiki/Lookup_table.  You can replace the nested ifs with a lookup operation.



  • Isn't your problem more general? If you need to implement that game you need to know the moves you can make. Calculate those, and if there are none, then the turn cannot be taken. Such a function could be used other things as wel, for instance a computer player.

     

    Edit: this particular problem is known as the Subset sum problem



  • Hint, in Haskell:

    f uncovered total = map try uncovered
      where
      try x = f new_uncovered (total - x)
      new_uncovered = delete x uncovered
    

    Figure out what this function does and a solution should be apparent. This is not a solution, but it's structurally similar to one.

    You don't need to know Haskell to follow it. 'uncovered' is a list of integers, and 'total' is an integer. The function 'map g xs' applies g to each element of the list xs in turn, returning the list of results, and the function 'delete y ys' removes the first element from the list ys that is equal to y. (Adjusting it to use your data structures is straightforward, I'm just keeping the example simple)



  • ahh.. sleep makes it all better... woke up and had an idea.. which now makes me feel rather stupid now, because it seems oh so obvious.. and quite easy..

    just go through th numbers backwards checking if they're available, and if they equal the total.. if they equal, return true, if not, next number, if it's less than, take the number from the total then move to the next number.. if it exits the loop, aint no turn to take.. from my quick tests it works, any i cant see anything obviously wrong with it so woo!

    Thank's for the advice, and in response to  Oscar L, i didn't mean it to sound like i wanted someone to do it for me, i just wanted some advice, a push in the right direction, i.e. the last post about the subset sum was very informative.. and with regards to showing the code i had in mind... i dont think any of you deserve to witness code that bad... i was cringing as i was typing it, i felt dirty... (it had if within loop within if over 18 times.. :S i'm glad i stopped writing it..)

    anyhoo, here's what i came up with :

    left is the total of the dice throw, covered is a bool array, true means it's covered (hence unavailable) and false, the opposite..

    public boolean canGo() {
        int total = left;
        for (int i = 9; i > 0; i--){
            if(i == total && !covered[i-1]) {
                return true;
            } else if (i < total && !covered[i-1]) {
                total -= i;
            }
        }
        return false;
    }



  • Right idea. Not quite the right solution.

    Total is 9. The uncovered values are 6, 5, and 4.


Log in to reply