Implementiere Tyrant Sort [geschlossen]

8

TL; DR

  • Aufzeichnung (links-rechts) / Länge für jedes Paar aufeinanderfolgender Elemente. Wenn sie 0 oder negativ sind, zeichnen Sie sie nicht auf.
  • Sobald dies erledigt ist, ergreifen Sie diese Maßnahmen. Quotienten nicht aktualisieren:
    • Inkrementiere rechts und dekrementiere links für (0, .3)
    • Entfernen Sie aus dem Array bei> =. 3
    • Drucken Sie beide Elemente für> .5
  • Drucken Sie das verbleibende Array. Habe ein Trennzeichen zum Ausführen und Verbleiben.

Nun zur Herausforderung…

Dies ist der Sortieralgorithmus, der eine Worst-Case von hat GLORIOUS LINEAR TIME , und wo jeder, der seine entgegenstellen dare INFINITE WISDOM prompt wird EXECUTED für ihre abscheulichen Verbrechen des Hochverrats .

Der FEARLESS LEADER hat Sie mit der EHRENWERTIGEN MISSION beauftragt , ein Programm oder eine Funktion zu schreiben, die ein Array von Ganzzahlen aufnimmt und mit dem folgenden Sortieralgorithmus sortiert:

  1. Durchlaufen Sie Ihr Array und erleuchten Sie jedes Element mit der HERRLICHEN Präsenz seines FEARLESS LEADER .
  2. Haben Sie Ihre Geheimpolizei Kontrolle über jedes Paar von zwei aufeinander folgenden Elementen , um sicherzustellen , sie sind IHRE NATION RICHTIG LOYALEN . Wenn sie nicht richtig sortiert sind, notieren Sie die Differenz zwischen den Zahlen geteilt durch die Länge des Arrays. Dies ist ihr Dissensquotient.
  3. Gehen Sie am Ende Ihrer GLORIOUS TOUR die Liste und die göttliche Bestrafung von RAIN FEARLESS LEADER für alle TREASONOUS DISSENTERS wie folgt durch:
    • Für einen abweichenden Quotienten von weniger als 0,3 müssen sie lediglich einer Gehirnwäsche unterzogen werden, um an die unendliche Herrlichkeit des furchtlosen Führers zu erinnern . Dekrementieren Sie das linke Element und erhöhen Sie das rechte Element. Ändern Sie keine abweichenden Quotienten.
    • Für einen abweichenden Quotienten von 0,3 bis 0,5 (einschließlich) sind sie TRAITOREN und sollten an PRISON CAMPS gesendet werden . Entfernen Sie sie aus dem Array.
    • Für einen Dissensquotienten größer als 0,5 sind sie ODIOUS REBEL SCUM . Sie sollten werden öffentlich hinrichten als Beispiel für andere verräterische Ketzer sie mit haben könnte verbündet. Entfernen Sie sie aus dem Array und senden Sie sie an die nationale Nachrichtenquelle The STDOUT Times.
  4. Ihr Array ist jetzt VOLLSTÄNDIG UND FÜR IMMER sortiert. Senden Sie es an die STDOUT Times, damit sie von Ihrem GLORIOUS VICTORY singen können .

Als PFLICHT VIEWING für diejenigen , die auch sind FOOLISH das verstehen INFINITE GLORY dieses Algorithmus, wird es verwendet werden , um die folgende Array zu sortieren:

[1,8,6,0,4,9,3,5,7,2]
  • 1 und 8 sind korrekt bestellt.
  • 8 und 6 sind nicht richtig geordnet, daher wird der Dissensquotient von 0,2 für beide aufgezeichnet.
  • 6 und 0 sind ein weiteres Paar von Andersdenkenden. Dieser Dissensquotient ist .6.
  • 0 und 4 sind richtig bestellt.
  • 4 und 9 sind richtig bestellt.
  • 9 und 3 haben einen Dissensquotienten von 0,6.
  • 3 und 5 sind richtig bestellt.
  • 5 und 7 sind korrekt bestellt.
  • 7 und 2 haben einen Dissensquotienten von 0,5.

Sie führen also im Namen des FEARLESS LEADER die folgenden Aktionen aus :

  • Dekrementieren Sie 8 auf 7 und erhöhen Sie 6 auf 7.
  • Entfernen 0 und die neuen 7 und führt sie aus .
  • Folgen Sie mit 9 und 3.
  • Bringen Sie die ursprünglichen 7 und 2 in die Umerziehungslager und entfernen Sie sie.

