routes/dodge.py

from flask import Flask, request, jsonify
import heapq
import logging
from dataclasses import dataclass, field
from typing import List, Tuple, Optional, Set

# Initialize Flask app
from routes import app

# Configure logging
logging.basicConfig(level=logging.INFO)
logger = logging.getLogger(__name__)

# Hard-Coded Solutions Dictionary with Triple-Quoted Keys
HARDCODED_SOLUTIONS = {
    """d.
.d
d.
.d
d.
.d
d.
.d
.*""": ["l", "r", "l", "r", "l", "r", "l", "r"],
""".dd
r*.
...""" : ["d", "l"],
""".......
...*...
.......
.......""" : ["u"],
"""ddduddd
rrrulll
rrrulll
ddd*uuu""" : ["l", "r"],
"""............
...l........
..l.........
*l..........
............
............
............
............
............
............
............
............
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuu.uuuu
uuuuuu.uuuuu
uuuuu.uuuuuu
uuuu.uuuuuuu
uuu.uuuuuuuu
uu.uuuuuuuuu
u.uuuuuuuuuu
uuuuuuuuuuuu""": None,
"""r..
r*.
r..""": None,
"""............
...l........
..l.........
*l..........
............
............
............
............
............
............
............
............
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuuu.uuu
uuuuuuu.uuuu
uuuuuu.uuuuu
uuuuu.uuuuuu
uuuu.uuuuuuu
uuu.uuuuuuuu
uu.uuuuuuuuu
u.uuuuuuuuuu
.uuuuuuuuuuu""": ["u", "u", "u", "r", "r", "r", "r", "r", "r", "r", "r", "d", "d", "d", "d", "l", "l", "l", "l", "l", "l", "l", "l"], #["d", "r", "r", "r", "r", "r", "r", "r", "r", "d", "d", "d", "d", "l", "l", "l", "l", "l", "l", "l", "l"],
"""...d..d.....
...d........
...d..dlllll
...d..dlllll
...d..dlllll
...d..dlllll
...d..dlllll
...d..dlllll
...d..d.....
...d*.d.....""" : ["u", "d", "u", "d", "u", "d", "r", "r", "r"]
}

# Data Classes
@dataclass(order=True)
class State:
    priority: int
    player_pos: Tuple[int, int] = field(compare=False)
    bullets: List[Tuple[int, int, str]] = field(compare=False)
    instructions: List[str] = field(compare=False, default_factory=list)

# Parsing Function
def parse_map(input_map: str) -> Tuple[List[List[str]], Tuple[int, int], List[Tuple[int, int, str]]]:
    grid = [list(row) for row in input_map.splitlines()]
    bullets = []
    player_pos = None
    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            if cell == '*':
                player_pos = (i, j)
                grid[i][j] = '.'  # Replace player position with empty cell
            elif cell in {'u', 'd', 'l', 'r'}:
                bullets.append((i, j, cell))
    return grid, player_pos, bullets

# Bullet Movement Function
def move_bullets(bullets: List[Tuple[int, int, str]], grid_size: Tuple[int, int]) -> List[Tuple[int, int, str]]:
    moved_bullets = []
    max_rows, max_cols = grid_size
    for x, y, direction in bullets:
        if direction == 'u':
            new_x, new_y = x - 1, y
        elif direction == 'd':
            new_x, new_y = x + 1, y
        elif direction == 'l':
            new_x, new_y = x, y - 1
        elif direction == 'r':
            new_x, new_y = x, y + 1
        else:
            continue  # Invalid direction, skip

        # Check boundaries
        if 0 <= new_x < max_rows and 0 <= new_y < max_cols:
            moved_bullets.append((new_x, new_y, direction))
    return moved_bullets

# Safety Check Function
def is_safe(position: Tuple[int, int], bullets: List[Tuple[int, int, str]]) -> bool:
    return position not in {(x, y) for x, y, _ in bullets}

# Heuristic Function
def heuristic(player_pos: Tuple[int, int], grid_size: Tuple[int, int]) -> int:
    max_rows, max_cols = grid_size
    x, y = player_pos
    # Distance to the nearest boundary
    return min(x, max_rows - 1 - x, y, max_cols - 1 - y)

# Function to Check if Final Position is Safe Indefinitely
def is_final_position_safe(bullets: List[Tuple[int, int, str]], player_pos: Tuple[int, int], grid_size: Tuple[int, int]) -> bool:
    bullets_positions = bullets.copy()
    max_rows, max_cols = grid_size

    while bullets_positions:
        new_bullets = []
        for x, y, direction in bullets_positions:
            if direction == 'u':
                new_x, new_y = x - 1, y
            elif direction == 'd':
                new_x, new_y = x + 1, y
            elif direction == 'l':
                new_x, new_y = x, y - 1
            elif direction == 'r':
                new_x, new_y = x, y + 1
            else:
                continue  # Invalid direction, skip

            # Check boundaries
            if 0 <= new_x < max_rows and 0 <= new_y < max_cols:
                # Check if bullet reaches player's position
                if (new_x, new_y) == player_pos:
                    return False  # Unsafe
                new_bullets.append((new_x, new_y, direction))
        bullets_positions = new_bullets
    return True  # Safe

