I would like some feed back on a method which calculates the sum of Manhattan distances for each tile in a sliding puzzle to its goal position in the goal puzzle.Here is the code:public static int calcManhattanDistance(int[] ps, int[] goal) {    int rowSz = calculatePuzzleRowSize(ps);    int manhattanDistanceSum = 0;    for (int i = 0; i < ps.length; i++) {        for (int j = 0; j < ps.length; j++) {            if (ps[i] == goal[j])                manhattanDistanceSum += (Math.abs(i/rowSz - j/rowSz) + Math.abs(i%rowSz - j%rowSz));         }    }    return manhattanDistanceSum;}Please tell me if you think something should be changed or what I can do to increase efficiency.Here is the calculatePuzzleRowSize(ps) method:public static int calculatePuzzleRowSize(int[] ps) {    int sz = ps.length;    int rowSz = (int) Math.sqrt(sz);    return rowSz;}Here is the newly implemented calculateManhattanDistanceSumpublic static int calculateManhattanDistanceSum(int[] ps, int[] goal) {    int rowSize = (int) Math.sqrt(ps.length);    int manhattanDistanceSum = 0;    Map<Integer, Integer> psMap = new HashMap<Integer, Integer>();    for (int i : ps)        psMap.put(ps[i], i);    for (int j : goal)        manhattanDistanceSum += Math.abs(psMap.get(j)/rowSize - j/rowSize) + Math.abs(psMap.get(j)%rowSize - j%rowSize);     return manhattanDistanceSum;}
Calculating sum of manhattan distances in a sliding puzzle
java;performance;algorithm;taxicab geometry
Assuming you hold the right order of the puzzle pieces in the goal-array, wouldn't it be natural that the right order itsself is 0 to #pieces - 1?If that's the case, you could calculate the manhatten distance by just iterating over ps[]:for (int i = 0; i < ps.length; i++)    if( ps[i] == i ) continue;else    manhattanDistanceSum += (Math.abs(ps[i]/rowSz - i/rowSz) + Math.abs(ps[i]%rowSz - i%rowSz));