Skip to content

Yandex Cup 2021: Фронтенд-разработка (квалификация). A. Выбраться из лабиринта (20 баллов)

Notifications You must be signed in to change notification settings

aptash/Yandex-Cup-2021-Labyrinth

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Yandex Cup 2021: Фронтенд-разработка (квалификация)

A. Выбраться из лабиринта (20 баллов)

Результат и мои комментарии

На локальном компьютере с визуализацией получилось решить задачу. Алгоритм находит выход. Но на соревновании не получилось пройти все тесты. Четвертый тест заканчивается с вердиктом IL: idleness-limit-exceeded (Программа слишком долго не отвечала на запросы системы и не выполняла действий). В поддержке ответили:

IL скорее всего значит, что ваш асинхронный код не успевает выполниться за 10 секунд

При том, что на превышение времени выполнения имеется специальное ссобщение:

Сообщение: Time-limit exceeded

Кратко: TL

Значение вердикта: Программа превысила установленный лимит времени

Возможная причина: 1. ошибка в программе 2. неэффективное решение

Итого: мой результат по этой задаче: 7.5 с прохожденим трёх тестов.

Исходная постановка задачи

Вы начинаете свой путь в темном лабиринте мрачного подземелья. В углу видите маленькую оплывшую свечку. Осторожно, чтобы не задуть, берете ее в руки и оглядываетесь по сторонам. На полу замечаете несколько разбитых склянок и одну целую. Поднимаете и внимательно осматриваете бутылочку. Да в ней записка! Разворачиваете пожелтевший от времени листок: «Смекалка, упорство и находчивость приведут тебя к Алхимику». Неужели Алхимик правда существует и можно попытаться его найти? — размышляете вы. Но сначала нужно выбраться отсюда. Итак, ваша первая задача — проложить себе путь из лабиринта. Наверняка, что-то подобное вы уже решали на работе, осталось только вспомнить алгоритм!

В задаче требуется написать функцию для выхода из лабиринта (гарантируется, что выход есть всегда).

Далее описание функции и параметров дано на Typescript, но функцию требуется написать на JS.

// Функция должна вернуть точку x, y, для которой game.state(x, y).finish === true
// start - некая начальная точка.
// Не деструктурируйте game, ваше решение не будет проходить тесты.
module.exports = function main(game: Game, start: Point): Promise<Point> {

}

У game есть асинхронные функции, которые позволяют двигаться от любой ячейки влево/вправо/вверх/вниз (при попытке шагнуть в стену или шагнуть из не посещенной клетки кидает ошибку). А также асинхронная функция получения состояния ячейки (работает только для посещенных ячеек, для остальных кидает ошибку).

Ось x в лабиринте идет слева-направа, y - сверху-вниз.

Формат данных

export interface Point {
    x: number;
    y: number;
}

export interface Game {
    // Попытаться шагнуть из клетки лабиринта вверх
    up(x: number, y: number): Promise<void>;
    // Попытаться шагнуть из клетки лабиринта вниз
    down(x: number, y: number): Promise<void>;
    // Попытаться шагнуть из клетки лабиринта влево
    left(x: number, y: number): Promise<void>;
    // Попытаться шагнуть из клетки лабиринта вправо
    right(x: number, y: number): Promise<void>;

    // Получить состояние клетки лабиринта
    state(x: number, y: number): Promise<{
        top: boolean; // можно ли шагать вверх
        bottom: boolean; // можно ли шагать вниз
        left: boolean; // можно ли шагать влево
        right: boolean; // можно ли шагать вправо
        start: boolean; // ячейка - стартовая
        finish: boolean; // ячейка - финиш
    }>;
}

Для тестирования решения скачивайте приложенный файл labyrinth-tester.zip (ссылка "Скачать условие задачи" ниже), в нем в файле src/main.js можно писать решение и визуализировать прохождение лабиринта.

Есть следующие ограничения:

  • Ограничение времени: 10 секунд
  • Ограничение памяти: 64.0 Мб

Решение будет проверяться на Node 12.

About

Yandex Cup 2021: Фронтенд-разработка (квалификация). A. Выбраться из лабиринта (20 баллов)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published