Simulate a two-player card war game
Problem Description
Implement a function to simulate a two-player card game, commonly known as "War".
Game Setup
Each player starts with a deck of cards, represented as a queue of card ranks. The top card is at index 0. Card ranks range from 2 to 14, where 11 represents Jack (J), 12 Queen (Q), 13 King (K), and 14 Ace (A). Card suits are ignored for comparison.
Round Mechanics
In each round:
- Both players draw their top card.
- The ranks of these two cards are compared.
- The player with the higher-ranked card wins the round.
- The winner collects all cards that were on the table during that round. These cards are placed at the bottom of the winner's deck. The order of placement is crucial: the winner's card(s) from the current reveal are placed before the opponent's card(s) from the current reveal.
Tie-breaking (War)
If the two cards drawn in a round have the same rank:
- Each player must draw exactly three additional cards from their deck. These cards are placed face down.
- If a player cannot provide three additional cards, they immediately lose the game.
- Otherwise, the third additional card drawn by each player is compared. The player with the higher rank wins the "war".
- The winner of the war takes all cards that were on the table during this extended round (the initial two cards plus the six cards drawn for the war). These cards are added to the bottom of their deck, following the same ordering rule as a regular round.
Game Termination
The game continues until one player has no cards remaining in their deck. That player loses, and the other player is declared the winner.
To prevent infinite cycles:
- The simulation must stop if a previously seen game state (defined by the exact configuration of Player 1's deck and Player 2's deck) repeats.
- Alternatively, the simulation must stop if a large round cap (e.g., 1,000,000 rounds) is reached.
- In either of these cycle-prevention scenarios, the game is declared a "draw".
Output
The function should return:
- The winner: an integer (1 for Player 1, 2 for Player 2) or the string "draw".
- The total number of rounds simulated.
Performance Requirements
- Time Complexity: Aim for O(total cards moved).
- Space Complexity: Aim for O(n), where n is the total number of cards initially in play.
AI interview prep
Core dilemma
Efficiently managing dynamic deck states (queues) with complex card movement rules, especially during 'war' scenarios, while accurately detecting repeating game states to prevent infinite loops, all within strict O(total cards moved) time and O(N) space constraints.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Simulate a two-player card war game
Problem Description
Implement a function to simulate a two-player card game, commonly known as "War".
Game Setup
Each player starts with a deck of cards, represented as a queue of card ranks. The top card is at index 0. Card ranks range from 2 to 14, where 11 represents Jack (J), 12 Queen (Q), 13 King (K), and 14 Ace (A). Card suits are ignored for comparison.
Round Mechanics
In each round:
- Both players draw their top card.
- The ranks of these two cards are compared.
- The player with the higher-ranked card wins the round.
- The winner collects all cards that were on the table during that round. These cards are placed at the bottom of the winner's deck. The order of placement is crucial: the winner's card(s) from the current reveal are placed before the opponent's card(s) from the current reveal.
Tie-breaking (War)
If the two cards drawn in a round have the same rank:
- Each player must draw exactly three additional cards from their deck. These cards are placed face down.
- If a player cannot provide three additional cards, they immediately lose the game.
- Otherwise, the third additional card drawn by each player is compared. The player with the higher rank wins the "war".
- The winner of the war takes all cards that were on the table during this extended round (the initial two cards plus the six cards drawn for the war). These cards are added to the bottom of their deck, following the same ordering rule as a regular round.
Game Termination
The game continues until one player has no cards remaining in their deck. That player loses, and the other player is declared the winner.
To prevent infinite cycles:
- The simulation must stop if a previously seen game state (defined by the exact configuration of Player 1's deck and Player 2's deck) repeats.
- Alternatively, the simulation must stop if a large round cap (e.g., 1,000,000 rounds) is reached.
- In either of these cycle-prevention scenarios, the game is declared a "draw".
Output
The function should return:
- The winner: an integer (1 for Player 1, 2 for Player 2) or the string "draw".
- The total number of rounds simulated.
Performance Requirements
- Time Complexity: Aim for O(total cards moved).
- Space Complexity: Aim for O(n), where n is the total number of cards initially in play.