haifagame.c

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

#define MAX_TURNS 12

// true if we've found a way for the game to end by MAX_TURNS                                                                                                                                                                                                                                                                  
// false if not                                                                                                                                                                                                                                                                                                                
bool play(int turn, int p0, int p1, int p2) {
    turn++;
    
    if (turn >= MAX_TURNS) {
        return false;
    }
    
    if (p0 == p1 || p1 == p2 || p0 == p2) {
        return true;
    }
    
    // manually sort into p0 <= p1 <= p2                                                                                                                                                                                                                                                                                       
    if (p0 > p1) {
        int swap = p0;
        p0 = p1;
        p1 = swap;
    }
    if (p1 > p2) {
        int swap = p1;
        p1 = p2;
        p2 = swap;
    }
    if (p0 > p1) {
        int swap = p0;
        p0 = p1;
        p1 = swap;
    }
    
    return
        play(turn, p0 + p0, p1 - p0, p2) ||
        play(turn, p0 + p0, p1, p2 - p0) ||
        play(turn, p0, p1 + p1, p2 - p1);
}

int main() {
    // search through amounts of initial money, modulo obvious                                                                                                                                                                                                                                                                 
    // symmetry                                                                                                                                                                                                                                                                                                                
#pragma omp parallel for
    for (int p0 = 1; p0 < 256; p0++) {
        for (int p1 = p0; p1 < 256; p1++) {
            for (int p2 = p1; p2 < 256; p2++) {
                if (!play(0, p0, p1, p2)) {
                    printf("%d %d %d\n", p0, p1, p2);
                }
            }
        }
    }
}