Backtracking.java

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

public class Backtracking {

    // 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
    }
    // Node for the backtracking algorithm. Represents the state in the path space
    // A state is defined by coordinates and the ring state
    static class Node{
        int x, y;
        boolean ringOn;

        public Node(int x, int y, boolean ringOn){
            this.x = x;
            this.y = y;
            this.ringOn = ringOn;
        }
    }
    // array list for the containing the path and then backtracking
    public static ArrayList<Node> dfs_backtrack = new ArrayList<Node>();


    // 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 boolean[][][] visited = new boolean[SIZE][SIZE][2]; // global visited array for the backtracking

    public static int x_pos = 0, y_pos = 0;
    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
    public static boolean ring_toggle = false; // toggle for avoiding the ring toggle loop

    // 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
    // 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];
                    // 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;
                    }
                }
            }
        }
    }

    // Backtracking algorithm implementation
    /**
     * @param n - the current node
     * @return - the best fit neighbour (based on heuristic for optimization)
     */
    public static Node chooseNeighbour(Node n){
        int best_heuristic = 10000;
        Node bestCandidate = new Node(-1, -1, ringOn);
        // Move Actions ((-1, 0), (0, -1), (1, 0), (0, 1))
        for(int i = 0; i < 4; i++){
            int newX = n.x + dx[i];
            int newY = n.y + dy[i];
            boolean newRingState = n.ringOn;
            int newRingIdx = newRingState ? 1 : 0;
            //validating
            if(inBounds(newX, newY) && !visited[newX][newY][newRingIdx] && saveCell[newX][newY][newRingIdx]){
                int newH = Math.abs(newX - target_x) + Math.abs(newY -  target_y);
                Node neighbour = new Node(newX, newY, ringOn);
                //choosing the best fit
                if(newH < best_heuristic){
                    best_heuristic = newH;
                    bestCandidate = neighbour;
                }
            }
        }
        return bestCandidate;
    }

    public static String backTraking() {
        int curRingIdx = ringOn ? 1 : 0;
        //marking visited
        visited[x_pos][y_pos][curRingIdx] = true;
        // if the current cell in the path
        if(dfs_backtrack.isEmpty()
                || !(dfs_backtrack.get(dfs_backtrack.size() - 1).x == x_pos
                && dfs_backtrack.get(dfs_backtrack.size() - 1).y == y_pos && dfs_backtrack.get(dfs_backtrack.size() - 1).ringOn == ringOn)){
            dfs_backtrack.add(new Node(x_pos, y_pos, ringOn));
        }
        //choosing the best fit neighbour
        Node new_neighbour = chooseNeighbour(new Node(x_pos, y_pos, ringOn));
        if(new_neighbour.x != -1){
            //if we can move
            ring_toggle = false;
            move_count ++;
            return "m " + new_neighbour.x + " " + new_neighbour.y;
        } else{ // if we cannot move - backtrack
            // 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 = x_pos - 1; cellx  <= x_pos + 1; cellx++){
                for(int celly = y_pos -1; celly <= y_pos + 1; celly++){
                    if(inBounds(cellx, celly)){
                        if(!saveCell[cellx][celly][0] || !saveCell[cellx][celly][1]){
                            is_super_safe = false;
                            break;
                        }
                    }
                }
            }
            // try to toggle
            int newRingIdx = ringOn ? 1 : 0;
            if(!ring_toggle && is_super_safe && !visited[x_pos][y_pos][newRingIdx]
                    && saveCell[x_pos][y_pos][newRingIdx]){
                ring_toggle = true; // to avoid the toggling loop
                boolean newRing = !ringOn;
                return newRing ? "r" : "rr";
            } else{
                // backtracking
                ring_toggle = false; // we moved, so we make toggle false
                if(dfs_backtrack.size() <= 1){
                    return "e -1"; //if we cannot more go back
                } else {
                    dfs_backtrack.remove(dfs_backtrack.size() - 1);
                    Node previous = dfs_backtrack.get(dfs_backtrack.size() - 1);;
                    if(ringOn != previous.ringOn){
                        // if the parent was with different ring state
                        boolean newRing  = previous.ringOn;
                        ring_toggle = true; // to avoid the toggling loop
                        return newRing ? "r" : "rr";
                    } else {
                        // else just move
                        move_count --;
                        return "m " + previous.x + " " + previous.y;
                    }
                }
            }
        }
    }


    // 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;

        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;
                for(int i = 0; i < SIZE; i++){
                    for (int j = 0; j < SIZE; j++){
                        visited[i][j][0] = false;
                        visited[i][j][1] = false;
                    }
                }

                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;
            }

            // 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;
            }

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

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

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

            // 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]);
            } else if (cmd.startsWith("r")) {
                ringOn = true;
            } else if (cmd.startsWith("rr")) {
                ringOn = false;
            }
        }
    }
}