jeudi 14 mai 2020

recursive brute force implementation in 2d array

i am tackling on a problem. i have gotten stuck, so i decided to ask here. so, the problem is, given n team and their points respectively of a world cup group. determine whether the set is possible or not. each team plays with every other team in the group once. hence, each group plays (n-1) times. for 1<=n<=5. in a match if a team win, they'll get 3 points, if lose 0 points, and tied, 1 point. my idea of the solution is using 2d(n x n) array which act like a scoreboard.

     A B C D E //column
   A X 1 3 0 1  //r
   B 1 X 0 1 0  //o
   C 0 3 X 0 3  //w
   D 3 1 3 X 1
   E 1 3 0 1 X

so for every column and row representing one distinct team in a multiplication table fashion(team in column 1(a) is same as team row 1(A), and so on)note that the alphabet above and beside the array(A,B..) isn't included, just for clearance. every intersection between a row and a column is representing a match, except intersection between same column and row. e.g. column 1, row 2, means team A tied against team B, column 2, row 1 means team B tied against A.

my idea is to use recursive brute-force-wise algorithm to check every possibilities. i have developed one, it's work good enough in 4 teams setting, but doesn't so well for 5. so the algorithm work like starting from column 2 row 1 check 1 out of 3 possibility then crawl to the bottom-side and right-side of it and repeat through the second last column, and last row.

you may have noticed that x diagonal act like mirror. when we change column 1 row 3(A against C) to win, we must change column 3 row 1(C against A) to lose simultaneously. here some part of my code

/*
 * scoreBoard[][] array <- the array which i have described above
 * scores[] array <- store the given score
 * x <- current column
 * y <-  current row
 * n <- gnumber of team
*/
bool Solve(int x, int y, int scoreBoard[][5], int scores[], int n)
{
    bool con1, con2, con3;
    if((x < y)&&(y < n)) {
        scoreBoard[x][y] = 3;//win-lose - possibiiity 1
        scoreBoard[y][x] = 0;
        //crawl to the right and bottom side array
        con1 = (Solve( x + 1, y, scoreBoard, scores, n)) || (Solve( x, y + 1, scoreBoard, scores, n));


        scoreBoard[x][y] = 0;//lose-win - possibility 2
        scoreBoard[y][x] = 3;
        con2 = (Solve( x + 1, y, scoreBoard, scores, n)) || (Solve( x, y + 1, scoreBoard, scores, n));

        scoreBoard[x][y] = 1;//tied - possibility 3
        scoreBoard[y][x] = 1;
        //crawl to the right and bottom side array
        con3 = (Solve( x + 1, y, scoreBoard, scores, n)) || (Solve( x, y + 1, scoreBoard, scores,n));

        return con1 || con2 || con3;
    } else {
        if((x==y)&&(y==n-1))
            return CheckArr(scoreBoard, scores, n); //to check whether the current array equal with the given score or not
        else
            return 0;
    }
}

i presume, the problem is that this algorithm does not cover every possibility, because it work on(give the expected output for some, and dont so for other) a few 5 team setting possiblity. but i haven't managed how to fix it.

thanks in advance for every suggestion, and helpful link, also, i'll welcome any other strategy. hope this clear enough.

Aucun commentaire:

Enregistrer un commentaire