In Chinese Checkers, a piece can move by hopping over any other piece, or by making a sequence of such hops. Your task is to find the longest possible sequence of hops.
A sequence of 121 zeroes or ones, each representing a place on a board. A zero means the place is empty; a one means the place is occupied. Positions are listed from left to right; top to bottom. For example, the input of this setup would be
The top-most place is occupied by a green piece, so the first digit in the input is
1. The second row has one empty position and then one occupied position, so
01comes next. The third row is all occupied, so
111. The fourth row has two empty and two occupied spaces (going left to right), so
0011. Then comes five
1, and seven
0's for the next row, and so on.
Like in that setup, there is a corner pointing straight up. There may be any number of pieces on the board (from 1 to 121). Note that pieces of different colors are not represented differently.
The maximum length of a legal hop, using any piece on the board. You may not visit the same place more than once (including the starting and ending positions). However, you may hop over the same piece more than once. If there is no legal hop, output
0. Do not consider whether there exists a legal non-hop move.
For example, the output to the setup described above is
Input and output may be done through stdin and stdout, through command-line arguments, through function calls, or any similar method.
0 (no two pieces are next to each other)
1 (initial setup for one player in top-left corner)