Score a game of Go

Question

Scoring a Go game is a task that is not all too easy. In the past there have been several debates about how to design rules to cover all the strange corner cases that may occur. Luckily, in this task you don't have to do complicated stuff like life and death or seki detection. In this task, you have to implement a program that scores a game according to the Tromp-Taylor rules without Komi.
The scoring procedure is pretty simple:

a point P, not colored C, is said to reach C, if there is a path of (vertically or horizontally) adjacent points of P's color from P to a point of color C.
A player's score is the number of points of her color, plus the number of empty points that reach only her color.

For example, consider the following board. X, O and - denote black, white and uncoloured intersections:

- - - X - O - - -
- - - X - O - - -
- - - X - O - - -
- - - X O - - O -
X X X O - O O - -
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -

Applying the scoring rule yields the following result. x, o and - represent uncoloured intersections that are counted as black, white and nobody's points.

x x x X - O o o o
x x x X - O o o o
x x x X - O o o o
x x x X O o o O o
X X X O o O O o o
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -

According to the diagram, black has 23 points, white has 29 points of territory. Thus, your program should print W+6 for this board.

I hope it is clear enough this way.

Input and output

The input is a string that contains exactly n² of the characters X, O, - where n is not known at compile time. Your program should ignore all other characters in the input stream. Behavior is undefined if there is no integer n such that the amount of XO- characters equals n². You may assume that n is in [0, 255].

The sequence of characters is to be interpreted as a Go-board of n rows and columns. The output is the absolute value of the difference of the total amount of points of white and black in decimal representation. If white has more points, it is prefixed by W+, if black has more points it is prefixed by B+. In the case that both players have an equal amount of points, the output is Jigo.

Input is to be read in an implementation defined manner. Input may not be part of the source code.

Winning conditions

This is code-golf. Usual code-golf conventions apply. The submission with the least amount of characters in its source wins. Only programs that fully implement the specification may win.

Test cases

Input:

- - - X - O - - -
- - - X - O - - -
- - - X - O - - -
- - - X O - - O -
X X X O - O O - -
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -

Output: W+6

Input:

Xavier is insane -- says Oliver

Output: Jigo

Inpout:

Code-Golf

Output: Jigo

Input:

-XXXXXXX-XOOOOOOOXXO-OXXXOXXXOX--XOXXOOX
-
XOOXXOX--XOXXXOXXXO-OXXOOOOOOOX-XXXXXXX-

Output: B+21

Input:

- - X O O O O X X - - - - - - X O O -
- X X O X O X X O X X X X X X - X O -
- X O O X X X - O O O X O O X X X O -
- X O O O X X O O O O O O X X X O - -
- - X X O X - X X X X O O O O O O O -
- - X O O X X X - X X X O O O X X O -
- - X O - O X O X O O O O O X X X O -
- X O O - O O O X X X X X O O X O - -
- X X X O - - - O X O X X X O X O - -
X O O O O - - O - O O O O X X X O O -
X X O - - - O - - O O X X - - X X O O
X O O O - - O - O O X - - - - X O O X
- X X X O O X O O X X - - - - X X X X
X - X X X O X X O O X - - X X O X O O
X X O O X O X O X X - - - X O O O O -
X O - O X X X O X - - - - - X O - - -
O O - O X O O O O X X - X X X X O - -
O O - O O O X O X X - - X - X X O - -
- - O - - O X X X - - - - X O O O - -

Output: B+6

More testcases will come soon.

reference implementation

I have created a reference implementation written in ANSI C. This implementation reads input from the standard input and writes output to the standard output.

/* http://codegolf.stackexchange.com/q/6693/134
 * reference implementation
 * by user FUZxxl
 */

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

#define MAXBOARD 256

/* bit 0x01: black colour
 * bit 0x02: white colour
 * bit 0x04: there is a stone on the intersection
 */

enum colour {
    UNCOLOURED    = 0x0,
    BLACK_REACHED = 0x1,
    WHITE_REACHED = 0x2,
    BOTH_REACHED  = 0x3,
    HAS_STONE     = 0x4,
    BLACK         = 0x5,
    WHITE         = 0x6
};

static enum colour board[MAXBOARD*MAXBOARD] = { 0 };

static int bsize = 0;

static void read_input(void);
static void fill_board(void);
static void show_score(void);

int main() {
    read_input();
    fill_board();
    show_score();
    return EXIT_SUCCESS;
}

static void read_input(void) {
    int n = 0;
    int invalue;

    while ((invalue = getchar()) != EOF) {
        switch (invalue) {
            case '-': board[n++] = UNCOLOURED; break;
            case 'X': board[n++] = BLACK; break;
            case 'O': board[n++] = WHITE; break;
        }
    }

    while (bsize*bsize < n) bsize++;

    /* your program may exhibit undefined behavior if this is true */
    if (bsize*bsize != n) exit(EXIT_FAILURE);
}

