Necesito llamar a mis amigos, pero los botones de mi teléfono inalámbrico no funcionan correctamente. Los únicos botones que puedo presionar son [Arriba], [Abajo] y [Llamar]. [Arriba] y [Abajo] se pueden usar para navegar en mis llamadas recientes y [Llamar] se puede usar para llamar al nombre seleccionado. Mi teléfono tiene una lista que contiene Nllamadas recientes, y sé que todos los amigos a los que necesito llamar están en esta lista.

Tarea:

Recibirá un número Ny una lista de nombres L:

• N es la cantidad de llamadas recientes que mi teléfono puede recordar;
• L tiene los nombres en el orden que necesito llamar.

Debe generar el número de pulsaciones de botones que necesito hacer en una disposición óptima de la lista de llamadas recientes.

Ejemplo:

-> Entrada:

Llamando a Anna, Bob y luego Anna otra vez. Con una lista de llamadas recientes de tamaño 5.

5
Anna
Bob
Anna

-> Salida:

Posible arreglo óptimo: Anna, Foo, Bar, Foobar, Bob

5    # Key presses: [Call] Anna, [Up] + [Call] Bob, [Down] + [Call] Anna

Más casos de prueba:

Input: 5, Anna, Bob, Carl
Output: 5

Input: 5, Anna, Bob, Carl, Anna
Output: 8

Input: 5, A, B, C, D, E, A
Output: 11

Input: 6, A, B, C, D, E, A
Output: 12

Input: 4, A, B, C, B, A
Output: 10

Reglas:

• Su cursor siempre comenzará en la primera posición de la lista;
• Puede tomar la entrada Ny Ldesde cualquier fuente: teclado, parámetros, archivo, etc.
• Los nombres en la lista pueden estar en cualquier formato razonable como: cadenas, enteros, caracteres;
• Cuando llega al final de la lista de llamadas recientes y presiona [Abajo] nuevamente, su cursor se envuelve. Lo mismo sucede cuando estás al comienzo de la lista de llamadas recientes y presiona [Arriba];
• Cuando llama a alguien, el nombre de esa persona se moverá a la primera posición de la lista de llamadas recientes y el resto se desplazará hacia abajo;
• Cuando llame a alguien, su cursor se moverá a la primera posición;
• El nombre de un amigo no puede aparecer más de una vez en la lista de llamadas recientes;
• Puede completar su lista de llamadas recientes con entradas ficticias (ver ejemplo);
• El número de amigos a los que llamar no será mayor que N.

Ruby , 97 95 94 bytes

->n,a{r=a.size;1.upto(r-1){|i|r+=[p=a[(a[0,i].rindex(a[i])||i-2)+1...i].uniq.size,n-p].min};r}

Pruébalo en línea!

En una disposición óptima, el primer nombre tendrá una pulsación ( Call). Los nombres que no se han llamado todavía toman dos prensas (Up Call ), y los nombres que han tomado números variables dependiendo de cuántos otros nombres únicos se hayan llamado desde entonces y si eso los coloca más cerca de la parte superior o inferior de la lista.

Creo que esta es una estrategia similar o idéntica a la de WaffleCohn.

Python 3 , 195 185 164 bytes

-4 bytes gracias a @notjagan
-27 bytes gracias a @FelipeNardiBatista

lambda n,l:min(g([*x],l,n)for x in permutations(range(n)))
def g(x,l,n,r=0):
 for p in l:a=x.index(p);x=[x.pop(a)]+x;r-=~min(a,n-a)
 return r
from itertools import*

Pruébalo en línea!

L se toma como una lista de enteros de [0, N)

JavaScript (SpiderMonkey) , 213 143 bytes

(N,L)=>L.reduce((t,v,i)=>{x=0,a=[v]
for(j=i;j-->=0&!~a.indexOf(L[j]);x++)a+=L[j]+","
return i?t+((x=L.indexOf(v)-i?x:1)<N-x?x:N-x):t},L.length)

Pruébalo en línea!

Genera una disposición óptima de los nombres de pila y luego cuenta el número de pulsaciones de teclas.

Se saltó la generación y solo contó cuántas pulsaciones de teclas tomaría cada nombre en la disposición óptima