Implementieren Sie den Thanos-Sortieralgorithmus

93

Der Sortieralgorithmus sieht folgendermaßen aus:

Wenn die Liste nicht sortiert ist, fangen Sie die Hälfte aller Elemente (entfernen Sie sie aus der Liste). Fahren Sie fort, bis die Liste sortiert ist oder nur noch ein Element vorhanden ist (standardmäßig sortiert). Dieser Sortieralgorithmus kann je nach Implementierung unterschiedliche Ergebnisse liefern.

Über das Verfahren zum Entfernen von Elementen entscheidet die Implementierung. Die Liste sollte jedoch nach einem Durchgang des Verfahrens zum Entfernen von Elementen halb so lang sein wie zuvor. Ihr Algorithmus kann entscheiden, entweder die erste Hälfte oder die Liste, die letzte Hälfte der Liste, alle ungeraden Elemente, alle geraden Elemente nacheinander zu entfernen, bis die Liste halb so lang ist, oder alle nicht erwähnten.

Die Eingabeliste kann eine beliebige Anzahl von Elementen enthalten (innerhalb des vorgegebenen Rahmens, sagen wir bis zu 1000 Elemente), nicht nur perfekt unterteilbare Listen mit 2 ^ n Elementen. Sie müssen entweder (n + 1) / 2 oder (n-1) / 2 Elemente entfernen, wenn die Liste ungerade ist, entweder fest codiert oder während der Laufzeit zufällig entschieden wird. Überlegen Sie selbst: Was würde Thanos tun, wenn das Universum eine ungerade Menge an Lebewesen enthalten würde?

Die Liste wird sortiert, wenn kein Element kleiner als ein vorheriges Element ist. Duplikate können in der Eingabe und in der Ausgabe auftreten.

Ihr Programm sollte ein Array von Ganzzahlen (über stdin oder als Parameter, entweder einzelne Elemente oder einen Array-Parameter) aufnehmen und das sortierte Array zurückgeben (oder auf stdout ausgeben).

Beispiele:

// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]

// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half

[1, 2, 4, 3, 5] könnte zu unterschiedlichen Ergebnissen führen:

// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]

oder:

// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed

oder:

// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed

oder:

// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
vrwim
quelle
Es wäre sehr hilfreich, einen Testfall zu haben, der tatsächlich mehrere Snaps für mehrere verschiedene Snap-Algorithmen erfordert.
Unrelated String
22
Müssen wir nicht die Hälfte der Antworten sortieren und eliminieren ...
Sumner18,
4
Empfohlene Testfall: [9, 1, 1, 1, 1]. Mein eigener Algorithmus ist bei diesem Eingang fehlgeschlagen
Conor O'Brien

Antworten:

19

R , 41 Bytes

x=scan();while(any(x-sort(x)))x=x[!0:1];x

Probieren Sie es online!

Kirill L.
quelle
3
is.unsortedStattdessen any(...)wären es auch 41 Bytes.
Giuseppe
Diese Basismethode hat 44 Bytes als rekursive Funktion, ist möglicherweise golffähig: Probieren Sie es online aus!
CriminallyVulgar
18

Python 3 , 38 42 39 Bytes

q=lambda t:t>sorted(t)and q(t[::2])or t

Probieren Sie es online!

-3 bytes danke an @JoKing und @Quuxplusone

Sara J
quelle
2
40 Bytes
Jo King
39 Bytes dank TFelds Beobachtung, dass jede Permutation sein != sorted(t)muss > sorted(t).
Quuxplusone
12

Brachylog (v2), 6 Bytes

≤₁|ḍt↰

Probieren Sie es online!

Dies ist eine Funktionsübermittlung. Eingabe von links, Ausgabe nach rechts wie gewohnt. (Der TIO-Link verwendet ein Befehlszeilenargument, das die Funktion automatisch in ein vollständiges Programm einbindet, damit Sie es in Aktion sehen können.)

Erläuterung

≤₁|ḍt↰
≤₁       Assert that {the input} is sorted {and output it}
  |      Handler for exceptions (e.g. assertion failures):
   ḍ     Split the list into two halves (as evenly as possible)
    t    Take the last (i.e. second) half
     ↰   Recurse {and output the result of the recursion}

Bonusrunde

≤₁|⊇ᵇlᵍḍhtṛ↰

Probieren Sie es online!

