## Cracker Barrel

### August 19, 2014 While I was out of town last week, I ate dinner one evening at Cracker Barrel, which provides a triangle puzzle at each table so you can amuse yourself while you are waiting for your food. When my daughter challenged me to solve the problem, I failed, but I promised her that I would write a program to solve it.

As shown in the picture at right, the puzzle is a triangle with 15 holes and 14 pegs; one hole is initially vacant. The game is played by making 13 jumps; each jump removes one peg from the triangle, so at the end of 13 jumps there is one peg remaining. A jump takes a peg from a starting hole, over an occupied hole, to an empty finishing hole, removing the intermediate peg.

Your task is to write a program that solves the Cracker Barrel puzzle; find all possible solutions that start with a corner hole vacant and end with the remaining peg in the original vacant corner. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 20 Responses to “Cracker Barrel”

1. JP said

That’s amusing. About a month and a half ago, I came across another site that had the same challenge, so I worked it out then:
Cracker Barrel Peg Game – framework and basic solver
Cracker Barrel Peg Game, Part 2 – which solutions are most solvable
Cracker Barrel Peg Game, Part 3 – interactive command line game

Although I will admit I don’t have anything that will end in a specific win state. It should be only a single line to add though.

(All three in Racket.)

2. kbob said

I remember writing a solver for that puzzle long ago. I was still living with my parents, and I was writing in C, so that dates it around 1981-84. Of course, the code is long gone.

3. ```use strict;
use warnings;

my \$possible_moves = [
[ [1,3],[2,5] ],
[ [3,6],[4,8] ],
[ [4,7],[5,9] ],
[ [1,0],[4,5],[6,10],[7,12] ],
[ [7,11],[8,13] ],
[ [2,0],[4,3],[8,12],[9,14] ],
[ [3,1],[7,8] ],
[ [4,2],[8,9] ],
[ [4,1],[7,6] ],
[ [5,2],[8,7] ],
[ [6,3],[11,12] ],
[ [7,4],[12,13] ],
[ [7,3],[8,5],[11,10],[13,14] ],
[ [8,4],[12,11] ],
[ [9,5],[13,12] ],
];

solve_grid( q(011111111111111), [] );

sub solve_grid {
my ( \$grid, \$moves ) = @_;
if( @{\$moves} == 13 && \$grid eq q(100000000000000) ) {
print "@{\$moves}\n";
return;
}
foreach my \$i (0..14) {
next unless substr \$grid, \$i, 1;
foreach my \$m (@{\$possible_moves->[\$i]}) {
next if     substr \$grid, \$m->, 1;
next unless substr \$grid, \$m->, 1;
my \$g = \$grid;
substr \$g, \$i,     1, 0;
substr \$g, \$m->,1, 0;
substr \$g, \$m->,1, 1;
solve_grid( \$g, [@{\$moves},"\$i->\$m->"] );
}
}
return;
}

```
4. I think this is slightly slower – but slight more compact code…

```use strict;
use warnings;
use feature qw(say);

my \$possible_moves = [
[0,1,3], [0,2,5], [1,3,6],   [1,4,8],    [2,4,7], [2,5,9],
[3,1,0], [3,4,5], [3,6,10],  [3,7,12],   [4,7,11],[4,8,13],   [5,2,0], [5,4,3],[5,8,12],[5,9,14],
[6,3,1], [6,7,8], [7,4,2],   [7,8,9],    [8,4,1], [8,7,6],
[9,5,2], [9,8,7], [10,6,3],  [10,11,12], [11,7,4],[11,12,13],
[12,7,3],[12,8,5],[12,11,10],[12,13,14], [13,8,4],[13,12,11], [14,9,5],[14,13,12],
];

solve_grid( q(011111111111111), q() );

sub solve_grid {
my ( \$grid, \$moves ) = @_;
return say \$moves if \$grid eq q(100000000000000);
foreach (@{\$possible_moves}) {
my \$g = \$grid;
next if ! substr( \$g, \$_->,1, 0 ) || ! substr( \$g, \$_->,1, 0 ) || substr( \$g, \$_->,1, 1 );
solve_grid( \$g, \$moves."\$_->->\$_-> " );
}
return;
}
```
5. Paul said

In Python.

```BOARD_INIT =  +  * 14
MOVE_MASKS = [(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)]

def find_moves(board):
"""move: tuple with (from, over, to)"""
for m1, m2, m3 in MOVE_MASKS:
if board[m2]:
if board[m1] and not board[m3]:
yield m1, m2, m3
elif board[m3] and not board[m1]:
yield m3, m2, m1

def do_move(move, board):
board = list(board)
m1, m2, m3 = move
board[m1], board[m2], board[m3] = 0, 0, 1
return board

def solve(board=BOARD_INIT, movs=[]):
"""generate all movesequences that result in one peg"""
if sum(board) == 1:
yield movs
else:
for m in find_moves(board):
for g in solve(do_move(m, board), movs + [m]):
yield g

print sum(1 for moves in solve() if moves[-1][-1] == 0) # 6816
print sum(1 for moves in solve()) # 29760
```
6. matthew said