Dies sollte Ihre Pressemitteilung sein, die in STDOUT erstellt wurde oder was auch immer zweckmäßig ist:

Executions: 7, 0, 9, 3
[1, 7, 4, 5]

Wie Sie sehen können, ist das resultierende Array VOLLSTÄNDIG UND FÜR IMMER SORTIERT . Der Versuch, darauf hinzuweisen , dass es nicht sortiert ist, ist HIGH TREASON .

Jetzt, als GLORIOUS DEMONSTRATION der Unending RESOURCES durch die gegebene FEARLESS LEADER hat er dich mit seinen zur Verfügung gestellt INFINITE WISDOM Testfälle zu erzeugen:

import random

len=random.randint(2,20)
arr=list(range(len))
random.shuffle(arr)
print(arr)

dissent=[(arr[i]-arr[i+1])/len for i in range(len-1)]
dissent.append(0) # Barrier between front and back of the array.
executions=[]
for i in range(len-1):
    if dissent[i] > 0:
        if dissent[i] < 0.3:
            arr[i] -= 1
            arr[i+1] += 1
        elif dissent[i] > 0.5:
            if dissent[i-1] <= 0.5:
                executions.append(arr[i])
            executions.append(arr[i+1])

print([arr[i] for i in range(len) if dissent[i] < 0.3 and dissent[i-1] < 0.3])
print(executions)

Probieren Sie es online aus - klicken Sie auf die Schaltfläche "Ausführen", um es zu verwenden. Andernfalls erhalten Sie nur das, was die letzte Person erhalten hat.

Im Interesse von stare desecis hat der FEARLESS LEADER auch ein Beispiel für einen Randfall geliefert:

Input                  Output
3,2,1,4,4,1,2,3,4,5    2,2,2,4,2,3,4,5

(In diesem Beispiel gibt es keine Ausführungen.)

Schließlich sollten Sie die Bytes in Ihrem Programm als wichtige Unterstützer behandeln und minimieren. Das kürzeste Programm in Bytes gewinnt den ETERNAL FAVOR OF THE FEARLESS LEADER .

Gutschrift, wo es fällig ist

Das Konzept hierfür wurde von Lazy Drop Sort inspiriert , und der verwendete Schreibstil wurde größtenteils von psychotischen Diktaturen übernommen. Besuchen Sie sie, wenn Ihnen der Parodieaspekt gefallen hat.

Zusätzliches Guthaben geht an alle, die frühzeitig in der Sandbox darüber abgestimmt haben . Die erreichten +8 waren meine Motivation, sie neu zu schreiben, um Doppelarbeit zu vermeiden.

Nissa
quelle
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben .
Mego
Das muss verdammt viel renoviert werden. Mehr darüber, was zu tun ist und weniger über Geschichten. Was denken Sie ?
Muhammad Salman
@ MuhammadSalman Da dies zum ersten Mal geschlossen wurde, würde ich wirklich gerne wissen, was in der Zusammenfassung fehlt.
Nissa
@StephenLeppik: In der Zusammenfassung fehlt nichts (ich bin mir ziemlich sicher), aber wie gesagt, weniger Geschichten und mehr auf den Punkt gebracht Fakten darüber, was getan werden muss. Zumindest habe ich deshalb dafür gestimmt, dass es auf Eis gelegt wird. Andere können andere Gründe haben.
Muhammad Salman
+1 für die interessante Idee. -1 für den unnötigen übertriebenen Schreibstil. Interessante Geschichten, obwohl ich kein Fan von ihnen bin, können in Ordnung sein, wenn sie die Herausforderung nicht beeinträchtigen, aber ich musste die Herausforderung dreimal wiederholen (auch mit den Beispielen), um sicherzustellen, dass ich nichts verpasst habe . Auch in Ihrem tl; dr fehlt Ihnen der Punkt, wenn links <rechts, dann abweichend = 0 ist. Außerdem bin ich mir ziemlich sicher, dass Sie links minus rechts, nicht rechts minus links meinen, da dies immer negativ wäre, wenn rechts kleiner als links ist .
PunPun1000

Antworten:

2

Ruby , 146 135 Bytes

->l{e=[];i=0;l.inject{|j,k|q=(j-k)*10.0/l.size;b,c=l[i],l[i+=1];q>5&&e<<b<<c;q>0&&(l[i-1],l[i]=q<3?[b&&b-1,c&&c+1]:p);k};[l-a=[a],e-a]}

Probieren Sie es online aus!

Asone Tuhid
quelle