Оценка игры в го

23

Забить игру в Го - задача не из легких. В прошлом было несколько споров о том, как разработать правила, чтобы охватить все странные случаи, которые могут возникнуть. К счастью, в этом задании вам не нужно делать сложные вещи, такие как жизнь и смерть или обнаружение секи. В этом задании вы должны реализовать программу, которая оценивает игру по правилам Тромпа-Тейлора без Коми.
Процедура подсчета очков довольно проста:

говорят, что точка P, не окрашенная в C, достигает C, если существует путь (по вертикали или горизонтали) смежных точек цвета P от P до точки цвета C.
Оценка игрока - это количество очков ее цвета. плюс количество пустых точек, которые достигают только ее цвета.

Например, рассмотрим следующую доску. X, OИ -обозначают черные, белые и неокрашенные перекрестки:

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

Применение правила оценки дает следующий результат. x, 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
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 - - -

Согласно диаграмме, у черных 23 очка, у белых 29 точек территории. Таким образом, ваша программа должна печатать W+6для этой доски.

Я надеюсь, что так понятно.

Вход и выход

Вход является строкой , которая содержит ровно n² из символов X, O, -где п не известен во время компиляции. Ваша программа должна игнорировать все другие символы в потоке ввода. Поведение не определено, если нет такого целого числа n , что количество XO-символов равно n² . Вы можете предположить, что n находится в [0, 255] .

Последовательность символов следует интерпретировать как доску из n строк и столбцов. На выходе получается абсолютное значение разницы общего количества точек белого и черного в десятичном представлении. Если белые имеют больше очков, он предваряется W+, если черные имеют больше очков он приставка B+. Если у обоих игроков одинаковое количество очков, результат будет Jigo.

Ввод должен быть прочитан способом, определяемым реализацией. Ввод не может быть частью исходного кода.

Условия выигрыша

Это код-гольф. Применяются обычные правила игры в гольф. Представление с наименьшим количеством символов в источнике выигрывает. Только программы, которые полностью реализуют спецификацию, могут победить.

Контрольные примеры

Входные данные:

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

Выход: W+6

Входные данные:

Xavier is insane -- says Oliver

Выход: Jigo

Inpout:

Code-Golf

Выход: Jigo

Входные данные:

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

Выход: B+21

Входные данные:

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

Выход: B+6

Скоро появятся новые тесты.

эталонная реализация

Я создал эталонную реализацию, написанную на ANSI C. Эта реализация считывает ввод со стандартного ввода и записывает вывод в стандартный вывод.

/* 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");
}
code-golf game graph-theory board-game go FUZxxl
источник
Предположительно, вы имеете в виду последний выход W+7?
dmckee
Нет ... Как вы пришли к такому выводу?
FUZxxl
Э - э ... Я предположил , что S+была опечатка (потому что ранее перечисленные возможные выходные или как W+, B+или Jigo) , и я смотрел на мою клавиатуру и увидел Sрядом W... Или вы используете Дворжака?
dmckee
@dmckee Я полагаю, что "S" происходит от немецкого "Schwarz" вместо "Black".
Говард
Ох ... Ты прав. Извините за это
FUZxxl

Ответы:

2

GolfScript (105 байт)

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

Демо онлайн .

Flood-fill адаптирован из этого моего предыдущего ответа .

Решение заполняет одну копию исходной доски X, а другую - O. Таким образом, пустые ячейки, доступные обоим цветам, оцениваются для обоих, но отменяются при вычитании.

Питер Тейлор
источник
Справедливо. Вы можете выиграть этот раунд.
FUZxxl
6

C ( 438 434 413 382 364 336 322 298 294 292 290 знаков)

#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));}

Все символы новой строки, кроме первой, вставлены для улучшения читаемости. Комментируемую и чуть более разборчивую версию можно найти здесь .

Этот ответ по сути является эталонным решением, но со всеми этими бесполезными вещами (такими как типы [кому что-то нужно от чего-либо отличного int?] И соответствие стандартам [возвращаемое значение main? Пожалуйста!])

Исправления и улучшения

438 → 434

Отбросил явную инициализацию переменных после того, как убедился в том, что они автоматически инициализируются 0согласно стандарту.

434 → 413

Утверждение удаленного случая: если неокрашенное пересечение достижимо как из черного, так и из белого, мы можем посчитать его как одно очко для упрощения программы. Переключение логических веток, чтобы избежать отрицания.

413 → 382

Назначьте, dчтобы getchar()+1сохранить одну пару скобок. В предположении, что bинициализируется в нули, изменить порядок caseзаявлений, отбрасывая все breakутверждения. (a>b?c:0)длиннее чем (a>b)*c. (d+1)*g+eдлиннее чем d*g+e+g.

382 → 364

Улучшены циклы, нет новых строк в выводе, более короткие процедуры вывода.

364 → 336

Избавился от этого switchзаявления. (Спасибо, Говард!), Отслеживайте разницу очков для двух персонажей. Отрицание cза одного персонажа. четыре символа в большом или оговорке.

336 → 323

Замена &на %позволяет удалить фигурные скобки для четырех символов. Слил квадратный корень с входным циклом для девяти или около того символов (да!), Удалил ifдля одного символа.

323 → 298

Введен макрос Hдля замены часто встречающейся и громоздкой b[d*g+e]конструкции.

298 → 294

Измените a&=~4на, a&=3поскольку мы наблюдаем только самые младшие три байта a. Также изменено тело цикла, ((a=I])<3)?a|=...на I]<3?a=I]|...которое короче два символа. Кроме того, введите hвместо повторного использования c, что на один символ короче.

294 → 292

Устранить hпеременную. Если мы протестируем cс !c--вместо !c++, cравно 0 в конце цикла наводнения заполнения и , таким образом , может быть использована для этой цели hбыла использована ранее (т.е. балла держать).

292 → 290

Заменить конструкцию d-46?f--:0с d-46&&f--которой короче по характеру и объединить эти два задания , чтобы aво внутреннем цикле.

FUZxxl
источник
1
Вы можете заменить оператор switch чем-то вроде {b[f]=d-80?d-89?d-46?f--:0:5:6;f++;}сохранения нескольких символов.
Говард
@ Ховард: Да. Это сработало очень хорошо! Спасибо
FUZxxl
«Для повышения разборчивости» - как бы.
Томсминг
@tomsmeding Ну, прокрутка одной строки гораздо менее читабельна. Кроме того, комментируемая версия связана с.
FUZxxl
@FUZxxl Это было в шутку. :) Кроме того, вы правы, говоря, что это лучше, чем на 1 линии.
Томсминг
6

J ( 140 136 131 129 119 117 116 знаков)

После наращивания своих навыков в области J, я, наконец, могу представить представление в J. Хотя это немного долго.

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

Алгоритм, реализованный в этом представлении, очень похож на эталонную реализацию, но отличается тем, как обрабатываются занятые поля.

Вот решение, разделенное на несколько частей, для облегчения понимания. Решение для игры в гольф немного отличается от этого, но разница не очень большая.

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
FUZxxl
источник
5

GolfScript, 190 символов

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

Сценарий стал намного длиннее, чем я думал в начале. Передайте любой ввод в STDIN, и затем вывод будет напечатан после завершения программы.

Говард
источник
2

Рубин (314)

можно сделать короче с еще немного времени:

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}"
jsvnm
источник