m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Nim
(game/nim.hpp)

Overview

Helpers for ordinary Nim and misere Nim. A position is given as a range of nonnegative heap sizes. An empty or all-zero position is losing in ordinary Nim and winning under the misere convention, where the player with no move wins.

In ordinary Nim, the first player wins exactly when the xor of all heap sizes is nonzero. In misere Nim, the same rule applies while some heap has size at least two; if every nonempty heap has size one, the first player wins exactly when their count is even.

Functions

All functions are in namespace m1une::game. Heap values must support default construction, ^=, comparison with zero, and, for misere Nim, comparison with one.

NimMove<T> stores the zero-based heap index and its strictly smaller new_size. Winning-move functions return std::nullopt for losing positions. For the empty misere position they also return std::nullopt: the position is winning because the player already has no move, so no move can be constructed.

Function signature Description Complexity
template<class Iterator>
auto nim_sum(Iterator first, Iterator last) 		Returns the xor of the heap sizes in [first, last). O(N) time, O(1) space
template<class Range>
auto nim_sum(const Range& heaps) 		Range overload of nim_sum. O(N) time, O(1) space
template<class Range>
bool nim_first_player_wins(const Range& heaps) 		Whether the first player wins ordinary Nim under normal play. O(N) time, O(1) space
template<class Range>
std::optional<NimMove<T>> nim_winning_move(const Range& heaps) 		Returns a move to an ordinary-Nim losing position when one exists. O(N) time, O(1) space
template<class Range>
bool misere_nim_first_player_wins(const Range& heaps) 		Whether the first player wins Nim when taking the last object loses. O(N) time, O(1) space
template<class Range>
std::optional<NimMove<T>> misere_nim_winning_move(const Range& heaps) 		Returns a move to a misere-Nim losing position when one exists. O(N) time, O(1) space

Example

#include "game/nim.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<int> heaps = {1, 4, 5};
    std::cout << m1une::game::nim_sum(heaps) << '\n';
    std::cout << m1une::game::nim_first_player_wins(heaps) << '\n';
    auto move = m1une::game::nim_winning_move(heaps);
    if (move) heaps[move->heap] = move->new_size;

    std::vector<int> misere_heaps = {1, 1};
    std::cout << m1une::game::misere_nim_first_player_wins(misere_heaps) << '\n';
}

Required by

Verified with

Code

#ifndef M1UNE_GAME_NIM_HPP
#define M1UNE_GAME_NIM_HPP 1

#include <iterator>
#include <optional>
#include <type_traits>
#include <utility>

namespace m1une {
namespace game {

template <typename T>
struct NimMove {
    int heap;
    T new_size;
};

template <typename Iterator>
auto nim_sum(Iterator first, Iterator last) {
    using T = typename std::iterator_traits<Iterator>::value_type;
    T result{};
    while (first != last) {
        result ^= *first;
        ++first;
    }
    return result;
}

template <typename Range>
auto nim_sum(const Range& heaps) {
    using std::begin;
    using std::end;
    return nim_sum(begin(heaps), end(heaps));
}

template <typename Range>
bool nim_first_player_wins(const Range& heaps) {
    return nim_sum(heaps) != 0;
}

template <typename Range>
auto nim_winning_move(const Range& heaps) {
    using std::begin;
    using std::end;
    using T = std::decay_t<decltype(*begin(heaps))>;

    const T sum = nim_sum(heaps);
    if (sum == 0) return std::optional<NimMove<T>>{};
    int index = 0;
    for (
        auto iterator = begin(heaps);
        iterator != end(heaps);
        ++iterator, ++index
    ) {
        const T new_size = *iterator ^ sum;
        if (new_size < *iterator) return std::optional(NimMove<T>{index, new_size});
    }
    return std::optional<NimMove<T>>{};
}

template <typename Range>
bool misere_nim_first_player_wins(const Range& heaps) {
    using std::begin;
    using std::end;

    auto first = begin(heaps);
    const auto last = end(heaps);
    bool odd_nonzero_heaps = false;
    bool has_large_heap = false;
    using T = typename std::iterator_traits<decltype(first)>::value_type;
    T sum{};
    for (; first != last; ++first) {
        sum ^= *first;
        if (*first != 0) {
            odd_nonzero_heaps = !odd_nonzero_heaps;
        }
        if (*first > 1) has_large_heap = true;
    }
    return has_large_heap ? sum != 0 : !odd_nonzero_heaps;
}

template <typename Range>
auto misere_nim_winning_move(const Range& heaps) {
    using std::begin;
    using std::end;
    using T = std::decay_t<decltype(*begin(heaps))>;

    T sum{};
    int ones = 0;
    int large_heaps = 0;
    int only_large_heap = -1;
    int index = 0;
    for (
        auto iterator = begin(heaps);
        iterator != end(heaps);
        ++iterator, ++index
    ) {
        sum ^= *iterator;
        if (*iterator == 1) ones++;
        if (*iterator > 1) {
            large_heaps++;
            only_large_heap = index;
        }
    }

    if (large_heaps == 0) {
        if (ones == 0 || ones % 2 == 1) return std::optional<NimMove<T>>{};
        index = 0;
        for (
            auto iterator = begin(heaps);
            iterator != end(heaps);
            ++iterator, ++index
        ) {
            if (*iterator == 1) return std::optional(NimMove<T>{index, T(0)});
        }
    }
    if (large_heaps == 1) {
        const T new_size = ones % 2 == 0 ? T(1) : T(0);
        return std::optional(NimMove<T>{only_large_heap, new_size});
    }
    if (sum == 0) return std::optional<NimMove<T>>{};

    index = 0;
    for (auto iterator = begin(heaps); iterator != end(heaps); ++iterator, ++index) {
        const T new_size = *iterator ^ sum;
        if (new_size < *iterator) return std::optional(NimMove<T>{index, new_size});
    }
    return std::optional<NimMove<T>>{};
}

}  // namespace game
}  // namespace m1une

