findRoute01.py

import copy
from tqdm import tqdm


# ODリストを取得する
def getODs(list):
    results = []
    # 並び順の候補を取得する
    for o in removeDuplicates(getOrders(list)):
        # 経路を作成
        result = []
        for j in range(len(o) - 1):
            result.append([o[j], o[j + 1]])
        results.append(result)
    return results

# 並び順の候補を取得する
def getOrders(list):
    if len(list) == 1:
        return [[list[0]]]
    else:
        orders = []
        for i in range(len(list)):
            for o in getOrders(listExcluded(list, i)):
                orders.append([list[i]] + o)
        return orders

# 並び順の候補から逆順を削除
def removeDuplicates(orders):
    orders_out = []
    for order in orders:
        match = False
        for order_out in orders_out:
            match_local = True
            for i, v in enumerate(order):
                if order_out[-1 - i] != v:
                    match_local = False
                    break
            if match_local is True:
                match = True
                break
        if match is False:
            orders_out.append(order)
    return orders_out

# リストから指定idxを除いたリストを作成する
def listExcluded(list, idx):
    return [x for i, x in enumerate(list) if i != idx]


# ODから経路を探索する
def findRoute(size_x, size_y, posO, posD, route, inters):
    route0 = copy.deepcopy(route)
    if len(route0) == 0:
        route0.append([posO[0], posO[1]])

    poss = []
    if posO[0] > 0:
        poss.append([posO[0] - 1, posO[1]])
    if posO[0] < size_x - 1:
        poss.append([posO[0] + 1, posO[1]])
    if posO[1] > 0:
        poss.append([posO[0], posO[1] - 1])
    if posO[1] < size_y - 1:
        poss.append([posO[0], posO[1] + 1])

    for pos in poss:
        # 目的地に到達したら出力
        if pos[0] == posD[0] and pos[1] == posD[1]:
            route_out = copy.deepcopy(route0)
            route_out.append(pos)
            inters_out = copy.deepcopy(inters)
            yield route_out, inters_out
        # 目的地に到達しなかったら次を探索
        elif inters[pos[1]][pos[0]] is None:
            route_out = copy.deepcopy(route0)
            route_out.append(pos)
            inters_out = copy.deepcopy(inters)
            inters_out[pos[1]][pos[0]] = 't'
            yield from findRoute(size_x, size_y, pos, posD, route_out, inters_out)


# ODリストから経路を探索する
def findRoutes(size_x, size_y, ods, routes, inters):
    if len(ods) == 0:
        if len(routes) > 0:
            routes_out = copy.deepcopy(routes)
            inters_out = copy.deepcopy(inters)
            yield routes_out, inters_out
    else:
        for route_out, inters_out in findRoute(size_x, size_y, ods[0][0], ods[0][1], [], inters):
            routes_out = copy.deepcopy(routes)
            routes_out.append(route_out)
            yield from findRoutes(size_x, size_y, ods[1:], routes_out, inters_out)


# 石の配置に基づいて、一筆書き経路のパターンを取得する
def getRoutePatterns(size_x, size_y, stones, inters):
    # ODリストを作成
    odss = getODs(range(len(stones)))

    patterns = []
    for ods in tqdm(odss, desc='get_routes'):
        # ODリストを座標に変換
        ods_c = []
        for od in ods:
            ods_c.append([stones[od[0]], stones[od[1]]])

        # ODリストから経路を探索
        for routes_out, inters_out in findRoutes(size_x, size_y, ods_c, [], inters):
            patterns.append({
                'routes': routes_out,
                'inters': inters_out
            })
    return patterns


