Компактный способ представления всех допустимых «строк» ​​в сетке крестики-нолики - PullRequest
Новая
       11

Компактный способ представления всех допустимых «строк» ​​в сетке крестики-нолики

1 голос
/ 05 июля 2010

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

Во-первых, доска представляется в виде одно- или двумерного массива, а строки явно определяются тройками позиций (числа - это пустые пробелы): 

board = [1, x, 3, 4, o, 6, 7, 8, x]

def match3(x,y,z)
  board[x] == board[y] && board[y] == board[z]
end

def winner
  match3(1,2,3) || match3(4,5,6) || ...
end

Это имеет преимущество немагической явности, но кажется многословным.

Другой подход заключается в использовании массива массивов и map + сокращение строк.Это немного лучше, но не до конца до конца: 

board = [[nil, 1, nil], [nil, -1, nil], [nil, nil, 1]]

def diag(x,y,z)
  [board[x/3,x%3], board[y/3,y%3], board[z/3,z%3]]
end

def winner
  rows = board + board.transpose << diag(0,4,8) << diag(2,4,6)
  rows.map { |r| r.reduce(:&) }.reduce { |m,c| m || c }
end

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

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

Мой псевдокод - Rubyish, но, пожалуйста, не стесняйтесь писать на любом языке, который вам нравится.Я видел гольф в крестики-нолики, и хотя некоторые из этих решений гениальны (особенно магические квадраты!), Я ищу что-то менее запутывающее.

1 Ответ

1 голос
/ 06 июля 2010

Система, которая намного быстрее и компактнее, должна использовать один бит для каждого квадрата. Текущее положение может быть сохранено в двух переменных: X содержит все метки «X» и O содержит все метки «O». Возможное кодирование для 9 квадратов, например 

 1   2   4
 8  16  32
64 128 256

В этой кодировке первая строка равна 1+2+4=7, а верхняя / левая-> нижняя / правая диагональ 1+16+256=273.

Проверка, выиграл ли X в первом ряду только if ((X & 7) == 7), другие проверки аналогичны, но с другими номерами вместо 7. Полная проверка победы становится ... 

def winner(p):
    for m in (7, 56, 448, 73, 146, 292, 273, 84):
        if p & m == m: return True
    return False
...