Zusammenführen einer Liste aufheben

14

Einführung

Die meisten von Ihnen sind mit dem Algorithmus für die Zusammenführung zum Sortieren einer Liste von Zahlen vertraut . Als Teil des Algorithmus schreibt man eine Hilfsfunktion merge, die zwei sortierte Listen zu einer sortierten Liste kombiniert. Im Python-ähnlichen Pseudocode sieht die Funktion normalerweise so aus:

function merge(A, B):
  C = []
  while A is not empty or B is not empty:
    if A is empty:
      C.append(B.pop())
    else if B is empty or A[0] ≤ B[0]:
      C.append(A.pop())
    else:
      C.append(B.pop())
  return C

Die Idee ist, das kleinere der ersten Elemente von Aund Bso lange auszublenden, bis beide Listen leer sind, und die Ergebnisse in zu sammeln C. Wenn Aund Bbeide sortiert sind, ist dies auch der Fall C.

Umgekehrt ist if Ceine sortierte Liste und wir teilen sie in zwei beliebige Untersequenzen auf Aund B, dann Aund Bwerden auch sortiert und merge(A, B) == C. Interessanterweise gilt dies nicht unbedingt, wenn Cnicht sortiert wird, was uns zu dieser Herausforderung bringt.

Eingang

Ihre Eingabe ist eine Permutation der ersten 2*nnichtnegativen Ganzzahlen [0, 1, 2, ..., 2*n-1]für einige n > 0, angegeben als Liste C.

Ausgabe

Ihr Ausgang wird ein truthy Wert sein , wenn es zwei Listen Aund Bdie Länge , nso dass C == merge(A, B), und ein falsy Wert anders. Da die Eingabe keine Duplikate enthält, müssen Sie sich keine Gedanken darüber machen, wie Verbindungen in der mergeFunktion unterbrochen werden.

Regeln und Boni

Sie können entweder eine Funktion oder ein vollständiges Programm schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Beachten Sie, dass Sie nicht verpflichtet sind, die Listen Aund Bin den "Ja" -Instanzen zu berechnen . Wenn Sie jedoch auf die Ausgabe der Listen erhalten Sie einen Bonus von 20% . Um diesen Bonus zu erhalten, müssen Sie nur ein Listenpaar ausgeben, nicht alle Möglichkeiten. Damit dieser Bonus leichter in stark typisierten Sprachen beansprucht werden kann, ist es zulässig, ein Paar leerer Listen in den "Nein" -Instanzen auszugeben.

Brute Forcing ist nicht verboten, aber es gibt einen Bonus von -10% für die Berechnung aller letzten vier Testfälle in weniger als 1 Sekunde.

Testfälle

In den "Ja" -Instanzen ist nur ein möglicher Ausgang angegeben.

[1,0] -> False
[0,1] -> [0] [1]
[3,2,1,0] -> False
[0,3,2,1] -> False
[0,1,2,3] -> [0,1] [2,3]
[1,4,0,3,2,5] -> False
[4,2,0,5,1,3] -> [4,2,0] [5,1,3]
[3,4,1,2,5,0] -> [4,1,2] [3,5,0]
[6,2,9,3,0,7,5,1,8,4] -> False
[5,7,2,9,6,8,3,4,1,0] -> False
[5,6,0,7,8,1,3,9,2,4] -> [6,0,8,1,3] [5,7,9,2,4]
[5,3,7,0,2,9,1,6,4,8] -> [5,3,7,0,2] [9,1,6,4,8]
[0,6,4,8,7,5,2,3,9,1] -> [8,7,5,2,3] [0,6,4,9,1]
[9,6,10,15,12,13,1,3,8,19,0,16,5,7,17,2,4,11,18,14] -> False
[14,8,12,0,5,4,16,9,17,7,11,1,2,10,18,19,13,15,6,3] -> False
[4,11,5,6,9,14,17,1,3,15,10,12,7,8,0,18,19,2,13,16] -> [4,17,1,3,15,10,12,7,8,0] [11,5,6,9,14,18,19,2,13,16]
[9,4,2,14,7,13,1,16,12,11,3,8,6,15,17,19,0,10,18,5] -> [9,4,2,16,12,11,3,8,6,15] [14,7,13,1,17,19,0,10,18,5]
code-golf array-manipulation sorting Zgarb
quelle

