import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class Main {
    private static Random random = new Random(); // No seed for varied results

    // Q1: Check if distance matrix is valid (square, symmetric, non-negative, zero diagonal)
    public static int isValidMatrix(double[][] matrix) {
        if (matrix == null) return -1;

        int n = matrix.length;
        // Check if matrix is square and rows are not null
        for (int i = 0; i < n; i++) {
            if (matrix[i] == null || matrix[i].length != n) return -1;
        }

        // Check diagonal zeros, non-negative, and symmetry
        for (int i = 0; i < n; i++) {
            if (matrix[i][i] != 0) return -1; // Diagonal must be 0
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] < 0) return -1; // Non-negative distances
                if (matrix[i][j] != matrix[j][i]) return -1; // Symmetry
            }
        }
        return 1; // Valid matrix
    }

    // Q2: Generate random initial tour (permutation of 1 to n)
    public static ArrayList<Integer> initialTour(int n) {
        if (n <= 0) return null;

        ArrayList<Integer> tour = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            tour.add(i);
        }
        Collections.shuffle(tour, random); // Random permutation
        return tour;
    }

    // Q3: Check if tour is valid (permutation of 1 to n, matches matrix)
    public static int isValidTour(ArrayList<Integer> tour, double[][] matrix) {
        if (tour == null || matrix == null) return -1;
        if (isValidMatrix(matrix) != 1) return -1;

        int n = matrix.length;
        if (tour.size() != n) return -1;

        // Check if tour is a valid permutation of 1 to n
        boolean[] visited = new boolean[n + 1];
        for (int city : tour) {
            if (city < 1 || city > n || visited[city]) return -1;
            visited[city] = true;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) return -1;
        }
        return 1; // Valid tour
    }

    // Q4: Calculate tour fitness (total distance)
    public static double fitness(ArrayList<Integer> tour, double[][] matrix) {
        if (isValidTour(tour, matrix) != 1) return -1.0;

        double totalDistance = 0.0;
        int n = tour.size();
        for (int i = 0; i < n - 1; i++) {
            int city1 = tour.get(i);
            int city2 = tour.get(i + 1);
            totalDistance += matrix[city1 - 1][city2 - 1];
        }
        // Add return to start
        totalDistance += matrix[tour.get(n - 1) - 1][tour.get(0) - 1];
        return totalDistance;
    }

    // Q5: Create new tour by swapping two cities
    public static ArrayList<Integer> smallChange(ArrayList<Integer> tour) {
        if (tour == null || tour.size() < 2) return null;

        ArrayList<Integer> newTour = new ArrayList<>(tour); // Return a copy
        int i = random.nextInt(newTour.size());
        int j;
        do {
            j = random.nextInt(newTour.size());
        } while (i == j);
        Collections.swap(newTour, i, j); // Swap two cities
        return newTour;
    }

    // Q6: Solve TSP using Hill Climbing
    public static ArrayList<Integer> solveTSP(int n, double[][] distanceMatrix, int iterations) {
        // Input validation
        if (n <= 0 || iterations <= 1 || distanceMatrix == null || isValidMatrix(distanceMatrix) != 1 || distanceMatrix.length != n) {
            return null;
        }

        // Initialize with random tour
        ArrayList<Integer> currentTour = initialTour(n);
        if (currentTour == null) return null;
        double currentFitness = fitness(currentTour, distanceMatrix);
        if (currentFitness < 0) return null;
        ArrayList<Integer> bestTour = new ArrayList<>(currentTour);
        double bestFitness = currentFitness;

        // Hill Climbing loop
        for (int i = 0; i < iterations; i++) {
            ArrayList<Integer> neighbor = smallChange(currentTour);
            if (neighbor == null) continue;
            double neighborFitness = fitness(neighbor, distanceMatrix);
            if (neighborFitness < 0) continue;

            // Accept better or equal fitness (10% chance for equal)
            if (neighborFitness < currentFitness ||
                    (neighborFitness == currentFitness && random.nextDouble() < 0.1)) {
                currentTour = new ArrayList<>(neighbor);
                currentFitness = neighborFitness;
                // Update best if improved
                if (currentFitness < bestFitness) {
                    bestTour = new ArrayList<>(currentTour);
                    bestFitness = currentFitness;
                }
            }
        }
        return bestTour;
    }
}