DISCLAIMER This problem is part of a COMPLETED competition and will not be reused
I was hoping someone could create and explain a solution efficient enough to run file sizes at most 15 x 15 tiles. Below is the problem:
Tiled Floor (40 points) Sam recently hired a tile installer to tile a kitchen floor. The floor was supposed to be very colorful with no two adjacent tiles having the same color. Unfortunately, the installer failed to ensure adjacent tiles have different colors. The mortar is still wet, but it is difficult to lift just one tile at a time, so the installer is limited to swapping adjacent tiles. The question is how to exchange adjacent tiles in as few moves as possible so that the floor meets the criteria that no two adjacent tiles have the same color. A sample input is RGR RPC GRB YPG Representing the tiles on a three by four floor where R is a red tile, G is green, B is blue, C is cyan, P is purple, and Y is yellow. In general, the input will be a series of lines of R, G, B, C, P, and Y. Each line will have the same length and there will be a maximum of 15 lines with 15 characters in each line. The output is to be an integer representing the number of swaps of adjacent tiles. For this problem, “adjacent” means touching and in the same row or column; for example, the only two tiles are adjacent to the yellow tile in the lower left corner of the above floor: the green tile at the start of the third row and the purple tile in the middle of the fourth row. The output for the above floor will be 2 since the red tile at the start of row 2 can be swapped with the green tile at the start of row three, and then the red tile in middle of row 3 can be swapped with the blue tile at the end. This gives the arrangement RGR GPC RBR YPG Other fixes are possible such as exchanging the first two tiles on row 2 to get PRC and then exchanging the middle tiles in rows 3 and 4. Your program does not print the resulting floor arrangement, just the minimum number of tile swaps that must take place. Sometimes it is not possible to fix a floor: GGYGP CGGRG This isn’t possible to tile because there are 6 Gs and a floor this size can fit only 5 without two being adjacent. In cases where there is no solution, the output is to be not possible
I have created a solution but it works only for approximately 16 tiles (4 x 4), any more takes an enormous amount of time. This is because of the recursive and naive nature of this function, for every call it calls itself at least 4 times.
Below is my attempted solution, keep in mind that there are extra methods from previous attempts and that minimumSwaps() is the main recursive method:
import java.util.*;
import java.io.*;
class Main {
private static ArrayList<String[][]> solutions = new ArrayList<String[][]>();
private static ArrayList<Integer> moves = new ArrayList<Integer>();
private static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
File file = new File("Tiles.txt");
Scanner scan = new Scanner(file);
Scanner scan1 = new Scanner(file);
int length = 0;
while (scan1.hasNextLine()) {
scan1.nextLine();
length ;
}
String[][] tiles = new String[length][];
for (int i = 0; i < length; i ) {
String line = scan.nextLine();
tiles[i] = new String[line.length()];
for (int l = 0; l < tiles[i].length; l ) {
tiles[i][l] = line.substring(l, l 1);
}
}
System.out.println("Start");
minimumSwaps(tiles, 0, new ArrayList<String>());
//System.out.println(Arrays.toString(findCount(tiles)));
//findSolutions(new String[tiles.length][tiles[0].length], findCount(tiles), 0, 0);
//System.out.println(solutions.size());
System.out.println(min);
//display();
}
//tilesIDs: more efficient way to check if computer has seen previous situation
//how to know if there are moves that do not involve problem areas that reduces total number of moves?
public static void minimumSwaps (String[][] tiles, int moves, ArrayList<String> tilesIDs) {
if (moves < min) {
String newID = computeID(tiles);
if (linearSearch(tilesIDs, newID)) return;
tilesIDs.add(newID);
if (solved(tiles)) {
//Main.moves.add(moves);
if (moves < min) min = moves;
//solutions.add(cloneTiles(tiles));
}
else if (moves < min - 1) {
for (int i = 0; i < tiles.length; i ) {
for (int l = 0; l < tiles[i].length; l ) {
if (adjacentPresent(tiles, tiles[i][l], i, l)) {
try {
String[][] newTiles = cloneTiles(tiles);
String current = newTiles[i][l];
newTiles[i][l] = newTiles[i][l - 1];
newTiles[i][l - 1] = current;
minimumSwaps(newTiles, moves 1, (ArrayList<String>)(tilesIDs.clone()));
}
catch (Exception e) {}
try {
String[][] newTiles = cloneTiles(tiles);
String current = newTiles[i][l];
newTiles[i][l] = newTiles[i][l 1];
newTiles[i][l 1] = current;
minimumSwaps(newTiles, moves 1, (ArrayList<String>)(tilesIDs.clone()));
}
catch (Exception e) {}
try {
String[][] newTiles = cloneTiles(tiles);
String current = newTiles[i][l];
newTiles[i][l] = newTiles[i - 1][l];
newTiles[i - 1][l] = current;
minimumSwaps(newTiles, moves 1, (ArrayList<String>)(tilesIDs.clone()));
}
catch (Exception e) {}
try {
String[][] newTiles = cloneTiles(tiles);
String current = newTiles[i][l];
newTiles[i][l] = newTiles[i 1][l];
newTiles[i 1][l] = current;
minimumSwaps(newTiles, moves 1, (ArrayList<String>)(tilesIDs.clone()));
}
catch (Exception e) {}
}
}
}
}
}
}
public static boolean linearSearch(ArrayList<String> IDs, String newID) {
for (String ID : IDs) if (ID.equals(newID)) return true;
return false;
}
public static String computeID(String[][] tiles) {
String ID = "";
for (String[] letters : tiles) {
for (String letter : letters) {
ID = letter;
}
}
return ID;
}
public static String[][] cloneTiles(String[][] tiles) {
String[][] newTiles = new String[tiles.length][tiles[0].length];
for (int i = 0; i < tiles.length; i ) {
newTiles[i] = tiles[i].clone();
}
return newTiles;
}
public static boolean solved(String[][] tiles) {
for (int i = 0; i < tiles.length; i ) {
for (int l = 0; l < tiles[i].length; l ) {
if (adjacentPresent(tiles, tiles[i][l], i, l)) return false;
}
}
return true;
}
public static int minMoves() {
int min = Integer.MAX_VALUE;
for (int num : moves) if (num < min) min = num;
return min;
}
public static void findSolutions(String[][] tiles, int[] count, int i, int l) {
String[] colors = {"R", "G", "B", "C", "P", "Y"};
for (int z = 0; z < 6; z ) {
//System.out.println("testing");
if (!adjacentPresent(tiles, colors[z], i, l) && count[z] > 0) {
String[][] newTiles = new String[tiles.length][tiles[0].length];
for (int a = 0; a < newTiles.length; a ) {
for (int b = 0; b < newTiles[0].length; b ) {
newTiles[a][b] = tiles[a][b]; // clone does not work properly?
}
}
newTiles[i][l] = colors[z];
//System.out.println(Arrays.deepToString(newTiles));
int[] newCount = count.clone();
newCount[z]--;
if (l == tiles[0].length - 1 && i != tiles.length - 1) {
findSolutions(newTiles, newCount, i 1, 0);
}
else if (l < tiles[0].length - 1) {
findSolutions(newTiles, newCount, i, l 1);
}
else if (l == tiles[0].length - 1 && i == tiles.length - 1) {
solutions.add(newTiles);
}
}
}
}
public static boolean adjacentPresent(String[][] tiles, String color, int i, int l) {
try {
if (tiles[i][l 1].equals(color)) return true;
}
catch (Exception e) {}
try {
if (tiles[i][l - 1].equals(color)) return true;
}
catch (Exception e) {}
try {
if (tiles[i 1][l].equals(color)) return true;
}
catch (Exception e) {}
try {
if (tiles[i - 1][l].equals(color)) return true;
}
catch (Exception e) {}
return false;
}
public static int[] findCount(String[][] tiles) {
int[] count = new int[6];
for (String[] line : tiles) {
for (String letter : line) {
switch (letter) {
case "R": count[0] ;
break;
case "G": count[1] ;
break;
case "B": count[2] ;
break;
case "C": count[3] ;
break;
case "P": count[4] ;
break;
case "Y": count[5] ;
break;
}
}
}
return count;
}
public static void display() {
for (String[][] lines : solutions) {
for (String[] line : lines) {
for (String letter : line) {
System.out.print(letter);
}
System.out.println();
}
System.out.println("\n\n");
}
}
}
CodePudding user response：
Improving the algorithm
A breadth-first search would yield, as first result, an optimal solution. It could still be slow on larger problems where the solution is deeper in; or in the worst case, when there is no solution at all.
Your current algorithm looks like backtracking, which is depth-first, and therefore you need to look at all possible solutions before being sure you have found the shortest one. This is very wasteful.
Improving the data representation
You have 6 colors in a 15x15 grid. You are currently storing up to 15x15=225 strings, and constantly copying that String[][] over. It would be a lot more efficient to use a single byte[] (of length dim x dim), which can be copied over faster. Use integers (1, 2, ...) instead of color-chars ("R", "Y", ...). With a single dimension you have to do some math to check for adjacency, but it is nothing too fancy; and you win a lot of memory locality.