joguinho do Brito

game.c

#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;
}