Skip to content

Instantly share code, notes, and snippets.

@felipap
Created September 14, 2012 23:31
Show Gist options
  • Save felipap/3725596 to your computer and use it in GitHub Desktop.
Save felipap/3725596 to your computer and use it in GitHub Desktop.
joguinho do Brito
#include <stdio.h>
#include <stdlib.h>
struct _element {
struct _element *prev, *next;
int value;
};
struct _column {
struct _column *prev, *next;
struct _element *efirst, *elast;
unsigned rsize;
};
struct _matrix {
struct _column *cfirst, *clast;
unsigned csize;
};
typedef struct _column column;
typedef struct _matrix matrix;
typedef struct _element element;
//
// These MUST be non-negative different from NULLPIECE.
#define PIECE int
#define NULLPIECE (CCC++)
int CCC = 0;
#define REQLEN 3
void
printMatrix (matrix *M)
// Prints the matrix, with columns represented vertically.
{
column *C;
element *E[M->csize]; // Vector of pointers to elements of each column.
int i, i2;
// Initialize vectors.
for (C=M->cfirst, i=0; C; C=C->next)
E[i++] = C->efirst;
for (i=0; i<(M->cfirst->rsize); i++) { // i in 0..n-rows
for (i2=0; i2<M->csize; i2++) { // i2 in 0..n-cols
printf("%3d", E[i2]->value);
E[i2] = E[i2]->next; // Substitute each element by it's successor.
}
printf("\n");
}
}
inline column *
getColumn (matrix *M, unsigned int n)
// Get (n+1)th column from matrix M (count starting from 0).
// If M doesn't have such column, NULL is returned.
{
column *C;
C = M->cfirst;
while (n-- && C)
C = C->next;
return C; // NULL if nth column doesn't exist.
}
inline element *
getPiece (matrix *M, unsigned col, unsigned row)
{
// Assert piece is within board bounds.
column *C;
element *E;
if (!(C = getColumn(M, col)))
return NULL; // Column out-of-bounds.
E = C->efirst;
while (row-- && E)
E = E->next;
return E; // NULL if nth element doesn't exist;
}
matrix *
allocMatrix (int columns, int lines)
{
int c, l;
matrix *M;
column *C, *prevC = NULL;
element *E, *prevE = NULL;
if (!(M = malloc(sizeof *M)))
return NULL;
if (!columns || !lines) {
M->csize = 0;
M->cfirst= M->clast = NULL;
return M;
}
for (c=0; c<columns; c++) {
prevE = NULL;
if (!(C = malloc(sizeof *C)))
return NULL;
for (l=0; l<lines; l++) {
if (!(E = malloc(sizeof *E)))
return NULL;
E->prev = prevE;
if (prevE)
prevE->next = E;
else C->efirst = E;
E->value = NULLPIECE;
prevE = E;
}
E->next = NULL;
C->prev = prevC;
C->elast = prevE;
if (prevC)
prevC->next = C;
else M->cfirst = C;
C->rsize = lines;
prevC = C;
}
C->next = NULL;
M->clast = prevC;
M->csize = columns;
return M;
}
int
placePiece (column *C, PIECE p)
// Places a generic piece p on the column col.
// The final row is the biggest non-occupied
{
element *E = C->elast;
while (E && E->value != 0) {
E = E->prev;
}
if (!E) { // Column is full.
puts("Column is full.");
return 1;
} else {
E->value = p;
}
return 0;
}
PIECE // winner
_testVictory_vertical (matrix *M)
// Tests vertical lines;
{
column *C;
element *E;
int counter = 1,
lastp = -1; // Invalid piece value;
for (C=M->cfirst; C; C=C->next) {
for (E=C->efirst; E; E=E->next) {
// printf("counter: %d\n", counter);
if (!E->value || E->value != lastp) { // Reset counter.
lastp = (E->value)?(E->value):-1;
counter = 1;
} else { // Increment counter.
counter++;
}
if (counter == REQLEN)
return (PIECE) lastp;
}
}
return 0;
}
PIECE // winner
_testVictory_horizontal (matrix *M)
// Tests horizontal lines;
{
column *C;
element *E[M->csize]; // Vector of pointers to elements of each column;
int counter = 1,
lastp = -1, // Invalid piece value;
i, i2;
for (C=M->cfirst, i=0; C; C=C->next)
E[i++] = C->efirst;
for (i=0; i<(M->cfirst->rsize); i++) { // i in 0..n-rows
for (i2=0; i2<M->csize; i2++) { // i2 in 0..n-cols
// printf("counter: %d\n", counter);
if (!E[i2]->value || E[i2]->value != lastp) { // Reset counter.
lastp = (E[i2]->value)?(E[i2]->value):-1;
counter = 1;
} else { // Increment counter.
counter++;
}
if (counter == REQLEN)
return (PIECE) lastp;
E[i2] = E[i2]->next; // Substitute each element by it's successor.
}
}
return 0;
}
PIECE // winner
_testVictory_diagonal (matrix *M)
// Tests diagonal lines;
{
int i, c, l,
cSize = M->csize, rSize = M->cfirst->rsize,
counter1, lastp1, // for l+c = i (case 1);
counter2, lastp2; // for l-c = i (case 2);
element *E;
// Do some math...
for (i=REQLEN+1; // Line for x+y=i has at least RL items if i=RL+1;
i <= (cSize+rSize-REQLEN+1); // Line for x+y=i has at least RL items if i<=cS+rS-RL+1;
i++) {
counter1 = counter2 = 1;
lastp1 = lastp2 = -1; // Invalid piece value.
for (c=1; c<i; c++) {
l = i-c;
if (c>cSize || l>rSize) // Coordinate surpasses board.
continue;
// Check first case (l+c=i)
E = getPiece(M, c-1, l-1);
if (!E->value || E->value != lastp1) { // Reset counter.
lastp1 = (E->value)?(E->value):-1;
counter1 = 1;
} else counter1++;
// printf("counter 1: %d\n", counter1);
if (counter1 == REQLEN)
return (PIECE) E->value;
// printf("M[%d,%d]: %d\n", c-1, l-1, E->value);
// Check second case (l-c=i)
E = getPiece(M, cSize-c, l-1);
if (!E->value || E->value != lastp2) { // Reset counter.
lastp2 = (E->value)?(E->value):-1;
counter2 = 1;
} else counter2++;
// printf("counter 2: %d\n", counter2);
if (0 && counter2 == REQLEN)
return (PIECE) E->value;
// printf("M[%d,%d]: %d\n", cSize-c, l-1, E->value);
}
// printf("\n");
}
return 0;
}
PIECE // winner
testVictory (matrix *M)
{
PIECE p;
if ((p = _testVictory_vertical(M)) ||
(p = _testVictory_horizontal(M)) ||
(p = _testVictory_diagonal(M)))
return p;
return 0; // Or return p anyways...
}
int main ()
{
matrix *m;
puts("allocing");
m = allocMatrix(5, 5);
puts("placing piece");
/*
placePiece(m->cfirst, 1);
placePiece(m->cfirst, 1);
placePiece(m->cfirst, 1);
placePiece(m->cfirst, 4);
placePiece(m->cfirst, 1);
placePiece(m->cfirst->next, 1);
placePiece(m->cfirst->next->next, 1);
placePiece(m->cfirst->next, 4);
placePiece(m->cfirst->next->next, 4);
placePiece(m->cfirst->next->next->next, 4);
placePiece(m->cfirst->next->next->next, 4);
puts("printing");
printMatrix(m);
getColumn(m, 3);
printf("v piece: %d\n", _testVictory_vertical(m));
printf("h piece: %d\n", _testVictory_horizontal(m));
*/
puts("printing");
printMatrix(m);
printf("d piece: %d\n", _testVictory_diagonal(m));
printf("v %d\n", testVictory(m));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment