二角取り生成

nikakudori.py

#!/usr/bin/env python2.7
# coding: utf-8

from __future__ import print_function
from __future__ import division


class Board(object):
    def __init__(self, W, H):
        assert W * H % 4 == 0
        self.W = W
        self.H = H
        self.fields = {(x, y): None
                       for x in range(self.W + 2) for y in range(self.H + 2)}

    def is_edge(self, p):
        '''pが縁か'''
        return (p[0] == 0 or p[0] == self.W + 1 or
                p[1] == 0 or p[1] == self.H + 1)

    def empty_fields(self):
        '''縁以外の空マス'''
        return [p for p, v in self.fields.items()
                if v is None and not self.is_edge(p)]

    def horizontally_connected_fields(self, p):
        '''pの横方向に続く空マス'''
        y = p[1]
        x_left = p[0]
        while x_left >= 0 and self.fields[x_left, y] is None:
            x_left -= 1
        x_right = p[0]
        while x_right <= self.W + 1 and self.fields[x_right, y] is None:
            x_right += 1
        return [(x, y) for x in range(x_left, x_right + 1)]

    def vertically_connected_fields(self, p):
        '''pの縦方向に続く空マス'''
        x = p[0]
        y_top = p[1]
        while y_top >= 0 and self.fields[x, y_top] is None:
            y_top -= 1
        y_bottom = p[1]
        while y_bottom <= self.H + 1 and self.fields[x, y_bottom] is None:
            y_bottom += 1
        return [(x, y) for y in range(y_top, y_bottom + 1)]

    def connected_fields(self, p):
        '''pから続きになった空マス'''
        fields = set()
        front_fields = set((p,))
        while front_fields:
            field = front_fields.pop()
            for f in (self.empty_adjacent_fields(field)
                    + self.empty_edge_fields(field)):
                if f not in fields and f not in front_fields:
                    front_fields.add(f)
            fields.add(field)
        return fields

    def is_straightly_connected(self, p1, p2):
        '''p1, p2が直線上に接続されてるか'''
        if p1[0] == p2[0]:
            x = p1[0]
            y1 = min(p1[1], p2[1])
            y2 = max(p1[1], p2[1])
            for y in range(y1, y2 + 1):
                if self.fields[x, y] is not None:
                    return False
            return True
        elif p1[1] == p2[1]:
            y = p1[1]
            x1 = min(p1[0], p2[0])
            x2 = max(p1[0], p2[0])
            for x in range(x1, x2 + 1):
                if self.fields[x, y] is not None:
                    return False
            return True
        else:
            return False

    def is_nikaku_connected(self, p1, p2):
        shared_x = {p[0] for p in self.horizontally_connected_fields(p1)}
        shared_x &= {p[0] for p in self.horizontally_connected_fields(p2)}
        for x in shared_x:
            if self.is_straightly_connected((x, p1[1]), (x, p2[1])):
                return True
        shared_y = {p[1] for p in self.vertically_connected_fields(p1)}
        shared_y &= {p[1] for p in self.vertically_connected_fields(p2)}
        for y in shared_y:
            if self.is_straightly_connected((p1[0], y), (p2[0], y)):
                return True
        return False

    def is_adjacent(self, p1, p2):
        return -1 <= p1[0] - p2[0] <= 1 and -1 <= p1[1] - p2[1] <= 1

    def adjacent_fields(self, p):
        fields = []
        if p[0] != 1:
            fields.append((p[0] - 1, p[1]))
        if p[0] != self.W:
            fields.append((p[0] + 1, p[1]))
        if p[1] != 1:
            fields.append((p[0], p[1] - 1))
        if p[1] != self.H:
            fields.append((p[0], p[1] + 1))
        return fields

    def empty_adjacent_fields(self, p):
        return [p for p in self.adjacent_fields(p) if self.fields[p] is None]

    def edge_fields(self, p):
        edge_fields = set()
        if p[0] == 1:
            edge_fields |= {(1, y) for y in range(1, self.H + 1)}
        elif p[0] == self.W:
            edge_fields |= {(self.W, y) for y in range(1, self.H + 1)}
        if p[1] == 1:
            edge_fields |= {(x, 1) for x in range(1, self.W + 1)}
        elif p[1] == self.H:
            edge_fields |= {(x, self.H) for x in range(1, self.W + 1)}
        return list(edge_fields)

    def empty_edge_fields(self, p):
        return [p for p in self.edge_fields(p) if self.fields[p] is None]

    def sub_empty_fields(self):
        empty_fields = set(self.empty_fields())
        sub_empty_fields = []
        while empty_fields:
            fields = set(self.connected_fields(empty_fields.pop()))
            empty_fields -= fields
            sub_empty_fields.append(fields)
        return sub_empty_fields

    def __str__(self):
        lines = []
        for y in range(1, self.H + 1):
            figs = [self.fields[x, y] or ' ' for x in range(1, self.W + 1)]
            lines.append(' '.join(figs))
        return '\n'.join(lines)


def count_adjacent_connected(board):
    count = 0
    for x1 in range(1, board.W):
        x2 = x1 + 1
        for y1 in range(1, board.H):
            y2 = y1 + 1
            if (board.fields[x1, y1] == board.fields[x1, y2]
                    or board.fields[x1, y1] == board.fields[x2, y1]):
                count += 1
    return count


def generate_board():
    import random
    import itertools

    W = 17
    H = 8
    board = Board(W, H)

    num_figures = W * H // 4
    assert num_figures <= 34
    figures = list('abcdefghijklmnopqrstuvwxyz0123456789'[:num_figures]) * 2
    random.shuffle(figures)

    trace = []
    for figure in figures:
        pairs = list(itertools.permutations(board.empty_fields(), 2))
        random.shuffle(pairs)
        for p1, p2 in pairs:
            # 移動可能な2点を選ぶ
            if board.is_nikaku_connected(p1, p2):
                f = board.connected_fields(p1)
                if len(f) > 4 and board.is_adjacent(p1, p2):
                    # 十分に広い空マス集合で隣接するマスが選ばれたら選び直し
                    continue
                board.fields[p1] = figure
                board.fields[p2] = figure
                for s in board.sub_empty_fields():
                    # 要素数が奇数の連続する空マスが発生するならマスを選び直す
                    if len(s) % 2 != 0:
                        board.fields[p1] = None
                        board.fields[p2] = None
                        break
                else:
                    # マスの確定
                    trace.append((p1, p2))
                    #print(board)
                    #print()
                    break
        else:
            print('あり得る？')  # TODO エラー処理なりなんなり
    return board, trace


def main():
    n = 1
    counts = []
    for _ in range(n):
        board, _ = generate_board()
        print(board)
        count = count_adjacent_connected(board)
        print(count)
        counts.append(count)
    print(sum(counts) / n)

if __name__ == '__main__':
    main()