задачка с собеседования: кто выиграл в крестики-нолики

redzor

В ходе собеседовании написал функцию, которая возвращает, кто выиграл в крестики-нолики. На вход принимается доска и тип игрока. Выигравший обязательно есть. Еще на доске могут быть незаполненные ячейки. Язык Ява, но, не принципиально. Интересуют вообще, какие есть варианты, как это можно сделать.

katrin2201

задаешь четыре направления сдвига (0, 1 (1, 1 (1, 0 (-1, -1)
и каждым из сдвигов ходишь из крайних клеток, считая подряд идущие значки

redzor

а по-проще можно?

katrin2201

проще всмысле вычислительной сложности? сомневаюсь.
тут и так линейная сложность от кол-ва клеток на доске.

NataNata

(11, 12, 13)
(21, 22, 23)
(31, 32, 33)
1) если 11 непусто, то если 11,12,13 значки одного типа, то выиграл значок из клетки 11
2) поле симмертично относительно поворота на 90 градусов для этого случая, поэтому делаем аналогичную проверку, поворачивая поле на 90 градусов еще 3 раза
3) если 12 непусто, то если 12,22,13 значки одного типа, то выиграл значок из клетки 12
4) поворачиваем поле на 90 градусов и проверяем аналогично
5) если 11 непусто, то если 11,22,33 значки одного типа, то выиграл значок из клетки 11
6) поворачиваем поле на 90 градусов и проверяем аналогично
для случае поля NxN алгоритм легко обобщается
если известно, что поле может быть "некорректно", то собрать все возможные выигрыши и ругаться матом, если найдено более одного

redzor

я имел в виду, объяснить по-проще, я ничего не понял.

stm6692945

ну допуситим так
доска:
a1 b1 c1
a2 b2 c2
a3 b3 c3
все эти переменные могут быть либо 1 либо 0
 


int fun (int a1,....., int c3)

{

if ( (a1*b1*c1)||(a2*b2*c2)||(a3*b3*c3)||(a1*a2*a3)||(b1*b2*b3)||(c1*c2*c3)||(a1*b2*c3)||(c1*b2*a3) )  return 1

else return 0



}

redzor

да там при любом раскладе сложность линейная. Только вопрос в коэффициенте. Я как сделал, сначала пройдем по всем строчкам, потом по всем столбцам, потом по 2м диагоналям, если крестик, прибавляем 1, если нолик - вычитаем, если пусто, то текущую строку\столбец\диагональ дальше не проверяем. После каждой такой проверки, сравниваем, если сумма 3 и игрок крестик возвращаем тру, если -3 и нолик, тоже тру.

katrin2201

а
ну у тебя есть координаты клетки
ты можешь ходить по клеткам в четырех направлениях - добавляешь к координатам текущей клетки один из векторов, что я выше написал - получаешь следующую
ну и дальше цикл
для каждой внешней клетки {
для каждого направления {
идти по выбранному направлению, от выбранной клетки, пока не кончится доска, считая идущие подряд значки, завершаясь, если нашел подряд нужное число значков
}
}

stm6692945

девелопмент совсем отупел

katrin2201

я то же самое в принципе и написал, только обобщил для доски произвольных размеров

katrin2201

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

redzor

кстати, оч. круто, единственная проблема - не отражена ситуация, когда клетка пустая, я брал значение клетки за Boolean, т.е. может быть тру, фалс и нул (пустая). И еще не понятно, как такой алгоритм масштабировать. В смысле, чтобы работало не для известного заранее размера, а просто передаешь массив, а дальше он сам на основании его измерений в цикле или как-то там еще обрабатывается.

redzor

не понял, почему в четырех-то направлениях. Если клетка угловая, то в трех, если боковая, тоже в пяти, если центральная, то шести

katrin2201

например, из верхней правой клетки два пути просто будут нулевой длины... итд соответственно
иначе ты попадаешь на кучу ненужных в общем-то ифов

redzor

че-то я ни в один вариант не втупил кроме кпбисовского, попробую завтра с утра еще раз посмотреть.

andra1980

да там при любом раскладе сложность линейная. Только вопрос в коэффициенте. Я как сделал, сначала пройдем по всем строчкам, потом по всем столбцам, потом по 2м диагоналям, если крестик, прибавляем 1, если нолик - вычитаем, если пусто, то текущую строку\столбец\диагональ дальше не проверяем. После каждой такой проверки, сравниваем, если сумма 3 и игрок крестик возвращаем тру, если -3 и нолик, тоже тру.
Насколько я понимаю, твой алгоритм имеет квадратичную сложность. Если размер доски NxN, то ты проверишь 2N+2 рядов по N клеток каждый. Т.е. всего O(N^2) проверок.

redzor

линейная от числа элементов, а число элементов NxN

vall

