Advent of Code Day 21 Part 2

aoc.c

#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct Player
{
    int position;
    int score;
} Player;

typedef struct GameState
{
    Player player1;
    Player player2;
    bool player1Turn;
} GameState;

typedef struct Result
{
    uint64_t player1Wins;
    uint64_t player2Wins;
} Result;

typedef struct Memo
{
    GameState state;
    Result result;
    struct Memo *next;
} Memo;

Memo *memo[131072];

uint64_t hash(GameState *state)
{
    uint64_t hash = 5381;
    hash = ((hash << 5) + hash) + state->player1.position;
    hash = ((hash << 5) + hash) + state->player1.score;
    hash = ((hash << 5) + hash) + state->player2.position;
    hash = ((hash << 5) + hash) + state->player2.score;
    hash = ((hash << 5) + hash) + state->player1Turn;
    return hash & 131071;
}

bool stateEquals(GameState *s1, GameState *s2)
{
    return s1->player1.position == s2->player1.position && s1->player1.score == s2->player1.score
            && s1->player2.position == s2->player2.position && s1->player2.score == s2->player2.score
            && s1->player1Turn == s2->player1Turn;
}

bool getMemo(GameState *state, Result *result)
{
    Memo *cur = memo[hash(state)];
    while (cur != NULL)
    {
        if (stateEquals(&cur->state, state))
        {
            result->player1Wins = cur->result.player1Wins;
            result->player2Wins = cur->result.player2Wins;
            return true;
        }
        cur = cur->next;
    }
    return false;
}

void addMemo(GameState *state, Result *result)
{
    Memo *newMemo = malloc(sizeof(Memo));
    if (newMemo == NULL)
    {
        puts("malloc failed");
        return;
    }
    newMemo->state = *state;
    newMemo->result = *result;
    uint64_t location = hash(state);
    newMemo->next = memo[location];
    memo[location] = newMemo;
}

Result playGame(GameState *state)
{
    Result result;
    if (state->player1.score >= 21)
    {
        result.player1Wins = 1;
        result.player2Wins = 0;
        return result;
    }
    if (state->player2.score >= 21)
    {
        result.player1Wins = 0;
        result.player2Wins = 1;
        return result;
    }
    if (getMemo(state, &result))
    {
        return result;
    }
    result.player1Wins = 0;
    result.player2Wins = 0;
    for (int i = 1; i < 4; i++)
    {
        for (int j = 1; j < 4; j++)
        {
            for (int k = 1; k < 4; k++)
            {
                GameState newState = *state;
                if (newState.player1Turn)
                {
                    newState.player1Turn = false;
                    newState.player1.position = newState.player1.position + i + j + k;
                    newState.player1.position--;
                    newState.player1.position = (newState.player1.position % 10) + 1;
                    newState.player1.score = newState.player1.score + newState.player1.position;
                }
                else
                {
                    newState.player1Turn = true;
                    newState.player2.position = newState.player2.position + i + j + k;
                    newState.player2.position--;
                    newState.player2.position = (newState.player2.position % 10) + 1;
                    newState.player2.score = newState.player2.score + newState.player2.position;
                }
                Result rec = playGame(&newState);
                result.player1Wins += rec.player1Wins;
                result.player2Wins += rec.player2Wins;
            }
        }
    }
    addMemo(state, &result);
    return result;
}

int main()
{
    GameState state;
    state.player1.position = 4;
    state.player2.position = 8;
    state.player1.score = 0;
    state.player2.score = 0;
    state.player1Turn = true;
    Result result = playGame(&state);
    printf("Player 1 Wins: %lu\nPlayer 2 Wins: %lu\n", result.player1Wins, result.player2Wins);
    return 0;
}