Ich muss meine Freunde anrufen, aber die Tasten meines schnurlosen Telefons funktionieren nicht richtig. Die einzigen Tasten, die ich drücken kann, sind [Auf], [Ab] und [Anrufen]. Mit [Auf] und [Ab] können Sie in meinen letzten Anrufen navigieren und mit [Anruf] den ausgewählten Namen aufrufen. Mein Telefon verfügt über eine Liste mit den Nletzten Anrufen, und ich weiß, dass alle Freunde, die ich anrufen muss, in dieser Liste enthalten sind.

Aufgabe:

Sie erhalten eine Nummer Nund eine Liste mit Namen L:

• N ist die Anzahl der letzten Anrufe, an die sich mein Telefon erinnern kann;
• L hat die Namen in der Reihenfolge, in der ich anrufen muss.

Sie müssen die Anzahl der Tastendrücke ausgeben, die ich in einer optimalen Anordnung der letzten Anrufliste ausführen muss.

Beispiel:

-> Eingabe:

Ich rufe Anna, Bob und dann wieder Anna an. Mit einer Liste der letzten Anrufe der Größe 5.

5
Anna
Bob
Anna

-> Ausgabe:

Mögliche optimale Anordnung: Anna, Foo, Bar, Foobar, Bob

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

Weitere Testfälle:

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

Regeln:

• Ihr Cursor startet immer an der ersten Position der Liste.
• Sie können die Eingabe Nund Lvon jeder Quelle nehmen: Tastatur, Parameter, Datei usw.;
• Die Namen in der Liste können in jedem vernünftigen Format vorliegen, z. B.: Zeichenfolgen, Ganzzahlen, Zeichen;
• Wenn Sie das Ende der Liste der letzten Anrufe erreicht haben und erneut [Ab] drücken, bewegt sich der Cursor. Das gleiche passiert, wenn Sie am Anfang der Liste der letzten Anrufe stehen und [Nach oben] drücken.
• Wenn Sie jemanden anrufen, wird der Name dieser Person an die erste Position der Liste der letzten Anrufe verschoben und der Rest wird nach unten gedrückt.
• Wenn Sie jemanden anrufen, wird Ihr Cursor an die erste Position bewegt.
• Ein Freundesname kann in der Liste der letzten Anrufe nur einmal vorkommen.
• Sie können Ihre Liste der letzten Anrufe mit Dummy-Einträgen füllen (siehe Beispiel).
• Die Anzahl der anzurufenden Freunde ist nicht größer als 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}

Probieren Sie es online aus!

In einer optimalen Anordnung benötigt der Vorname einen Druck ( Call). Namen, die noch nicht aufgerufen wurden, müssen zweimal gedrückt werden (Up Call ), und Namen, die unterschiedliche Nummern haben, hängen davon ab, wie viele andere eindeutige Namen seitdem aufgerufen wurden und ob sie dadurch näher am oberen oder unteren Rand der Liste platziert werden.

Ich denke, dies ist eine Strategie, die der von WaffleCohn ähnlich oder identisch ist.

Python 3 , 195 185 164 Bytes

-4 Bytes dank @notjagan
-27 Bytes dank @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*

Probieren Sie es online aus!

L wird als Liste von ganzen Zahlen aus genommen [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)

Probieren Sie es online aus!

Erzeugt eine optimale Anordnung der Vornamen und zählt dann die Anzahl der Tastendrücke.

Übersprang die Generation und zählte nur, wie viele Tastendrücke jeder Name in der optimalen Anordnung annehmen würde