- Forum
- General C++ Programming
- How to get the odd and even parity on a
How to get the odd and even parity on a game board
I am creating a memory game where there are "X" and "O" on the board. The user selects particular row and column to change it to "X" if it is "O" or to change it to "O" if it is "X". The other player need to find the changed piece on the board.
Everything is working fine. But, on the game board I need to have "ODD" number of "X" in each row and column. How can I achieve this?
Everything is working fine. But, on the game board I need to have "ODD" number of "X" in each row and column. How can I achieve this?
|
|
That's a lot of ifs. Have you learned to use arrays yet?
Is there a particular reason you need an odd number of 'X' in each row and column? Does the board need to be generated uniformly randomly over the set of legal boards or is it okay if the distribution is not uniform? It is not hard to generate boards that fit the first criterion or the second alone, but I can't think of a very easy way to do them together other than generating the set of all legal boards and randomly picking one.
Is there a particular reason you need an odd number of 'X' in each row and column? Does the board need to be generated uniformly randomly over the set of legal boards or is it okay if the distribution is not uniform? It is not hard to generate boards that fit the first criterion or the second alone, but I can't think of a very easy way to do them together other than generating the set of all legal boards and randomly picking one.
@Browni3141, it's actually pretty simple. You can populate the board randomly, adjust rows to odd number of X's, and then iteratively adjust the columns and rows until there's no change. The length of the code below is mostly repetition (adjust_rows and adjust_cols are very similar). I'm not sure how to reduce it.
|
|
Last edited on
|
|
1 2 3 4 5 6 - - - - - - A| O X X X O O B| O X O X X O C| O X X O X O D| X X X X X O E| O O X O O O F| O X X O O X |
@lastchance, Thanks, for the reply. But, I am not supposed to use arrays. Can you please tell me in my method. That would be more helpful. Thanks again.
| Can you please tell me in my method. |
No.
| That would be more helpful. |
To whom?
| But, I am not supposed to use arrays. |
Why on earth not? 36 items being treated in the same way ... says only one thing to me.
@lastchance, It's much simpler (and faster, and just generally better looking!) than mine. But it's statistics seem a little worse.
Out of 100000 runs, counting rows and cols with 1, 3, or 5 Xs:
I feel it makes sense that 3 would be more common in general, but mine creates more 1's and 5's.
Out of 100000 runs, counting rows and cols with 1, 3, or 5 Xs:
1 3 5 Yours: 224462 750756 224782 Mine : 290221 618902 290877 |
I feel it makes sense that 3 would be more common in general, but mine creates more 1's and 5's.
Hi @dutch,
If there were free choice of elements from 6 then they would be in the ratio 3:10:3 (consider binomial distribution with n=6, p=1/2), giving 0.1875 as the fraction of 1's. However, the last row is fixed once you have the other rows ... so that will change the probabilities slightly (haven't quite worked out how!).
I'll have to work out how your code operates, but there is indeed a statistical difference.
If there were free choice of elements from 6 then they would be in the ratio 3:10:3 (consider binomial distribution with n=6, p=1/2), giving 0.1875 as the fraction of 1's. However, the last row is fixed once you have the other rows ... so that will change the probabilities slightly (haven't quite worked out how!).
I'll have to work out how your code operates, but there is indeed a statistical difference.
Hey @lastchance,
Are you sure about those calculated probabilities? (I have no idea.) I just wrote a version that places the Xs randomly over the whole board and then checks for the odd-criterion. If it doesn't pass the check, it starts over again. It's pretty much the least efficient method imaginable, but it seems to me that it should be totally random. However, it has the same stats as yours! So I have no idea which stats are more correct.
As for my algorithm in the program above, it places the Xs randomly, then adjust the rows one at a time (by randomly adding or removing an X if it's not odd). Then it goes into a loop, adjusting the columns and, if there's a change, adjusts the rows and, if there's a change, adjusts the columns and ..., until there's no change. It runs faster than one might think (4 to 5 times slower than yours). But maybe that process is queering the stats.
Here's that "totally random" (I think) version:
Are you sure about those calculated probabilities? (I have no idea.) I just wrote a version that places the Xs randomly over the whole board and then checks for the odd-criterion. If it doesn't pass the check, it starts over again. It's pretty much the least efficient method imaginable, but it seems to me that it should be totally random. However, it has the same stats as yours! So I have no idea which stats are more correct.
As for my algorithm in the program above, it places the Xs randomly, then adjust the rows one at a time (by randomly adding or removing an X if it's not odd). Then it goes into a loop, adjusting the columns and, if there's a change, adjusts the rows and, if there's a change, adjusts the columns and ..., until there's no change. It runs faster than one might think (4 to 5 times slower than yours). But maybe that process is queering the stats.
Here's that "totally random" (I think) version:
|
|
Last edited on
Are you sure that your lines 32 and 62 (in your first code) aren't creating a slight bias to particular values of cnt? Also, only changing a few selected elements isn't the same as regenerating all 6: you might do better regenerating a whole row if there is an even count.
For the probabilities, the chance of getting x from 6 is, from binomial(6,1/2):
if x=1: 6C1/2^6, or 6/2^6
if x=3: 6C3/2^6, or 20/2^6
if x=5: 6C5/2^6, or 6/2^6
so the ratios are 6:20:6, or 3:10:3
and the relative probabilities are 3/16, 10/16, 3/16
This doesn't apply in the last row, because that would be fixed by the preceding rows, so the final probabilities aren't very easy to work out.
Our editing has just crossed! If your second code gives the same stats as mine then I'm happy. Your second code looks statistically correct. My daughter has just grabbed my computer, so I'm not in a position to do more on it at the moment: dratted university holidays!
For the probabilities, the chance of getting x from 6 is, from binomial(6,1/2):
if x=1: 6C1/2^6, or 6/2^6
if x=3: 6C3/2^6, or 20/2^6
if x=5: 6C5/2^6, or 6/2^6
so the ratios are 6:20:6, or 3:10:3
and the relative probabilities are 3/16, 10/16, 3/16
This doesn't apply in the last row, because that would be fixed by the preceding rows, so the final probabilities aren't very easy to work out.
Our editing has just crossed! If your second code gives the same stats as mine then I'm happy. Your second code looks statistically correct. My daughter has just grabbed my computer, so I'm not in a position to do more on it at the moment: dratted university holidays!
Last edited on
| Are you sure that your lines 32 and 62 (in your first code) aren't creating a slight bias to particular values of cnt? |
I think that's probably the case.
| philip1999 wrote: |
|---|
| @lastchance, Thanks, for the reply. But, I am not supposed to use arrays. Can you please tell me in my method. That would be more helpful. Thanks again. |
If your professor wants you to create and modify 36 individually named variables like this then he's an idiot. This is not learning how to program. Feel free to tell him/her so and use arrays anyway.
Topic archived. No new replies allowed.