2019-12-29 22:43

Python 全然わからないのとツリーをどうあらわすかよくわかってなくてしっちゃかめっちゃか。

moja888.hatenadiary.org

このやつを Python で書いてみたやつ。手段が "わや" な状態で何か解く、みたいなのむずかしい。

MAP = """
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
""".strip()

EXPECTED = """
**************************
*S* * $$$                *
*$* *$$*$ *************  *
*$* $$* $$$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************
""".strip()

WALL  = '*'
PATH  = ' '
START = 'S'
GOAL  = 'G'
ROUTE = '$'

def create_item_nodes(map_str):
    blocks = [list(line) for line in MAP.split('\n')]
    item_nodes = []
    for row, line in enumerate(blocks):
        for col, item in enumerate(line):
            node = (row, col)
            item_nodes.append((item, node))
    return item_nodes

def find_item_node(target_item, item_nodes):
    for item, node in item_nodes:
        if item == target_item:
            return node
    return None

def find_neighbors(node, path_nodes):
    row, col = node
    candidates = {(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)}
    return [n for n in path_nodes if n in candidates]

def find_route(item_nodes):
    start = find_item_node(START, item_nodes)
    assert start, 'start not found'
    goal = find_item_node(GOAL, item_nodes)
    assert goal, 'goal not found'

    path_nodes = [node for item, node in item_nodes if item in {PATH, START, GOAL}]

    known_path = {start}
    direction_origin_nodes = {start}
    directions = []

    while True:
        next_direction_origin_nodes = []
        for direction_origin in direction_origin_nodes:
            neighbors = [neighbor for neighbor in find_neighbors(direction_origin, path_nodes) if neighbor not in known_path]
            directions += [(direction_origin, neighbor) for neighbor in neighbors]
            next_direction_origin_nodes += neighbors
        direction_origin_nodes = set(next_direction_origin_nodes)
        known_path = known_path.union(direction_origin_nodes)

        if goal in direction_origin_nodes:
            break
        if not direction_origin_nodes:
            raise ValueError('path not found')

    def find_direction_by_dest(dest_node, directions):
        for direction in reversed(directions):
            orig, dest = direction
            if dest == dest_node:
                return direction

    route = []
    dest_node = goal
    while dest_node is not start:
        direction = find_direction_by_dest(dest_node, directions)
        orig, dest = direction
        route.append(orig)
        dest_node = orig

    return list(reversed(route))

def main():
    item_nodes = create_item_nodes(MAP)
    route = find_route(item_nodes)

    matrix = [list(line) for line in [line for line in MAP.split('\n')]]
    for row, col in route:
        if matrix[row][col] == PATH:
            matrix[row][col] = ROUTE

    routed_map = '\n'.join([''.join(cols) for cols in matrix])

    print(routed_map)

    print('FOUND PATH LENGTH:', sum([1 for char in routed_map if char == '$']))
    print('EXPECTED PATH LENGTH:', sum([1 for char in EXPECTED if char == '$']))

if __name__ == '__main__':
    main()

% python route.py
**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$*$$$*  $$************  *
*$$$ *    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************
FOUND PATH LENGTH: 59
EXPECTED PATH LENGTH: 59

幅優先のつもりなので最短のはず…。