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 <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 behaviour if this is true */
    if (bsize * bsize != n) exit(EXIT_FAILURE);
}

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

    do {
        changes = 0;

        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 (105 bytes)

{'-XO'?}/]-1-.{2*3%}%{.,:N),{.*N=}?/{{[{.2$+1={+.}*}*]}%zip}N*[]*.1--,\}2*-.{.0>'W+B+'2/=\abs}{;'Jigo'}if

Online demo.

Flood-fill adapted from this earlier answer of mine.

The solution flood-fills one copy of the original board with X, and another with O. Thus empty cells which are reachable by both colours are scored for both, but cancel in the subtraction.

Answer 2

J (140 136 131 129 119 117 116 characters)

After ramping up my J skills, I can finally provide a submission in J. It's a little bit long though.

exit echo>(*{'Jigo';('B+',":);'W+',":@|)+/,-/1 2=/(]OR(0=[)*[:OR((,.|.)0,i:1)|.!.0])^:_~($~,~@%:@#)3-.~'-XO'i:1!:1]3

The algorithm implemented by this submission is very similar to the reference implementation but different in the way occupied fields are handled.

Here is the solution split up into more parts for easier understandability. The golfed solution is slightly different from that, but the difference isn't very large.

input =. 3 -.~ '-XO' i: 1!:1 ] 3
board =. ($~ ,~@%:@#) input
NB. shift up, down, left, right
rotm =. (,. |.) 0 , i: 1
fill =. ] OR (0 = [) * [: OR rotm |.!.0 ]
filledboard =. fill^:_~ board
score =. +/ , -/ 1 2 =/ filledboard
echo > (* { 'Jigo' ; ('B+' , ":) ; ('W+', ":@|)) score
exit 0

Answer 3

C (438 434 413 382 364 336 322 298 294 292 290 characters)

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

All newlines except the first one inserted for enhanced legibility. A commented and slightly more legible version can be found here.

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.

323 → 298

Introduced the macro H to replace the often occuring and bulky b[d*g+e] construct.

298 → 294

Change a&=~4 to a&=3 as we only every observe the lowest three bytes of a. Also changed to loop body from ((a=I])<3)?a|=... to I]<3?a=I]|... which is two characters shorter. Also, introduce h instead of reusing c, which is one character shorter.

294 → 292

Eliminate h variable. If we test c with !c-- instead of !c++, c equals 0 at the end of the flood-fill loop and can thus be used for the purpose h was used before (i.e. score keeping).

292 → 290

Replace the construct d-46?f--:0 with d-46&&f-- which is shorter by a character and combine the two assignments to a in the inner loop.

Answer 4

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 5

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}"