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)