Finding dice roll results in a combinable list of numbers

Question

This code takes a selection of numbers between 1 to 9 which could be 1,2,3,4,5,6,7,8,9 or 1,2,4 or 4,5,8,9, etc.

Looks for every possible combination and compares them to a dice roll of two dice

e.g. If the dice roll is 7 then can it be found in a list which contains

1,2,3,4,5,6,7,8,9 - (Yes, 7 and 5+2 and 3+4 etc)

OR the list could contain

1,3,4,8 - (Yes 3+4 only)

OR

1,4,8,9 - (No)

Note:

• remainder is the dice roll

• Binarypositions works out the different possibilities and returns a list of all the combinations available for checking

---

    void gameovercheck(){
        List <int> selection = new List <int> ();

        bool found = false;
        //Calculate number of possible combinations
        int combination = (int)Mathf.Pow (2, blocklist.Count);

        //Loop to step through each possible combination
        for (int x = 0; x < combination; x++) {         
            selection = ReturnBinary.Binarypositions (x, 8);

            //string output = "";
            int sum = 0;
            for (int z = 0; z < selection.Count; z++) {
                sum += blocklist [selection [z]];
            }
            if (sum == remainder)
                found = true;
        }


        if (!found) {
            gamerunning = false;
        }

}
}

to find out all the possible combinations I work out the binary positions using the following function

public static List<int> Binarypositions(int number,int bits){           
    List <int> newanswer = new List <int>();

    int count = 0;

    for (int y = 0; y < bits; y++) {
        int answer = number >> y & 0x1;
        if (answer==1) {
            newanswer.Add (count);
        }
        count++;

    }
    //Output
    return (newanswer);
}

I have to run this everytime I want to check if it can be found, so how can I optimise this for performance?

Answer 1

You can make gameovercheck more efficient by returning as soon as sum equals remainder. The standard naming convention is UpperCamelCase for methods and lowerCamelCase for variables. It's good practice to not use class level variables in a method when possible so you can count on the method to return the same answer when given the same input. I will change the class level variables to parameters and return a bool, which you can then assign to gamerunning In Binarypositions, you declare count at the same time as y, and also increment it at the same time, so it's not necessary. I prefer to have method names use a verb to describe what they are doing. I think diceRoll is more descriptive than remainder.

private bool CheckIfGameOver(List<int> blockList, int diceRoll){

    //Calculate number of possible combinations
    int combinations = (int)Mathf.Pow(2, blocklist.Count);

    //Loop to step through each possible combination
    for (int x = 0; x < combinations; x++) {         
        List <int> selection = ReturnBinary.CalculateBinaryPositions(x, 8);

        int sum = 0;
        for (int z = 0; z < selection.Count; z++) {
            sum += blockList[selection[z]];
        }
        if (sum == diceRoll)
            return false;
    }
    return true;
}

public static List<int> CalculateBinaryPositions(int number, int bits){         
    List<int> newAnswer = new List<int>();

    for (int y = 0; y < bits; y++) {
        int answer = number >> y & 0x1;
        if (answer == 1) {
            newAnswer.Add(y);
        }
    }
    //Output
    return newAnswer;
}

I prefer using LINQ instead of loops when I can. It probably won't affect performance that much, but it can make code safer, more readable, and shorter.

private bool CheckIfGameOver(List<int> blockList, int diceRoll) {
    //Calculate number of possible combinations
    int combinations = (int)Mathf.Pow(2, blocklist.Count);

    var gameOver = Enumerable
        .Range(0, combinations)
        .Select(x => ReturnBinary.CalculateBinaryPositions(x, 8).Sum(y => blockList[y]))
        .All(x => x != diceRoll);
    return gameOver;
}

public static List<int> CalculateBinaryPositions(int number, int bits){         
    return Enumerable.Range(0, bits).Where(x => (number >> x & 0x1) == 1).ToList();
}

Why do you set it at 8 bits? Wouldn't that omit a bit if blockList has 9 items?

An optimization you could make is to make a list of lists containing all possible binary position combinations. Like [[],[1],[1,2],[1,3],[1,2,3],etc]. Then you could just take the number of combinations you need each time instead of calculating them. I might try and code this optimization in the future.

Another thing to try is to calculate all possible binary position combinations using recursion instead of bit manipulation.

Answer 2

void gameovercheck()

• methods should be named using PascalCase casing.
• methods should be named using verbs or verb phrases
• instead of setting some class variable (gamerunning) you should return a boolean.
• because found won't change after it is set to true you can just break out of the loop. There is no need to calculate any more combinations and sums afterwards.
• you have an edge case in that method which if forgotten can lead to an IndexOutOfRangeException. Assume blocklist isn't containing any items then int combinationresults in 1 meaning the loop will be executed and the exception will be thrown at sum += blocklist [selection [z]];.
• starting the loop at 0 isn't needed because ReturnBinary.Binarypositions (0, 8); returns an empty list.
• You should declare your variables as near as possible to their usage. Declaring selection at the top of the method doesn't buy you anything. The truth is it costs you because you are overwriting its value inside the loop.
• commented out code like //string output = ""; doesn't belong here. Commented out code is dead code and should be removed.
• using braces {} although they are optional is a good way to structure your code which increases readability and will help to make the code less error prone.
• you should be consistent in your coding style. Being consistent with the style helps a reader of the code to grasp it at first glance. Right now you are using different styles for the same type of code.
• a variable which is used as an index is usually named either i or j.
• if you have a comment like //Calculate number of possible combinations you should as well use the plural form to name the variable.

Implementing the mentioned points will lead to

private bool IsGameOver()
{

    if (blocklist.Count == 0) 
    { 
        return true; 
    }

    //Calculate number of possible combinations
    int combinations = (int)Mathf.Pow(2, blocklist.Count);

    for (int i = 1; i < combinations; i++)
    {
        var selections = ReturnBinary.Binarypositions(i, 8);

        var sum = 0;
        for (int j = 0; j < selections.Count; j++)
        {
            sum += blocklist[selections[j]];
        }

        if (sum == remainder)
        {
            return false;
        }
    }

    return true;
}

Answer 3

To get the best performance stats you will need to decompile the C# application's dump file and review the ASM.

for (int x = 0; x < combination; x++)
for (int z = 0; z < selection.Count; z++)

For your for loops you should decrement it (seeing how the order doesn't matter). Increment for loops check the value of selection.Count on each loop.

i would suggest the same for

for (int y = 0; y < bits; y++)

but im not entirely sure on how your compiler would compile this. ( i would decrement it just in case since it doesn't matter)

---

consider returning gamerunning from your check method instead of setting a global that can be easily manipulated and takes up unnecessary memory.

It is very important you look at Malachi answer as well.

Answer 4

It's hard to follow your code and understand how it operates. Others have made good remarks regarding it already.

Reading your description I wonder if your entire code can't be replaced by the following construct though;

public class Game
{
    public void game_loop()
    {
        //game code here 

        if (canSelectionBecome(7, new[] { 1, 3, 4, 5, 9 }, 5))
        {
            //Game decides to stop running
        }
    }

    bool canSelectionBecome(int targetValue, int[] selection, int selectionValuesToCheck)
    {
        for (var index = selectionValuesToCheck - 1; index >= 0; index--)
        {
            if (targetValue < selection[index])
                continue;

            if (targetValue == selection[index])
                return true;

            var remainder = targetValue - selection[index];
            if (canSelectionBecome(remainder, selection, index))
                return true;
        }

        return false;
    }
}

This works if any combination of the selection can be used to create the target value. I'm not sure it is more effective than what you have but it should be easier to read and doesn't use global variables.

Answer 5

Edit

The code that I provided is not the same as the code in the OP. with the new information I would code gameovercheck to return a boolean and change its name to IsGameOver()

Then I would return as soon as the remainder was found. this eliminates a boolean variable and reduces the amount of times we iterate through the for loop to only what is absolutely needed

I too agree with the other answers, you should not use global variables in this case. You should pass in the information that the method needs, this encapsulates the method and keeps it standard, you always know what is happening inside the method, nothing outside of the method can affect the method except for what is given to it through the parameters.

it would look something like this

bool gameovercheck(int diceRoll){
    List <int> selection = new List <int> ();

    //Calculate number of possible combinations
    int combination = (int)Mathf.Pow (2, blocklist.Count);

    for (int x = 0; x < combination; x++) {         
        selection = ReturnBinary.Binarypositions (x, 8);

        //string output = "";
        int sum = 0;
        for (int z = 0; z < selection.Count; z++) {
            sum += blocklist [selection [z]];
        }
        if (sum == diceRoll) return true;
    }
    return false;
}

---

first thing that I saw.

if (sum == remainder)
    found = true;

you should just make this

found = sum == remainder;

and then

if (!found) {
    gamerunning = false;
}

can become this

gamerunning = found;

but, what does gamerunning do? I don't see where it is created or sent anywhere to do anything. I was thinking I might be able to get rid of a variable and make the code shorter, but here is what I have so far:

void gameovercheck(){
    List <int> selection = new List <int> ();

    bool found = false;
    //Calculate number of possible combinations
    int combination = (int)Mathf.Pow (2, blocklist.Count);

    for (int x = 0; x < combination; x++) {         
        selection = ReturnBinary.Binarypositions (x, 8);

        //string output = "";
        int sum = 0;
        for (int z = 0; z < selection.Count; z++) {
            sum += blocklist [selection [z]];
        }
        found = sum == remainder;
    }
    gamerunning = found;
}

I also removed a comment that was rather obvious.

but I noticed something else as well, what is remainder?

We now have two orphan variables, this isn't a complete workable piece of code.