Chinese Checkers longest move

Question

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.

Input

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

1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111

Explanation:

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 01 comes 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 0's, a 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.

Output

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 3.

Input and output may be done through stdin and stdout, through command-line arguments, through function calls, or any similar method.

Test Cases

Input:

0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001

Output: 0 (no two pieces are next to each other)

---

Input:

0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000

Output: 1 (initial setup for one player in top-left corner)

Answer 1

Perl, 345 322

Edit: golfed, slightly.

More test cases would be nice, but for now it looks like it works. I'll add comments later if necessary. With newlines and indentation for readability:

$_=<>;
$s=2x185;
substr$s,(4,22,unpack'C5(A3)*','(:H[n129148166184202220243262281300')[$i++],0,$_ 
    for unpack A.join A,1..4,13,12,11,10,9..13,4,3,2,1;
$_=$s;
sub f{
    my(@a,%h)=@_;
    $h{$_}++&&return for@a;
    $-+=$#a>$-;
    $s=~/^.{$a[0]}$_/&&f($+[1],@a)
        for map{("(?=.{$_}1.{$_}(0))","(?<=(0).{$_}1.{$_}.)")}0,17,18
}
f$+[0]while/1/g;
print$-

Answer 2

C,262 260

Golfed code (debugging code and unnecessary whitespace removed. Changed from input via stdin to input via command line, and took advantage of the opportunity to declare variable i there. Latest edit: code moved into brackets of for loops to save two semicolons.)

t[420],j,l,x,y;f(p,d){int z,q,k;for(k=6;k--;t[q]&!t[p+z]?t[q]=0,f(q,d+1),t[q]=1:0)z="AST?-,"[k]-64,q=p+z*2;l=d>l?d:l;}main(int i,char**s){for(i=840;i--;x>3&y>5&x+y<23|x<13&y<15&x+y>13?i>420?t[i-420]=49-s[1][j++]:t[i]||f(i,0):0)x=i%20,y=i/20%21;printf("%d",l);}

Explanation

This relies on a 20x21 board which looks like this, initially filled with zeroes when the program starts (this ASCII art was generated by a modified version of the program, and as the i loop counts downwards, zero is in the bottom right corner):

....................
....................
...............#....
..............##....
.............###....
............####....
.......#############
.......############.
.......###########..
.......##########...
.......#########....
......##########....
.....###########....
....############....
...#############....
.......####.........
.......###..........
.......##...........
.......#............
....................
....................

Loop i runs through this board twice, using x and y to calculate whether a square actually belongs to the checkerboard or not (this requires 6 separate inequalities in x and y.)

If it does, the first time round it fills the squares, putting a 0 (falsy) for a 1 (occupied) and a 1 (truthy) for a 0 (unoccupied). This inversion is important, because all out-of-bounds squares already contain a 0, which means they resemble occupied squares and it is clear they can't be jumped into, without the need for a specific check.

The second time round, if the square is occupied (contains 0) it calls the function f that searches for the moves.

f searches recursively in the 6 possible directions encoded by +/-1 (horizontal), +/-20 (vertical) and +/-19 (diagonal) encoded in the expression "AST?-,"[k]-64. When it finds a hit, it sets that cell to a 0 (occupied) before calling itself recursively, then sets it back to 1 (empty) when the function is returned. The cell value must be changed before the recursive call to prevent hopping into that cell more than once.

Ungolfed code

char s[999];                           //input string.
t[420],i,j,l,x,y;                      //t=board. i=board counter, j=input counter. l=length of longest hop found so far.

f(p,d){                                //p=position, d= recursion depth.
  //printf("%d,%d ",p,d);              //debug code: uncomment to show the nodes visited.
  int k,z,q;                           //k=counter,z=displacement,q=destination
  for(k=6;k--;)                        //for each direction
    z="AST?-,"[k]-64,                  //z=direction
    q=p+z*2,                           //q=destination cell
    t[q]&!t[p+z]?                      //if destination cell is empty (and not out of bounds) and intervening cell is full
      t[q]=0,f(q,d+1),t[q]=1           //mark destination cell as full, recurse, then mark it as empty again.
      :0;
  l=d>l?d:l;                           //if d exceeds the max recorded recursion depth, update l
}

main(){
  gets(s);                             //get input
  for(i=840;i--;)                      //cycle twice through t
    x=i%20,                            //get x
    y=i/20%21,                         //and y coordinates
    x>3&y>5&x+y<23|x<13&y<15&x+y>13?   //if they are in the bounds of the board
      i>420?
        t[i-420]=49-s[j++]             //first time through the array put 0 for a 1 and a 1 for a 0 ('1'=ASCII49)
        :t[i]||f(i,0)                  //second time, if t[i]=0,call f(). 
       //,puts("")                     //puts() formats debug output to 1 line per in-bounds cell of the board
      :0;
  printf("%d",l);                      //print output
}