coderbyte__array_jumping.py

coderbyte__array_jumping.py

def ArrayJumping(arr):
    # Inicialização de um dicionário para armazenar as informações de salto para cada índice na lista
    hashtable = {}
    
    # Obter o comprimento da lista
    arr_len = len(arr)    
    # Preencher o dicionário com informações de salto para cada índice na lista
    for i in range(arr_len):
        hashtable[i] = (left(arr_len, i, arr[i]), right(arr_len, i, arr[i]))
    
    # Encontrar o índice do maior elemento na lista
    max_index = arr.index(max(arr))
    # Se o índice do maior elemento estiver nos índices resultantes dos saltos para a esquerda ou para a direita, retornar 1
    if max_index in hashtable[max_index]:
        return 1
    
    # Criar um conjunto de índices resultantes dos saltos
    travel_set = set(hashtable[max_index])  
    
    # Verificar se é possível voltar à posição do maior elemento em mais de um salto
    for step in range(2, arr_len + 1):
        # Iterar sobre os índices resultantes dos saltos
        for val in tuple(travel_set):
            # Adicionar os índices resultantes dos saltos para a esquerda e para a direita
            travel_set.add(hashtable[val][0])
            travel_set.add(hashtable[val][1])
            
        # Se o índice do maior elemento estiver presente nos índices resultantes dos saltos, retornar o número de saltos
        if max_index in travel_set:
            return step
    
    # Se não for possível voltar à posição do maior elemento, retornar -1
    return -1
        

def left(length, index, number):
    # Calcular o índice resultante ao mover para a esquerda a partir da posição atual
    left = number % length
    if left > index:
        left = length + index - left
    else:
        left = index - left
    return left

def right(length, index, number):
    # Calcular o índice resultante ao mover para a direita a partir da posição atual
    right = number % length
    if right > length - index - 1:
        right = right + index - length
    else:
        right = right + index
    return right