alice-bob.cpp

#ifndef NUM_THROWS
#define NUM_THROWS 100
#endif

#include <iostream>
#include <iomanip>
#include <cstdint>

template <unsigned K>
struct bigint
{
    std::uint64_t val[K];
    constexpr friend bigint<K> operator+(bigint<K> a, bigint<K> b)
    {
        bigint<K> res = 0;
        unsigned carry = 0;
        for (unsigned i = 0; i < K; ++i)
        {
            unsigned next_carry = 0;
            auto res1 = a.val[i] + b.val[i];
            if (res1 < a.val[i]) // wrap around
                next_carry = 1;
            auto res2 = res1 + carry;
            if (res2 < res1)
                next_carry = 1;
            carry = next_carry;
            res.val[i] = res2;
        }
        return res;
    }

    constexpr bigint(std::uint64_t i = 0) : val{0}
    {
        val[0] = i;
    }

    friend std::ostream& operator<<(std::ostream& os, const bigint<K>& n)
    {
        bool start = false;
        bool first = true;
        for (int i = K-1; i >= 0; i--)
        {
            if (n.val[i]) start = true;
            if (start)
            {
                if (first) os << std::hex << n.val[i];
                else os << std::hex << std::setw(16) << std::setfill('0') << n.val[i];
                first = false;
            }
        }

        if (!start) os << "0";

        return os;
    }
};

using mybigint = bigint<(NUM_THROWS+63)/64>;

template <unsigned num_throws, bool is_last_throw_heads, int alice_minus_bob>
constexpr mybigint num_games_alice_leads_by()
{
    if constexpr (num_throws == 1)
    {
        if constexpr (alice_minus_bob == 0)
            return 1;
        else
            return 0;
    }
    else
    {
        constexpr auto t0 = num_games_alice_leads_by<num_throws-1, false, alice_minus_bob>();
        if constexpr (is_last_throw_heads)
        {
            constexpr auto hm1 = num_games_alice_leads_by<num_throws-1, true, alice_minus_bob-1>();
            // heads-heads, alice wins
            // tails-heads, nobody wins
            return hm1 + t0;
        }
        else
        {
            constexpr auto tp1 = num_games_alice_leads_by<num_throws-1, true, alice_minus_bob+1>();
            // heads-tails, Bob wins
            // tails-tails, nobody wins
            return tp1 + t0;
        }
    }
}

template <int num_throws, int alice_leads>
constexpr mybigint num_games_alice_leads_in()
{
    if constexpr (alice_leads == 1)
    {
        return num_games_alice_leads_by<num_throws, true, 1>() + num_games_alice_leads_by<num_throws, false, 1>();
    }
    else
    {
        return num_games_alice_leads_by<num_throws, true, alice_leads>() + num_games_alice_leads_by<num_throws, false, alice_leads>()
            +  num_games_alice_leads_in<num_throws, alice_leads-1>();
    }
}

template <int num_throws>
constexpr mybigint num_games_alice_leads()
{
    return num_games_alice_leads_in<num_throws, num_throws>();
}

template <int num_throws, int bob_leads>
constexpr mybigint num_games_bob_leads_in()
{
    if constexpr (bob_leads == 1)
    {
        return num_games_alice_leads_by<num_throws, true, -1>() + num_games_alice_leads_by<num_throws, false, -1>();
    }
    else
    {
        return num_games_alice_leads_by<num_throws, true, -bob_leads>() + num_games_alice_leads_by<num_throws, false, -bob_leads>()
            +  num_games_bob_leads_in<num_throws, bob_leads-1>();
    }
}
template <int num_throws>
constexpr mybigint num_games_bob_leads()
{
    return num_games_bob_leads_in<num_throws, num_throws>();
}

template <int num_throws>
constexpr mybigint num_draws()
{
    return num_games_alice_leads_by<num_throws, true, 0>() + num_games_alice_leads_by<num_throws, false, 0>();
}

int main()
{
    std::cout << "Alice wins: " << num_games_alice_leads<NUM_THROWS>() << "\n";
    std::cout << "Bob wins:   " << num_games_bob_leads<NUM_THROWS>() << "\n";
    std::cout << "Draws:      " << num_draws<NUM_THROWS>() << "\n";
}