Tor
Schreiben Sie eine Funktion oder ein Programm, und sortieren Sie ein Array von Ganzzahlen in absteigender Reihenfolge nach der Anzahl der Einsen in ihrer Binärdarstellung. Es ist keine sekundäre Sortierbedingung erforderlich.
Beispiel sortierte Liste
(unter Verwendung von 16-Bit-Ganzzahlen)
Dec Bin 1's
16375 0011111111110111 13
15342 0011101111101110 11
32425 0111111010101001 10
11746 0010110111100010 8
28436 0000110111110100 8
19944 0100110111101000 8
28943 0000011100011111 8
3944 0000011111101000 7
15752 0011110110001000 7
825 0000000011111001 6
21826 0101010101000010 6
Eingang
Ein Array von 32-Bit-Ganzzahlen.
Ausgabe
Ein Array der gleichen Ganzzahlen, sortiert wie beschrieben.
Wertung
Dies ist Codegolf für die geringste Anzahl von Bytes, die in einer Woche ausgewählt werden können.
Antworten:
J (11)
Dies ist eine Funktion, die eine Liste annimmt:
Wenn Sie ihm einen Namen geben möchten, kostet dies ein zusätzliches Zeichen:
Erläuterung:
\:
: nach unten sortieren+/
: die Summe von"1
: jede Reihe von#:
: binäre Darstellungquelle
\:1#.#:
was ein paar Bytes spart.JavaScript, 39
Update: Jetzt kürzer als Ruby.
40
Erläuterung:
q ist eine rekursive Funktion. Wenn x oder y 0 sind, wird zurückgegeben
x-y
(eine negative Zahl, wenn x Null ist, oder eine positive Zahl, wenn y Null ist). Andernfalls wird das niedrigste Bit entfernt (x&x-1
) aus x und y entfernt und wiederholt.Vorherige Version (42)
quelle
~y
funktionieren statt-!y
?!x|-!y
ungleich Null.~
passt nicht wirklich hinein, da es für viele Eingaben ungleich Null ist (einschließlich Null)Rubin 41
Prüfung:
quelle
Python 3 (44):
quelle
Gemeiner Lisp, 35
logcount
Gibt die Anzahl der Ein-Bits in einer Zahl zurück. Für eine Listel
haben wir:Als eigenständige Funktion und worauf ich die Byteanzahl stützen werde:
quelle
Python 3,
90777267 Zeichen.Unsere Lösung verwendet eine Eingabe von der Befehlszeile und gibt die Nummer in absteigender Reihenfolge (67 Zeichen) oder aufsteigender Reihenfolge (66 Zeichen) aus.
Absteigende Reihenfolge
Vielen Dank an @daniero für den Vorschlag, ein Minus in der 1 zu verwenden, um es umzukehren, anstatt ein Slice zu verwenden, um das Array am Ende umzukehren! Dies sparte effektiv 5 Zeichen.
Nur um es zu veröffentlichen, würde die Version in aufsteigender Reihenfolge (die die erste war, die wir gemacht haben) ein Zeichen weniger haben.
Aufsteigende Reihenfolge :
Vielen Dank an @ Bakuriu für den Vorschlag key = lambda x… . ; D
quelle
0
wird immer ein Teil Ihrer Ausgabe dann sein; Das stimmt nicht.raw_input()
paar Zeichen verwenden und ablegen?[]
Innere fallen lassensorted
. Die Ausgabe dieses Programms ist auch die Anzahl der Einsen in den eingegebenen Zahlen sortiert, aber Sie sollten die Anzahl, die Sie in der Eingabe erhalten haben, sortiert nach der Anzahl von1
s ausgeben . So etwas wie:print(sorted(input().split(), key=lambda x:bin(int(x)).count('1')))
wäre richtig.JavaScript [76 Bytes]
wo
a
ist ein Eingabearray von Zahlen.Prüfung:
quelle
..
funktioniert? Mein Verständnis ist , dass , wennx = 5
danneval(x + r)
wirdeval(5..toString(2).match(/1/g).length)
das ist, glaube ich, ungültig. Vielen Dank.'string'.length
oder tun[1,2,3].pop()
. Bei Zahlen können Sie dasselbe tun, aber Sie sollten berücksichtigen, dass der Parser nach einem einzelnen Punkt nach einem Bruchteil der Zahl sucht, der einen Gleitkommawert erwartet (wie in123.45
). Wenn Sie eine ganze Zahl verwenden , sollten Sie „sagen“ den Parser , dass ein Bruchteil leer ist, einen zusätzlichen Punkt Einstellung bereits vor dem Adressieren:123..method()
.match(/1/g).length
durchreplace(/0/g,"")
.a.sort(function(x,y){r='..toString(2).match(/1/g).length';return eval(y+r+-x+r)})
Mathematica 30
Verwendung:
quelle
k [15 Zeichen]
Beispiel 1
Beispiel 2 (alle Zahlen sind 2 ^ n -1)
quelle
Mathematica 39
IntegerDigits[#,2]
wandelt eine Zahl zur Basis 10 in eine Liste mit Einsen und Nullen um.Tr
summiert die Ziffern.Testfall
quelle
Java 8 -
87/11381/11160/8060/74/48 ZeichenDies ist kein vollständiges Java-Programm, sondern nur eine Funktion (um genau zu sein eine Methode).
Es wird davon ausgegangen, dass
java.util.List
undjava.lang.Long.bitCount
importiert werden, und hat 60 Zeichen:Wenn keine vorimportierten Sachen erlaubt sind, ist dies hier mit 74 Zeichen:
Fügen Sie weitere 7 Zeichen hinzu, falls dies erforderlich sein sollte
static
.[4 Jahre später] Oder wenn Sie es vorziehen, könnte es ein Lambda sein (danke @KevinCruijssen für den Vorschlag), mit 48 Bytes:
quelle
Integer.bitCount(x)<Integer.bitCount(y)?-1:1;
? Benötigen Sie das-1,0,1
Verhalten?<Integer>
durch Leerzeichen zu ersetzen ?Long
, die etwas Platz sparen :)a.sort((x,y)->Long.bitCount(x)-Long.bitCount(y));
Python 2.x - 65 Zeichen (Bytes)
Das sind tatsächlich 66 Zeichen, 65, wenn wir es zu einer Funktion machen (dann brauchen Sie etwas, um es zu nennen, das lamer ist, um es zu präsentieren).
Demo in Bash / CMD:
quelle
sum(int(d)for d in bin(x)[2:])
zusum(map(int,bin(x)[2:]))
print sorted(input(),key=lambda x:-bin(x).count('1'))
Matlab, 34
Eingabe in 'a'
Funktioniert für nicht negative Zahlen.
quelle
C - 85 Bytes (
108106 Bytes)Portable Version auf GCC / Clang / wo
__builtin_popcount
immer verfügbar (106 Bytes):Ultrakondensierte, nicht tragbare, kaum funktionierende MSVC-Version (85 Byte):
Die erste Zeile ist in der Byteanzahl enthalten
#define
, die anderen Zeilen sind nicht erforderlich.Die aufzurufende Funktion entspricht
s(array, length)
den Spezifikationen.Kann die
sizeof
in der portablen Version fest codieren , um weitere 7 Zeichen zu speichern, wie es einige andere C-Antworten taten. Ich bin mir nicht sicher, welches Modell in Bezug auf das Verhältnis von Länge und Nutzbarkeit am besten geeignet ist, entscheiden Sie.quelle
sizeof l
Speichert ein Byte. Das schrecklich Hässliche#define p-__builtin_popcount(
kann helfen, ein anderes zu retten.PowerShell v3,
615853Der ScriptBlock für das
Sort-Object
Cmdlet gibt für jede 1 in der binären Darstellung der Zahl ein Array mit Einsen zurück.Sort-Object
sortiert die Liste basierend auf der Länge des Arrays, das für jede Nummer zurückgegeben wird.Ausführen:
quelle
$f={
ist überflüssig,while
->for
,-band1
->%2
,-des
->-d
und andere Golf-Tricks. Es ist klar. Können Sie erklären, wie man arbeitet$args|sort{@(1,1,...,1)}
? Es ist Arbeit! Wie vergleicht die Sortierung Arrays ohne explizite.Count
? Wo kann man darüber lesen? Vielen Dank!help Sort-Object -Parameter property
Ich weiß nicht, wo die Standardsortiereigenschaft für Typen definiert ist, aber für Arrays ist sie Count oder Length.$args|sort{while($_){if($_-band1){$_};$_=$_-shr1}}-des
gibt ein falsches Ergebnis. Deshalb ist es nichtCount
. Es ist sehr interessant. Danke noch einmal.ECMAScript 6, 61
Angenommen,
z
ist die EingabeTestdaten
Danke, Zahnbürste für die kürzere Lösung.
quelle
z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d)
(und danke für die Gegenstimme).R ,
1329694888475735351 Bytes-20 dank J.Does Implementierung -2 mehr dank Giuseppe
Mein ursprünglicher Beitrag:
Probieren Sie es online!
Ich habe verschiedene Methoden ausprobiert, bevor ich zu diesem Ergebnis kam.
Matrix-Methode: Erstellt eine zweispaltige Matrix, eine Spalte mit dem Eingabevektor, eine aus der Summe der Binärdarstellung, und sortiert dann nach der Summe der Binärdarstellungen.
Nicht-Matrix: Es wurde erkannt, dass ich die Matrixfunktion wegwerfen und stattdessen einen Vektor von Binärwerten erstellen, diese summieren, ordnen und dann die geordneten Werte verwenden könnte, um den Eingabevektor neu zu ordnen.
Kleinere Änderungen
Kleinere Änderungen Konvertieren des gesamten Objekts in eine Codezeile anstelle von zwei durch ein Semikolon getrennten.
Summenmethode Anstatt die Spalten mit der
colSums
von erstellten binären Matrix hinzuzufügensapply
, habe ich die Elemente in der Spalte vorsapply
"Fertig" hinzugefügt .Abnahme auf Umkehr Ich wollte eigentlich die Abnahme verkürzen, aber R quäkelt mich an, wenn ich versuche,
decreasing
dieorder
Funktion zu verkürzen , was notwendig war, um die gewünschte Reihenfolge alsorder
Standard zu erreichen. Dann erinnerte ich mich an dierev
Funktion zum Umkehren eines Vektors. EUREKA !!! Die letzte Änderung in der endgültigen Lösung bestandfunction
darinpryr::f
, 2 weitere Bytes einzusparenquelle
Haskell, 123C
Dies ist der erste Weg, den ich mir überlegt habe, aber ich wette, es gibt einen besseren Weg, dies zu tun. Wenn jemand eine Möglichkeit zum Golfen von Haskell-Importen kennt, wäre ich sehr interessiert, das zu hören.
Beispiel
Ungolfed version (mit erklärungen)
quelle
mod
, zu verwendenn`mod`2
? Es hat die gleiche Priorität wie Multiplikation und Division.Kaffeeskript (94)
Lesbarer Code (212):
Optimiert (213):
Verschleierung (147):
Ternäre Operatoren sind zu lang (129):
Noch zu lange, hör auf zu wirken (121):
Finale (94):
quelle
Smalltalk (Smalltalk / X), 36 (oder vielleicht 24)
Eingabe in a; destruktiv sortiert in einem:
funktionale Version: gibt ein neues sortiertes Array zurück:
Es gibt sogar eine kürzere Variante (Übergabe des Namens oder der Funktion als Argument) in 24 Zeichen. Aber (seufz) es wird zuletzt am höchsten sortiert. Soweit ich verstanden habe, wurde dies nicht verlangt, daher nehme ich das nicht als Golf-Score:
quelle
PHP 5.4+ 131
Ich weiß nicht einmal, warum ich mich mit PHP beschäftige, in diesem Fall:
Verwendung:
quelle
Scala, 58
quelle
DFSORT (IBM Mainframe-Sortierprodukt) 288 (jede Quellzeile besteht aus 72 Zeichen und muss an Position 1 ein Leerzeichen enthalten.)
Nur zum Spaß und ohne Mathematik.
Nimmt eine Datei (kann von einem Programm ausgeführt werden, das ein "Array" verwendet) mit den ganzen Zahlen. Vor dem Sortieren werden die Ganzzahlen in Bits (in einem 16-stelligen Feld) übersetzt. Dann ändert sich die 0 in den Bits zu nichts. SORT Absteigend vom Ergebnis der geänderten Bits. Erstellt die sortierte Datei nur mit den ganzen Zahlen.
quelle
C
quelle
C #,
8889Bearbeiten: absteigende Reihenfolge fügt ein Zeichen hinzu.
quelle
Javascript 84
Inspiriert von anderen Javascript-Antworten, aber ohne eval und Regex.
quelle
Javascript (82)
quelle
Nachschrift, 126
Da die Liste der Werte, nach denen wir sortieren, im Voraus bekannt und sehr begrenzt ist (32), kann diese Aufgabe auch dann problemlos durchgeführt werden, wenn keine Sortierfunktion integriert ist, indem übereinstimmende Werte für 1..32 ausgewählt werden. (Ist es O (32n)? Wahrscheinlich).
Die Prozedur erwartet das Array auf dem Stack und gibt das sortierte Array zurück.
Oder rituell von Leerzeichen und Lesbarkeit befreit:
Wenn es gespeichert ist,
bits.ps
kann es folgendermaßen verwendet werden:Ich denke, es ist effektiv dasselbe wie dieses Perl (es gibt hier auch noch kein Perl):
Obwohl , dass , im Gegensatz zu Postscript, kann leicht golfed werden:
quelle
C -
124111Implementiert als Methode und unter Verwendung der Standardbibliothek für die Sortierung. Ein Zeiger auf das Array und die Größe sollten als Parameter übergeben werden. Dies funktioniert nur auf Systemen mit 32-Bit-Zeigern. Auf 64-Bit-Systemen müssen einige Zeichen für die Angabe von Zeigerdefinitionen verwendet werden.
Einzug für die Lesbarkeit
Beispielanruf:
quelle
Java 8: 144
In erweiterter Form:
Wie Sie sehen können, funktioniert dies, indem Sie das
args
in einStream<String>
konvertieren und dannStream<Integer>
mit derInteger::decode
Funktionsreferenz in ein konvertieren (kürzer alsparseInt
oder)valueOf
) und anschließend nach sortierenInteger::bitCount
, dann in ein Array einfügen und es ausdrucken.Streams machen alles einfacher.
quelle