Design an Animal Chess OOP simulation
Company: Duolingo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Design and implement a simplified Animal Chess (Dou Shou Qi) game using object-oriented principles. Include:
1) Piece classes Elephant, Lion, Tiger, Leopard, Wolf, Dog, Cat, and Rat, each encapsulating its movement and capture rules;
2) A 9x7 board that models cell types (river, trap, den, land) and ownership;
3) Movement validation, capturing logic, turn handling, and win conditions;
4) A simple API to initialize the board in a standard setup, place pieces, query/display board state, and execute moves;
5) Test cases that
(a) initialize the board and place all pieces,
(b) demonstrate a lion moving to capture another piece, and
(c) simulate a full turn with several moves. Input: actions invoked via predefined APIs (no CLI/IO required). Data constraints: at most 16 pieces on the board.
Quick Answer: This question evaluates object-oriented design and software engineering skills, specifically class modeling, encapsulation, state management, and rule-based logic for a game simulation.
Implement a simplified Animal Chess (Dou Shou Qi) engine using object-oriented design. Write a function `solution(actions)` that processes a sequence of API-style actions and returns one result per action.
Board rules:
- The board is 9 x 7 and uses 0-based coordinates `(row, col)`.
- Player `A` starts at the top, player `B` at the bottom.
- Special cells:
- Rivers: rows 3, 4, 5 and columns 1, 2, 4, 5
- Dens: `A` den at `(0, 3)`, `B` den at `(8, 3)`
- Traps owned by `A`: `(0, 2)`, `(0, 4)`, `(1, 3)`
- Traps owned by `B`: `(8, 2)`, `(8, 4)`, `(7, 3)`
Pieces and ranks:
- Elephant = 8
- Lion = 7
- Tiger = 6
- Leopard = 5
- Wolf = 4
- Dog = 3
- Cat = 2
- Rat = 1
Movement rules:
- All pieces move one square orthogonally.
- Only the Rat may enter river cells.
- Lion and Tiger may also jump in a straight line across exactly one contiguous river section if no Rat is standing in any jumped river cell.
- A piece may not move into its own den.
Capture rules:
- You may capture only an enemy piece on the destination square.
- A piece cannot move onto a square occupied by its own side.
- If the defender is standing in a trap owned by the attacker, the capture is always allowed.
- Otherwise, the attacker's effective rank must be at least the defender's effective rank.
- A piece standing in an enemy trap has effective rank 0.
- Special exception: Rat can capture Elephant, but Elephant cannot capture Rat.
- This simplified version does not add extra land/water capture restrictions for Rat beyond adjacency.
Win conditions:
- Entering the opponent's den wins immediately.
- Capturing the opponent's last remaining piece also wins.
Supported actions:
- `('init',)` -> reset to the standard Animal Chess setup
- `('clear',)` -> clear the board
- `('place', owner, piece_name, row, col)` -> place one piece manually
- `('move', owner, r1, c1, r2, c2)` -> attempt a move for the current turn
- `('piece', row, col)` -> return the piece code at a square or `None`
- `('snapshot',)` -> return all pieces as `(row, col, code)` in row-major order
- `('display',)` -> return a 9 x 7 grid of piece codes or `'__'`
- `('turn',)` -> return the current player to move
- `('winner',)` -> return `'A'`, `'B'`, or `None`
Standard setup used by `init`:
- `A`: Lion `(0,0)`, Tiger `(0,6)`, Dog `(1,1)`, Cat `(1,5)`, Rat `(2,0)`, Leopard `(2,2)`, Wolf `(2,4)`, Elephant `(2,6)`
- `B`: Elephant `(6,0)`, Wolf `(6,2)`, Leopard `(6,4)`, Rat `(6,6)`, Cat `(7,1)`, Dog `(7,5)`, Tiger `(8,0)`, Lion `(8,6)`
Piece codes are `owner + letter`, where Leopard uses `P` to avoid colliding with Lion: `AE, AL, AT, AP, AW, AD, AC, AR` and similarly for player `B`.
Constraints
- Board size is fixed at 9 x 7.
- At most 16 pieces are on the board at any time.
- 0 <= len(actions) <= 1000.
- Each player has at most one of each piece type.
Examples
Input: [('clear',), ('place', 'A', 'Lion', 0, 0), ('place', 'A', 'Tiger', 0, 6), ('place', 'A', 'Dog', 1, 1), ('place', 'A', 'Cat', 1, 5), ('place', 'A', 'Rat', 2, 0), ('place', 'A', 'Leopard', 2, 2), ('place', 'A', 'Wolf', 2, 4), ('place', 'A', 'Elephant', 2, 6), ('place', 'B', 'Elephant', 6, 0), ('place', 'B', 'Wolf', 6, 2), ('place', 'B', 'Leopard', 6, 4), ('place', 'B', 'Rat', 6, 6), ('place', 'B', 'Cat', 7, 1), ('place', 'B', 'Dog', 7, 5), ('place', 'B', 'Tiger', 8, 0), ('place', 'B', 'Lion', 8, 6), ('snapshot',)]
Expected Output: [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, [(0, 0, 'AL'), (0, 6, 'AT'), (1, 1, 'AD'), (1, 5, 'AC'), (2, 0, 'AR'), (2, 2, 'AP'), (2, 4, 'AW'), (2, 6, 'AE'), (6, 0, 'BE'), (6, 2, 'BW'), (6, 4, 'BP'), (6, 6, 'BR'), (7, 1, 'BC'), (7, 5, 'BD'), (8, 0, 'BT'), (8, 6, 'BL')]]
Explanation: The board is cleared, all 16 standard pieces are manually placed, and `snapshot` returns the row-major board state.
Input: [('clear',), ('place', 'A', 'Lion', 3, 0), ('place', 'B', 'Dog', 3, 3), ('move', 'A', 3, 0, 3, 3), ('piece', 3, 3), ('winner',)]
Expected Output: [True, True, True, True, 'AL', 'A']
Explanation: The Lion jumps horizontally across the river from `(3,0)` to `(3,3)`, captures the Dog, and wins because `B` has no remaining pieces.
Input: [('init',), ('move', 'A', 2, 0, 3, 0), ('move', 'B', 6, 6, 5, 6), ('move', 'A', 1, 1, 2, 1), ('move', 'B', 7, 1, 6, 1), ('piece', 3, 0), ('piece', 5, 6), ('piece', 2, 1), ('piece', 6, 1), ('turn',), ('winner',)]
Expected Output: [True, True, True, True, True, 'AR', 'BR', 'AD', 'BC', 'A', None]
Explanation: Starting from the standard setup, four legal moves are played in turn order. The queried squares show the moved pieces, it is now `A`'s turn again, and there is no winner yet.
Input: [('clear',), ('move', 'A', 0, 0, 0, 1), ('winner',)]
Expected Output: [True, False, None]
Explanation: Edge case: after clearing the board, attempting to move from an empty square is invalid.
Solution
def solution(actions):
class Board:
ROWS = 9
COLS = 7
DENS = {(0, 3): 'A', (8, 3): 'B'}
TRAPS = {
(0, 2): 'A', (0, 4): 'A', (1, 3): 'A',
(8, 2): 'B', (8, 4): 'B', (7, 3): 'B'
}
RIVERS = {(r, c) for r in (3, 4, 5) for c in (1, 2, 4, 5)}
def __init__(self):
self.grid = [[None for _ in range(self.COLS)] for _ in range(self.ROWS)]
def in_bounds(self, r, c):
return 0 <= r < self.ROWS and 0 <= c < self.COLS
def get(self, r, c):
return self.grid[r][c]
def set(self, r, c, piece):
self.grid[r][c] = piece
def is_river(self, r, c):
return (r, c) in self.RIVERS
def is_den(self, r, c):
return (r, c) in self.DENS
def is_trap(self, r, c):
return (r, c) in self.TRAPS
def cell_owner(self, r, c):
if (r, c) in self.DENS:
return self.DENS[(r, c)]
if (r, c) in self.TRAPS:
return self.TRAPS[(r, c)]
return None
def effective_rank(self, piece):
if piece is None or piece.position is None:
return None
r, c = piece.position
if self.is_trap(r, c) and self.cell_owner(r, c) != piece.owner:
return 0
return piece.rank
def has_piece_of_owner(self, owner):
for r in range(self.ROWS):
for c in range(self.COLS):
p = self.grid[r][c]
if p is not None and p.owner == owner:
return True
return False
class Piece:
name = ''
short = '?'
rank = 0
def __init__(self, owner):
self.owner = owner
self.position = None
@property
def code(self):
return self.owner + self.short
def _one_step(self, r1, c1, r2, c2):
return abs(r1 - r2) + abs(c1 - c2) == 1
def can_move(self, board, r1, c1, r2, c2):
return self._one_step(r1, c1, r2, c2) and not board.is_river(r2, c2)
def can_capture(self, defender, board, from_pos, to_pos):
if defender is None or defender.owner == self.owner:
return False
tr, tc = to_pos
if board.is_trap(tr, tc) and board.cell_owner(tr, tc) == self.owner:
return True
return board.effective_rank(self) >= board.effective_rank(defender)
class Rat(Piece):
name = 'Rat'
short = 'R'
rank = 1
def can_move(self, board, r1, c1, r2, c2):
return self._one_step(r1, c1, r2, c2)
def can_capture(self, defender, board, from_pos, to_pos):
if defender is None or defender.owner == self.owner:
return False
tr, tc = to_pos
if board.is_trap(tr, tc) and board.cell_owner(tr, tc) == self.owner:
return True
if isinstance(defender, Elephant):
return board.effective_rank(self) > 0
return board.effective_rank(self) >= board.effective_rank(defender)
class Elephant(Piece):
name = 'Elephant'
short = 'E'
rank = 8
def can_capture(self, defender, board, from_pos, to_pos):
if defender is None or defender.owner == self.owner:
return False
tr, tc = to_pos
if board.is_trap(tr, tc) and board.cell_owner(tr, tc) == self.owner:
return True
if isinstance(defender, Rat):
return False
return board.effective_rank(self) >= board.effective_rank(defender)
class JumpPiece(Piece):
def can_move(self, board, r1, c1, r2, c2):
if self._one_step(r1, c1, r2, c2):
return not board.is_river(r2, c2)
if r1 != r2 and c1 != c2:
return False
dr = 0 if r1 == r2 else (1 if r2 > r1 else -1)
dc = 0 if c1 == c2 else (1 if c2 > c1 else -1)
cr, cc = r1 + dr, c1 + dc
jumped = []
while board.in_bounds(cr, cc) and board.is_river(cr, cc):
jumped.append((cr, cc))
blocker = board.get(cr, cc)
if blocker is not None and isinstance(blocker, Rat):
return False
cr += dr
cc += dc
if not jumped:
return False
if not board.in_bounds(cr, cc):
return False
return (cr, cc) == (r2, c2) and not board.is_river(r2, c2)
class Lion(JumpPiece):
name = 'Lion'
short = 'L'
rank = 7
class Tiger(JumpPiece):
name = 'Tiger'
short = 'T'
rank = 6
class Leopard(Piece):
name = 'Leopard'
short = 'P'
rank = 5
class Wolf(Piece):
name = 'Wolf'
short = 'W'
rank = 4
class Dog(Piece):
name = 'Dog'
short = 'D'
rank = 3
class Cat(Piece):
name = 'Cat'
short = 'C'
rank = 2
piece_types = {
'Elephant': Elephant,
'Lion': Lion,
'Tiger': Tiger,
'Leopard': Leopard,
'Wolf': Wolf,
'Dog': Dog,
'Cat': Cat,
'Rat': Rat,
}
class Game:
STANDARD_SETUP = [
('A', 'Lion', 0, 0), ('A', 'Tiger', 0, 6),
('A', 'Dog', 1, 1), ('A', 'Cat', 1, 5),
('A', 'Rat', 2, 0), ('A', 'Leopard', 2, 2),
('A', 'Wolf', 2, 4), ('A', 'Elephant', 2, 6),
('B', 'Elephant', 6, 0), ('B', 'Wolf', 6, 2),
('B', 'Leopard', 6, 4), ('B', 'Rat', 6, 6),
('B', 'Cat', 7, 1), ('B', 'Dog', 7, 5),
('B', 'Tiger', 8, 0), ('B', 'Lion', 8, 6)
]
def __init__(self):
self.clear()
def clear(self):
self.board = Board()
self.turn = 'A'
self.winner = None
self.used = set()
return True
def init(self):
self.clear()
for owner, name, r, c in self.STANDARD_SETUP:
self.place(owner, name, r, c)
self.turn = 'A'
self.winner = None
return True
def place(self, owner, name, r, c):
if owner not in ('A', 'B'):
return False
if name not in piece_types:
return False
if not self.board.in_bounds(r, c):
return False
if self.board.get(r, c) is not None:
return False
if self.board.is_den(r, c):
return False
if (owner, name) in self.used:
return False
piece = piece_types[name](owner)
if self.board.is_river(r, c) and not isinstance(piece, Rat):
return False
self.board.set(r, c, piece)
piece.position = (r, c)
self.used.add((owner, name))
return True
def piece_at(self, r, c):
if not self.board.in_bounds(r, c):
return None
piece = self.board.get(r, c)
return piece.code if piece is not None else None
def snapshot(self):
out = []
for r in range(self.board.ROWS):
for c in range(self.board.COLS):
piece = self.board.get(r, c)
if piece is not None:
out.append((r, c, piece.code))
return out
def display(self):
grid = []
for r in range(self.board.ROWS):
row = []
for c in range(self.board.COLS):
piece = self.board.get(r, c)
row.append(piece.code if piece is not None else '__')
grid.append(row)
return grid
def move(self, owner, r1, c1, r2, c2):
if self.winner is not None:
return False
if owner != self.turn:
return False
if not self.board.in_bounds(r1, c1) or not self.board.in_bounds(r2, c2):
return False
piece = self.board.get(r1, c1)
if piece is None or piece.owner != owner:
return False
if self.board.is_den(r2, c2) and self.board.cell_owner(r2, c2) == owner:
return False
dest = self.board.get(r2, c2)
if dest is not None and dest.owner == owner:
return False
if not piece.can_move(self.board, r1, c1, r2, c2):
return False
if dest is not None and not piece.can_capture(dest, self.board, (r1, c1), (r2, c2)):
return False
self.board.set(r1, c1, None)
if dest is not None:
dest.position = None
self.board.set(r2, c2, piece)
piece.position = (r2, c2)
opponent = 'B' if owner == 'A' else 'A'
if self.board.is_den(r2, c2) and self.board.cell_owner(r2, c2) == opponent:
self.winner = owner
elif not self.board.has_piece_of_owner(opponent):
self.winner = owner
else:
self.turn = opponent
return True
game = Game()
results = []
for action in actions:
if not action:
results.append(False)
continue
op = action[0]
if op == 'init':
results.append(game.init())
elif op == 'clear':
results.append(game.clear())
elif op == 'place':
_, owner, name, r, c = action
results.append(game.place(owner, name, r, c))
elif op == 'move':
_, owner, r1, c1, r2, c2 = action
results.append(game.move(owner, r1, c1, r2, c2))
elif op == 'piece':
_, r, c = action
results.append(game.piece_at(r, c))
elif op == 'snapshot':
results.append(game.snapshot())
elif op == 'display':
results.append(game.display())
elif op == 'turn':
results.append(game.turn)
elif op == 'winner':
results.append(game.winner)
else:
results.append(False)
return resultsTime complexity: O(k), where k is the number of actions. Each move check is O(1) on a fixed-size board, and `snapshot`/`display` scan at most 63 cells.. Space complexity: O(1), because the board size is fixed (9 x 7) and there are at most 16 pieces..
Hints
- Use a base Piece class for shared behavior, then override only the special cases: Rat, Elephant, Lion, and Tiger.
- Validate a move in phases: turn/bounds, terrain, movement pattern, capture rule, then win-condition update.