Astar.java

import java.io.*;
import java.util.*;

public class Astar {

    // Constants
    public static final int SIZE = 13;
    public static final int X_MIN_BOUND = 0;
    public static final int X_MAX_BOUND = 12;
    public static final int Y_MIN_BOUND = 0;
    public static final int Y_MAX_BOUND = 12;

    // Enum for entities
    /**\
     * UNKNOWN - cell whit does not contain the info for the current state
     */
    public enum Type {
        PERCEPTION, ORK, URUK, NAZGUL, WATCHTOWER, RING, COAT, MOUNT, GOLLUM, OK, UNKNOWN
    }


    // Global Knowledge & State
    public static Type[][][] available = new Type[SIZE][SIZE][2]; // knowledge per ring-state
    public static boolean[][][] saveCell = new boolean[SIZE][SIZE][2]; // computed safe cells

    public static int x_pos = 0, y_pos = 0; // general position on the map
    public static int gollum_x = -1, gollum_y = -1; // coordinates of the gollum
    public static int mount_x = -1, mount_y = -1; // coordinates of the mount
    public static int target_x = -1, target_y = -1; // coordinates of the current target (depends on knowledge)
    public static boolean know_mount = false; // toggle for knowing the mount position to avoid extra scanning
    public static boolean ringOn = false; // toggle for having the ring put on
    public static boolean have_coat_flag = false; // toggle for having the coat

    // Move counts for final output
    public static int move_count = 0;
    public static int gollum_moves_count = 0;

    // Available moves
    public static final int[] dx = {-1, 0, 1, 0};
    public static final int[] dy = {0, 1, 0, -1};

    // General function for validation the particular point
    public static boolean inBounds(int x, int y) {
        return x >= X_MIN_BOUND && x <= X_MAX_BOUND && y >= Y_MIN_BOUND && y <= Y_MAX_BOUND;
    }

