Checking An Array For Similarities

[DeepBlueCode]

I am amking a Tic Tac Toe game and have a one dimensional array (0-8 for the nine spaces). How can I check with the smallest and most efficient amount of code whether or not someone has won the game, or if it's a draw?

Much thanks in advance.

[CornedBee]

How is the aray filled?
0 = empty
1 = player1
2 = player2
or something else?
Have to go, if no answer tomorrow, I'll think about it.

[kedaman]

There's 8 win lines, make an array of 8 arrays of 3 pointers to each element in each winning row

to check for winning status, for each winline check first element which is player if someone wins, and it's equality with the two other elements.
to check for draw game, check if both players are in all winlines, you could do this by OR-assigning each winlines elements, and AND-assigning their equality with 3 (which is 2 | 1)

[DeepBlueCode]

The array is the rows that have the 'X's and 'O's in them. I need some exemplary code if that's ok. My code took about 100 lines because it included everything I would do after I checked each row, column, and diagonal. A loop would be helpful, but not sure how to do it. Thanks.

[jim mcnamara]

tic-tac-toe:

#include <stdio.h>
#include <stdlib.h>

char matrix[3][3];  /* the tic tac toe matrix */

char check(void);
void init_matrix(void);
void get_player_move(void);
void get_computer_move(void);
void disp_matrix(void);

int main(void)
{
  char done;

  printf("This is the game of Tic Tac Toe.\n");
  printf("You will be playing against the computer.\n");

  done =  ' ';
  init_matrix();

  do {
    disp_matrix();
    get_player_move();
    done = check(); /* see if winner */
    if(done!= ' ') break; /* winner!*/
    get_computer_move();
    done = check(); /* see if winner */
  } while(done== ' ');

  if(done=='X') printf("You won!\n");
  else printf("I won!!!!\n");
  disp_matrix(); /* show final positions */

  return 0;
}

/* Initialize the matrix. */
void init_matrix(void)
{
  int i, j;

  for(i=0; i<3; i++)
    for(j=0; j<3; j++) matrix[i][j] =  ' ';
}

/* Get a player's move. */
void get_player_move(void)
{
  int x, y;

  printf("Enter X,Y coordinates for your move: ");
  scanf("%d%*c%d", &x, &y);

  x--; y--;

  if(matrix[x][y]!= ' '){
    printf("Invalid move, try again.\n");
    get_player_move();
  }
  else matrix[x][y] = 'X';
}

/* Get a move from the computer. */
void get_computer_move(void)
{
  int i, j;
  for(i=0; i<3; i++){
    for(j=0; j<3; j++)
      if(matrix[i][j]==' ') break;
    if(matrix[i][j]==' ') break;
  }

  if(i*j==9)  {
    printf("draw\n");
    exit(0);
  }
  else
    matrix[i][j] = 'O';
}

/* Display the matrix on the screen. */
void disp_matrix(void)
{
  int t;

  for(t=0; t<3; t++) {
    printf(" %c | %c | %c ",matrix[t][0],
            matrix[t][1], matrix [t][2]);
    if(t!=2) printf("\n---|---|---\n");
  }
  printf("\n");
}

/* See if there is a winner. */
char check(void)
{
  int i;

  for(i=0; i<3; i++)  /* check rows */
    if(matrix[i][0]==matrix[i][1] &&
       matrix[i][0]==matrix[i][2]) return matrix[i][0];

  for(i=0; i<3; i++)  /* check columns */
    if(matrix[0][i]==matrix[1][i] &&
       matrix[0][i]==matrix[2][i]) return matrix[0][i];

  /* test diagonals */
  if(matrix[0][0]==matrix[1][1] &&
     matrix[1][1]==matrix[2][2])
       return matrix[0][0];

  if(matrix[0][2]==matrix[1][1] &&
     matrix[1][1]==matrix[2][0])
       return matrix[0][2];

  return ' ';
}

[DeepBlueCode]

Alright, I know now that I'm being lazy and annoying, but I am using a one dimensional array (0-8). Can someone translate this for me into the code I need?

[transcendental]

One dimensional can do.

data[0*3+n] first row
data[1*3+n] second row
data[2*3+n] third row

n starts from 0 to 2

Two dimensional is better. Don't you think so?

data[0][n] first row
data[1][n] second row
data[2][n] third row

just my 2 cents.......

[kedaman]

Why is that? You need to dereference twice, which means actual performance loss.
1D all the way is always best

[transcendental]

Actually 2d, 3d arrays and so on, are actually 1d in C++.(Written in the book "Core C++".)

The elements in any dimensional array are numbered consecutively in the memory.