#define LINE(x,y,dx,dy) {{x,y},{x+dx,y+dy},{x+dx*2,y+dy*2}}
int lines[][3][2] = {
LINE(0,0,1,0
LINE(0,1,1,0
LINE(0,2,1,0
LINE(0,0,0,1
LINE(1,0,0,1
LINE(2,0,0,1
LINE(0,0,1,1
LINE(2,0,-1,1
LINE(-1,-1,0,0
};
дальше очевидно

redzor

кажется, я реально не туда за ответами пришел.

katrin2201

собсно, весь алгоритм - это Board#getWinner
все остальное - синтактик шугар


import java.util.HashSet;

import java.util.Set;



/**

 * User: 

 * Date: Oct 6, 2010

 */

public class Gomoku {



    public static final int BOARD_SIZE = 5;

    public static final int WINNING_STREAK = 3;



    public enum Direction {

        RIGHT (1, 0

        DOWN (0, 1

        DOWNLEFT (-1, 1

        DOWNRIGHT (1, 1);



        public final int deltaX;

        public final int deltaY;



        Direction(int deltaX, int deltaY) {

            this.deltaX = deltaX;

            this.deltaY = deltaY;

        }

    }



    public enum Sign {

        X,

        O,

        EMPTY

    }



    public static class Point {



        private int x, y;



        public Point(int x, int y) {

            this.x = x;

            this.y = y;

        }



        public Point(Point point) {

            this.x = point.x;

            this.y = point.y;

        }



        public void shiftTo(Direction dir) {

            x += dir.deltaX;

            y += dir.deltaY;

        }



        public int getX {

            return x;

        }



        public int getY {

            return y;

        }



        public boolean isInRange {

            return x >=0 && y >= 0 && x < BOARD_SIZE && y < BOARD_SIZE;

        }



        public static Set<Point> borderPoints {

            Set<Point> result = new HashSet<Point>

            for(int i=0; i<BOARD_SIZE; i++) {

                result.add(new Point(i, 0;

                result.add(new Point(0, i;

                result.add(new Point(BOARD_SIZE-1, i;

            }

            return result;

        }



    }



    public static class Board {



        private Sign[][] gameField;



        public Board {

            gameField = new Sign[BOARD_SIZE][];

            for(int i=0; i<BOARD_SIZE; i++) {

                gameField[i] = new Sign[BOARD_SIZE];

                for(int j=0; j<BOARD_SIZE; j++) {

                    gameField[i][j] = Sign.EMPTY;

                }

            }

            gameField[0][0] = Sign.X;

            gameField[1][1] = Sign.X;

            gameField[2][2] = Sign.X;

        }



        private Sign getSignAt(Point p) {

            return gameField[p.getX][p.getY];

        }



        public Sign getWinner {

            for (Point point : Point.borderPoints {

                for (Direction dir : Direction.values {

                    Point curPoint = new Point(point);

                    Sign lastSign = Sign.EMPTY;

                    int streak = 0;



                    while(curPoint.isInRange {

                        Sign curSign = getSignAt(curPoint);

                        if(lastSign.equals(curSign {

                            streak++;

                        } else {

                            streak = 1;

                            lastSign = curSign;

                        }

                        if(lastSign != Sign.EMPTY && streak == WINNING_STREAK) {

                            return lastSign;

                        }

                        curPoint.shiftTo(dir);

                    }

                }

            }

            return Sign.EMPTY;

        }

    }



    public static void main(String[] args) {

        System.out.println(new Board.getWinner;

    }



}

stm6692945

ну смотри есть доска на ней N = n*n чисел
a(1) a(2) .... a(n*n)
На доске они расположены так:
a(1) a(2) a(n)
........................
a(n*n-n) a(n*n-n+1) a(n*n)
если крестик то число равно 1
если пустое то число равно 0.5
если нолик то число равно 0
Условие того что выграл "нолик" это то что сумма чисел в каком то ряду равно нулю
в остальных случаях выграл "кресит"
 


int fun(Array c)

{

N = c.lenth; - определяем число элементов

D = Math.sqrt(N) - число столбцок

int Sum = 0 - тут будем считать сумму элементов в ряду или стобце

int Win = 1;



// проверяем на наличие выграша по строке

for (i=1;i<D;i++) 

       {

        for (k=1;k<D;k++) 

               {

                Sum = Sum + c(i*(D-1)+k-1) - здесь суммируем элементы по строке

               } 

        if (Sum==0) Win =0 - выграл "нулик"

       Sum = 0; обнуляем накопленную сумму по строке.

       }



// проверяем на наличие выграша по столбцам

for (i=1;i<D;i++) 

       {

        for (k=1;k<D;k++) 

             {

            Sum = Sum + c(i-1+k(D-1 - здесь суммируем элементы по столбцу

            }

       if (Sum==0) Win =0 - выграл "нулик"

       Sum = 0; обнуляем накопленную сумму по столбцу.

      }



// теперь проверяем 2 диагонали



for (i=1;i<D;i++) 

    {

     Sum = Sum + c(i*i);

     if (Sum==0) Win = 0

     Sum =0;

    }



for (i=1;i<D;i++) 

    {

    Sum = Sum + c(i*D-i+1);

    if (Sum==0) Win = 0

   Sum =0;

   }





return Win;



}

redzor

ох, блин, похоже ты тот, кто им был нужен

katrin2201

Спасибо за комплимент, если это, конечно, он =)
Собеседование в какую организацию, если не секрет?

redzor

в епам, в америку

katrin2201

прикольно. не в гугловый епам случайно? =)

procenkotanya



static bool

xo_win_1(unsigned int f)

{

  return f & (f >> 3) & (f >> 6

          || (f & (f >> 1) & (f >> 2) & 0111)

          || f & 0421) == 0421)

          || f & 0124) == 0124;

}



bool

xo_win(unsigned player, unsigned field[3][3])

{

  unsigned mask = 0;

  for (int i = 0; i < 3; i++)

    for (int j = 0; j < 3; j++)

      mask = (mask << 1) | (field[i][j] == player);

  return xo_win_1 (mask);

}

Я бы не прошёл, да?

redzor

они не говорят, в какую компанию, это конфиденциальная информация.

katrin2201

зато экзамен по дискре, небось, сдал на 5 :grin:

redzor

я не знаю, какие у них для сишников задачи

katrin2201

ясн. вообще иногда вроде говорят, it depends видимо...

redzor

можешь сам проверить ;)

redzor

там несколько вариантов по размещению, наверное для нескольких клиентов ищут

katrin2201

это да, это наверняка

redzor

я имел в виду, что не говорят, потому что сами не знают, кто тебя возьмет.

katrin2201

а, тоже вариант, да, согласен

pilot

http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B5%D1%81%D1%82%... :
 
Игроки по очереди ставят на свободные клетки поля 3х3 знаки (один всегда крестики, другой всегда нолики). Первый, выстроивший в ряд 3 своих фигуры по вертикали, горизонтали или диагонали, выигрывает. Первый ход делает игрок, ставящий крестики.

Если крестиков на поле больше, выиграл тот, который ставил крестики, если поровну — тот, который ставил нолики. :p

redzor

в условии задачи не сказано, кто ходил первый

pilot

в условии задачи не сказано, кто ходил первый
Сначала как раз хотел спросить сказано ли такое в условии задачи, но потом понял что не помню чтобы кто-нибудь начинал игру с нолика. И википедия тоже :)
В общем я на что намекаю: отметившиеся в треде вмкшники никак в своих алгоритмах не учли что крестиков и ноликов почти поровну.

katrin2201

x . o
. x o
x . o
mask для крестиков будет 100010100 и выдаст true по первой скобочке, не?
пожалуй, с дискрой я промахнулся-поторопился =)

procenkotanya

x . o
. x o
x . o
mask для крестиков будет 100010100 и выдаст true по первой скобочке, не?
пожалуй, с дискрой я промахнулся-поторопился =)
(100010100 & 100010 & 100) == 0

katrin2201

понял
пошел спать =)
и дискра нипричем, полный фейл =)

pilot

Хорошая показательная задачка:
Жава-программист наворотил кучу кода, Сишник посчитал битики, а Python использовал antigravity:
def f(field, user): return reduce(lambda sum, row: sum + reduce(lambda rowsum, cell: rowsum + {'0': -1, 'x': 1, '*':0}[cell], row, 0 field, 0) != user


>>> field = [['x', '*', '0'], ['*', 'x', '0'], ['x', '*', '0']]

>>> f(field, 0)

False

>>> f(field, 1)

True

procenkotanya

а Python использовал antigravity:
def f(field, user): return reduce(lambda sum, row: sum + reduce(lambda rowsum, cell: rowsum + {'0': -1, 'x': 1, '*':0}[cell], row, 0 field, 0) != user
и написал при этом код, не решающий задачу

pilot

и написал при этом код, не решающий задачу
Очень может быть, я последние пару лет пишу в основном письма и тикеты :(
Что, кстати, не работает, если не секрет?

danilov

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


x - 0

x x 0

- x 0

pilot

К тому же твоя задача выдаст неправильный результат при
Это некорректное условие.
Твоё решение подходит для второго. А на собесе тебе пришлось бы решить исходную задачу.
Почему же? Я вроде и решил исходную задачу. Я, собственно, поддерживаю обсуждение потому как мне интересно что сказали бы на собеседовании :)

danilov

> Это некорректное условие.
Чем, если не секрет?
Выигравший очень даже есть - нолики.

pilot

Чем, если не секрет?
Вроде я цитировал правила, ты как олимпиадник со стажем давно уже понял о чем решение, я верю :)

danilov

> Вроде я цитировал правила, ты как олимпиадник со стажем давно уже понял о чем решение, я верю
Тоже немного понудю )
Приведённая мной картинка хорошо вписывается в цитируемые тобой правила. Можешь самостоятельно убедиться, я верю, хоть ты и не олимпиадник.

katrin2201

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

pilot

Все короткие приведенные здесь решения заточены на 3х3.
Да, и такого размера тоже кстати не было в условии :D
Если уж месье хочет померяться, пускай приводит свое решение для произвольного размера доски, где никто ничего не гарантирует, и мы посравниваем.

Да я .

katrin2201

Да я уже .
понял отстал
Оставить комментарий
Имя или ник:
Комментарий: