import random
import os
import subprocess

random.seed(42) # For reproducible random testcases

test_cases = []

# 1. Corner Case: Minimal 1x2 grid
test_cases.append((1, 2, [
    "0",
    "1"
]))

# 2. Corner Case: Minimal 2x1 grid
test_cases.append((2, 1, [
    "01"
]))

# 3. Corner Case: Unsolvable grid (start '0' blocked)
test_cases.append((3, 3, [
    "xxx",
    "x0x",
    "x1x"
]))

# 4. Mistake Breaker 1: Simple BFS / Step-by-step breaker (Thick wall leap)
# A wall of thickness 3 separates 0 and 1.
# Simple BFS (moving 1 step) cannot jump this wall.
test_cases.append((10, 3, [
    "xxxxxxxxxx",
    "x0xxx1xxxx",
    "xxxxxxxxxx"
]))

# 5. Mistake Breaker 2: Checkpoint ordering breaker
# '2' is right next to '0' but '1' is far away.
test_cases.append((10, 3, [
    "xxxxxxxxxx",
    "x02xxxx1xx",
    "xxxxxxxxxx"
]))

# 6. Mistake Breaker 3: Velocity bounds breaker (requires velocity >= 5 to leap over 4-cell thick wall)
test_cases.append((15, 7, [
    "xxxxxxxxxxxxxxx",
    "x0xxxxx1xxxxxxx",
    "x             x",
    "x             x",
    "x             x",
    "x             x",
    "xxxxxxxxxxxxxxx"
]))

# 7. Corner Case: Checkpoint '1' is completely surrounded by walls but solvable via a leap
# Start at '0', build up horizontal speed, leap over the 3x3 wall block surrounding '1', land exactly on '1'.
test_cases.append((12, 5, [
    "xxxxxxxxxxxx",
    "x          x",
    "x0   xxx  1x",
    "x    x2x   x",
    "xxxxxxxxxxxx"
]))

# 8. Corner Case: Even and Odd checkpoints segregated by a wall
# '0', '2', '4' are on the left. '1', '3', '5' are on the right.
# The rider must leap back and forth over the vertical wall.
test_cases.append((15, 7, [
    "xxxxxxxXxxxxxxx",
    "x0     X     1x",
    "x      X      x",
    "x2     X     3x",
    "x      X      x",
    "x4     X     5x",
    "xxxxxxxXxxxxxxx"
]))

# 9. Corner Case: Overshooting Trap (requires careful deceleration)
# Width 20. Start '0' at index 1, '1' at index 18.
# "x0                 1x"
# Index 0: 'x', 1: '0', 2-17 (16 spaces): ' ', 18: '1', 19: 'x'.
test_cases.append((20, 3, [
    "xxxxxxxxxxxxxxxxxxxx",
    "x0                1x",
    "xxxxxxxxxxxxxxxxxxxx"
]))

# 10. Corner Case: Velocity 6 Required Sprint
# Requires building up exactly horizontal speed 6 to jump over 5-cell thick wall from 16 to 22,
# then decelerating safely on the other side to stop exactly at checkpoint 1.
test_cases.append((40, 3, [
    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx",
    "x0               xxxxx                1x",
    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
]))

# 11. Corner Case: Velocity 7 Required Sprint (to break mistake_v6)
# Requires building up exactly horizontal speed 7 to jump over 6-cell thick wall from 22 to 29,
# landing exactly on checkpoint 1 at index 29.
# Index 0: 'x', 1: '0', 2-22 (21 spaces): ' ', 23-28 (6 characters): 'xxxxxx', 29: '1', 30-38 (9 spaces): ' ', 39: 'x'.
test_cases.append((40, 3, [
    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx",
    "x0                     xxxxxx1         x",
    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
]))

# 12. Corner Case: Velocity 8 Required Sprint (to break mistake_v7)
# Requires building up horizontal speed 7 to jump first 6-cell wall from 22 to 29,
# then accelerating to speed 8 to jump second 7-cell wall from 29 to 37, landing exactly on checkpoint 1 at index 37.
# Index 0: 'x', 1: '0', 2-22 (21 spaces): ' ', 23-28 (6 characters): 'xxxxxx', 29: ' ', 30-36 (7 characters): 'xxxxxxx', 37: '1', 38: ' ', 39: 'x'.
test_cases.append((40, 3, [
    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx",
    "x0                     xxxxxx xxxxxxx1 x",
    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
]))

# 13. Corner Case: Constant Velocity Required Tunnel (to break mistake_no_maintain)
# Requires maintaining a horizontal velocity of exactly 2 for multiple steps to pass through the gaps.
test_cases.append((14, 3, [
    "xxxxxxxxxxxxxx",
    "x0 x x x x x1x",
    "xxxxxxxxxxxxxx"
]))

