Платформа: CodeWars
Название задачи: The Jumbler (Неумеха)
Ссылка на задачу: https://www.codewars.com/kata/69269262ced9e95dc63abd1e
Сложность: 7 kyu
Уже решили (На момент написания статьи): 96 из 237
Тэги: Fundamentals, Algorithms, Data Structures
Оригинальное описание задачи:
Situation
One day Alice was at the casino on her favorite slot machine ("The Jumbler") when she noticed a set of numbers occasionally flashing in one corner of the screen. She found that by treating them as indices, reordering them according to a pattern, and counting the reorderings, she could know how many spins to make before the machine would finally hit a big jackpot payout!
Reordering
The pattern Alice discovers goes as follows:
select the value at index `zero`
(if the value is `0` do not continue)
elsewise, the value is our search index
go to new value found at the search index
remove this new value from its place in order
reposition this new value onto the front of the list
(if the new value is `zero`, the reorderings will cease)
elsewise, repeat all instructions with this new ordering
Task
Write a function to help Alice find out the count of times the given integers have to be reordered and thus know how many Jumbler spins to make before betting large and getting a huge payout!!
Input A(n) `array / list / tuple / vector` of unsigned integers.
values represent the indices of the collection itself
thus the values are all distinct from one another
and all indices guaranteed to be present
the values will be randomly shuffled
Output
An unsigned integer of the count of times the given numbers must be reordered according to Alice's Reordering Pattern before the value at index `zero` actually becomes `0` itself.
Example
Step 1
Given the numbers `2, 0, 3, 1`, we select `2` as the search index.
The value `3` is found at that index, so `3` is moved to the front.
Step 2 Now with numbers `3, 2, 0, 1`, we select `3` as the search index.
The value `1` is found at that index, so `1` is moved to the front.
Step 3 Now with numbers `1, 3, 2, 0`, we select `1` as the search index.
The value `3` is found at that index, so `3` is moved to the front.
Step 4 Now with numbers `3, 1, 2, 0`, we select `3` as the search index.
The value `0` is found at that index, so `0` is moved to the front.
Conclusion
With `zero` now finally at the front of the order: `0, 3, 1, 2` the reordering comes to a close, and we have our answer.
In this case, it took `4` steps of reordering to jumble zero to the front. Enjoy!
Пояснение задачи:
Задача состоит в том, чтобы разработать функцию, моделирующую процесс перестановок элементов массива согласно заданному правилу:
- Извлечь элемент по индексу, равному первому числу в массиве.
- Если извлечённый элемент равен нулю — прекратить выполнение.
- Иначе переместить найденный элемент на первое место в массиве и удалить его исходное положение.
- Повторять до тех пор, пока первый элемент массива не станет нулём.
Таким образом, задача сводится к подсчёту количества шагов, необходимых для перемещения первого элемента массива на первую позицию, после чего он становится равным нулю.
Примеры работы функции:
- Для входного массива `[2, 0, 3, 1]`:
Исходный массив: [2, 0, 3, 1] → выбираем элемент по индексу 2 (значение 3), перемещаем его на начало: [3, 2, 0, 1] 2. Новый массив: [3, 2, 0, 1] → выбираем элемент по индексу 3 (значение 1), перемещаем его на начало: [1, 3, 2, 0] 3.
Новый массив: [1, 3, 2, 0] → выбираем элемент по индексу 1 (значение 3), перемещаем его на начало: [3, 1, 2, 0] 4.
Новый массив: [3, 1, 2, 0] → выбираем элемент по индексу 3 (значение 0), перемещаем его на начало: [0, 3, 1, 2]
Итоговое количество шагов: 4.
- Для входного массива `[1, 0, 2]`:
Исходный массив: [1, 0, 2] → выбираем элемент по индексу 1 (значение 0), перемещаем его на начало: [0, 1, 2]
" Итоговое количество шагов: 1.
Функция должна эффективно обрабатывать случайные входные данные, проверяя корректность индексов и останавливаясь при достижении нуля.
