/*
Jeg bruker en ferdig FibonacciHeap-klasse. Den er litt knotete men skal
fors?ke ? forklare underveis. For ? bruke denne m? en laste ned JGraphT,
enten fra http://www.jgrapht.org eller akkurat det en trenger fra

http://heim.ifi.uio.no/dagss/jgrapht.jar

For de som ikke kan ? bruke jar-filer: Legg den i samme mappe som filene
dine og kj?r javac og java s?nn:

javac -classpath .:jgrapht.jar Oppgave1.java
java -classpath .:jgrapht.jar Oppgave1 innfil utfil

----
Koden er vel ikke et kroneksempel p? enkapsulasjon, og legger heller ikke
til rette for den beste metoden for ? beregne heuristikk (men den er grei
nok). Poenget er bare ? demonstrere hvilke datastrukturer en kan bruke,
og jeg har fjernet selve algoritmen.
*/
import org.jgrapht.util.FibonacciHeap;
import org.jgrapht.util.FibonacciHeapNode;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

/*
Enum er fine. Denne lagrer b?de output-verdier og differansene en skal
legge til p? rader og kolonner om en velger den retningen. Dessuten
kan en lage en l?kke over DIRECTIONS for ? pr?ve alle retninger:

for (Direction dir : Direction.DIRECTIONS) { ... }
*/
enum Direction {
    LEFT(-1, 0, "V"), RIGHT(1, 0, "H"), UP(0, -1, "O"), DOWN(0, 1, "N");

    public final int rowOffset;
    public final int colOffset;
    public final String strVal;

    Direction(int colOffset, int rowOffset, String strVal) {
        this.rowOffset = rowOffset;
        this.colOffset = colOffset;
        this.strVal = strVal;
    }

    public static Direction[] DIRECTIONS = new Direction[] {LEFT, RIGHT, UP, DOWN};

    public String toString() {
        return strVal;
    }
}

/*
Denne fungerer som n?kkelverdi og lagrer bare brettkonfigurasjonen, ikke
node-informasjon som trengs i s?ket. Merk bruken av equals og hashCode.
*/
class Board {
    byte[] board;
    int row, col;
    int n;

    public Board(int n) {
        this.n = n;
        board = new byte[n*n];
    }

    public boolean equals(Object o) {
        if (o == null || getClass() != o.getClass()) return false;
        final Board other = (Board)o;
        return (n == other.n) && Arrays.equals(board, other.board);
    }

    public int hashCode() {
        int result = 0;
        for (byte i : board) {
            result = 29 * result + i;
        }
        return result;
    }

    /**
     * Returner en ny brettkonfigurasjon som kommer om en g?r i angitt retning.
     * Gir null dersom en kommer utenfor brettet.
     */
    public Board move(Direction dir) {
        int newRow = row + dir.rowOffset;
        int newCol = col + dir.colOffset;
        if (newRow < 0 || newCol < 0 || newRow >= n || newCol >= n)
            return null;
        else {
            Board result = new Board(n);
            System.arraycopy(board, 0, result.board, 0, n*n);
            result.board[row*n + col] = result.board[newRow*n + newCol];
            result.board[newRow*n + newCol] = 0;
            result.row = newRow;
            result.col = newCol;
            return result;
        }
    }
}

/*
Dette er en node i tilstandsgrafen. Den har b?de det som er n?dvendig for ?
puttes i en k? og for ? fungere i algoritmen.
*/
class State extends FibonacciHeapNode<State> {
    Direction dirLeadingToThis;
    State parent;
    Board board;
    int h; // heuristic
    int g; // known cost from start to here
    // cost in queue is h + g
    boolean inQueue = false; // egentlig ikke n?dvendig, bare for en assert...

    public State(Board board, int heuristicCost, Direction dirLeadingToThis) {
        super(null, 0); // her hacker jeg litt rundt hvordan FibonacciQueue-klassa fungerer...
        this.board = board;
        h = heuristicCost;
        this.dirLeadingToThis = dirLeadingToThis;
    }
}

interface Heuristic {
    int heuristic(Board b);
}

class ManhattanDistance implements Heuristic {
// kan ikke r?pe alt...
}


public class Oppgave1 {
    private final Heuristic h;
    int queuePops, queueInserts, queueDecreaseKeys;

    public Oppgave1(int n) {
        h = new ManhattanDistance(n);
    }

    public static void main(String[] args) throws FileNotFoundException {
        // Parse input
        Scanner in = new Scanner(new File(args[0]));
        int n;
        Board startBoard;
        try {
            n = in.nextInt();
            startBoard = new Board(n);
            for (int i = 0; i != n * n; ++i) {
                byte val = in.nextByte();
                startBoard.board[i] = val;
                if (val == 0) {
                    startBoard.col = i % n;
                    startBoard.row = i / n;
                }
            }

        } finally {
            in.close();
        }

        Oppgave1 oppgave = new Oppgave1(n);
        State endState = oppgave.aStarSearch(startBoard);

        Stack<Direction> stack = new Stack<Direction>();
        while (endState.parent != null) {
            stack.push(endState.dirLeadingToThis);
            endState = endState.parent;
        }

        // Serialize output
        PrintWriter out = new PrintWriter(new File(args[1]));
        try {
            out.println(stack.size());
            while (!stack.empty()) {
                out.print(stack.pop());
            }
            out.println();
            out.println(oppgave.queuePops);
            out.println(oppgave.queueInserts);
            out.println(oppgave.queueDecreaseKeys);
        } finally {
            out.close();
        }
    }

    private State aStarSearch(Board startBoard) {
        FibonacciHeap<State> queue = new FibonacciHeap<State>();
        HashMap<Board, State> knownStates = new HashMap<Board, State>();
        
        // Resten tar jeg ikke med. Men litt instrukser:
        
        // Ta ut minste element:
        State u = (State)queue.removeMin();
        
        // Sette inn element:
        queue.insert(v, kostnaden til v i k?en);
        
        // Lavere kostnad:
        queue.decreaseKey(v, ny kostnad til v i k?en)
        
        // G? til en nabotilstand: Anta at vi har en State u. S?:
        Direction dir = retningen en vil g? i;
        Board nextBoard = u.board.move(dir);
        State v = knownStates.get(nextBoard);
        if (v == null) {
          // m? opprette ny state og legge den i knownStates etc.
        } else {
          // vet at vi har bes?kt v f?r
        }
    }

}