Der Schnappschuss soll zufällig sein, nicht wahr? Hier ist eine Version des Programms, die die überlebenden Elemente nach dem Zufallsprinzip auswählt (wobei sichergestellt wird, dass die Hälfte bei jeder Runde überlebt).

≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁            Assert that {the input} is sorted {and output it}
  |           Handler for exceptions (e.g. assertion failures):
   ⊇ᵇ         Find all subsets of the input (preserving order)
     lᵍ       Group them by length
       ḍht    Find the group with median length:
         t      last element of
        h       first
       ḍ        half (split so that the first half is larger)
          ṛ   Pick a random subset from that group
           ↰  Recurse

Dies wäre eher kürzer , wenn wir die Elemente neu anordnen könnte, aber whyever möchte ein Sortieralgorithmus zu tun , dass ?

ais523
quelle
12
Ein Byte pro unendlich Stein.
Djechlin
@djechlin das unendliche Byte ist, warum Sie für den Kopf und besonders den Kiefer gehen müssen.
Die große Ente
10

Perl 6 , 30 Bytes

$!={[<=]($_)??$_!!.[^*/2].&$!}

Probieren Sie es online!

Rekursive Funktion, die die zweite Hälfte der Liste entfernt, bis die Liste sortiert ist.

Erläuterung:

$!={                         }    # Assign the function to $!
    [<=]($_)??                    # If the input is sorted
              $_                  # Return the input
                !!                # Else
                  .[^*/2]         # Take the first half of the list (rounding up)
                         .&$!     # And apply the function again
Scherzen
quelle
8

Java 10, 106 97 Bytes

L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}

-9 Bytes dank @ OlivierGrégoire .

Probieren Sie es online aus.

n+12

Erläuterung:

L->{               // Method with Integer-list as both parameter and return-type
  for(;;           //  Loop indefinitely:
      L=L.subList(0,L.size()/2)){
                   //    After every iteration: only leave halve the numbers in the list
    int p=1<<31,   //   Previous integer, starting at -2147483648
        f=1;       //   Flag-integer, starting at 1
    for(int i:L)   //   Inner loop over the integer in the list:
      f=p>(p=i)?   //    If `a>b` in a pair of integers `a,b`:
         0         //     Set the flag to 0
        :          //    Else (`a<=b`):
         f;        //     Leave the flag the same
    if(f>0)        //   If the flag is still 1 after the loop:
      return L;}}  //    Return the list as result
Kevin Cruijssen
quelle
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} ist mit Streams kürzer, aber ich konnte nicht herausfinden, wie der java.lang.IllegalStateException: stream has already been operated upon or closedFehler nach der Rückgabe des Streams
vermieden werden kann
@EmbodimentofIgnorance Dies geschieht, weil reducees sich um eine Terminaloperation handelt, die den Stream schließt. Sie werden niemals reducezweimal im selben Stream telefonieren können . Sie können jedoch einen neuen Stream erstellen.
Olivier Grégoire
1
97 Bytes
Olivier Grégoire
@ OlivierGrégoire Diese Bestellung sieht jetzt so einfach aus, dass ich sie sehe. Manchmal muss man einen Blick aus einem anderen Blickwinkel werfen, um die offensichtlichen Fehler anderer zu erkennen, denke ich. :) Vielen Dank!
Kevin Cruijssen
1
Keine Sorge, es war nicht offensichtlich: Ich habe gearbeitet, um dorthin zu gelangen. Ich habe mindestens 10 Versionen getestet, bevor ich diese gefunden habe;)
Olivier Grégoire
8

Wolfram Language (Mathematica) , 30 Byte

#//.x_/;Sort@x!=x:>x[[;;;;2]]&

Probieren Sie es online!

@Doorknob hat 12 Bytes gespeichert

J42161217
quelle
1
Anstatt die erste Hälfte zu nehmen, könnten Sie einige Bytes sparen, indem Sie jedes andere Element nehmen ( x[[;;;;2]]).
Türklinke
@Doorknob ja natürlich ...
J42161217
Ich dachte, es könnte etwas gespart werden OrderedQ, aber es könnte nicht funktionieren
Greg Martin
@ GregMartin Ich habe OrderedQin meinem ersten Ansatz verwendet (siehe Änderungen)
J42161217
7

JavaScript (ES6),  49  48 Bytes

1 Byte dank @tsh gespeichert