You can declare a 2d array and use it as an 1d array.

char myfriend[10][10];

myfriend[6*10+5]=52;

whether it is myfriend[6][5]=52 or myfriend[5][6]=52 depends on your compiler, you got to check it yourself by writting a simple program to test.

Some compilers use the first index, some use the second index as the multipler.

[kedaman]

Nope, I use MSVC and a[b][c] means arrays of arrays, not "real" 2d arrays that can be used as 1d arrays.

[transcendental]

VC does not allow that, does not mean it is not 1d.

All arrays are sequential in the memory.

I guess they implement this way, is bcos it is very diffcult to create a real 2d array in memory.

[kedaman]

Okay, but what about arrays allocated on the heap, is it even possible to allocate "real" 2d arrays on the heap? It would have to store onf of the dimension somewhere to determine offset at runtime which sounds weird. But can you have 2d arrays as a type with static first dimension?

[transcendental]

Hi kedaman, I was wrong about 2d array. I tested and tried to use a 2d array as a pointer to access its element, Borland C++ and VC does not allow that at compile time. However 1d array can.

[kedaman]

Okay, i think i have to check it out too...

[CornedBee]

#define DEREF2D(ar, x, y, size) \
    ((ar)[((x)*size) + (y)])

this can dereference 1-dimensional arrays as if they were 2-dimensional. Slow though (relatively). You supply the array, x, y, and max_y (size of one dimension).

I don't think it is possible to allocate a multi-dimensional array on the heap. I will write a little C++ class for this and upload it (I hope it will work).

[kedaman]

Well i'd rather do it my way, pointer aritmethics

I've used single dimensioned arrays anyways, i just wondered if there was a type with it's dimensions as constants in the dereference process. If you make a class, make it act like an array too And no runtime dimensions

[CornedBee]

No runtime dimensions? Why not?
You can specify the dimensions in the constructor, or later. It's nearly no extra work. I can make a fixed one too, but I don't see why (speed?).

[kedaman]

Well make two versions then, because i want a static one too, specifying dimension by template parameter (yes for speed of course)

[CornedBee]

[CornedBee]

wait a moment - if it should be static, then why on the heap? I have to call malloc or new anyway if it's on the heap, and then I don't really care if it's dynamic...

[CornedBee]

ok, so my class does not change size dynamically, but only if you tell it to do (by calling ReAlloc). It does not dynamically change size as needed ( as STL containers do).

[kedaman]

well, i didn't mean like that.
to dereference a 2d array you need to know one of the dimensions, the inner one. It's not only speed btw, that will be 4 bytes more on the heap per array and i want it to be 4.

The array object itself is on the stack while it's content and size is on the heap, and you know, _msize can be used right? that means the empty 2d array will be 8 bytes, and static on the inner dimension (you can redimension the outher one)

the 2d array with 2 dynamical dimensions would then be 12 bytes, as it also holds the size of the inner dimension.

[CornedBee]

you know what? I just found out that "new" supports multidimensional arrays

int* ar = new int [10][20];
// All sizes but the first have to be constants, so
int x = 4;
int* ar1 = new int[x][5];
// is allowed, but not
int* ar2 = new int[5][x];

Makes my class pretty useless, doesn't it?

[kedaman]

Maybe, but I don't like this freaky syntax:

    int* ar =(int*)(void*) new int [10][20];
    // All sizes but the first have to be constants, so
    int x = 4;
    int* ar1 = (int*)(void*)new int[x][5];
    cout << &ar1[6]<<endl;
    cout << &((int (*)[5])ar1)[1][1]<<endl; 

[kedaman]

now this is odd!

    int x = 4;
    int* ar1= (int*)(void*)new int[x][5];
    cout << &ar1[6]<<endl;
    cout << &((int (*)[5])ar1)[1][1]<<endl; 

gives:
00481E68
00481E68

    int x = 4;
    int(* ar1)[5] = new int[x][5];
    cout << &ar1[6]<<endl;
    cout << &ar1[1][1]<<endl; 

gives:
00481EC8
00481E68
and worst thing is i get assertion failure on both versions!

[CornedBee]

try
int (*ar1)[5]
as your pointer declaration.

[kedaman]

um.. thats what i did, but both versions crashed

[kedaman]

hmm MSVC stuff...
well what output do you get on both?

[jim mcnamara]

CB -

Bracketing is just fine.

Compared with German - English is a 'freeform' language.
I guess it's because people from everywhere came here and did their own interesting things with English.

Words are coined virtually every day - meaning: if you hear a term or see it written several times, people seem to accept it. Different world view. I just saw 'Anthraxiety' = anxiety over anthrax.