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[]>()));
 }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s