1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
#include "Set.hpp"
#include <iostream>

/*
template <unsigned int i, unsigned int ...set>
struct MexSearch
{
    static constexpr unsigned int value = (IsMemberInSet<i, set...>::is_member)
                                        ? MexSearch<i+1,set...>::value
                                        : i;
};
*/

template <unsigned int i, unsigned int ...set>
struct MexSearch;

template <unsigned int i, bool isMember, unsigned int ...set>
struct MexSelect;

template <unsigned int i, unsigned int ...set>
struct MexSelect<itrue, set...>
{
    static constexpr unsigned int value = MexSearch<i+1, set...>::value;
};

template <unsigned int i, unsigned int ...set>
struct MexSelect<ifalse, set...>
{
    static constexpr unsigned int value = i;
};

template <unsigned int i, unsigned int ...set>
struct MexSearch
{
    static constexpr bool found = IsMemberInSet<i, set...>::is_member;
    static constexpr unsigned int value = MexSelect<i, found, set...>::value;
};

template <unsigned int ...set>
struct Mex
{
    static constexpr unsigned int value = MexSearch<0, set...>::value;
};

//------------------------------------------------------------------------------

template<unsigned int heap_size, unsigned int ... moves>
struct Nim;

template <unsigned int heap_size, unsigned int take, bool can_be_taken,
          unsigned int ... moves>
struct NimTakeNextStep;

template <unsigned int heap_size, unsigned int take, unsigned int ... moves>
struct NimTakeNextStep<heap_size, takefalse, moves...>
{
    static constexpr unsigned int value
        = std::numeric_limits<unsigned int>::max();
};

template <unsigned int heap_size, unsigned int take, unsigned int ... moves>
struct NimTakeNextStep<heap_size, taketrue, moves...>
{
    static constexpr unsigned int value
        = Nim<heap_size - take, moves...>::value;
};

template <unsigned int heap_size, unsigned int take, unsigned int ... moves>
struct NimTake
{
    static constexpr unsigned int value
        = NimTakeNextStep<heap_size, take, take<=heap_size, moves...>::value;
};

template <unsigned int heap_size, unsigned int ...moves>
struct Nim
{
    static constexpr unsigned int value
        = Mex<NimTake<heap_size, moves, moves...>::value...>::value;
};

template <unsigned int ...moves>
struct Nim<0, moves...>
{
    static constexpr unsigned int value = 0;
};

int
main()
{
    std::cout << "Mex<0, 1, 3, 4>::value = "
              << Mex<0134>::value << std::endl;
    std::cout << "Mex<0, 1, 2, 3, 4>::value = "
              << Mex<01234>::value << std::endl;
    std::cout << "Mex<>::value = "
              << Mex<>::value << std::endl;
    std::cout << Nim<42345>::value << std::endl;
    std::cout << Nim<14256>::value << std::endl;
}