Recursive backtracking solution with memoization, using a bitset for the board. I was going to keep track of the moves in a tree structure, but thought it would be more fun to output a .dot file – see http://matthewarcus.files.wordpress.com/2014/08/puzzle.png for the (2Mb) result.

```#include <stdint.h>
#include <stdio.h>
#include <vector>

std::vector<uint16_t> moves;
std::vector<int16_t> memo((1<<15)-1,-1);

void add(int a, int b, int c)
{
uint16_t move1 = (1<<a)|(1<<b);
uint16_t move2 = (1<<b)|(1<<c);
moves.push_back(move1);
moves.push_back(move2);
}

int solve(std::vector<uint16_t> &game, int n)
{
if (memo[game[n]] >= 0) return memo[game[n]];
int result = 0;
for (int i = 0; i < (int)moves.size(); i++) {
if ((game[n] & masks[i]) == moves[i]) {
int t = solve(game,n+1);
if (t > 0) printf(" x%X -> x%X;\n", game[n], game[n+1]);
result += t;
}
}
memo[game[n]] = result;
return result;
}

int main()
{
std::vector<uint16_t> game(15);
memo = 1; // Prime the pump
game = 0x7ffe;
printf("digraph g {\n");
fprintf(stderr,"%d\n", solve(game,0));
printf("}\n");
}
```
7. matthew said

That should have been:

```   ...
moves.push_back(move1);
moves.push_back(move2);
```

(Last minute “improvement” – means the same of course).

8. mcmillhj said

The solution that you posted above seems to timeout on my machine and on codepad. I also have a scheme solution that is timing out at the moment, attempting to debug it.

9. programmingpraxis said

It is slow because it must form all possible solutions. It times out at both codepad and ideone, but runs to completion on my machine at work:

```Petite Chez Scheme Version 8.4

> (define (identity x) x)
> (define (mappend f . xss) (apply append (apply map f xss)))
> (define (filter pred? xs)
(let loop ((xs xs) (ys '()))
(cond ((null? xs) (reverse ys))
((pred? (car xs))
(loop (cdr xs) (cons (car xs) ys)))
(else (loop (cdr xs) ys)))))
> (define (remove x xs)
(let loop ((xs xs) (zs '()))
(cond ((null? xs) (reverse zs))
((equal? (car xs) x) (loop (cdr xs) zs))
(else (loop (cdr xs) (cons (car xs) zs))))))
> (define (insert x xs)
(if (null? xs) (list x)
(if ( (define possibles '((1 2 4) (1 3 6) (2 4 7) (2 5 9) (3 5 8)
(3 6 10) (4 2 1) (4 5 6) (4 7 11) (4 8 13) (5 8 12) (5 9 14)
(6 3 1) (6 5 4) (6 9 13) (6 10 15) (7 4 2) (7 8 9) (8 5 3)
(8 9 10) (9 5 2) (9 8 7) (10 6 3) (10 9 8) (11 7 4)
(11 12 13) (12 8 5) (12 13 14) (13 8 4) (13 9 6) (13 12 11)
(13 14 15) (14 9 5) (14 13 12) (15 10 6) (15 14 13)))
> (define init '((2 3 4 5 6 7 8 9 10 11 12 13 14 15)))
> (define (feasible? board move)
(and (member (car move) (car board))
(not (member (caddr move) (car board)))))
> (define (jump board move)
(and (feasible? board move)
(remove (car move)
(cons move (cdr board)))))
> (define (all-jumps board)
(filter identity
(map (lambda (move) (jump board move))
possibles)))
> (define (solve init)
(let loop ((k (- (length (car init)) 1))
(boards (list init)))
(if (zero? k) boards
(loop (- k 1) (mappend all-jumps boards)))))
> (time (let ((solutions (solve init)))
(display (length solutions)) (newline)
(display (length (filter (lambda (x) (equal? (car x) '(1))) solutions))) (newline)
(display (list-ref solutions 17493)) (newline)))
29760
6816
((13) (11 12 13) (14 13 12) (6 9 13) (2 5 9) (7 4 2) (15 10 6) (3 6 10) (13 9 6)
(1 2 4) (12 8 5) (10 6 3) (4 5 6) (6 3 1))
(time (let ((...)) ...))
214 collections
13634 ms elapsed cpu time, including 1484 ms collecting
13655 ms elapsed real time, including 1471 ms collecting
1804614480 bytes allocated, including 1815872208 bytes reclaimed
```
10. mcmillhj said

