Square Up

Implementing a two-player grid game with infinite columns and win detection

This hard coding problem asks you to build the core engine of a gravity-based board game in Python. It combines game-state management, efficient spatial indexing, and win-condition detection into a single class. The twist is that the board is unbounded horizontally, so your data structure cannot assume a fixed grid.

The main challenge is implementing the drop method to handle piece placement, gravity, and win detection correctly. After each move, you must check whether the newly placed piece (or pieces near it) complete a 2×2 square. A robust solution uses a sparse representation of the board and checks only the O(1) neighborhood around each new placement, avoiding the cost of scanning the entire grid after every move. Handling negative and positive column indices, managing stack heights dynamically, and returning the exact string required all matter for correctness.

• Sparse data structures for unbounded grids
• Efficient localized win detection
• Edge cases: first move, early game, column management
• String formatting and exact output matching