Können Sie Bill Gates übertreffen?

13

Pfannkuchensortierung ist der umgangssprachliche Begriff für das mathematische Problem, einen ungeordneten Stapel Pfannkuchen in der Reihenfolge seiner Größe zu sortieren, in der ein Spatel an einer beliebigen Stelle des Stapels eingesetzt und zum Umdrehen aller darüber liegenden Pfannkuchen verwendet werden kann. Eine Pfannkuchennummer P (n) ist die minimale Anzahl von Flips, die für n Pfannkuchen erforderlich sind . 1

1979 schrieben ein junger Bill Gates und Christos Papadimitriou eine Arbeit, in der eine Obergrenze von P (n) = (5n + 5) / 3 bewiesen wird . 2

Ich denke, es ist sicher anzunehmen, dass Gates (und / oder Papadimitriou) ein Programm geschrieben haben, um die Pfannkuchensortierung mit dem von ihnen entwickelten Algorithmus durchzuführen (möglicherweise später als 1979). Da Gates ein erfahrener Programmierer war, haben sie wahrscheinlich versucht, diesen Code so gut wie möglich zu spielen, aber die Größe des Quellcodes ist nicht öffentlich verfügbar (AFAIK).

Herausforderung:

Erstellen Sie eine Funktion / ein Programm, die / das eine Pfannkuchensortierung durchführt, wobei die maximale Anzahl von Flips die von Gates und Papadimitriou festgestellte Grenze nicht überschreitet. 3 Sie können wählen, ob die Liste aufsteigend oder absteigend sein soll, sofern dies konsistent ist.

Sie können annehmen, dass n <50 ist . Sie müssen daher die Anzahl der Flips auf (einige zufällig ausgewählte n- Werte) begrenzen :

 n   P(n)
38   65
49   83
50   85

Die Ausgabe sollte die Position des Spatels vor jedem Flip sein. Die Ausgabe kann null oder eins sein und Sie können wählen, ob Sie von oben oder unten zählen.

Zusätzliche Regeln:

  • Die Laufzeit muss deterministisch sein
  • Es gibt kein festes Zeitlimit, aber Sie müssen in der Lage sein, die Ausgabe für eine Liste mit 50 Elementen bereitzustellen

Testlisten:

Ich kann nicht die schwierigsten Listen bereitstellen (wenn ja, würde ich eine Arbeit schreiben, keine Herausforderung), deshalb werde ich einige zufällige Listen mit Zahlen bereitstellen, mit denen Sie Ihre Funktionen / Programme testen können. Ich könnte andere hinzufügen, wenn sich herausstellt, dass diese Listen "einfach" sind.

9, 63, 62, 75, 45, 78, 59, 75, 69, 3, 28, 94, 51, 10, 45, 93, 97, 80, 72, 36, 80, 88, 30, 93, 84, 80, 17, 31, 6, 80, 76, 91, 9, 76, 38, 33, 22, 15, 45, 46, 15, 98, 2, 56, 90, 27, 27, 26, 69, 25
...
74, 89, 57, 52, 70, 96, 16, 5, 77, 84, 54, 13, 90, 64, 31, 80, 3, 25, 13, 19, 13, 34, 1, 79, 35, 43, 4, 19, 82, 29, 48, 95, 97, 28, 45, 62, 64, 82, 70, 34, 38, 15, 51, 83, 21, 66, 4, 42, 74, 84
...
62, 73, 7, 90, 83, 18, 12, 35, 72, 71, 99, 67, 87, 62, 65, 70, 14, 72, 55, 92, 87, 3, 7, 4, 4, 95, 49, 25, 4, 18, 49, 39, 26, 1, 45, 64, 23, 66, 39, 17, 33, 24, 58, 72, 77, 46, 99, 71, 10, 21

Hoffentlich werden Bill Gates und Papadimitriou diese Herausforderung annehmen und ihren Code bereitstellen, damit wir feststellen können, ob Sie sie tatsächlich übertroffen haben.

3 Es wurden bessere Obergrenzen gefunden, die Sie jedoch nicht beachten müssen.

code-golf number sorting optimization stack Stewie Griffin
quelle
Verwandte , aber kein Duplikat. Die Antworten dort würden hier nicht funktionieren.
Stewie Griffin
Ich habe damals BFS in meiner Lösung verwendet, hier sollte es noch funktionieren (mit geringfügiger Aktualisierung), um die Lösung mit der minimalen Anzahl von Flips zu finden.
Meilen
@miles dann zögern Sie nicht, es zu posten. Ich habe nicht alle Antworten im Detail durchgesehen, aber die meisten benutzten einfach den naiven Ansatz.
Stewie Griffin

Antworten:

4

Python 2 (PyPy) , 238 235 222 Bytes

a=input();n=len(a);r=range(n);a=zip(a,r);a=map(sorted(a).index,a)+[n]
def s(u,m):
 if m<1:return[0]
 for k in r:
  v=u[k::-1]+u[k+1:]
  if sum(1<abs(v[i]-v[i+1])for i in r)<m:
   p=s(v,m-1)
   if p:return[k]+p
print s(a,5*n/3)

* (2 Leerzeichen = Tab)

Probieren Sie es online!

13 Bytes beim Ausleihen einer Methode zum Einordnen einer Liste gespeichert .

DFS mit einer einfachen Heuristik, die prüft, ob ein Flip ein Paar "Pfannkuchen" trennt, die beim Sortieren benachbart wären. Sortiert es in aufsteigender Reihenfolge. Die Ausgabe wird von links mit 0 indiziert, wobei 0 die ersten 2 und so weiter spiegelt. Die Anzahl der verwendeten Züge ist (5/3)*n+1 < 5/3*(n+1)wo (18/11)*n < (5/3)*n+1 < 5/3*(n+1)und (18/11)*nist eine engere Obergrenze, die 2009 gefunden wurde .

Meilen
quelle