I didn’t think that you were wrong, was just curious. I was using the mit-scheme interpreter, which apparently has very low memory limits. Switch to Gauche the program ran fine.

11. matthew said

My C++ program takes about 1.5ms to generate the .dot file (perf reckons about 2000000 cycles). As well as the obvious left-right symmetry, there’s also a forward and backward symmetry, swapping pegs for holes, which might save some time.

12. mcmillhj said

So I was having trouble with my scheme implemenation, it got to the point where I was just swapping in all of the functions that you wrote and I ran them and was still getting the incorrect answer. It turns out it was the way that I was encoding the data. If you run your program with data that marks the first peg as position 0 the results are skewed. Still haven’t figured out why.

Results:
40520
5736
((14) (12 13 14) (10 11 12) (5 8 11) (6 7 8) (11 12 13) (0 2 5) (1 3 6) (9 8 7) (5 4 3) (14 13 12) (6 3 1) (12 7 3) (3 1 0))

(define possible-moves
‘((0 1 3) (0 2 5)
(1 3 6) (1 4 8)
(2 4 7) (2 5 9)
(3 1 0) (3 4 5) (3 6 10) (3 7 12)
(4 7 11) (4 8 13)
(5 2 0) (5 4 3) (5 8 11) (5 9 14)
(6 3 1) (6 7 8)
(7 4 2) (7 8 9)
(8 4 1) (8 7 6)
(9 5 2) (9 8 7)
(10 6 3) (10 11 12)
(11 7 4) (11 12 13)
(12 7 3) (12 8 5) (12 11 10) (12 13 14)
(13 12 11) (13 8 4)
(14 9 5) (14 13 12)))

13. mcmillhj said

The initial board is also different due to the zero encoding:

(define init ‘((1 2 3 4 5 6 7 8 9 10 11 12 13 14)))

14. matthew said

That (5 8 11) should be (5 8 12)

15. mcmillhj said

…………………………………………. That is what I get for drawing a shoddy triangle in my notes. Thank you.

16. matthew said

Pleasure. Here’s some general code for the lower to higher moves:

```#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int N = atoi(argv);
for (int i = 0, n = 0; i < N; i++) {
for (int j = 0; j <= i; j++,n++) {
if (i+2 < N) {
printf("%d %d %d\n",n,n+i+1,n+i+i+3);
printf("%d %d %d\n",n,n+i+2,n+i+i+5);
}
if (j+2 <= i) {
printf("%d %d %d\n",n,n+1,n+2);
}
}
}
}
```
17. mcmillhj said

Awesome, here is a solution using your standard prelude but with the data format a little more compressed:

```;; we can see from above that many of these triplets share the same
;; middle digit, we can use these to reduce the size of our list of moves
;; (0 1 3)  <=> (3 1 0)
;; (0 2 5)  <=> (5 2 0)
;; (1 4 8)  <=> (8 4 1)
;; (2 4 7)  <=> (7 4 2)
;; (2 5 9)  <=> (9 5 2)
;; (3 4 5)  <=> (5 4 3)
;; (3 6 10) <=> (10 6 3)
;; (3 7 12) <=> (12 7 3)
;; we can now say that a triplet (a b c) represents both the moves
;; (a b c) AND (c b a)
;; this allows us to reduce our list of moves from 36 -> 18
(define compressed-possible-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)))

(define initial-board '((1 2 3 4 5 6 7 8 9 10 11 12 13 14)))

(define (can-move? board move)
(let ((from (car move))
(b    (car board)))
(and (member from b)
(member over b)
(not (member to b)))))

(define (flip-move move)

(define (make-move board move)
(remove (car move)
(cons move (cdr board))))

(define (move board move)
(letrec ((move2 (flip-move move))
(canmove1 (can-move? board move))
(canmove2 (can-move? board move2)))
(cond ((and canmove1 canmove2)
(cons (make-move board move) (make-move board move2)))
(canmove1 (make-move board move))
(canmove2 (make-move board move2))
(else #f))))

(define (all-moves board)
(filter identity
(map (lambda (m) (move board m)) compressed-possible-moves)))

(define (solve init)
(let loop ((k 13)
(boards (list init)))
(if (= 0 k) boards
(loop (- k 1) (mappend all-moves boards)))))

(let ((solutions (solve initial-board)))
(display (length solutions)) (newline)
(display (length (filter (lambda (x) (equal? (car x) '(0))) solutions))) (newline)
(display (list-ref solutions 17493)) (newline))
;; 29760
;; 6816
;; ((0) (3 1 0) (12 7 3) (14 13 12) (6 3 1) (5 4 3) (11 12 13) (1 3 6) (0 2 5) (13 8 4) (10 6 3) (9 5 2) (3 4 5) (5 2 0))
```
18. Christophe said

