Je dois appeler mes amis, mais les boutons de mon téléphone sans fil ne fonctionnent pas correctement. Les seuls boutons sur lesquels je peux appuyer sont [Haut], [Bas] et [Appel]. [Haut] et [Bas] peuvent être utilisés pour naviguer dans mes appels récents et [Appel] peut être utilisé pour appeler le nom sélectionné. Mon téléphone a une liste qui contient Nles appels récents, et je sais que tous les amis que je dois appeler figurent dans cette liste.

Tâche:

Vous recevrez un numéro Net une liste de noms L:

• N est le nombre d'appels récents dont mon téléphone peut se souvenir;
• L a les noms dans l'ordre que je dois appeler.

Vous devez afficher le nombre d'appuis sur les boutons que je dois effectuer dans une disposition optimale de la liste des appels récents.

Exemple:

-> Entrée:

Appelant Anna, Bob puis Anna à nouveau. Avec une liste d'appels récents de taille 5.

5
Anna
Bob
Anna

-> Sortie:

Arrangement optimal possible: Anna, Foo, Bar, Foobar, Bob

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

Plus de cas de test:

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

Règles:

• Votre curseur commencera toujours à la première position de la liste;
• Vous pouvez prendre l'entrée Net Lde n'importe quelle source: clavier, paramètres, fichier, etc;
• Les noms dans la liste peuvent être dans n'importe quel format raisonnable tel que: chaînes, entiers, caractères;
• Lorsque vous atteignez la fin de la liste des appels récents et appuyez à nouveau sur [Bas], votre curseur revient. La même chose se produit lorsque vous êtes au début de la liste des appels récents et que vous appuyez sur [Haut];
• Lorsque vous appelez quelqu'un, le nom de cette personne sera déplacé à la première position de la liste des appels récents et le reste sera poussé vers le bas;
• Lorsque vous appelez quelqu'un, votre curseur sera déplacé vers la première position;
• Un nom d'ami ne peut pas apparaître plus d'une fois dans la liste des appels récents;
• Vous pouvez remplir votre liste d'appels récents avec des entrées factices (voir l'exemple);
• Le nombre d'amis à appeler ne sera pas supérieur à N.

Rubis , 97 95 94 octets

->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}

Essayez-le en ligne!

Dans un arrangement optimal, le prénom prendra une pression ( Call). Les noms qui n'ont pas encore été appelés prennent deux pressions ( Up Call), et les noms qui prennent des nombres variables selon le nombre d'autres noms uniques qui ont été appelés depuis et si cela les place plus près du haut ou du bas de la liste.

Je pense que c'est une stratégie similaire ou identique à WaffleCohn.

Python 3 , 195 185 164 octets

-4 octets grâce à @notjagan
-27 octets grâce à @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*

Essayez-le en ligne!

L est considéré comme une liste d'entiers de [0, N)

JavaScript (SpiderMonkey) , 213 143 octets

(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)

Essayez-le en ligne!

Génère une disposition optimale des noms donnés puis compte le nombre d'appuis sur les touches.

Ignoré la génération et juste compté le nombre de pressions de touches qu'il faudrait pour chaque nom dans l'arrangement optimal