Кодовое время процесса игры ребенка истекло

Question

Я пытаюсь решить проблему кодирования Детская игра на Codingame с использованием python. С моей программой я могу пройти первые два тестовых случая, но когда тест требует много циклов, моя программа проходит по таймауту. Что я могу улучшить?

Чтобы полностью понять проблему, нужны детали задачи, но я не хочу копировать и вставлять их здесь, потому что я не уверен, что это разрешено.

Я пытаюсь объяснить проблему своими словами. С учетом этого ввода:

12 6
987
...#........
...........#
............
............
..#O........
..........#.

• O является отправной точкой персонажа.
• # - стены, на которые вы не можете наступить
• . где символ может шагать

В этом примере w = 12 (ширина матрицы) и h = 6 (высота матрицы). n = 987 - это количество шагов, которое должен выполнить персонаж.

Обязательный вывод :

В этом случае 7 1 позиция символа после числаданные движения

Правила :

• Персонаж всегда начинает двигаться вверх
• Когда встречается стена, персонаж поворачивается по часовой стрелке и продолжает двигаться
• Стены расположены так, что персонаж не может застрять и не может выйти из матрицы.

Когда я запускаю программу с этим тестом, я получаю правильный результат.

При использовании следующего контрольного примера:

14 10
123456789
..#...........
....#..#......
.#O.....#.....
..............
..............
.......##...#.
............#.
.#........###.
.#.#..........
..............

Я получаю:

Время сбоя процесса истекло. Это может означать, что ваше решение недостаточно оптимизировано для обработки некоторых случаев.

Вот код, который мне удалось написать:

import math
import sys


def find_initial_position(maze, w, h):
    for i in range(0, h):
        for j in range(0,w):
            if maze[i][j] == "O":
                return [i, j]

    return -1


def can_move(maze, direction, x, y):

    if direction == "U":
        if maze[ x -1 ][ y ] == "#":
            return False
    elif direction == "R":
        if maze[ x ][ y + 1 ] == "#":
            return False
    elif direction == "D":
        if maze[ x +1 ][ y ] == "#":
            return False
    elif direction == "L":
        if maze[ x ][ y-1 ] == "#":
            return False

    return True


def turn_clockwise(direction):
    directions = ["U", "R", "D", "L"]
    return directions[ (directions.index(direction) + 1) % 4 ]


def move(direction, coordinates):
    if direction == "U":
        coordinates[0] -=1
    elif direction == "R":
        coordinates[1] +=1
    elif direction == "D":
        coordinates[0] +=1
    elif direction == "L":
        coordinates[1] -=1


def main():
    w, h = [int(i) for i in input().split()]
    n = int(input())

    maze = []
    direction = "U"
    position = [0, 0]

    for i in range(h):
        line = input()
        maze.append(line)

    position = find_initial_position(maze, w, h)

    for i in range(0, n):
        while not can_move(maze, direction, position[0], position[1]):
            direction = turn_clockwise(direction)

        move(direction, position)

    print( "%(x)d %(y)d" %{"x": position[1], "y": position[0]} )


main()

Answer 1

Я немного упорядочил ваш код и сделал его несколько более читабельным:

• , используя умножение матриц с numpy для поворота по часовой стрелке на 90 °;
• с помощью встроенного str.index(), чтобы найти начальную позицию.

Результат ниже ... Но на самом деле, это упущение.

Если вы посмотрите на «лабиринты» во всех тестовых случаях, то, что происходит, это то, что «робот» циклически подпрыгивает между четырьмя # препятствиями в прямоугольной схеме (также может быть более сложной схемой),Итак, с вашим подходом вы вычисляете и пересчитываете одну и ту же короткую последовательность движений, миллионы и миллиарды раз;даже если в самом длинном из возможных циклов не может быть больше ходов, чем количество квадратов в вашем маленьком лабиринте (на порядок величины).

То, что вы должны попытаться сделать, это вести непрерывный журнал всех выполненных на данный момент ходов (позиция, направление). И если - или, скорее, когда - вы окажетесь в (положении, направлении), где вы уже были раньше, тогда вы пройдете один полный цикл. Нет необходимости вычислять больше ходов. Скажем, ваша циклическая последовательность имеет длину L , а общее количество предписанных ходов составляет n , тогда конечной позицией будет номер элемента последовательности L mod n (или что-то в этом роде, несмотря на отдельные ошибки).

import sys
import numpy as np


def is_obstacle(maze, position):
    return maze[position[0]][position[1]] == '#'


def main():
    w, h = [int(i) for i in input().split()]
    n = int(input())

    # Load maze
    maze = []
    for i in range(h):
        line = input()
        maze.append(line)
        if 'O' in line:
            # Found initial position
            position = np.array([i, line.index('O')])

    # Initial direction
    direction = np.array([-1,0])

    # Define actions
    turn_clockwise = np.array([[0,-1],[1,0]])

    # Walk maze
    for i in range(n):
        while is_obstacle(maze, position + direction):
            direction = direction @ turn_clockwise
        position = position + direction

    print( "%(x)d %(y)d" %{"x": position[1], "y": position[0]} )


main()