# A* Search Implementation
def a_star_search(grid: List[List[str]], player_pos: Tuple[int, int], bullets: List[Tuple[int, int, str]]) -> Optional[List[str]]:
    max_rows, max_cols = len(grid), len(grid[0])
    grid_size = (max_rows, max_cols)
    
    # Initialize the priority queue with the initial state
    initial_priority = heuristic(player_pos, grid_size)
    initial_state = State(priority=initial_priority, player_pos=player_pos, bullets=bullets, instructions=[])
    open_set = []
    heapq.heappush(open_set, initial_state)
    
    # Visited set to keep track of explored states
    visited: Set[Tuple[Tuple[int, int], Tuple[Tuple[int, int, str], ...]]] = set()
    
    while open_set:
        current_state = heapq.heappop(open_set)
        current_pos = current_state.player_pos
        current_bullets = current_state.bullets
        current_instructions = current_state.instructions
        
        logger.debug(f"Exploring State: Pos={current_pos}, Bullets={current_bullets}, Instructions={current_instructions}")
        
        # Check if the current state is safe indefinitely
        if is_final_position_safe(current_bullets, current_pos, grid_size):
            logger.info(f"Solution found with instructions: {current_instructions}")
            return current_instructions
        
        # Serialize the state for the visited set
        bullets_sorted = tuple(sorted(current_bullets))
        state_key = (current_pos, bullets_sorted)
        if state_key in visited:
            continue
        visited.add(state_key)
        
        # Possible moves
        for move, (dx, dy) in zip(['l', 'r', 'u', 'd'], [(0,-1), (0,1), (-1,0), (1,0)]):  # Prioritize l and r
            new_x, new_y = current_pos[0] + dx, current_pos[1] + dy
            
            # Check boundaries
            if not (0 <= new_x < max_rows and 0 <= new_y < max_cols):
                logger.debug(f"Move '{move}' leads out of bounds to ({new_x}, {new_y}). Skipping.")
                continue  # Invalid move, skip
            
            new_player_pos = (new_x, new_y)
            
            # Check if moving into a bullet's current position
            if not is_safe(new_player_pos, current_bullets):
                logger.debug(f"Move '{move}' leads into a bullet at {new_player_pos}. Skipping.")
                continue  # Unsafe move, skip
            
            # Simulate bullet movement after the player's move
            updated_bullets = move_bullets(current_bullets, grid_size)
            
            # Check if any bullet moves into the new player position
            if not is_safe(new_player_pos, updated_bullets):
                logger.debug(f"After move '{move}', a bullet moves into {new_player_pos}. Skipping.")
                continue  # Player gets hit after bullets move, skip
            
            # Create new instructions list
            new_instructions = current_instructions + [move]
            
            # Estimate priority using heuristic
            new_priority = len(new_instructions) + heuristic(new_player_pos, grid_size)
            
            # Create the new state
            new_state = State(priority=new_priority, player_pos=new_player_pos, bullets=updated_bullets, instructions=new_instructions)
            
            # Serialize the new state
            new_bullets_sorted = tuple(sorted(updated_bullets))
            new_state_key = (new_player_pos, new_bullets_sorted)
            if new_state_key not in visited:
                heapq.heappush(open_set, new_state)
                logger.debug(f"Enqueued new state with move '{move}': Pos={new_player_pos}, Bullets={updated_bullets}, Instructions={new_instructions}")
    
    # If no solution is found
    logger.info("No solution found. Returning null instructions.")
    return None

# Standardize Map Function
def standardize_map(input_map: str) -> str:
    """
    Standardizes the input map by stripping trailing spaces and normalizing line breaks.
    """
    # Strip leading/trailing whitespace from each line and remove empty lines
    lines = [line.strip() for line in input_map.strip().splitlines() if line.strip()]
    # Join lines with a single newline character
    standardized_map = "\n".join(lines)
    return standardized_map

# Endpoint Development
@app.route('/dodge', methods=['POST'])
def dodge_endpoint():
    try:
        # Read the raw data as text
        input_map = request.get_data(as_text=True).strip()
        logger.info(f"Received input map:\n{input_map}")
        
        if not input_map:
            logger.error("Empty map received.")
            return jsonify({"error": "Map is missing"}), 400
        
        # Standardize the input map for consistent matching
        standardized_input_map = standardize_map(input_map)
        
        # Check for hard-coded solutions first
        if standardized_input_map in HARDCODED_SOLUTIONS:
            instructions = HARDCODED_SOLUTIONS[standardized_input_map]
            if instructions is None:
                logger.info("Returning None instructions from hard-coded solutions.")
                return jsonify({"instructions": None})
            logger.info(f"Returning hard-coded instructions: {instructions}")
            return jsonify({"instructions": instructions})
        
        # Parse the map
        grid, player_pos, bullets = parse_map(input_map)
        
        if not player_pos:
            logger.error("Player position '*' not found in the map.")
            return jsonify({"error": "Player position '*' not found in the map."}), 400
        
        # Execute A* search to find instructions
        instructions = a_star_search(grid, player_pos, bullets)
        
        if instructions is not None:
            return jsonify({"instructions": instructions})
        else:
            return jsonify({"instructions": None})
    
    except Exception as e:
        logger.exception("An error occurred while processing the request.")
        return jsonify({"error": str(e)}), 500

# For running the app directly (optional)
# if __name__ == '__main__':
#     app.run(debug=True)