Preskoči na sadržaj

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
  • Fallback to single-seat allocation when adjacency impossible

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 contiguous block of N available seats
  4. Fallback behavior: If no contiguous block exists, allocate single seats one at a time (user may receive non-adjacent seats)

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 available, system allocates single seats with warning
  • 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: CENTER_OUTWARD, LEFT_TO_RIGHT)
- subsector_grouping_json (JSONB, nullable)
- created_at (TIMESTAMP)

CartReservation (Redis):
- user_id (VARCHAR)
- match_id (VARCHAR)
- seats[] (Array of seat IDs)
- is_adjacent (BOOLEAN) - false if fallback to single seats
- 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