# 14. Max Test Case: 40x40 empty grid with 10 checkpoints spread in a spiral
grid_40_empty = [[" " for _ in range(40)] for _ in range(40)]
# Place walls as outer boundary
for r in range(40):
    grid_40_empty[r][0] = "x"
    grid_40_empty[r][39] = "x"
for c in range(40):
    grid_40_empty[0][c] = "x"
    grid_40_empty[39][c] = "x"

# Place 10 checkpoints
chks = [
    (1, 1), (1, 38), (38, 38), (38, 1), 
    (5, 5), (5, 33), (33, 33), (33, 5),
    (10, 10), (10, 28)
]
for i, (r, c) in enumerate(chks):
    grid_40_empty[r][c] = str(i)

test_cases.append((40, 40, ["".join(row) for row in grid_40_empty]))

# 15. Max Test Case: 40x40 grid with horizontal maze barriers
grid_40_maze = [[" " for _ in range(40)] for _ in range(40)]
# Boundaries
for r in range(40):
    grid_40_maze[r][0] = "x"
    grid_40_maze[r][39] = "x"
for c in range(40):
    grid_40_maze[0][c] = "x"
    grid_40_maze[39][c] = "x"

# Place horizontal stripes with gaps to force serpentine path
for r in range(5, 35, 5):
    gap = 2 + (r % 10) * 3
    for c in range(1, 39):
        if c < gap or c > gap + 3:
            grid_40_maze[r][c] = "x"

# Place checkpoints along the serpentine path
grid_40_maze[2][2] = "0"
grid_40_maze[7][35] = "1"
grid_40_maze[12][2] = "2"
grid_40_maze[17][35] = "3"
grid_40_maze[22][2] = "4"
grid_40_maze[27][35] = "5"
grid_40_maze[32][2] = "6"
grid_40_maze[37][35] = "7"

test_cases.append((40, 40, ["".join(row) for row in grid_40_maze]))

# 16. Several Random Max Test Cases (40x40, 3 solvable, 2 unsolvable)
for r_idx in range(5):
    grid = [[" " for _ in range(40)] for _ in range(40)]
    for r in range(40):
        grid[r][0] = "X"
        grid[r][39] = "X"
    for c in range(40):
        grid[0][c] = "X"
        grid[39][c] = "X"
    
    # Random block walls
    for _ in range(150):
        rr = random.randint(1, 38)
        rc = random.randint(1, 38)
        grid[rr][rc] = "x"
        
    solvable = r_idx < 3
    # If solvable, let's carve a path to ensure it has a solution
    # Place checkpoints in empty locations
    placed = 0
    attempts = 0
    while placed < 8 and attempts < 1000:
        rr = random.randint(2, 37)
        rc = random.randint(2, 37)
        if grid[rr][rc] == " " or grid[rr][rc] == "x":
            grid[rr][rc] = str(placed)
            placed += 1
        attempts += 1
    
    if placed < 8:
        # Fallback if random placement failed
        for k in range(placed, 8):
            grid[k+2][k+2] = str(k)
            
    # For solvable cases, clear neighborhood around checkpoints to guarantee path
    if solvable:
        for r in range(40):
            for c in range(40):
                if grid[r][c].isdigit():
                    # clear adjacent blocks
                    for dr in [-1, 0, 1]:
                        for dc in [-1, 0, 1]:
                            nr, nc = r+dr, c+dc
                            if 0 < nr < 39 and 0 < nc < 39:
                                if not grid[nr][nc].isdigit():
                                    grid[nr][nc] = " "
                                    
    # If unsolvable, completely block off checkpoint '0'
    else:
        for r in range(40):
            for c in range(40):
                if grid[r][c] == "0":
                    for dr in [-1, 0, 1]:
                        for dc in [-1, 0, 1]:
                            nr, nc = r+dr, c+dc
                            if 0 <= nr < 40 and 0 <= nc < 40:
                                if not grid[nr][nc].isdigit():
                                    grid[nr][nc] = "x"

    test_cases.append((40, 40, ["".join(row) for row in grid]))

# Write all testcases to roadrally_ai.in
input_path = "/home/kevin/.gemini/tmp/grid-scrimmage/roadrally_ai.in"
with open(input_path, "w") as f:
    for w, h, rows in test_cases:
        f.write(f"{w} {h}\n")
        for row in rows:
            f.write(row + "\n")
    f.write("0 0\n")

print(f"Generated {len(test_cases)} test cases in {input_path}")