Магия телепортации
- Не решено
Эпилог
Сегодня вы - искатель приключений в магическом мире. Этот мир наполнен сокровищами и различными порталами. Вначале своего путешествия вы находитесь у самого первого - входного - портала в магический мир. Ваша цель - добраться до последнего - финального - портала и получить самое главное сокровище.
Дано
Вам дан массив ports
, который содержит в себе числа - энергию каждого портала. Для перемещения между порталами вы можете использовать искусство телепортации, и вот как оно работает:
- Можно сделать небольшой прыжок в следующий по порядку портал
ports[i+1]
. Главное не выпрыгнуть из порталов совсем -ports[i+1] < ports.length
. - Либо можно прыгнуть в предыдущий портал (по порядку расположения в массиве)
ports[i-1]
. Учтите, чтоi - 1 >= 0
. - Но настоящая магия в том, что вы можете прыгнуть в любой имеющийся портал, если его энергия равна энергии портала, в котором вы находитесь
ports[i] == ports[j] and i != j
.
Ваша задача - найти минимальное количество прыжков, которое понадобится для попадания в последний портал и получения главного сокровища!
Задача
Напишите функцию teleports
, которая принимает на вход массив ports
и возвращает число - минимальное количество телепортов.
Пример:
ports = [11, 22, 7, 7, 7, 7, 7, 7, 7, 22, 13]
Вы находитесь в первом портале - ports[0]
, энергия которого равна 11, вам нужно попасть в последний портал - ports[10]
с энергией 13. По правилам телепортации, из первого портала, вы можете переместиться только в следующий портал - ports[1]
с энергией 22. Из ports[1]
вы уже можете перепрыгнуть в ports[2]
, или в ports[9]
с аналогичной, вашему настоящему порталу, энергией - 22. И следующим шагом можете переместиться в последний портал.
Таким образом, для данного массива минимальным количеством прыжков будет число 3. Три прыжка по индексам: 0 --> 1 --> 9 --> 10.
Вызов функции: teleports([7])
Вывод: 0
Пояснение: Начальный портал - это и последний портал. Нет необходимости прыгать.
Вызов функции: teleports([7, 6, 9, 6, 9, 6, 9, 7])
Вывод: 1
Пояснение: Можем сразу перепрыгнуть в последний портал, так как их энергии одинаковы.