    // Initialization function, used to reset all non-valid data
    public static void resetKnowledge() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                available[i][j][0] = Type.UNKNOWN;
                available[i][j][1] = Type.UNKNOWN;
                saveCell[i][j][0] = true;
                saveCell[i][j][1] = true;
            }
        }
    }

    // Converter from the chat tu the enumerator
    public static Type charToType(char c) {
        switch (c) {
            case 'P': return Type.PERCEPTION;
            case 'O': return Type.ORK;
            case 'U': return Type.URUK;
            case 'N': return Type.NAZGUL;
            case 'W': return Type.WATCHTOWER;
            case 'R': return Type.RING;
            case 'C': return Type.COAT;
            case 'M': return Type.MOUNT;
            case 'G': return Type.GOLLUM;
            default: return Type.UNKNOWN;
        }
    }

    // Safety Computation
    // For Ork and Uruk-Khai
    /**
     * @param ex - current position of the enemy x
     * @param ey - current position of the enemy y
     * @param r - radius of the danger zone
     * @param ringState - the flag for the map (perception cells are ring dependent)
     */
    public static void markVonNeumann(int ex, int ey, int r, boolean ringState) {
        int ringIdx = ringState ? 1 : 0;
        for (int i = Math.max(X_MIN_BOUND, ex - r); i <= Math.min(X_MAX_BOUND, ex + r); ++i) {
            for (int j = Math.max(Y_MIN_BOUND, ey - r); j <= Math.min(Y_MAX_BOUND, ey + r); ++j) {
                if (Math.abs(ex - i) + Math.abs(ey - j) <= r) {
                    saveCell[i][j][ringIdx] = false;
                }
            }
        }
        // The enemy exact cell
        if (inBounds(ex, ey)) {
            saveCell[ex][ey][0] = false;
            saveCell[ex][ey][1] = false;
        }
    }
    // For Nazgul and Watchtower
    /**
     * @param ex - current position of the enemy x
     * @param ey - current position of the enemy y
     * @param r - radius of the danger zone
     * @param ears - flag for the ears
     * @param ringState - the flag for the map (perception cells are ring dependent)
     */
    public static void markMoore(int ex, int ey, int r, boolean ears, boolean ringState) {
        int ringIdx = ringState ? 1 : 0;
        for (int i = Math.max(X_MIN_BOUND, ex - r); i <= Math.min(X_MAX_BOUND, ex + r); ++i) {
            for (int j = Math.max(Y_MIN_BOUND, ey - r); j <= Math.min(Y_MAX_BOUND, ey + r); ++j) {
                saveCell[i][j][ringIdx] = false;
            }
        }
        // Calculation of the ears position
        if (ears) {
            int c1x = ex - r - 1, c1y = ey - r - 1;
            int c2x = ex - r - 1, c2y = ey + r + 1;
            int c3x = ex + r + 1, c3y = ey - r - 1;
            int c4x = ex + r + 1, c4y = ey + r + 1;

            if (inBounds(c1x, c1y)) saveCell[c1x][c1y][ringIdx] = false;
            if (inBounds(c2x, c2y)) saveCell[c2x][c2y][ringIdx] = false;
            if (inBounds(c3x, c3y)) saveCell[c3x][c3y][ringIdx] = false;
            if (inBounds(c4x, c4y)) saveCell[c4x][c4y][ringIdx] = false;
        }
        // The enemy exact cell
        if (inBounds(ex, ey)) {
            saveCell[ex][ey][0] = false;
            saveCell[ex][ey][1] = false;
        }
    }

    // General function of recomputing the saveCell map
    public static void recomputeSafe() {
        for (int ring_state = 0; ring_state <= 1; ring_state++) {
            boolean ringStateBool = (ring_state == 1);

            // Initialize all cells as safe for this ring state
            for (int i = 0; i < SIZE; i++) {
                for (int j = 0; j < SIZE; j++) {
                    saveCell[i][j][ring_state] = true;
                }
            }

            // Mark unsafe cells based on knowledge about enemies and perceptions
            for (int i = 0; i < SIZE; i++) {
                for (int j = 0; j < SIZE; j++) {
                    Type t = available[i][j][0]; // Enemy type is ring-independent
                    Type t_for_perception = available[i][j][ring_state]; // For perception is special case
                    // marking base on the task condition
                    if (t == Type.ORK) {
                        if (ringStateBool || have_coat_flag) markVonNeumann(i, j, 0, ringStateBool);
                        else markVonNeumann(i, j, 1, ringStateBool);
                    } else if (t == Type.URUK) {
                        if (ringStateBool || have_coat_flag) markVonNeumann(i, j, 1, ringStateBool);
                        else markVonNeumann(i, j, 2, ringStateBool);
                    } else if (t == Type.NAZGUL) {
                        if (ringStateBool) markMoore(i, j, 2, true, ringStateBool);
                        else if ((!ringStateBool) && have_coat_flag) markMoore(i, j, 1, false, ringStateBool);
                        else markMoore(i, j, 1, true, ringStateBool);
                    } else if (t == Type.WATCHTOWER) {
                        if (ringStateBool) markMoore(i, j, 2, true, ringStateBool);
                        else markMoore(i, j, 2, false, ringStateBool);
                    }

                    if (t_for_perception == Type.PERCEPTION) {
                        saveCell[i][j][ring_state] = false;
                    }
                }
            }
        }
    }

    // A* algorithm realization

    // Node for A* search. Represents a state in the search space.
    // A state is defined by its coordinates and ring state.

    static class Node implements Comparable<Node> {
        int x, y;
        boolean ringOn;
        int g; // cost from start to this node (real distance)
        int h; // heuristic (estimated cost from here to target, Manhatten distance)
        int f; // f = g + h (the general distance function)
        Node parent; // parent node for recreating the path
        String action; // The action taken to reach this node: "m", "r", "rr"
        int moveX, moveY; // Coordinates for "m" action

        public Node(int x, int y, boolean ringOn, int g, int h, Node parent, String action, int moveX, int moveY) {
            this.x = x;
            this.y = y;
            this.ringOn = ringOn;
            this.g = g;
            this.h = h;
            this.f = g + h;
            this.parent = parent;
            this.action = action;
            this.moveX = moveX;
            this.moveY = moveY;
        }

        // Comparing for the Priority queue (node with the lowest f will be the first)
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.f, other.f);
        }
    }

    /**
     * Executes the A* algorithm to find the shortest safe path to the current target.
     * @return A string command for the first step on the optimal path ("m x y", "r", "rr"), or "e -1" if no path exists.
     */
    public static String aStar() {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        boolean[][][] visited = new boolean[SIZE][SIZE][2]; // visited[x][y][ringOn ? 1 : 0]

        // We try to reach the target from the current cell by looking at the all possible ways. Only taking in to the account the current constraints

        // Create the starting node from the current global state
        int h_start = Math.abs(x_pos - target_x) + Math.abs(y_pos - target_y);
        Node startNode = new Node(x_pos, y_pos, ringOn, 0, h_start, null, "", -1, -1);
        openList.add(startNode);

        while (!openList.isEmpty()) {
            // Get the node with the lowest 'f' score from the priority queue
            Node currentNode = openList.poll();
            int currentRingIdx = currentNode.ringOn ? 1 : 0;
            // If this state has been visited via a better or equal path, skip it
            if (visited[currentNode.x][currentNode.y][currentRingIdx]) {
                continue;
            }
            visited[currentNode.x][currentNode.y][currentRingIdx] = true;

            // Goal Check: If we've reached the target
            if (currentNode.x == target_x && currentNode.y == target_y) {
                // Path found! Backtrack to find the first move from the start state.
                Node stepNode = currentNode;
                if (stepNode.parent == null) {
                    return "e -1";
                }
                while (stepNode.parent != null && stepNode.parent.parent != null) {
                    stepNode = stepNode.parent;
                }

                // Return the command for the first step
                if (stepNode.action.equals("m")) {
                    return "m " + stepNode.moveX + " " + stepNode.moveY;
                } else {
                    return stepNode.action; // "r" or "rr"
                }
            }

            // Generate Successors (neighboring states)

            // Move Actions ((-1, 0), (0, -1), (1, 0), (0, 1))
            for (int i = 0; i < 4; i++) {
                int newX = currentNode.x + dx[i];
                int newY = currentNode.y + dy[i];
                boolean newRingState = currentNode.ringOn;
                int newRingIdx = newRingState ? 1 : 0;

                // Check if the move is valid (in bounds, safe, and not visited)
                if (inBounds(newX, newY) && !visited[newX][newY][newRingIdx] && saveCell[newX][newY][newRingIdx]) {
                    int newG = currentNode.g + 1; //the cost of the movement
                    int newH = Math.abs(newX - target_x) + Math.abs(newY - target_y);
                    Node neighborNode = new Node(newX, newY, newRingState, newG, newH, currentNode, "m", newX, newY);
                    openList.add(neighborNode);
                }
            }

            // Toggle Ring Action
            boolean newRingState = !currentNode.ringOn;
            int newRingIdx = newRingState ? 1 : 0;

            // supersafe cell - it cel cell with the safe neighbours (only in such cells we can be sure that we can toggle)
            boolean is_super_safe = true;
            for(int cellx = currentNode.x - 1; cellx  <= currentNode.x + 1; cellx++){
                for(int celly = currentNode.y -1; celly <= currentNode.y + 1; celly++){
                    if(inBounds(cellx, celly)){
                        if(!saveCell[cellx][celly][0] || !saveCell[cellx][celly][1]){
                            is_super_safe = false;
                            break;
                        }
                    }
                }
            }

            // Check if toggling the ring is a valid action (safe in the new state and not visited)
            if (saveCell[currentNode.x][currentNode.y][newRingIdx]
                    && !visited[currentNode.x][currentNode.y][newRingIdx]
                    && is_super_safe) {
                int newG = currentNode.g + 1; // the cost of the movement
                int newH = currentNode.h;
                String action = newRingState ? "r" : "rr";
                Node neighborNode = new Node(currentNode.x, currentNode.y, newRingState, newG, newH, currentNode, action, -1, -1);
                openList.add(neighborNode);
            }

        }

        // No path found
        return "e -1";
    }


    // Main function
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int variant; // 1 or 2
        int zone; // 8 or 25 (in max depends on the variant)
        //resetting the maps
        resetKnowledge();
        // Validation of the initial input
        try{
            variant = Integer.parseInt(sc.nextLine());
            if (variant != 1 && variant != 2) {
                System.out.println("e -1");
                return;
            }
            String[] gollumCoords = sc.nextLine().split(" ");
            gollum_x = Integer.parseInt(gollumCoords[0]);
            gollum_y = Integer.parseInt(gollumCoords[1]);
        }
        catch (Exception e){
            System.out.println("e -1");
            return;
        }

        if(variant == 1) zone = 8;
        else zone = 25;

        if (!inBounds(gollum_x, gollum_y)) {
            System.out.println("e -1");
            return;
        }
        target_x = gollum_x;
        target_y = gollum_y;
        //initializing the 0 0 position
        x_pos = 0; y_pos = 0;
        available[x_pos][y_pos][0] = Type.OK;
        available[x_pos][y_pos][1] = Type.OK;

        // Main interactive loop
        while (true) {
            boolean new_data = false; //the flag for updating the data. Preventing the extra updating


            int danger_cells;
            // checking invalid variant of the perceived cells
            try{
                danger_cells = Integer.parseInt(sc.nextLine());
            } catch (Exception e){
                System.out.println("e -1");
                return;
            }

            if(danger_cells < 0 || danger_cells > zone){
                System.out.println("e -1");
                return;
            }

            int perceptionRadius = (variant == 1) ? 1 : 2;
            int currentRingIdx = ringOn ? 1 : 0;

            // read perceptions
            for (int i = 0; i < danger_cells; i++) {
                String[] perception = sc.nextLine().split(" ");
                int x = Integer.parseInt(perception[0]);
                int y = Integer.parseInt(perception[1]);
                char tc = perception[2].charAt(0);
                Type t = charToType(tc);

                if (t == Type.COAT && x == x_pos && y == y_pos) {
                    if (!have_coat_flag) {
                        have_coat_flag = true;
                        new_data = true;
                    }
                }
                if (t == Type.GOLLUM) {
                    if(!inBounds(x, y)){
                        System.out.println("e -1");
                        return;
                    }
                    gollum_x = x;
                    gollum_y = y;
                }
                if(inBounds(x, y)){
                    if(t == Type.PERCEPTION){
                        Type staticType = available[x][y][0];
                        boolean isKnownEnemyLocation = (staticType == Type.ORK || staticType == Type.URUK ||
                                staticType == Type.NAZGUL || staticType == Type.WATCHTOWER);
                        if (!isKnownEnemyLocation) {
                            // 'P' is state-dependent. Only update the knowledge for the CURRENT ring state.
                            if (available[x][y][currentRingIdx] != t) {
                                available[x][y][currentRingIdx] = t;
                                new_data = true;
                            }
                        }
                    } else {
                        // An actual enemy/item exists. This knowledge is static and applies to both states.
                        if(available[x][y][0] != t)
                            available[x][y][0] = t; new_data = true;
                        if(available[x][y][1] != t)
                            available[x][y][1] = t; new_data = true;
                    }
                }

            }

            // Check for Gollum message
            if (x_pos == gollum_x && y_pos == gollum_y && !know_mount) {
                //checking invalid input
                try {
                    while (sc.hasNext() && !sc.hasNextInt()) {
                        sc.next();
                    }
                    mount_x = sc.nextInt();
                    while (sc.hasNext() && !sc.hasNextInt()) {
                        sc.next();
                    }
                    mount_y = sc.nextInt();
                    if (sc.hasNextLine()) {
                        sc.nextLine();
                    }
                } catch (Exception e){
                    System.out.println("e -1");
                    return;
                }
                //checking invalid coordinates
                if (!inBounds(mount_x, mount_y)) {
                    System.out.println("e -1");
                }

                know_mount = true;
                target_x = mount_x;
                target_y = mount_y;

                gollum_moves_count = move_count;
                move_count = 0;

                new_data = true;

                if (inBounds(mount_x, mount_y)) {
                    available[mount_x][mount_y][0] = Type.MOUNT;
                    available[mount_x][mount_y][1] = Type.MOUNT;
                }
            }

            //updating all unknown but perceived cells
            for (int px = x_pos - perceptionRadius; px <= x_pos + perceptionRadius; px++) {
                for (int py = y_pos - perceptionRadius; py <= y_pos + perceptionRadius; py++) {
                    // Skip the agent's own cell and out-of-bounds cells
                    if ((px == x_pos && py == y_pos) || !inBounds(px, py)) {
                        continue;
                    }
                    if (available[px][py][currentRingIdx] == Type.UNKNOWN) {
                        available[px][py][currentRingIdx] = Type.OK; // Mark as known safe space
                        new_data = true; // This is new information, a re-plan might be needed
                    }
                }
            }

            if(available[x_pos][y_pos][currentRingIdx] == Type.UNKNOWN){
                available[x_pos][y_pos][currentRingIdx] = Type.OK;
            }

            // 3. Check for win condition
            if (know_mount && x_pos == mount_x && y_pos == mount_y) {
                System.out.println("e " + (gollum_moves_count + move_count));
                return;
            }

            // 4. Recompute safety if we have new info
            if (new_data || (move_count == 0 && gollum_moves_count == 0)) {
                recomputeSafe();
            }

            // 5. Decide and execute next move using A*
            String cmd = aStar();
            System.out.println(cmd);

            // 6. Check for exit condition (A* found no path)
            if (cmd.equals("e -1")) {
                return;
            }

            // 7. IMPORTANT: Update internal state based on the command we just sent
            if (cmd.startsWith("m ")) {
                String[] parts = cmd.split(" ");
                x_pos = Integer.parseInt(parts[1]);
                y_pos = Integer.parseInt(parts[2]);
                move_count++;
            } else if (cmd.startsWith("r")) {
                if(ringOn == true){
                    System.out.println("e -1");
                    return;
                }
                ringOn = true;
            } else if (cmd.startsWith("rr")) {
                if(ringOn == false){
                    System.out.println("e -1");
                    return;
                }
                ringOn = false;
            }
        }
    }
}