Antworten:

3

Pyth, 39 * 0,9 * 0,8 = 28,08

#aY->QxQeS-QsY&YsY)KfqylTlQmsdty_Y%tlKK

Dieses Programm schließt alle zwei Boni ein. Es druckt ein Listenpaar, wenn das Aufheben der Zusammenführung möglich ist, oder eine leere Liste, die in Pyth (und Python) ein falscher Wert ist.

Input:  [5,3,7,0,2,9,1,6,4,8]
Output: ([9, 1, 6, 4, 8], [5, 3, 7, 0, 2])
Input:  [5,7,2,9,6,8,3,4,1,0]
Output: [] (falsy value)

Sie können es online testen, es ist jedoch möglicherweise etwas langsamer als die Offline-Version. Die Offline-Version löst jeden der Testfälle in <0,15 Sekunden auf meinem Laptop.

Wahrscheinlich (eines von) dem ersten Mal, dass eine Pyth-Lösung aktiv Ausnahmen verwendet (es wurden mindestens 1 Zeichen gespeichert). Es verwendet dieselbe Idee wie Peter Taylors Lösung.

                         preinitialisations: Q = input(), Y = []
#                 )     while 1: (infinite loop)
        eS-QsY             finds the biggest, not previous used, number
      xQ                   finds the index
    >Q                     all elements from ... to end
   -          &YsY         but remove all used elements
 aY                        append the resulting list to Y

When all numbers are used, finding the biggest number fails, 
throws an exception and the while loop ends.  
This converts [5,3,7,0,2,9,1,6,4,8] to [[9, 1, 6, 4, 8], [7, 0, 2], [5, 3]]

        msdty_Y  combine the lists each for every possible subset of Y (except the empty subset)
 fqylTlQ         and filter them for lists T with 2*len(T) == len(Q)
K                and store them in K

%tlKK        print K[::len(K)-1] (prints first and last if K, else empty list)

Pyth, 30 * 0,9 = 27,0

Ich habe nicht wirklich versucht, es zu lösen, ohne die resultierenden Listen auszudrucken. Aber hier ist eine schnelle Lösung basierend auf dem obigen Code.

#aY->QxQeS-QsY&YsY)fqylsTlQtyY

Ich habe im Grunde nur die print-Anweisung entfernt. Die Ausgabe ist allerdings ziemlich hässlich.

Input:  [0,1,2,3]
Output: [[[3], [2]], [[3], [1]], [[2], [1]], [[3], [0]], [[2], [0]], [[1], [0]]] (truthy value)
Input:  [5,7,2,9,6,8,3,4,1,0]
Output: [] (falsy value)

Probieren Sie es online aus .

Jakube
quelle
Möglicherweise stellen Sie fest, dass (K[0], Q-K[0])Sie nicht drucken , sondern drucken können (K[0], K[-1]). Ich weiß aber nicht, ob das eine Ersparnis wäre.
Peter Taylor
@ PeterTaylor danke, 2 Zeichen gespeichert.
Jakube,
@PeterTaylor und noch 2 Zeichen, wenn ich drucke K[::len(K)-1].
Jakube,
4

GolfScript (35 * 0,9 = 31,5)

{.$-1>/~,)\.}do;]1,\{{1$+}+%}/)2/&,

Die Online-Demo ist ziemlich langsam: Auf meinem Computer werden alle Tests in weniger als 0,04 Sekunden ausgeführt.

Erläuterung

Das Suffix von C, das mit der größten Zahl in C beginnt, muss aus derselben Liste stammen. Dann kann diese Argumentation auf (C - Suffix) angewendet werden, so dass sich das Problem auf eine Teilmenge der Summe reduziert.

Peter Taylor
quelle