C: Printing a valid path through recursion

67 Views Asked by At

Desc. I am making a game between two players that draw tokens. Player A always starts first. They have 5 options to pick: left, right, left + left + 1, left + right, right + right - 1 If they pick 2 in one turn, the next turn, they have to pick only 2.

Problem It gives me the correct result, but I want to keep track of what turns were made. How do I save only the valid paths through recursion?

Code

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct {
    int score;
    int moves[MAX_SIZE];
    int turns;
} SCORE;

/**     Drawing tokens
 * this is a game where 2 AI opponens draw tokens (numbers)
 * Each player can either draw 2 cards, but then has to draw only one card the next turn
 * or can draw 1 card only
 * player with larger tokenSum wins
 * program uses minimax algorithm
 */

void getTokens(int* tokens, size_t* size) {

    int token;
    printf("Zetony:\n");
    while(scanf("%d", &token) == 1) {
        tokens[(*size)++] = token;
        if (*size > MAX_SIZE) {
            *size = 0;
            break;
        }
    }
    //if (!feof(stdin) ) *size = 0;
}
//------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------
/**     A function to get the highest of 5 choices (playerA)
 * if player A can draw 2 cards
 * @returns max of 5
 */
int maxOfFive (int a, int b, int c, int d, int e) {
    int choices[] = {b, c, d, e};
    int max = a;
    for (int i = 0; i < 4; i++) {
        if (choices[i] > max) {
            max = choices[i];
        }
    }
    return max;
}
//------------------------------------------------------------------------------------------------
/**     A function to get the lowest of 5 choices (playerB)
 * if playerB can draw 2 cards
 * @returns min of 5 ints
 */
int minOfFive (int a, int b, int c, int d, int e) {
    int choices[] = {b, c, d, e};
    int min = a;
    for (int i = 0; i < 4; i++) {
        if (choices[i] < min) {
            min = choices[i];
        }
    }
    return min;
}
//------------------------------------------------------------------------------------------------
/**
 * @returns max of 2 ints
 */
int max (int a, int b) {
    return a > b ? a : b;
}
//------------------------------------------------------------------------------------------------
/**
 * @returns min of 2 ints
 */
int min (int a, int b) {
    return a < b ? a : b;
}
//------------------------------------------------------------------------------------------------
int minimaxRec (int* tokens, int start, int end, int scoreA, bool maximize, bool twoA, bool twoB) {
    if (start > end) return scoreA; //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

    if (maximize) {
        if(twoA && ( (end - start) >= 1) ) {
            int a = minimaxRec(tokens, start + 1, end, scoreA + tokens[start], !maximize, twoA, twoB );
            int b = minimaxRec(tokens, start, end - 1, scoreA + tokens[end], !maximize, twoA, twoB );
            int c = minimaxRec(tokens, start + 2, end, scoreA + tokens[start] + tokens[start + 1], !maximize, !twoA, twoB );
            int d = minimaxRec(tokens, start, end - 2, scoreA + tokens[end] + tokens[end - 1], !maximize, !twoA, twoB );
            int e = minimaxRec(tokens, start + 1, end - 1, scoreA + tokens[start] + tokens[end], !maximize, !twoA, twoB );
            printf("start:%d end:%d", start, end);
            return maxOfFive(a, b, c, d, e);
        }
        else {
            int a = minimaxRec(tokens, start + 1, end, scoreA + tokens[start], !maximize, !twoA, twoB );
            int b = minimaxRec(tokens, start, end - 1, scoreA + tokens[end], !maximize, !twoA, twoB );
            printf("start:%d end:%d", start, end);
            return max(a,b);
        }
    }
    else {
        if(twoB && ( (end - start) >= 1) ) {
            int a = minimaxRec(tokens, start + 1, end, scoreA, !maximize, twoA, twoB);
            int b = minimaxRec(tokens, start, end - 1, scoreA, !maximize, twoA, twoB);
            int c = minimaxRec(tokens, start + 2, end, scoreA, !maximize, twoA, !twoB);
            int d = minimaxRec(tokens, start, end - 2, scoreA, !maximize, twoA, !twoB);
            int e = minimaxRec(tokens, start + 1, end - 1, scoreA, !maximize, twoA, !twoB);
            return minOfFive(a, b, c, d, e);
        }
        else {
            int a = minimaxRec(tokens, start + 1, end, scoreA, !maximize, twoA, !twoB );
            int b = minimaxRec(tokens, start, end - 1, scoreA, !maximize, twoA, !twoB );
            return min(a, b);
        }
    }
}
//------------------------------------------------------------------------------------------------
SCORE minimax2 (int* tokens, int start, int end, bool maximize, int* turns) {
    SCORE result;
    if (start > end) {
        *turns = 0;
        return result;
    }
    SCORE l = minimax2(tokens, start + 1, end, !maximize, turns);
    SCORE r = minimax2(tokens, start, end - 1, !maximize, turns);

    if (maximize) {
        if (tokens[start] + l.score > tokens[end] + r.score) {
            result.score = tokens[start] + l.score;
            result.moves[*(turns)++] = start;
            return result;
        }
        else {
            result.score = tokens[end] + r.score;
            result.moves[*(turns)++] = end;
            return result;
        }
    }
    else {
        if (l.score < r.score) {
            result.score = l.score;
            result.moves[*(turns)++] = start;
            return result;
        }
        else {
            result.score = r.score;
            result.moves[*(turns)++] = end;
            return result;
        }
    }
}
//------------------------------------------------------------------------------------------------
SCORE minimax (int* tokens, size_t size) {
    int start = 0, end = size - 1;
    bool maximize = true, twoA = true, twoB = true;
    SCORE result;
    result.score = 0;
    result.score = minimaxRec(tokens, start, end, result.score, maximize, twoA, twoB);
    return result;
}
//------------------------------------------------------------------------------------------------

int main() {

    int tokens[MAX_SIZE], turns = 0;
    size_t size = 0;
    SCORE result;
    getTokens(tokens, &size);
    if (!size) {
        printf("Nespravny vstup.\n");
        return 0;
    }
    result = minimax(tokens, size);
    printf("\n%d\n", result.score);

    return 0;
}

I tried saving in into an array and got all tangled up.

0

There are 0 best solutions below