const N = 10;

class PriorityQueue {
    constructor() {
        this.heap = [];
    }

    push(item, priority) {
        this.heap.push({ item, priority });
        this._heapifyUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop().item;

        const result = this.heap[0].item;
        this.heap[0] = this.heap.pop();
        this._heapifyDown(0);
        return result;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    _heapifyUp(index) {
        if (index === 0) return;
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[parentIndex].priority > this.heap[index].priority) {
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            this._heapifyUp(parentIndex);
        }
    }

    _heapifyDown(index) {
        const leftChild = 2 * index + 1;
        const rightChild = 2 * index + 2;
        let smallest = index;

        if (leftChild < this.heap.length && this.heap[leftChild].priority < this.heap[smallest].priority) {
            smallest = leftChild;
        }

        if (rightChild < this.heap.length && this.heap[rightChild].priority < this.heap[smallest].priority) {
            smallest = rightChild;
        }

        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            this._heapifyDown(smallest);
        }
    }
}

// Optimized state for the original multi-path A* approach
class State {
    constructor(currentPos, activePath, occupiedCells, completedPaths = []) {
        this.currentPos = currentPos;
        this.activePath = activePath;
        this.occupiedCells = occupiedCells; // Set of occupied positions
        this.completedPaths = completedPaths; // For reconstruction
    }
    
    encode() {
        // More efficient encoding
        const occupiedArray = Array.from(this.occupiedCells).sort();
        return `${this.currentPos}|${this.activePath}|${occupiedArray.join(',')}`;
    }
    
    heuristic(stations) {
        if (this.activePath >= 3) return 0;
        
        const target = stations[this.activePath + 1];
        const [x1, y1] = [Math.floor(this.currentPos / N), this.currentPos % N];
        const [x2, y2] = [Math.floor(target / N), target % N];
        
        // Manhattan distance with penalty for congestion
        let base = Math.abs(x2 - x1) + Math.abs(y2 - y1);
        
        // Add heuristic for remaining segments
        for (let i = this.activePath + 1; i < 3; i++) {
            const from = stations[i];
            const to = stations[i + 1];
            const [fx, fy] = [Math.floor(from / N), from % N];
            const [tx, ty] = [Math.floor(to / N), to % N];
            base += Math.abs(tx - fx) + Math.abs(ty - fy);
        }
        
        return base;
    }
    
    getNextStates(stations, parent = null) {
        const states = [];
        const [x, y] = [Math.floor(this.currentPos / N), this.currentPos % N];
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        const target = stations[this.activePath + 1];
        
        for (const [dx, dy] of directions) {
            const [nx, ny] = [x + dx, y + dy];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            
            const nextPos = nx * N + ny;
            if (this.occupiedCells.has(nextPos)) continue;
            
            // Avoid other stations unless they're our target
            const otherStations = stations.filter((s, i) => i !== this.activePath + 1);
            if (otherStations.includes(nextPos)) continue;
            
            if (nextPos === target) {
                // Reached target - complete current segment
                if (this.activePath === 2) {
                    // Completed all paths
                    const finalPath = this.reconstructPath(parent, this.currentPos, nextPos);
                    const newCompletedPaths = [...this.completedPaths, finalPath];
                    const newState = new State(nextPos, this.activePath + 1, 
                        new Set([...this.occupiedCells, nextPos]), newCompletedPaths);
                    states.push(newState);
                } else {
                    // Move to next segment
                    const currentPath = this.reconstructPath(parent, 
                        stations[this.activePath], nextPos);
                    const newOccupied = new Set([...this.occupiedCells, ...currentPath]);
                    const newCompletedPaths = [...this.completedPaths, currentPath];
                    const newState = new State(nextPos, this.activePath + 1, 
                        newOccupied, newCompletedPaths);
                    states.push(newState);
                }
            } else {
                // Regular move
                const newOccupied = new Set([...this.occupiedCells, nextPos]);
                const newState = new State(nextPos, this.activePath, 
                    newOccupied, this.completedPaths);
                states.push(newState);
            }
        }
        
        return states;
    }
    
    reconstructPath(parent, start, end) {
        if (!parent) return [start, end];
        
        const path = [end];
        let current = this;
        
        // This is simplified - in a real implementation you'd trace back through parent pointers
        // For now, just return the direct connection
        return [start, end];
    }
}

// Improved multi-path A* that considers global constraints
function multiPathAStar(stations) {
    const pq = new PriorityQueue();
    const visited = new Set();
    const gScore = new Map();
    const parent = new Map();
    
    // Start state: at station A, working on path 0 (A->B)
    const startState = new State(stations[0], 0, new Set([stations[0]]));
    const startKey = startState.encode();
    
    pq.push(startState, startState.heuristic(stations));
    gScore.set(startKey, 0);
    
    let iterations = 0;
    const maxIterations = 100000; // Prevent infinite loops
    
    while (!pq.isEmpty() && iterations < maxIterations) {
        iterations++;
        
        const currentState = pq.pop();
        const currentKey = currentState.encode();
        
        if (visited.has(currentKey)) continue;
        visited.add(currentKey);
        
        // Goal check: completed all 3 segments
        if (currentState.activePath >= 3) {
            console.log(`Solution found in ${iterations} iterations`);
            return reconstructFullPath(parent, currentState, stations);
        }
        
        const currentG = gScore.get(currentKey) || 0;
        
        for (const nextState of currentState.getNextStates(stations, currentState)) {
            const nextKey = nextState.encode();
            if (visited.has(nextKey)) continue;
            
            const tentativeG = currentG + 1;
            
            if (!gScore.has(nextKey) || tentativeG < gScore.get(nextKey)) {
                parent.set(nextKey, { state: currentState, pos: currentState.currentPos });
                gScore.set(nextKey, tentativeG);
                const priority = tentativeG + nextState.heuristic(stations);
                pq.push(nextState, priority);
            }
        }
        
        if (iterations % 10000 === 0) {
            console.log(`Iteration ${iterations}, queue size: ${pq.heap.length}, visited: ${visited.size}`);
        }
    }
    
    console.log(`Search terminated after ${iterations} iterations`);
    return null;
}

// Reconstruct the full path from parent pointers
function reconstructFullPath(parent, goalState, stations) {
    const fullPath = [];
    let currentKey = goalState.encode();
    let positions = [goalState.currentPos];
    
    // Trace back through parent pointers
    while (parent.has(currentKey)) {
        const parentInfo = parent.get(currentKey);
        positions.unshift(parentInfo.pos);
        currentKey = parentInfo.state.encode();
    }
    
    return positions;
}

// Fallback: try different path orders
function fourPass(stations) {
    console.log("Trying original order...");
    let result = multiPathAStar(stations);
    if (result) return result;
    
    // Could try different heuristics or approaches here
    console.log("No solution found with multi-path A*");
    return null;
}