Cracker Barrel in Python and Java F/J

Hi,

I’ve spent a few minutes solving the Cracker Barrel puzzle in Python. ┬áToday were my first few lines of Python so be gentle if my code is an eyesore.

It’s not very fast though. Therefore I’ve implemented using the Java F/J framework as well, which is a *lot* faster.

__author__ = 'Christophe De Troyer'

# Define the the puzzle with 14 pegs and 1 hole.
# 0 = no peg, 1 = peg
INITIAL_BOARD = [0] + [1] * 14

# Define all possible moves.
moves = [
    [0, 1, 3],
    [0, 2, 5],
    [1, 3, 6],
    [1, 4, 8],
    [2, 4, 7],
    [2, 5, 9],
    [3, 4, 5],
    [3, 6, 10],
    [3, 7, 12],
    [4, 7, 11],
    [4, 8, 13],
    [5, 8, 12],
    [5, 9, 14],
    [6, 7, 8],
    [7, 8, 9],
    [10, 11, 12],
    [11, 12, 13],
    [12, 13, 14],
]
TOTALMOVES = []

global total_solutions
total_solutions = 0
global total_with_zero_peg
total_with_zero_peg = 0

for m in moves:
    # Add initial move.
    TOTALMOVES.append(m)
    # Swap the move.
    m2 = list(m)
    temp = m2[0]
    m2[0] = m2[2]
    m2[2] = temp
    TOTALMOVES.append(m2)

# A move can be made iff the right index in the list contains a False value in
# the list (puzzle).
def can_make_move(move, board):
    if board[move[0]] == 1 and board[move[1]] == 1 and board[move[2]] \
            == 0:
        return True
    return False

# A move is made by marking the index contained in the 2nd position of the move
# as true in the puzzle list and the first position as false.
def make_move(move, board):
    new_board = list(board)
    # Move the peg.
    new_board[move[2]] = 1
    new_board[move[0]] = 0
    # Remove the peg that just got jumped over.
    new_board[move[1]] = 0
    return new_board

# A game is finished once the sum of the list is 1.
def is_finished(board):
    return sum(board) == 1

# Returns a list of all the moves we can make in the current game state.
def yield_moves(board):
    for move in TOTALMOVES:
        if can_make_move(move, board):
            yield move

def solve(board=INITIAL_BOARD, moves_done=[]):
    # If the game is done, print out the moves.
    global total_solutions, total_with_zero_peg
    if is_finished(board):
        total_solutions += 1
        if board[0] == 1:
            total_with_zero_peg += 1
    else:
        for move in yield_moves(board):
            solve(make_move(move, board), moves_done + [m])

solve(INITIAL_BOARD, [])
print 'Total solutions found: {0}:'.format(total_solutions)
print 'Total solutions found with a peg in the zero hole: {0}'.format(total_with_zero_peg)
/******************************************************************************
 * Cracker Barrel
 * @author : Christophe De Troyer
 * Last edit: 8-sep-2014 10:43:22 
 * Full source can be found on GitHub 
 ******************************************************************************/
import java.util.ArrayList;
import java.util.Date;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;


public class MoveTask extends RecursiveTask<ArrayList<Results>>
{

 /** The Constant serialVersionUID. */
 private static final long serialVersionUID = 9026570098669274448L;
 
 private final ArrayList<int[]> moves_todo;
 private final int[] gameboard;
 
 private int first;
 private int last;
 private ArrayList<int[]> movesDone;

 private final static int[][] MOVES = new int[][]
 { 
 new int[] { 0, 1, 3 },
 new int[] { 0, 2, 5 },
 new int[] { 1, 3, 6 },
 new int[] { 1, 4, 8 },
 new int[] { 2, 4, 7 },
 new int[] { 2, 5, 9 },
 new int[] { 3, 4, 5 },
 new int[] { 3, 6, 10 },
 new int[] { 3, 7, 12 },
 new int[] { 4, 7, 11 },
 new int[] { 4, 8, 13 },
 new int[] { 5, 8, 12 },
 new int[] { 5, 9, 14 },
 new int[] { 6, 7, 8 },
 new int[] { 7, 8, 9 },
 new int[] { 10, 11, 12 },
 new int[] { 11, 12, 13 },
 new int[] { 12, 13, 14 }
 };

