Problem
This question originates from this post.
Anyway, I’m trying to solve the following problem:
Given a 3×3 grid with numbers 1-9, for example:
2 8 3
1 4 5
7 9 6
I have to sort the grid by rotating a 2×2 subgrid clockwise or counter-clockwise. The above example could be solved like this:
Rotate the top left piece clockwise:
2 8 3 1 2 3
1 4 5 => 4 8 5
7 9 6 7 9 6
Rotate the bottom right piece counter-clockwise:
1 2 3 1 2 3
4 8 5 => 4 5 6
7 9 6 7 8 9
The grid is now ‘sorted’.
I have to find the number of least possible moves to get from situation B to situation A (sorted)
My current implementation consists of creating a look-up table for all the possible permutations of the grid (idea from the original thread by user Sirko). The look-up table is a HashMap. I reduce the grids to strings like this:
1 2 3
4 5 6 => "123456789"
7 8 9
My current implementation (in Java):
import java.util.*;
public class Kiertopeli {
// initialize the look-up table
public static Map<String, Integer> lookUp = createLookup();
public static int etsiLyhin(int[][] grid) {
String finale = "";
for(int[] row : grid)
for(int num : row)
finale += Integer.toString(num);
// fetch the wanted situation from the look-up table
return lookUp.get(finale);
}
public static Map<String, Integer> createLookup() {
// will hold the list of permutations we have already visited.
Map<String, Integer> visited = new HashMap<String, Integer>();
Queue q = new ArrayDeque<Object[]>();
q.add(new Object[] { "123456789", 0 });
// just for counting. should always result in 362880.
int permutations = 0;
Object[] str;
creation:
while(!q.isEmpty())
{
str = (Object[])q.poll();
// pick the next non-visited permutation.
while(visited.containsKey((String)str[0])) {
if(q.isEmpty()) break creation;
str = (Object[])q.poll();
}
// mark the permutation as visited.
visited.put((String)str[0], (Integer)str[1]);
// loop through all the rotations.
for(int i = 0; i < 4; i++) {
// get a String array with arr[0] being the permutation with clockwise rotation,
// and arr[1] with counter-clockwise rotation.
String[] rotated = rotate((String)str[0], i);
// if the generated permutations haven't been created before, add them to the queue.
if(!visited.containsKey(rotated[0])) q.add(new Object[] { rotated[0], (Integer)str[1]+1 });
if(!visited.containsKey(rotated[1])) q.add(new Object[] { rotated[1], (Integer)str[1]+1 });
}
permutations++;
}
System.out.println(permutations);
return visited;
}
public static String[] rotate(String string, int place) {
StringBuilder str1 = new StringBuilder(string);
StringBuilder str2 = new StringBuilder(string);
if(place == 0) { // top left piece
str1.setCharAt(0, string.charAt(3));
str1.setCharAt(1, string.charAt(0)); // clockwise rotation
str1.setCharAt(4, string.charAt(1)); //
str1.setCharAt(3, string.charAt(4));
str2.setCharAt(3, string.charAt(0));
str2.setCharAt(0, string.charAt(1)); // counter-clockwise
str2.setCharAt(1, string.charAt(4)); //
str2.setCharAt(4, string.charAt(3));
}
if(place == 1) { // top right
str1.setCharAt(1, string.charAt(4));
str1.setCharAt(2, string.charAt(1));
str1.setCharAt(5, string.charAt(2));
str1.setCharAt(4, string.charAt(5));
str2.setCharAt(4, string.charAt(1));
str2.setCharAt(1, string.charAt(2));
str2.setCharAt(2, string.charAt(5));
str2.setCharAt(5, string.charAt(4));
}
if(place == 2) { // bottom left
str1.setCharAt(3, string.charAt(6));
str1.setCharAt(4, string.charAt(3));
str1.setCharAt(7, string.charAt(4));
str1.setCharAt(6, string.charAt(7));
str2.setCharAt(6, string.charAt(3));
str2.setCharAt(3, string.charAt(4));
str2.setCharAt(4, string.charAt(7));
str2.setCharAt(7, string.charAt(6));
}
if(place == 3) { // bottom left
str1.setCharAt(4, string.charAt(7));
str1.setCharAt(5, string.charAt(4));
str1.setCharAt(8, string.charAt(5));
str1.setCharAt(7, string.charAt(8));
str2.setCharAt(7, string.charAt(4));
str2.setCharAt(4, string.charAt(5));
str2.setCharAt(5, string.charAt(8));
str2.setCharAt(8, string.charAt(7));
}
return new String[] { str1.toString(), str2.toString() };
}
public static void main(String[] args) {
String grids = "2 8 3 1 4 5 7 9 6 "
+ "1 6 5 8 7 2 3 4 9 "
+ "1 6 5 8 7 2 3 4 9 "
+ "1 7 6 8 2 5 3 4 9 "
+ "8 1 5 7 4 6 3 9 2 "
+ "9 8 7 6 5 4 3 2 1 ";
Scanner reader = new Scanner(grids);
System.out.println();
while (reader.hasNext()) {
System.out.println("Enter grid:");
int[][] grid = new int[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
grid[i][j] = reader.nextInt();
}
}
System.out.println(" Smallest: " + etsiLyhin(grid));
}
}
}
The problem is, this runs for too long. Well, to clarify, on the server this code is tested on it runs for more than 2000ms (maximum allowed), but on my machine it runs for 1500-1600ms. Is there any optimization I could do here?
Solution
I guess you could get quite some performance from changing your main data type from String to an byte or integer array like, e.g.:
byte[] sorted = new byte[]() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Then you could easily change the identifying code for each permutation to an integer as well. Which could be computed out of the above array like this:
int code = sorted[8] * 1 +
sorted[7] * 10 +
sorted[6] * 100 +
sorted[5] * 1000 +
sorted[4] * 10000 +
sorted[3] * 100000 +
sorted[2] * 1000000 +
sorted[1] * 10000000 +
sorted[0] * 100000000;
This would keep you from using String comparisons inside the Map visited. Generally int operations are faster than the equivalent String operations.
As I already mentioned in my answer to the original question, another improvement would be to look, if a permutation was already added to the queue before. If so, we don’t have to do this again as it will yield no new information. This will reduce the put()/poll() operations on the queue by a lot.
You could do this, by introducing a new Set and using this to verify, if a specific permutation has been added to the queue before.