Subtraction Game
(game/subtraction_game.hpp)

• View this file on GitHub
• Last update: 2026-08-24 02:07:48+09:00
• Include: #include "game/subtraction_game.hpp"

Overview

Solves impartial subtraction games. From one heap, a move removes any positive amount in a fixed move set without making the heap negative. Multiple heaps are played as a disjoint sum, so their Grundy numbers combine with xor.

The implementation builds all Grundy numbers from heap size zero through a requested maximum. It is useful when many heaps share the same move set or when the full Grundy sequence is needed for later queries.

Functions

All functions are in namespace m1une::game.

Function signature	Description	Complexity
std::vector<int> subtraction_game_grundy(int max_heap, const std::vector<int>& moves)	Returns Grundy numbers for heap sizes in [0, max_heap].	O(max_heap * moves.size()) time, O(max_heap + moves.size()) space
int subtraction_game_nim_sum(const std::vector<int>& heaps, const std::vector<int>& moves)	Returns the xor of the heaps’ Grundy numbers.	O(max(heaps) * moves.size() + heaps.size()) time
bool subtraction_game_first_player_wins(const std::vector<int>& heaps, const std::vector<int>& moves)	Whether the first player wins the disjoint sum under normal play.	O(max(heaps) * moves.size() + heaps.size()) time

max_heap and every heap size must be nonnegative. Every move must be positive. These conditions are asserted in debug builds. Duplicate moves are allowed.

Example

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

int main() {
    std::vector<int> moves = {1, 3, 4};
    auto grundy = m1une::game::subtraction_game_grundy(10, moves);
    std::cout << grundy[10] << '\n';

    std::vector<int> heaps = {7, 10};
    std::cout << m1une::game::subtraction_game_first_player_wins(heaps, moves)
              << '\n';
}

Required by

• Game Library (game/all.hpp)

Verified with

• verify/game/classic_games.test.cpp
• verify/game/game_algorithms.test.cpp

Code

#ifndef M1UNE_GAME_SUBTRACTION_GAME_HPP
#define M1UNE_GAME_SUBTRACTION_GAME_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

namespace m1une {
namespace game {

inline std::vector<int> subtraction_game_grundy(
    int max_heap,
    const std::vector<int>& moves
) {
    assert(max_heap >= 0);
    for (int move : moves) assert(move > 0);

    std::vector<int> grundy(max_heap + 1);
    std::vector<int> seen(moves.size() + 1, -1);
    for (int heap = 1; heap <= max_heap; ++heap) {
        for (int move : moves) {
            if (move > heap) continue;
            const int value = grundy[heap - move];
            if (value < int(seen.size())) seen[value] = heap;
        }
        while (
            grundy[heap] < int(seen.size())
            && seen[grundy[heap]] == heap
        ) {
            grundy[heap]++;
        }
    }
    return grundy;
}

inline int subtraction_game_nim_sum(
    const std::vector<int>& heaps,
    const std::vector<int>& moves
) {
    int max_heap = 0;
    for (int heap : heaps) {
        assert(heap >= 0);
        max_heap = std::max(max_heap, heap);
    }
    const std::vector<int> grundy = subtraction_game_grundy(max_heap, moves);
    int result = 0;
    for (int heap : heaps) result ^= grundy[heap];
    return result;
}

inline bool subtraction_game_first_player_wins(
    const std::vector<int>& heaps,
    const std::vector<int>& moves
) {
    return subtraction_game_nim_sum(heaps, moves) != 0;
}

}  // namespace game
}  // namespace m1une

#endif  // M1UNE_GAME_SUBTRACTION_GAME_HPP

#line 1 "game/subtraction_game.hpp"



#include <algorithm>
#include <cassert>
#include <vector>

namespace m1une {
namespace game {

inline std::vector<int> subtraction_game_grundy(
    int max_heap,
    const std::vector<int>& moves
) {
    assert(max_heap >= 0);
    for (int move : moves) assert(move > 0);

    std::vector<int> grundy(max_heap + 1);
    std::vector<int> seen(moves.size() + 1, -1);
    for (int heap = 1; heap <= max_heap; ++heap) {
        for (int move : moves) {
            if (move > heap) continue;
            const int value = grundy[heap - move];
            if (value < int(seen.size())) seen[value] = heap;
        }
        while (
            grundy[heap] < int(seen.size())
            && seen[grundy[heap]] == heap
        ) {
            grundy[heap]++;
        }
    }
    return grundy;
}

inline int subtraction_game_nim_sum(
    const std::vector<int>& heaps,
    const std::vector<int>& moves
) {
    int max_heap = 0;
    for (int heap : heaps) {
        assert(heap >= 0);
        max_heap = std::max(max_heap, heap);
    }
    const std::vector<int> grundy = subtraction_game_grundy(max_heap, moves);
    int result = 0;
    for (int heap : heaps) result ^= grundy[heap];
    return result;
}

inline bool subtraction_game_first_player_wins(
    const std::vector<int>& heaps,
    const std::vector<int>& moves
) {
    return subtraction_game_nim_sum(heaps, moves) != 0;
}

}  // namespace game
}  // namespace m1une

Back to top page