Entfernt jedes 2. Element.

f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a

Probieren Sie es online!

Arnauld
quelle
p++&1->a^=1
Dienstag,
6

05AB1E , 8 7 Bytes

[Ð{Q#ιн

-1 Byte dank @Emigna .

n12

Probieren Sie es online aus oder überprüfen Sie einige weitere Testfälle (oder überprüfen Sie diese Testfälle schrittweise für jede Iteration ).

7 Bytes Alternative von @Grimy :

ΔÐ{Ê>äн

n2n12

Probieren Sie es online aus oder überprüfen Sie einige weitere Testfälle (oder überprüfen Sie diese Testfälle schrittweise für jede Iteration ).

Erläuterung:

[        # Start an infinite loop:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
  {Q     #  Sort a copy, and check if they are equal
    #    #   If it is: Stop the infinite loop (and output the result implicitly)
  ι      #  Uninterweave: halve the list into two parts; first containing all even-indexed
         #  items, second containing all odd-indexed items (0-indexed)
         #   i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
   н     #  And only leave the first part

Δ        # Loop until the result no longer changes:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
       #  Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
    >    #  Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
     ä   #  Split the list in that many parts
      н  #  And only leave the first part
         # (and output the result implicitly after it no longer changes)
Kevin Cruijssen
quelle
3
Sie können ιstattdessen jede andere Elementstrategie verwenden, wenn Sie zu einer Beibehaltungsstrategie wechseln .
Emigna
1
Alternative 7 mit der Strategie "Entfernen Sie die letzte Hälfte":ΔÐ{Ê>äн
Grimy
@Grimy Das ist auch ein ziemlich netter Ansatz. Soll ich es zu meinem Beitrag hinzufügen (natürlich mit Gutschrift), oder möchten Sie es als separate Antwort veröffentlichen?
Kevin Cruijssen
Fühlen Sie sich frei, es hinzuzufügen.
Grimy
6

TI-BASIC (TI-84), 47 42 45 44 Byte

-1 Byte Danke an @SolomonUcko!

Ans→L1:Ans→L2:SortA(L1:While max(L1≠Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans

Eingabeliste ist in Ans.
Die Ausgabe erfolgt in Ansund wird implizit ausgedruckt.

Erläuterung:

Ans→L1                  ;store the input into two lists
Ans→L2
SortA(L1                ;sort the first list
                        ; two lists are needed because "SortA(" edits the list it sorts
While max(L1≠Ans        ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2  ;remove the latter half of the second list
                        ; removes (n+1)/2 elements if list has an odd length
L2→L1                   ;store the new list into the first list (updates "Ans")
SortA(L1                ;sort the first list
End
Ans                     ;implicitly output the list when the loop ends

Hinweis: TI-BASIC ist eine Token-Sprache. Die Anzahl der Zeichen entspricht nicht der Anzahl der Bytes.

Tau
quelle
Ich glaube , Sie ersetzen kann not(min(L1=Ansmit max(L1≠Anseinem Byte zu speichern.
Solomon Ucko
3

Haskell , 57 55 Bytes (nur dank ASCII)

f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x

Probieren Sie es online!


Ursprünglicher Code:

f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x

Probieren Sie es online!


Ungolfed:

f xs | sorted xs = f (halve xs)
     | otherwise = xs

sorted xs = or (zipWith (>) xs (tail xs))

halve xs = take (length xs `div` 2) xs
Sachera
quelle
1
Willkommen bei PPCG!
28.
56
Nur ASCII
57 :(
Nur ASCII
55
Nur ASCII
3

Oktave , 49 Bytes

l=input('');while(~issorted(l))l=l(1:2:end);end;l

Probieren Sie es online! Dies war eine Reise, auf der mehr Langeweile besser ist. Beachten Sie die zwei viel interessanteren Einträge unten:

50 Bytes

function l=q(l)if(~issorted(l))l=q(l(1:2:end));end

Probieren Sie es online! Anstelle der uninteressanten Imperativlösung können wir für nur ein zusätzliches Byte eine rekursive Lösung durchführen.

53 Bytes

f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())

Probieren Sie es online! Ja. Eine rekursive anonyme Funktion, dank @ ceilingcat die glänzende Antwort auf meine Frage. Eine anonyme Funktion, die eine rekursive anonyme Funktion zurückgibt, indem sie sich in ihrer Argumentliste definiert. Ich mag anonyme Funktionen. Mmmmm.

Sanchises
quelle
2

MATL , 11 Bytes

tv`1L)ttS-a

Probieren Sie es online!

Dies funktioniert, indem jeder zweite Gegenstand entfernt wird.

Erläuterung

t      % Take a row vector as input (implicit). Duplicate
v      % Vertically concatenate the two copies of the row vector. When read with
       % linear indexing (down, then across), this effectively repeats each entry
`      % Do...while
  1L)  %   Keep only odd-indexed entries (1-based, linear indexing)
  t    %   Duplicate. This will leave a copy for the next iteration
  tS   %   Duplicate, sort
  -a   %   True if the two arrays differ in any entry
       % End (implicit). A new iteration starts if the top of the stack is true
       % Display (implicit). Prints the array that is left on the stack
Luis Mendo
quelle
2
Für anfänglich sortierte Liste gebrochen: [1, 2, 3, 4, 5] sollte [1, 2, 3, 4, 5] bleiben
Falco
@ Falco Danke! Jetzt korrigiert
Luis Mendo
2

Japt , 10 Bytes

eUñ)?U:ßUë

Versuch es

eUñ)?U:ßUë     :Implicit input of array U
e              :Compare equality with
 Uñ            :  U sorted
   )           :End compare
    ?U:        :If true then return U else
       ß       :Run the programme again with input
        Uë     :  Every second element of U
Zottelig
quelle
2

Java (JDK) , 102 Byte

n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}

Da es bereits eine C # -Antwort gibt, habe ich beschlossen, mich an einer Java-Antwort zu versuchen.

Probieren Sie es online!

Verkörperung der Ignoranz
quelle
Zeit, es mit F # zu versuchen :)
aloisdg
2

Schale , 6 5 Bytes

1 Byte gespart dank Zgarb

ΩΛ<Ċ2

Probieren Sie es online!

Erläuterung

ΩΛ<Ċ2
Ω         Repeat until
 Λ<         all adjacent pairs are sorted (which means the list is sorted)
   Ċ2         drop every second element from the list
Löwe
quelle
Das sind 11 Bytes, nicht 6. ›echo -n" ΩΛ <(← ½ "| wc --bytes 11
Mike Holler
@MikeHoller Wie viele andere Golfsprachen verwendet Husk eine benutzerdefinierte Codepage, um Zugriff auf mehr verschiedene Charaktere zu erhalten: github.com/barbuz/Husk/wiki/Codepage
Leo
Vielen Dank, ich habe heute etwas gelernt :)
Mike Holler
1
Verwenden Sie Ċ2anstelle von (←½, um ein Byte zu speichern.
Zgarb
2

Gaia , 9 8 Bytes

eo₌⟨2%⟩↻

Probieren Sie es online!

Erläuterung:

e		| eval input as a list
       ↻	| until
 o		| the list is sorted
  ₌		| push additional copy
   ⟨2%⟩  	| and take every 2nd element
Giuseppe
quelle
2

Julia 1.0 , 30 Bytes

-x=x>sort(x) ? -x[1:2:end] : x

Probieren Sie es online!

Nimmt jedes zweite Element des Arrays, wenn es nicht sortiert ist.

niczky12
quelle
Verwenden Sie einen ASCII-Operator wie -für 20 Byte. auch zählen wir fast immer keine zeichen: | also wäre es schön, wenn das aus dem Header entfernt würde
ASCII
Das hat sich geändert. Danke für 2 Bytes!
niczky12
2

C ++ (gcc) , 103 Bytes

Ich kann nichts dazu sagen, aber ich habe die Version von movatica verbessert, indem ich die Includes reduziert und auto verwendet habe.

-2 Bytes: ceilingcat
-2 Bytes: Nur ASCII

#include<regex>
auto f(auto l){while(!std::is_sorted(l.begin(),l.end()))l.resize(l.size()/2);return l;}

Probieren Sie es online!

peterzuger
quelle
1
Einen Grund, den du nicht einfach benutzen kannst l.size()/2?
Nur ASCII
Ja, so geht das nicht :)
Peterzuger
1
Was meinst du? Rückgabe einer Liste der Größe (n+1)/2oder (n-1)/2sind beide gültig. hmm ....
Nur ASCII
Ohh hoppla, habe das nicht gesehen, danke
Peterzuger
1

VDM-SL , 99 Bytes

f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 

Nie zuvor in vdm eingereicht, daher sprachspezifisch nicht sicher. Ich habe also eine Funktionsdefinition übergeben, die a annimmt seq of intund a zurückgibtseq of int

Ein vollständiges Programm könnte so aussehen:

functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 
Abgelaufene Daten
quelle
1

Pyth, 10 Bytes

.W!SIHhc2Z

Probieren Sie es hier online aus . Dadurch wird die zweite Hälfte bei jeder Iteration entfernt und abgerundet. Um die erste Hälfte abzurunden, ändern Sie die hauf e.

.W!SIHhc2ZQ   Q=eval(input())
              Trailing Q inferred
  !SIH        Condition function - input variable is H
   SIH          Is H invariant under sorting?
  !             Logical not
      hc2Z    Iteration function - input variable is Z
       c2Z      Split Z into 2 halves, breaking ties to the left
      h         Take the first half
.W        Q   With initial value Q, execute iteration function while condition function is true
Sok
quelle
Jedes andere Element der Liste zu nehmen ist kürzer. Ersetzen hcdurch %. Auf diese Weise können Sie auch die Znachfolgende Lambda-Variable löschen und von Pyth implizit füllen lassen, sodass insgesamt 2 Bytes gespeichert werden.
Hakr14
1

C ++ (gcc) , 139 137 116 Bytes

-2 Bytes Danke an Ceilingcat, -21 Bytes Danke an PeterZuger

#include<regex>
auto f(std::vector<int>l){while(!std::is_sorted(l.begin(),l.end()))l.resize(-~l.size()/2);return l;}

Ändern Sie die Größe des Vektors auf die erste Hälfte, bis er sortiert ist.

Probieren Sie es online!

movatica
quelle
1
Importe müssen in die Byteanzahl einbezogen werden. Fügen Sie daher include
Ausführungsform der Ignoranz hinzu
Danke, ich werde sie hinzufügen.
Movatica
1

K (OK) , 22 20 Bytes

Lösung:

{(*2 0N#x;x)x~x@<x}/

Probieren Sie es online!

Durchlaufen Sie die Eingabe, bis sie sortiert ist. Wenn sie nicht sortiert ist, nehmen Sie zuerst n / 2 Elemente.

{(*2 0N#x;x)x~x@<x}/ / the solution
{                 }/ / lambda that iterates
                <x   / indices that sort x ascending (<)
              x@     / apply (@) these indices back to x
            x~       / matches (~) x? returns 0 or 1
 (       ; )         / 2-item list which we index into
          x          / original input (ie if list was sorted)
       #x            / reshape (#) x
   2 0N              / as 2 rows
  *                  / take the first one      

Bearbeitungen:

  • -2 Bytes dank ngn
Streetster
quelle
1
(.5*#x)#x->*2 0N#x
ngn
Ich habe darüber nachgedacht, 2 0Naber angenommen, es würde länger dauern (ohne zu testen), danke!
Streetster
0

Retina , 38 Bytes

\d+
*
/(_+),(?!\1)/+`,_+(,?)
$1
_+
$.&

Probieren Sie es online! Nimmt durch Kommas getrennte Zahlen. Erläuterung:

\d+
*

In Unary konvertieren.

/(_+),(?!\1)/+`

Wiederholen, während die Liste nicht sortiert ist ...

,_+(,?)
$1

... lösche jedes gerade Element.

_+
$.&

In Dezimalzahl konvertieren.

Neil
quelle
0

C (gcc) , 66 Bytes

Fängt die zweite Hälfte der Liste bei jeder Iteration ab ( n/2+1Elemente, wenn die Länge ungerade ist).

Probieren Sie es online!

Übernimmt die Eingabe als Zeiger auf den Anfang eines Arrays intgefolgt von seiner Länge. Ausgabe durch Rückgabe der neuen Länge des Arrays (direkte Sortierung).

t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}

Ungolfed-Version:

t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
  l: // jump label, will be goto'ed after each snap
  for(i = 0; i < n - 1; ) { // go through the whole array …
    if(a[i] > a[++i]) { // … if two elements are in the wrong order …
      n /= 2; // … snap off the second half …
      goto l; // … and start over
    }
  }
  a = n; // implicitly return the new length
}
OOBalance
quelle
Schlagen Sie ~i+nstattdessen vori<n-1
ceilingcat