# 経路探索結果を表示する
def printRoute(size_x, size_y, stone_black, stone_white, routes):
    inters = [[' ' for i in range(size_x)] for j in range(size_y)]
    r_hor = [[' ' for i in range(size_x - 1)] for j in range(size_y)]
    r_ver = [[' ' for i in range(size_x)] for j in range(size_y - 1)]

    for s in stone_black:
        inters[s[1]][s[0]] = '*'
    for s in stone_white:
        inters[s[1]][s[0]] = '@'

    for route in routes:
        for i, inter in enumerate(route):
            if i > 0:
                inter0 = route[i - 1]
                if inter0[0] == inter[0]:
                    r_ver[min(inter0[1], inter[1])][inter[0]] = '|'
                elif inter0[1] == inter[1]:
                    r_hor[inter[1]][min(inter0[0], inter[0])] = '-'
                if i < len(route) - 1:
                    inters[inter[1]][inter[0]] = '+'

    out = []
    for iy in range(size_y - 1):
        out.clear()
        for ix in range(size_x - 1):
            out.append(inters[iy][ix])
            out.append(r_hor[iy][ix])
        out.append(inters[iy][size_x - 1])
        print(' '.join(out))

        out.clear()
        for ix in range(size_x):
            out.append(r_ver[iy][ix])
        print('   '.join(out))

    out.clear()
    for ix in range(size_x - 1):
        out.append(inters[size_y - 1][ix])
        out.append(r_hor[size_y - 1][ix])
    out.append(inters[size_y - 1][size_x - 1])
    print(' '.join(out))



if __name__ == '__main__':
    '''
    size_x = 8
    size_y = 8
    stone_black = [
        [6, 0],
        [4, 2],
        [6, 3],
        [5, 5],
        [7, 5],
        [1, 6],
        [3, 6],
        [7, 7]
    ]
    stone_white = [
        [3, 2],
        [5, 2],
        [4, 4],
        [6, 4],
        [6, 5],
        [2, 6],
        [4, 6],
        [1, 7]
    ]
    size_x = 5
    size_y = 5
    stone_black = [
        [0, 0],
        [1, 3],
        [2, 1],
        [3, 3],
        [0, 2]
    ]
    stone_white = [
        [0, 4],
        [1, 2],
        [3, 0],
        [3, 4],
        [4, 2]
    ]
    '''
    size_x = 6
    size_y = 6
    stone_black = [
        [1, 4],
        [4, 2],
        [3, 5],
        [5, 3]
    ]
    stone_white = [
        [1, 5],
        [2, 4],
        [3, 2],
        [4, 4],
        [5, 2]
    ]

    '''
    # デバッグ用
    print(listExcluded(range(4), 2))
    input()
    print(getOrders(range(2)))
    print(getOrders(range(3)))
    print(getOrders(range(4)))
    input()
    print(removeDuplicates(getOrders(range(2))))
    print(removeDuplicates(getOrders(range(3))))
    print(removeDuplicates(getOrders(range(4))))
    input()
    print(getODs(range(2)))
    print(getODs(range(3)))
    print(getODs(range(4)))
    input()
    '''

    # 交差点の情報を保存
    inters = [[None for i in range(size_x)] for j in range(size_y)]
    for s in stone_black:
        inters[s[1]][s[0]] = '*'
    for s in stone_white:
        inters[s[1]][s[0]] = '@'

    # 黒石と白石それぞれについて一筆書き経路のパターンを取得
    patterns_black = getRoutePatterns(size_x, size_y, stone_black, inters)
    patterns_white = getRoutePatterns(size_x, size_y, stone_white, inters)

    patterns = []
    for pattern_black in tqdm(patterns_black, desc='pattern_black'):
        inters = pattern_black['inters']
        for pattern_white in patterns_white:
            touch = False
            for route in pattern_white['routes']:
                for i in range(len(route) - 2):
                    if inters[route[i + 1][1]][route[i + 1][0]] is not None:
                        touch = True
                        break
                if touch is True:
                    break
            # パターンが交差しない場合
            if touch is False:
                routes = []
                routes += pattern_black['routes']
                routes += pattern_white['routes']
                patterns.append(routes)

    # 正解を表示
    for pattern in patterns:
        print('=' * (size_x * 4 - 3))
        printRoute(size_x, size_y, stone_black, stone_white, pattern)
    print('=' * (size_x * 4 - 3))
    print('Found {} patterns!'.format(len(patterns)))