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.