static void fill_board(void) {
    int i,j;
    bool changes;
    enum colour here, top, bottom, left, right, accum;

    do {
        changes = false;

        for (i = 0; i < bsize; ++i) {
            for (j = 0; j < bsize; ++j) {

                here   = board[i*bsize+j];
                if (here >= BOTH_REACHED) continue;

                top    = i == 0 ? UNCOLOURED : board[(i-1)*bsize+j];
                left   = j == 0 ? UNCOLOURED : board[i*bsize+j-1];
                bottom = i == bsize-1 ? UNCOLOURED : board[(i+1)*bsize+j];
                right  = j == bsize-1 ? UNCOLOURED : board[i*bsize+j+1];

                accum = here | top | bottom | left | right;
                accum &= ~HAS_STONE;

                changes |= board[i*bsize+j] != accum;

                board[i*bsize+j] = accum;

            }
        }

    } while (changes);
}

static void show_score(void) {
    int w = 0, b = 0, n;

    for (n = 0; n < bsize*bsize; ++n) switch (board[n] & ~HAS_STONE) {
        case BLACK_REACHED: ++b; break;
        case WHITE_REACHED: ++w; break;
    }

    if (b != w)
        printf("%s%i\n",b>w?"B+":"W+",abs(b-w));
    else
        printf("Jigo\n");
}

Answer 1

GolfScript, 190 characters

{"XO-"?)},:v,.),\{\.*=}+,~:s.*:`0\,{s%!\2*+}/:r;88{0v@{=\2*+}+/}:%~79%1${{:<.r|r^2*|<2/r|r^|<2s?:h/|<h*|1$|1$^2`?(&}`*}:a~@@a\;.2$|2${^2*)2base{+}*}:m~@2$|@m-.{"BW"1/1$0>="+"@abs}{;"Jigo"}if

The script became much longer than I thought in the beginning. Pass any input on STDIN and the output will then be printed when the program terminates.

Answer 2

C (438 434 413 382 364 336 322 characters)

a;b[65536];c;d;e;f;g;main(){for(;d=getchar()+1;f++)b[f]=d-80?d-89?d-46?f--:0:5:6,
g+=g*g<f;while(!c++)for(d=g;d--;)for(e=g;e--;)(a=b[d*g+e])<3?a|=!!d*b[d*g+e-g]|!!
e*b[d*g+e-1]|(d<g-1)*b[d*g+e+g]|(e<g-1)*b[d*g+e+1],a&=~4,c&=b[d*g+e]==a,b[d*g+e]=
a:0;for(c=0;f--;)c+=b[f]%2-b[f]/2%2;printf(c?"%c+%i":"Jigo",c>0?66:87,abs(c));}

Newlines inserted for enhanced legibility.

This answer is essentially the reference solution but with all that useless stuff (such as types [who needs something different from int anyway?] and standards compliance [return value of main? please!])

Corrections and improvements

438 → 434

Dropped explicit initialization of variables after I convinced myself that they are automatically initialized to 0 according to standard.

434 → 413

Removed case statement: If an uncoloured intersection is reachable from both black and white, we can count it as one point for both to simplify the program. Switch of logical branches to avoid negation.

413 → 382

Assign d to getchar()+1 to save one pair of parenthesis. Under the assumption that b is initialized to zeroes, reorder case statements, discarding all break statements. (a>b?c:0) is longer than (a>b)*c. (d+1)*g+e is longer than d*g+e+g.

382 → 364

Improved looping, no newlines in the output, shorter output routines.

364 → 336

Got rid of that switch statement. (Thanks, Howard!), track difference of points for two characters. Negate c for one character. four characters in the big or clause.

336 → 323

Replacing & by % allows removal of braces for four characters. Fused the square-root with the input loop for nine or so characters (yeah!), removed an if for one char.

Answer 3

Ruby (314)

could be made shorter with some more time:

q={?-=>0,?X=>5,?O=>6};b=[];$<.chars{|c|(t=q[c])&&b<<t}
z=Math.sqrt b.size
loop{c=b.each_with_index.map{|h,i|
next h if h>2
x=i%z
y=i/z
u=y<1?0:b[i-z]
l=x<1?0:b[i-1]
d=y>z-2?0:b[i+z]
r=x>z-2?0:b[i+1]
~4&(h|u|d|l|r)}
break if c==b
b=c}
b.map!{|h|h&~4}
s=b.count(1)-b.count(2)
puts s==0?"Jigo":s>0?"B+#{s}":"W+#{-s}"