Problem 150644 · hard · Phase 01 Prerequisites & Setup

Sowing Seeds Around the Board

lists · simulation · index arithmetic

Two players share a board of 2n + 2 slots arranged in a ring, stored in the list board:

  • slots 0 to n - 1 are player 0's pits and slot n is player 0's store;
  • slots n + 1 to 2n are player 1's pits and slot 2n + 1 is player 1's store.

Player 0 moves first. moves lists the moves in order; each is a pit number m from 0 to n - 1 counted on the mover's own side (player 0's pit m is slot m, player 1's pit m is slot n + 1 + m). A move works like this:

  1. If the chosen pit is empty, nothing happens and the turn passes to the other player.
  2. Otherwise the mover lifts every seed from it and drops them one at a time into the following slots in increasing order, wrapping from slot 2n + 1 back to slot 0. The opponent's store is skipped; the mover's own store receives seeds.
  3. If the last seed lands in the mover's store, the same player moves again.
  4. Otherwise, if the last seed lands in one of the mover's own pits that was empty just before that seed arrived, and the pit opposite it (slot 2n - s for slot s) holds at least one seed, both pits are emptied into the mover's store. Either way the turn passes.

The game is over as soon as all pits of either player are empty, checked at the start and after every move. Then each player adds the seeds left in their own pits to their own store, and all later moves are ignored.

Write sow_game(board, moves) that returns a tuple (final_board, next_player), where next_player is 0 or 1 for the player whose turn it is after all moves, or -1 if the game is over. Do not change the input list.

Examples

Input:  board = [3, 3, 3, 0, 3, 3, 3, 0], moves = [0, 2]
Output: ([0, 4, 0, 2, 4, 4, 4, 0], 1)
Explanation: pit 0's last seed reaches the store, so player 0 goes again.

Input:  board = [1, 0, 0, 0, 0, 0, 9, 0], moves = [0, 2]
Output: ([2, 2, 1, 0, 1, 1, 1, 2], 0)
Explanation: player 1's nine seeds go round the board and skip slot 3.

Input:  board = [0, 1, 0, 5, 2, 0, 4, 2], moves = [1]
Output: ([0, 0, 0, 8, 0, 0, 0, 6], -1)
Explanation: the seed lands in empty slot 2 and captures the 2 seeds in slot 4. Player 0's pits
are now empty, so player 1 banks the 4 seeds in slot 6.

Constraints

  • 1 <= n <= 10, so 4 <= len(board) <= 22; every entry is between 0 and 100
  • 0 <= len(moves) <= 500, every move is between 0 and n - 1

Goals

  • Walk around a ring of slots with a wrapping index
  • Skip one slot depending on who is moving
  • Apply turn, capture and end-of-game rules in the right order
Starting Python…