So here is my code. It’s rough but it’s correct.

__author__ = ‘Christophe De Troyer’

# Define the the puzzle with 14 pegs and 1 hole.
# 0 = no peg, 1 = peg

INITIAL_BOARD =  +  * 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:
TOTALMOVES.append(m)
# Swap the move.
m2 = list(m)
temp = m2
m2 = m2
m2 = 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] == 1 and board[move] == 1 and board[move] \
== 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] = 1
new_board[move] = 0
# Remove the peg that just got jumped over.
new_board[move] = 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 == 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)

19. Christophe said

Another solution using Java Fork/Join framework:

```/******************************************************************************
* 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;

{

/** 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, move, move };
}

/**
* This function checks if a certain move is valid for a given gameboard.
*/
public static boolean canMakeMove(int[] move, int[] board)
{
return board[move] == 1 && board[move] == 1
&& board[move] == 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] = 1;
new_board[move] = 0;
new_board[move] = 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))
if (canMakeMove(flipMove(move), board))
}
return moves;

}

/*
*
*/
@Override
protected ArrayList<Results> compute()
{
int currentDataWidth = this.last - this.first;

if (isFinished(this.gameboard))
{
return new ArrayList<Results>()
{{
}};
}

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);
} else
{
int halfway = this.first + currentDataWidth / 2;

// Create the left and right tasks.
this.first, halfway, movesDone);
halfway + 1, this.last, movesDone);

left.fork();
ArrayList<Results> right_result = right.compute();
ArrayList<Results> left_result = left.join();

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

```

Total solutions: 29760
Total solutions with peg in top hole: 6816

duration: 244

20. kernelbob said

This is similar to the solver I wrote in the early 1980s.

I’d been sitting on this trying to get access to a fast server for some benchmarking. But I didn’t get the server, and it doesn’t matter. Suffice it to say that this solver runs in milliseconds.

```#include <stdbool.h>
#include <stdio.h>

// Peg numbering:
//       0
//      1 2
//     3 4 5
//    6 7 8 9
//   A B C D E

#define A 0xA
#define B 0xB
#define C 0xC
#define D 0xD
#define E 0xE

#define HOLE_COUNT 15

typedef short peg_mask;         // 15 pegs, fits in a signed short (-:

const peg_mask initial_state = 0x7ffe; // all except 0

const char triangle = {
{     0     },
{    1,2    },
{   3,4,5   },
{  6,7,8,9  },
{ A,B,C,D,E }
};

typedef struct move {
} move;

typedef struct solver_state {
move     possible_moves [6 * HOLE_COUNT]; // oversize
} solver_state;

{
// win when single peg remains.
return (state & (state - 1)) == 0;
}

void add_move(solver_state *p, int *pi, int row, int col, int dr, int dc)
{
int from = triangle[row][col];
int over = triangle[row += dr][col += dc];
int to = triangle[row += dr][col += dc];
peg_mask fm = 1 << from;
peg_mask om = 1 << over;
peg_mask tm = 1 << to;
move *mp = &p->possible_moves[*pi];

mp->mask = fm | om | tm;
mp->old = fm | om;
mp->new = tm;
++*pi;
}

void precalc_possible_moves(solver_state *p)
{
int i = 0;
for (int row = 0; row < 5; row++) {
for (int col = 0; col <= row; col++) {
if (row >= 2) {
if (col >= 2) {
// Jump NW from r/c
add_move(p, &i, row, col, -1, -1);
}
if (col <= row - 2) {
// Jump NE from r/c
add_move(p, &i, row, col, -1, 0);
}
if (col >= 2) {
// Jump E from r/c
add_move(p, &i, row, col, 0, -1);
}
if (col <= row - 2) {
// Jump W from r/c
add_move(p, &i, row, col, 0, +1);
}
}
if (row < 5 - 2) {
// Jump SE from r/c
add_move(p, &i, row, col, +1, 0);
// Jump SW from r/c
add_move(p, &i, row, col, +1, +1);
}
}
}
}

void print_path(peg_mask state, const solver_state *p)
{
if (state != initial_state)
print_path(p->prev_state[state], p);
for (int row = 0; row < 5; row++) {
printf("%*s", 4 - row, "");
for (int col = 0; col <= row; col++)
printf(" %c", state & (1 << triangle[row][col]) ? 'X' : '_');
printf("\n");
}
printf("\n");
}

// Given a board configuration, explore all possible moves from there.
{
if (is_winning_state(state))
return state;
for (const move *mp = p->possible_moves; mp->mask; mp++) {
if ((state & mp->mask) == mp->old) {
p->prev_state[next_state] = state;
if (winner)
return winner;
}
}
return 0;
}