Pythonで「四角に切れ」を解く＞問題を解く

問題を解く

solver.py のコード

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import sys

import file
import board

def mainLoop(board):
    f = True                        # ループ停止判定用
    while f:
        f = False
        for a in board.squareIDs:   # 全長方形に処理
            b = []
            for c in a.squares:     # 全長方形の候補に処理
                if isConteinOther(board, c, a):
                    f = True
                else:
                    b.append(c)
            a.squares = b
            c = products(b)         # 共通に含まれるマス
            if occupation(board, c, a): # マスにIDを書く
                f = True

def isConteinOther(board, square, myID): # マスに他のIDがあるか
    for x in range(square.x1, square.x2 + 1):
        for y in range(square.y1, square.y2 + 1):
            id = board.territory[y][x]
            if id is None: continue
            if id is myID: continue
            return True
    return False

def products(squares):              # 全長方形の共通部分
    if squares is None: return None
    if len(squares) == 1: return squares[0]
    r = squares[0]
    for a in squares:
        r = r.product(a)
    return r

def occupation(board, square, myID):# マスにIDを書く
    f = False
    for ix in range(square.x1, square.x2 + 1):
        for iy in range(square.y1, square.y2 + 1):
            if board.territory[iy][ix] is None:
                board.territory[iy][ix] = myID
                f = True
    return f

def outputData(board):              # 出力用のデータを生成
    return [[x.id for x in y] for y in board.territory ]

def solver(inFileName, outFileName):
    q = file.readCsv(inFileName)
    b = board.QuestBoard(q)
    mainLoop(b)
    o = outputData(b)
    file.writeCsv(outFileName, o)

if __name__ == '__main__':
    solver('testData.csv', 'testOut.csv')

mainLoopが問題を解くためのループになります。
リストの長方形の候補が他の長方形のIDが書かれたマスに重なる場合にその長方形の候補をリストから削除するのと、
リスト内の全ての長方形の候補で共通に含まれるマスにIDを書き込む処理をします。

isConteinOtherはループのサブルーチンで、長方形の候補が他の長方形のIDが書かれたマスに重なるかを判定します。

productsもループのサブルーチンで、全ての長方形の候補で共通に含まれるマスを計算します。

occupationもループのサブルーチンで、共通に含まれるマスにIDを書き込む処理をします。

outputDataは出力用のデータを生成する処理です。

solverは上記の処理の呼び出し元です。

outputDataでリスト内包表記を使用しています。
２次元配列を元に、各要素からidだけを取出した２次元配列を作っています。

戻る