#endif  // M1UNE_GAME_NIM_HPP
#line 1 "game/nim.hpp"



#include <iterator>
#include <optional>
#include <type_traits>
#include <utility>

namespace m1une {
namespace game {

template <typename T>
struct NimMove {
    int heap;
    T new_size;
};

template <typename Iterator>
auto nim_sum(Iterator first, Iterator last) {
    using T = typename std::iterator_traits<Iterator>::value_type;
    T result{};
    while (first != last) {
        result ^= *first;
        ++first;
    }
    return result;
}

template <typename Range>
auto nim_sum(const Range& heaps) {
    using std::begin;
    using std::end;
    return nim_sum(begin(heaps), end(heaps));
}

template <typename Range>
bool nim_first_player_wins(const Range& heaps) {
    return nim_sum(heaps) != 0;
}

template <typename Range>
auto nim_winning_move(const Range& heaps) {
    using std::begin;
    using std::end;
    using T = std::decay_t<decltype(*begin(heaps))>;

    const T sum = nim_sum(heaps);
    if (sum == 0) return std::optional<NimMove<T>>{};
    int index = 0;
    for (
        auto iterator = begin(heaps);
        iterator != end(heaps);
        ++iterator, ++index
    ) {
        const T new_size = *iterator ^ sum;
        if (new_size < *iterator) return std::optional(NimMove<T>{index, new_size});
    }
    return std::optional<NimMove<T>>{};
}

template <typename Range>
bool misere_nim_first_player_wins(const Range& heaps) {
    using std::begin;
    using std::end;

    auto first = begin(heaps);
    const auto last = end(heaps);
    bool odd_nonzero_heaps = false;
    bool has_large_heap = false;
    using T = typename std::iterator_traits<decltype(first)>::value_type;
    T sum{};
    for (; first != last; ++first) {
        sum ^= *first;
        if (*first != 0) {
            odd_nonzero_heaps = !odd_nonzero_heaps;
        }
        if (*first > 1) has_large_heap = true;
    }
    return has_large_heap ? sum != 0 : !odd_nonzero_heaps;
}

template <typename Range>
auto misere_nim_winning_move(const Range& heaps) {
    using std::begin;
    using std::end;
    using T = std::decay_t<decltype(*begin(heaps))>;

    T sum{};
    int ones = 0;
    int large_heaps = 0;
    int only_large_heap = -1;
    int index = 0;
    for (
        auto iterator = begin(heaps);
        iterator != end(heaps);
        ++iterator, ++index
    ) {
        sum ^= *iterator;
        if (*iterator == 1) ones++;
        if (*iterator > 1) {
            large_heaps++;
            only_large_heap = index;
        }
    }

    if (large_heaps == 0) {
        if (ones == 0 || ones % 2 == 1) return std::optional<NimMove<T>>{};
        index = 0;
        for (
            auto iterator = begin(heaps);
            iterator != end(heaps);
            ++iterator, ++index
        ) {
            if (*iterator == 1) return std::optional(NimMove<T>{index, T(0)});
        }
    }
    if (large_heaps == 1) {
        const T new_size = ones % 2 == 0 ? T(1) : T(0);
        return std::optional(NimMove<T>{only_large_heap, new_size});
    }
    if (sum == 0) return std::optional<NimMove<T>>{};

    index = 0;
    for (auto iterator = begin(heaps); iterator != end(heaps); ++iterator, ++index) {
        const T new_size = *iterator ^ sum;
        if (new_size < *iterator) return std::optional(NimMove<T>{index, new_size});
    }
    return std::optional<NimMove<T>>{};
}

}  // namespace game
}  // namespace m1une
Back to top page