Quick Overview

This question evaluates object-oriented design and software engineering skills, specifically class modeling, encapsulation, state management, and rule-based logic for a game simulation.

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.

Hints

  1. Use a base Piece class for shared behavior, then override only the special cases: Rat, Elephant, Lion, and Tiger.
  2. Validate a move in phases: turn/bounds, terrain, movement pattern, capture rule, then win-condition update.

Loading coding console...