Skip to content

E4-F3: Snake Algorithm Seat Assignment

Epic: E4: Ticket Purchase Flow

Size: M (Medium)

Problem / Outcome

System assigns best available adjacent seats when user adds to cart using the Snake algorithm.

Scope

In-Scope:

  • Snake algorithm implementation with per-sector configuration
  • Assign adjacent seats for order quantity
  • Reserve seats with TTL
  • Handle irregular stadium geometries
  • Reject the order when no contiguous block of N seats exists (groups are seated together or not at all — no scattering across gaps or rows)

Out-of-Scope:

  • User seat preference / manual seat selection

Algorithm Specification

The Snake algorithm assigns seats based on a "best row" principle with configurable traversal direction per sector.

Core Concepts

  1. Best Row: Each sector has a configured "best row" (typically closest to pitch). The algorithm starts from the best row and moves outward.

  2. Vertical Traversal Direction (per sector):

  3. TOP_TO_BOTTOM: Start at topmost row, move down

  4. BOTTOM_TO_TOP: Start at bottommost row, move up

  5. Within-Row Traversal: Alternating left-to-right, then right-to-left (snake pattern)

  6. Subsector Grouping: For irregular geometries (rows with different seat counts), subsectors are grouped for unified traversal

Allocation Logic

  1. Outer loop: Iterate rows in configured direction starting from "best row"
  2. Inner loop: Within each row, scan seats using snake pattern
  3. Adjacency requirement: For N seats, find a contiguous block of N available seats in a single row (adjacency = consecutive seat numbers)
  4. Rejection behavior: If no row has a contiguous block of N, the order is rejected — the group is never scattered across gaps or rows. (There may be ≥ N free seats in total, but if they are not N side-by-side, e.g. a sector left with only pairs cannot seat a group of 3.) A single seat (N=1) is trivially a block of 1, so it allocates whenever any seat is free.

Configuration per Sector

SectorSnakeConfig:
- sector_id (UUID)
- best_row_index (INTEGER)
- traversal_direction (ENUM: TOP_TO_BOTTOM, BOTTOM_TO_TOP)
- subsector_grouping (JSONB) - for irregular geometries

Acceptance Criteria

  • AC1: Given quantity N, when user adds to cart, then N adjacent seats assigned from best available
  • AC2: Snake fills rows using per-sector configured direction (top-down or bottom-up)
  • AC3: Within rows, snake alternates direction (L-to-R, then R-to-L)
  • AC4: When no contiguous block of N seats is available, the system rejects the order (no scattered/non-adjacent allocation)
  • AC5: Assigned seats reserved with 20-minute TTL from queue entry time
  • AC6: Irregular stadium geometries handled via subsector grouping

Data Model Impact

Seat table:
- status = RESERVED (during cart hold)

SectorSnakeConfig table:
- id (UUID, PK)
- sector_id (UUID, FK)
- stadium_template_id (UUID, FK)
- best_row_index (INTEGER)
- traversal_direction (ENUM: TOP_TO_BOTTOM, BOTTOM_TO_TOP)
- within_row_strategy (ENUM: LEFT_TO_RIGHT, RIGHT_TO_LEFT)
- subsector_grouping_json (JSONB, nullable)
- created_at (TIMESTAMP)

CartReservation (Redis):
- user_id (VARCHAR)
- match_id (VARCHAR)
- seats[] (Array of seat IDs)
- is_adjacent (BOOLEAN) - always true on a successful allocation (a group is only ever seated as one contiguous block; non-adjacent orders are rejected, not stored)
- expires_at (TIMESTAMP)
- created_at (TIMESTAMP)

Permissions/Roles

  • Authenticated user

How to Verify

npm test -- --grep "snake algorithm"

Expected: Adjacent seats assigned, reservation created with TTL.

Dependencies

Implementation Tasks

See E4: Ticket Purchase Tasks

Doc References

Last Updated: January 2026