Java exhaustive solution

Question

This is a take on Pebble Solitaire. The user inputs n number of games and after that inputs a strings of length 23 that contains a combinations of only 'o' (pebble) and '-' (empty space). If there are 2 adjacent pebbles and an empty space on either side, ie (oo- OR -oo), then you remove the middle pebble and you swap other two pieces with each other, ex 'oo-' will turn into '--o'.

My current approach is pretty much an exhaustive approach where it tries out every possible move and results the move set with the least number of pebbles left.

My program is working fine, in terms of output, but for some of my test cases it takes too long to find an answer (sometimes taking 18 seconds). I would like to know how I can improve the performance of my code without making it multithreaded.

package Pebble;
import java.util.Scanner;
public class PebbleSolitaire {
 public static void main(String[] args){
 Scanner input = new Scanner(System.in);
 int numOfGames = Integer.parseInt(input.nextLine());
 while (numOfGames > 0){
 char[] values = input.nextLine().toCharArray();
 long startTime = System.nanoTime();
 System.out.println(solve(values));
 System.out.println("Time to finish in ms: " + (System.nanoTime() - startTime) / 1000000);
 numOfGames--;
 }
 input.close();
 }
 private static int solve(char[] game){
 if(game != null && game.length == 0){
 return -1;
 }
 int result = 0;
 for (int i = 0; i < game.length; i++){
 if(game[i] == 'o'){
 result++;
 }
 }
 //print(game);
 for (int i = 0; i < game.length; i++ ){
 char[] temp = new char[game.length];
 copyArray(temp, game);
 if (i-2 >= 0 && temp[i] == '-' && temp[i-2] == 'o' && temp[i-1] == 'o'){//move pebble forwards
 temp[i-1] = temp[i-2] = '-'; 
 temp[i] = 'o';
 result = Math.min(result, solve(temp));
 }
 copyArray(temp, game);
 if(i+2 < temp.length && temp[i] == '-' && temp[i+1] == 'o' && temp[i+2] == 'o'){//move pebble backwards
 temp[i+1] = temp[i+2] = '-';
 temp[i] = 'o';
 result = Math.min(result, solve(temp));
 }
 }
 return result;
 }
 private static void copyArray(char[] copy, char[] og){
 for(int x = 0; x < copy.length; x++){
 copy[x] = og[x];
 }
 }
 private static void print(char[] c){
 for(char ch: c){
 System.out.print(ch);
 }
 System.out.println();
 }
}

My sample input and output:

2
-o----ooo----o----ooo--
6
Time to finish in ms: 0
oooooooooo-ooooooooooo-
4
Time to finish in ms: 18149

Answer 1

Don't copy the array

A lot of the time spent in your program is just making copies of the game array. Instead of copying the array, just use the same one. All you need to do is to undo the move you made after you are done recursing on it. In other words:

1. Make the move
2. Recursively solve
3. Undo the move

Don't count the number of o's

Another time waster is the part where you count the number of o's on every recursive call. Instead of doing that, just count the number once, at the very beginning. Then when you recurse, pass in the new count. The new count is always one less than the previous count because each move removes one o from the board.

Error check should only happen once

Similarly, this error checking:

 if(game != null && game.length == 0){
 return -1;
 }

only needs to be done once. Having that code be in every recursive call is just slowing things down.

Memoization

Another thing that could be slowing your program down is the possibility that you are solving the same game states multiple times. For example, from the starting position, making move A followed by move B might end up in game state S1. But making move B followed by A might end up in the same state S1. Right now your program would solve the S1 state twice.

What you could do is to create an array (or Map) to record the answers to any state you have already solved. Since there are 23 spots, there are \2ドル^{23}\$ possible game states, or around 8 million. You can number each game state based on the binary number you get from the board, where - is a 0 and o is a 1. For example, --------------------o-o would translate to the binary number 00000000000000000000101, or 5. That would be the "index" of your game state.

After solving for a game state, you record the result in your array or Map. At the beginning of your function, you check the array/Map to see if the current position has already been solved, and just return the result if it has.

Also you can use bit tricks to compute the new game state index from the previous game state index, so you don't have to recompute it every time. For example, if the index is index, and you are making a move starting at index i, then the new game state index would be index ^ (0x7 << (20-i)). This is because you are flipping the board positions at the three bits starting at 20-i.

This memoization is probably going to help speed up your program more than the other tips, because it will cut entire branches off your search space instead of just speeding up your program by a flat percentage.

Sample rewrite

I used the ideas above to rewrite your program. For the memoization part, I chose to use a HashSet to remember which game states were already visited. I found that there was no need to actually remember the score for previously visited states (hence the Set and not a Map).

