Silver Dollar Game
(game/silver_dollar_game.hpp)

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

Overview

Solves the Silver Dollar Game on the nonnegative integer strip. Coins occupy distinct cells. A move slides one coin left by a positive distance without jumping over or landing on another coin.

Pairing coins from the right reduces the position to independent Nim heaps. For an odd number of coins, the unpaired leftmost coin contributes its distance from cell zero. Each remaining pair contributes the number of empty cells between its coins.

Functions

All functions are in namespace m1une::game. Template parameter T must be a nonnegative integer-like type supporting comparison, subtraction, and xor.

Function signature	Description	Complexity
template<class T> T silver_dollar_grundy(const std::vector<T>& coins)	Returns the position’s Grundy number.	O(N) time, O(1) extra space
template<class T> bool silver_dollar_first_player_wins(const std::vector<T>& coins)	Whether the first player wins under normal play.	O(N) time, O(1) extra space

coins must be strictly increasing and nonnegative. This is asserted in debug builds. The empty position has Grundy number zero.

Example

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

int main() {
    std::vector<int> coins = {1, 3, 7};
    std::cout << m1une::game::silver_dollar_grundy(coins) << '\n';
    std::cout << m1une::game::silver_dollar_first_player_wins(coins) << '\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_SILVER_DOLLAR_GAME_HPP
#define M1UNE_GAME_SILVER_DOLLAR_GAME_HPP 1

#include <cassert>
#include <type_traits>
#include <vector>

namespace m1une {
namespace game {

template <typename T>
T silver_dollar_grundy(const std::vector<T>& coins) {
    for (int index = 0; index < int(coins.size()); ++index) {
        if constexpr (std::is_signed_v<T>) assert(coins[index] >= 0);
        if (index != 0) assert(coins[index - 1] < coins[index]);
    }

    T result{};
    int index = int(coins.size()) % 2;
    if (index == 1) result ^= coins[0];
    for (; index + 1 < int(coins.size()); index += 2) {
        result ^= coins[index + 1] - coins[index] - 1;
    }
    return result;
}

template <typename T>
bool silver_dollar_first_player_wins(const std::vector<T>& coins) {
    return silver_dollar_grundy(coins) != 0;
}

}  // namespace game
}  // namespace m1une

#endif  // M1UNE_GAME_SILVER_DOLLAR_GAME_HPP

#line 1 "game/silver_dollar_game.hpp"



#include <cassert>
#include <type_traits>
#include <vector>

namespace m1une {
namespace game {

template <typename T>
T silver_dollar_grundy(const std::vector<T>& coins) {
    for (int index = 0; index < int(coins.size()); ++index) {
        if constexpr (std::is_signed_v<T>) assert(coins[index] >= 0);
        if (index != 0) assert(coins[index - 1] < coins[index]);
    }

    T result{};
    int index = int(coins.size()) % 2;
    if (index == 1) result ^= coins[0];
    for (; index + 1 < int(coins.size()); index += 2) {
        result ^= coins[index + 1] - coins[index] - 1;
    }
    return result;
}

template <typename T>
bool silver_dollar_first_player_wins(const std::vector<T>& coins) {
    return silver_dollar_grundy(coins) != 0;
}

}  // namespace game
}  // namespace m1une

Back to top page