 /**
 * Instantiates a new move task.
 */
 public MoveTask(final int[] gameboard, ArrayList<int[]> initial_moves, ArrayList<int[]> movesDone)
 {
 this(gameboard, initial_moves, 0, initial_moves.size() - 1, movesDone);
 }

 /**
 * Instantiates a new move task.
 */
 public MoveTask(final int[] gameboard, final ArrayList<int[]> moves_todo,
 int first, int last, ArrayList<int[]> movesDone)
 {
 this.gameboard = gameboard;
 this.moves_todo = moves_todo;
 this.first = first;
 this.last = last;
 this.movesDone = movesDone;
 }

 /**
 * Flips the move's direction.
 */
 public static int[] flipMove(int[] move)
 {
 return new int[]
 { move[2], move[1], move[0] };
 }

 /**
 * This function checks if a certain move is valid for a given gameboard.
 */
 public static boolean canMakeMove(int[] move, int[] board)
 {
 return board[move[0]] == 1 && board[move[1]] == 1
 && board[move[2]] == 0;
 }

 /**
 * Applies a move to the board and returns a copy of the board.
 */
 public static int[] makeMove(int[] move, int[] board)
 {
 int[] new_board = board.clone();
 new_board[move[2]] = 1;
 new_board[move[0]] = 0;
 new_board[move[1]] = 0;
 return new_board;
 }

 /**
 * Returns true if there is only one more peg left on the gameboard.
 */
 public static boolean isFinished(int[] board)
 {
 int sum = 0;
 for (int hole : board)
 sum += hole;
 return sum == 1;
 }

 /**
 * Returns a list of all possible moves in this gamestate.
 *
 * @param board
 * the board
 * @return the moves to do
 */
 public static ArrayList<int[]> getMovesToDo(int[] board)
 {
 ArrayList<int[]> moves = new ArrayList<int[]>();

 for (int[] move : MOVES)
 {
 if (canMakeMove(move, board))
 moves.add(move);
 if (canMakeMove(flipMove(move), board))
 moves.add(flipMove(move));
 }
 return moves;

 }

 /*
 * (non-Javadoc)
 * 
 * @see java.util.concurrent.RecursiveTask#compute()
 */
 @Override
 protected ArrayList<Results> compute()
 {
 int currentDataWidth = this.last - this.first;
 
 if (isFinished(this.gameboard))
 {
 return new ArrayList<Results>() 
 {{ 
 add(new Results(movesDone, gameboard));
 }};
 }
 
 if(this.moves_todo.size() < 1)
 return new ArrayList<Results>();

 // We can only make one move.
 // We make the move and then start the process all over again.
 if (currentDataWidth == 0)
 {
 int[] newBoard = makeMove(moves_todo.get(this.first), gameboard);
 ArrayList<int[]> movesToDo = getMovesToDo(newBoard);
 movesDone.add(moves_todo.get(this.first));
 return new MoveTask(newBoard, movesToDo, movesDone).compute();
 } else
 {
 int halfway = this.first + currentDataWidth / 2;

 // Create the left and right tasks.
 MoveTask left = new MoveTask(this.gameboard, this.moves_todo,
 this.first, halfway, movesDone);
 MoveTask right = new MoveTask(this.gameboard, this.moves_todo,
 halfway + 1, this.last, movesDone);

 // Execute the tasks.
 left.fork();
 ArrayList<Results> right_result = right.compute();
 ArrayList<Results> left_result = left.join();
 
 right_result.addAll(left_result);
 return right_result;
 }
 }
 /**
 * The main method.
 */
 public static void main(String[] args) {
 long before = new Date().getTime();
 
 int[] gameboard = new int[]{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
 ArrayList<int[]> initial_moves = MoveTask.getMovesToDo(gameboard);

 ArrayList<Results> result = execute(gameboard, initial_moves);
 
 // Count the number of games where the top hole has a peg in it.
 int pegInTop = 0;
 for(Results res : result)
 if(res.gameboard[0] == 1)
 pegInTop++;
 System.out.println(String.format("Total solutions: %s \nTotal solutions with peg in top hole: %s\n", result.size(), pegInTop));
 System.out.println("duration: "+(new Date().getTime()-before));

 }
 public static ArrayList<Results> execute(int[] gameboard, ArrayList<int[]> initial_moves){
 // Initiate the F/J Pool.
 ForkJoinPool forkJoinPool = new ForkJoinPool(4);
 return forkJoinPool.invoke(new MoveTask(gameboard, initial_moves, new ArrayList<int[]>()));
 }
}