import java.util.HashSet;
import java.util.Scanner;
public class pebble {
 private static final int MAX_GAME_LENGTH = 31;
 public static void main(String[] args)
 {
 Scanner input = new Scanner(System.in);
 int numOfGames = Integer.parseInt(input.nextLine());
 while (numOfGames > 0) {
 char[] values = input.nextLine().toCharArray();
 if (values.length > MAX_GAME_LENGTH) {
 System.out.println("Skipping game: too large");
 continue;
 }
 long startTime = System.nanoTime();
 System.out.println(solve(values));
 System.out.println("Time to finish in ms: " +
 (System.nanoTime() - startTime) / 1000000);
 numOfGames--;
 }
 input.close();
 }
 private static int solve(char[] game)
 {
 int gameState = 0;
 int score = 0;
 HashSet<Integer> visited = new HashSet<Integer>();
 // Compute initial game state and score.
 for (int i=0;i<game.length;i++) {
 gameState <<= 1;
 if (game[i] == 'o') {
 gameState |= 1;
 score++;
 }
 }
 return solveHelper(gameState, score, visited, game.length);
 }
 private static int solveHelper(int gameState, int score,
 HashSet<Integer> visited, int gameLength)
 {
 int bestScore = score;
 visited.add(gameState);
 for (int i = gameLength-3; i >= 0; i--) {
 int trio = (gameState >> i) & 0x7;
 if (trio == 0x6 || trio == 0x3) {
 // 0x6: oo- -> --o
 // 0x3: -oo -> o--
 int mask = ~(0x7 << i);
 int newGameState = (gameState & mask) | ((trio ^ 0x7) << i);
 if (!visited.contains(newGameState)) {
 int ret = solveHelper(newGameState, score-1, visited,
 gameLength);
 if (ret < bestScore)
 bestScore = ret;
 }
 }
 }
 return bestScore;
 }
}

Optimizations helped a lot

I ran three programs to solve the difficult board. The first was the original program. The second was a variant of my program with the visited set removed to test how much of a difference the memoization made. The third was my sample rewrite program unmodified. Here are the results:

Original program : 41000 ms
JS1 (no memo) : 1460 ms (28x faster)
JS1 (with memo) : 3 ms (480x faster than no memo)

• bob dylan: Wow, you are amazing! I really need to sit down and fully understand your improvements! Thank you, I have learned a couple of new things today! :D

Answer 2

Array copies (1)

char[] temp = new char[game.length];
copyArray(temp, game);

can be expressed more elegantly (and probably with better performance) as

char[] temp = game.clone();

Array copies (2)

A better implementation of copyArray(char[] destination, char[] source) using standard library calls would be:

if (source != destination)
 System.arraycopy(source, 0, destination, 0, source.length);

Implementation of print(char[] chs)

... can be shortened to

System.out.println(chs);

Use try-resource blocks where applicable

Scanner input = new Scanner(System.in);
// do stuff with 'input' that may throw an exception
input.close();

can be better expressed as

try (Scanner input = new Scanner(System.in)) {
 // do stuff with 'input' that may throw an exception
}

Try-resource blocks ensure that the resource is closed properly even if the block terminates early due to exceptions, return, continue or break statements. They wrap the call to close() in a finally block and re-throw any occurring exception (if any).

Can we copy arrays less often?

What your implementation does in every recursive invocation is to

1. create a copy temp of the game state game,
2. work on and modify temp, update the result,
3. copy the content of temp back to game,
4. do some more work on temp and update the result.

As you can see you can omit one array copy if you perform step 2 directly on game. This doesn't alter the result since, at the beginning of step 2, temp is equivalent to game and step 3 sets the content of game to those of temp. Only in step 4 do you need to work on a copy of game because you need to preserve the state of game for the parent call:

for (int i = 0; i < game.length; i++ ) {
 if (i-2 >= 0 && game[i] == '-' && game[i-2] == 'o' && game[i-1] == 'o') { //move pebble forwards
 game[i-1] = game[i-2] = '-'; 
 game[i] = 'o';
 result = Math.min(result, solve(game));
 }
 if(i+2 < game.length && game[i] == '-' && game[i+1] == 'o' && game[i+2] == 'o') { //move pebble backwards
 char temp[] = game.clone();
 temp[i+1] = temp[i+2] = '-';
 temp[i] = 'o';
 result = Math.min(result, solve(temp));
 }
}

You can further improve the implementation if you don't create a new array instance for temp for every loop body invocation. It would be enough to use the same temporary array every time:

char[] temp = new char[game.length];
for (int i = 0; i < game.length; i++ ) {
 // ...
 if(i+2 < game.length && game[i] == '-' && game[i+1] == 'o' && game[i+2] == 'o') { //move pebble backwards
 System.arraycopy(game, 0, temp, 0, i);
 temp[i+1] = temp[i+2] = '-';
 temp[i] = 'o';
 System.arraycopy(game, i+3, temp, i+3, game.length - i - 3);
 result = Math.min(result, solve(temp));
 }
}