Hamminggewicht mit geringem Hamminggewicht berechnen

19

Erstellen Sie ein Programm, das das Hamming-Gewicht einer Zeichenfolge berechnet . Gewinner ist das Programm mit dem niedrigsten Hamminggewicht.

Regeln:

  • Die Hamming-Gewichtung für ein ASCII-Zeichen ist definiert als die Gesamtzahl der 1in seiner Binärdarstellung festgelegten Bits .
  • Angenommen, die Eingabecodierung ist 7-Bit-ASCII, die über den für Ihre Sprache normalen Eingabemechanismus (z. B. stdin, args usw.) übergeben wird.
  • Geben Sie das Ergebnis als Zahl an stdout oder an den Standard- / Normalausgabemechanismus aus, den Ihre Sprache verwendet.
  • Es sollte selbstverständlich sein, aber Sie müssen in der Lage sein, das Programm im wirklichen Leben auszuführen, damit es eine gültige Lösung darstellt.
  • Gewinner ist die Lösung, deren Code das niedrigste Hamming-Gewicht hat.
  • Entschuldigung, keine Lösungen im Leerraum für diese! Ok, Sie können in Leerzeichen codieren, jetzt habe ich die Regeln aussortiert :)

Beispiele pro Zeichen:

char |  binary  | weight
-----+----------+-------
a    | 01100001 | 3
x    | 01111000 | 4
?    | 00111111 | 6
\x00 | 00000000 | 0
\x7F | 01111111 | 7
Polynom
quelle
Wenn wir 0x20/ ASCII 32 als Referenz nehmen, ist das Summen von hello world10 nicht gleich 11?
Cristian Lupascu
Warum ist das Gewicht von hello world11? Nur 10 Zeichen unterscheiden sich von einem Leerzeichen. Auch - das Hamming-Gewicht eines Programms scheint nur seine Länge ohne Leerzeichen zu sein. Nicht so anders als beim normalen Codegolf.
Ugoren
Entschuldigung, ich habe das total vermasselt. Wikipedia's Hamming Weight Artikel ist ziemlich irreführend und ich habe die Regeln total befolgt. Jetzt umschreiben. Update: Ok, neu geschrieben, um die Anzahl der Bits zu definieren, die in der ASCII-Zeichenfolge auf 1 gesetzt sind.
Polynom
@ugoren Eine Lösung mit niedrigerem ASCII-Wert hat ein geringeres Hamming-Gewicht.
Polynom
1
Jetzt macht alles Sinn. VERWENDEN SIE GROSSBUCHSTABEN, BEACHTEN SIE ~UND o.
Ugoren

Antworten:

6

J (33)

Einer unter 34!

+/,#:3 u:

Stark inspiriert von dieser Antwort , aber ein Hamminggewicht von eins weniger.

   +/,#:3 u:'+/,#:3 u:'
33
ɐɔıɐɔuʇǝɥʇs
quelle
8

J, Gewicht 34

+/,#:a.i.

Verwendung - Platzieren Sie die zu messende Zeichenfolge in Anführungszeichen am Ende:

   +/,#:a.i.'+/,#:a.i.'
34

Alternativ können Sie Eingaben über die Tastatur vornehmen (Gewicht 54):

   +/,#:a.i.1!:1[1
hello
21
Gareth
quelle
Es gibt nur einen Weg, dies zu schreiben :)
ephemient
Es gibt keine ... Ich habe eine Lösung gefunden, die ein um eins geringeres Hamminggewicht hat.
ɐɔı Junuʇǝɥʇs
Ich versuche nicht, ein Buzzkill zu sein, aber die Regeln verlangen ein Programm, kein Fragment.
FUZxxl
5

J , 39

+/,#:a.i:]

Dies ist eine Funktion mit einem Argument. (Oder ]direkt durch die Zeichenfolge ersetzen ; Gareth merkt an, dass dies die Kosten auf 34 senkt.)

   + /, #: ai:] 'Hallo Welt'
45
   + /, #: ai:] '+ /, #: ai:]'
39
vergänglich
quelle
Große Köpfe denken ähnlich. :-)
Gareth
5

Python, 189

print sum(bin(ord(A)).count("1")for A in raw_input())
Keith Randall
quelle
2
Das Python 3-Äquivalent print(sum(bin(ord(A)).count('1')for A in input()))hat eine Punktzahl von 180.
dan04
4
@ Dan04: Verwenden Sie doppelte Anführungszeichen anstelle von einfachen für 176.
Keith Randall
5

QBasic, 322 311 286 264

H$=COMMAND$
FOR A=1 TO LEN(H$)
B=ASC(MID$(H$,A,1))
WHILE B>0
D=D+B MOD 2
B=B\2
WEND
NEXT
?D

Irgendwie das richtige Werkzeug für den Job, nervt natürlich immer noch.

hörte auf, sich gegen den Uhrzeigersinn zu drehen
quelle
1
+1 für die Verwendung einer meiner Lieblingssprachen aller Zeiten. Es ist die erste Sprache, die ich gelernt habe, auf einem PC zu programmieren.
Polynom
5

Unär 0

Sie alle wussten, dass es kommen würde. Zuerst das BrainFuck-Programm:

,[[>++[>>+>+<<<-]>>>
[<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>
[<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-]
[-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>[<<<<<<->>>->>>
[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<<
[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<<
[>>+<[>>+>+<<<-]>>>[<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>
[<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]> 
[-]>[<<<<<<->>>->>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<<
[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<<]>>>
[>+>+<<-]>>[<<+>>-][-]+<[>[-]<<[<<->>-]<<[>>+<<-]>>>[-]]>[<<<+<[-]>>>>
[-]]<<[->>>>+<<<<]<[-<<+>>]<<],]>>>>>>>.

Ich habe Zeilenumbrüche hinzugefügt, um es "lesbar" zu machen, aber es hat eine Hamming-Gewichtung von 4066. Es funktioniert, indem wiederholt der Quotient / die Reste einer Eingabezeichenfolge abgerufen und alle Reste addiert werden. Natürlich, sollten Sie es auf sich laufen lassen, erhalten Sie: 226 (4066% 256) (technisch gesehen \ xe2) so klar, dass es sich selbst zum Sieger erklärt.

Jetzt konvertieren wir es zu Unary und holen

000 ... 9*google^5.9 0's ... 000

Wir verwenden eine unäre Implementierung mit NULL-Zeichen \ x00 für '0' und Boom mit einer Hamming-Gewichtung von 0.

Bonusfrage : Für welche ASCII-Zeichen ckönnen Sie dieses Programm mit einer Zeichenfolge Nausführen, die aus Wiederholungen besteht, und dieses Zeichen ausgeben lassen. (ZB eine Zeichenfolge von 32 Leerzeichen ergibt ein Leerzeichen). Welche Werte der NArbeit (entweder eine unendliche Anzahl von ihnen wird funktionieren, oder keiner wird funktionieren).

walpen
quelle
1
Ich bin nicht sicher, ob ich diese Lösung verstehe. Das Brainfuck-Programm hat ein enormes Hamming-Gewicht. Akzeptiert Unary Null-Bytes als Programm oder müssen Sie Unary erneut implementieren? Wenn es das letztere ist, ist es keine wirklich gültige Lösung - jeder könnte einfach sagen "Ich definiere eine Programmiersprache, in der ein einzelnes Eingabebyte {result} ergibt" und jede Code-Golf-Herausforderung auf der Site gewinnen.
Polynom
1
Ein Nullzeichen Unary wäre in Ordnung. Alles, was Sie brauchen, ist ein EOF, um zu sagen, dass Sie aufhören sollen zu zählen. In der Tat ist hier ein Pseudo-C, um diese Datei zu lesen: Es main(){ bignum Unarynum = 0; int c; while(EOF!=(c=readchar())){ Unarynum++; } return Unarynum; }spielt überhaupt keine Rolle, was Sie als unären Charakter auswählen (solange es nicht EOF ist).
Walpen
1
Nun, hier ist ein für C unärer Compiler, der mit Null-Zeichen gut funktioniert : ideone.com/MIvAg . Natürlich würde die Datei, die benötigt wird, um dieses Programm zu erstellen, nicht in das Universum passen, aber wir haben die Fähigkeit, es auszuführen.
Walpen
3
Wenn Sie nicht können tatsächlich es laufen, ist es nicht wirklich eine Lösung.
Polynom
4
Wie Carl Sagan einmal sagte: "Wenn Sie das Hamming-Gewicht einer Saite berechnen möchten, müssen Sie zuerst 10 ^ 500 Universen erfinden." (Milliarden und Milliarden, sogar)
Walpen
4

C, Gewicht 322 263 256

Zählt das Hamming-Gewicht des Hamming-Gewichts?

main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))D+=*A%2;printf("%d",D-2);}

Meistens Standard-Golftechniken verwendet.
Eine einzelne Schleife berechnet das Gewicht (Verschieben nach rechts und Addieren bis Null) und tastet die Zeichenfolge ab (rückt den Zeiger vor, wenn Null erreicht ist).
Angenommen, es Dwird 2 (Einzelparameter) initialisiert.

Hamming gewichtsspezifische Optimierungen:
1. ABDHmit jeweils 2 Gewichten, die für Namen verwendet werden.
2. *++Hlieber als H[1].

ugoren
quelle
Hah, ich habe deinen ersten Satz bis jetzt überhaupt nicht verstanden.
Brotkasten
Sie können die Punktzahl auf 230 main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))if(*A%2)printf("@");}
herabsetzen,
@schnaader, ich wusste nie, dass @es im unären System eine Ziffer gibt. Ich dachte , es nur verwendet 0.. 0. Aber wenn Sie dies gehen möchten, ist der Weg printf("@"+*a%2)kürzer.
Ugoren
@ugoren: Kommt auf die Konvention / Definition von unary an. Beispiel: en.wikipedia.org/wiki/Unary_numeral_system verwendet Zählmarken und sagt: "Es gibt kein explizites Symbol, das Null in Unary darstellt, wie es in anderen traditionellen Basen der Fall ist."
Schnaader
@schnaader, OK, aber ich denke, dass es die Anforderung "als Zahl" zu weit ausdehnt.
Ugoren
4

Golfscript 84 72 58

{2base~}%{+}*

(Dank an Howard und Peter Taylor für ihre Hilfe)

Eingabe: Die Eingabezeichenfolge muss sich auf dem Stapel befinden (als Befehlszeilenargument übergeben oder einfach auf dem Stapel abgelegt).

echo -nWenn Sie es über die Befehlszeile ausführen, stellen Sie sicher, dass Sie es verwenden , da sonst auch die nachgestellte Zeile gezählt wird.

Ausgabe: Druckt den Hamming-Gewichtswert auf die Konsole

Das Programm kann hier getestet werden .

Cristian Lupascu
quelle
1
Unterscheidet Golfscript zwischen Groß- und Kleinschreibung? Wenn nicht, können Sie ein paar Bits speichern, indem Sie BASEanstelle von verwenden base. Update: Nur überprüft, BASEfunktioniert nicht. Gute Lösung :)
Polynom
@Polynomial Ich habe das versucht, nachdem ich deinen TEST/ testKommentar gesehen habe :) Aber es funktioniert nicht.
Cristian Lupascu
Sie können loswerden, {...}2*indem Sie sich zuerst bewerben 2base~. Erzielt einen Score von 72.
Howard
@Howard danke für diesen tollen Tipp! Ich habe es in meiner Antwort angewendet.
Cristian Lupascu
Ihr Testmechanismus ist falsch, weil Sie eine wichtige Einschränkung Ihrer Web GolfScript-Seite vergessen haben. Sie sollten einen ;String vor dem String haben, den Sie durch stdin ersetzen, damit dies (;nicht erforderlich ist. Dann bringt es Howards Beobachtung auf 65.
Peter Taylor,
2

Perl, 80 (22 Zeichen)

Gemacht und gemacht:

perl -0777nE 'say unpack"%32B*"'

Oder hier ist eine alternative Version mit einem Gewicht von 77 (21 Zeichen):

perl -0777pE '$_=unpack"%32B*"'

Diese Version gefällt mir allerdings nicht so gut, da in der Ausgabe die letzte Newline weggelassen wird.

Um die Gewichtung zu berechnen, gehe ich davon aus, dass ich die Zeichen auf die übliche Weise zähle (mit Ausnahme von perl -e/ -E, aber einschließlich anderer Optionszeichen). Wenn sich Leute aus irgendeinem Grund darüber beschweren, ist das Beste, was ich ohne Optionen tun kann, 90 (26 Zeichen):

$/=$,,say unpack"%32B*",<>

Beispielnutzung:

$ perl -0777nE 'say unpack"%32b*"' rickroll.txt
7071

Boom.

Brot-Box
quelle
2

Pyth - 15

Haftungsausschluss: Diese Antwort ist nicht gewinnberechtigt, da Pyth jünger als diese Herausforderung ist.

Verwendet .Bfür die binäre Darstellung und zählt die Anzahl der "1"'s.

/.BQ\1

Übernimmt die Eingabe in einer Zeichenfolge, um im zVergleich zu speichern Q.

Probieren Sie es hier online aus .

Maltysen
quelle
1

Scala 231

readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum

Selbsttestcode:

"""readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum""".map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum

mit selbsttest modifikation.

Benutzer unbekannt
quelle
Es ist Gewicht 495, nicht 231. Sie können Gewicht 231 nicht mit 126 Zeichen erhalten - das ist ein Durchschnitt von weniger als 2, und alle druckbaren Zeichen (außer @und Leerzeichen, die Sie nicht verwenden) haben mindestens Gewicht 2.
Ugoren
1
@ugoren: Aber es sind nur 65 Zeichen. Das Programm wird fast zweimal gedruckt: Einmal der Code zur Berechnung des Hamming Weight und ein zweites Mal als statische Eingabe zur Berechnung für das Programm. Dem berechnenden Teil fehlt jedoch das "readLine ()", da es die Literal-Eingabe übernimmt. Ich habe versucht, die Antwort selbst zu klären.
Benutzer unbekannt
1

Java, Gewicht 931 774 499 454

Ich denke, dies ist die einzige Antwort im Moment mit einem Gewicht von über 300.

class H{public static void main(String[]A){System.out.print(new java.math.BigInteger(A[0].getBytes()).bitCount());}}

Erwartet Eingabe als Befehlszeilenargument.

SuperJedi224
quelle
1

GNU sed -r , 467 + 1

(+1 für die Verwendung von -r- oder sollte das +4 sein?)

Ausgabe als unärer Wert pro Quellzeile; Um in eine Dezimalsumme umzuwandeln, leiten Sie die Ausgabe in um | tr -d "\n" | wc -c. Zählt alle druckbaren ASCII-Zeichen (32-126) plus Zeilenvorschub (10).

s@[a-z]@\U& @g
s@[?{}~]@      @g
s@[][/7;=>OW|^]@     @g
s@[-'+.3569:<GKMNSUVYZ\\]@    @g
s@[#%&)*,CEFIJL1248ORTX]@   @g
s@$|[!"$(ABDH0P`]@  @g
y! @!11!

Es ist schwer zu vermeiden, alle Zeichen aufzulisten, aber wir können dies reduzieren, da Kleinbuchstaben ein Hamming-Gewicht von eins mehr haben als die entsprechenden Großbuchstaben. Wir bevorzugen Zeilenvorschub (Punktzahl 2) gegenüber Semikolon (Punktzahl 5) als Anweisungstrennzeichen. Wir bevorzugen @(Punktzahl 1) oder !(Punktzahl 2) gegenüber /(Punktzahl 5) als Musterbegrenzer.

Hinweis - Um die richtigen Zeichensätze zu erhalten, habe ich diese Tabelle aus der man asciinach Gewicht sortierten Tabelle in erstellt . Addieren Sie einfach die Punkte rechts und unten, um das Gesamtgewicht jedes Charakters zu erhalten:

   2 4   3 5 6   7 
   ---  ------   - 
0:   @   0 P `   p |0

1: ! A   1 Q a   q | 
2: " B   2 R b   r |1
4: $ D   4 T d   t | 
8: ( H   8 X h   x | 

3: # C   3 S c   s | 
5: % E   5 U e   u | 
6: & F   6 V f   v |2
9: ) I   9 Y i   y | 
A: * J   : Z j   z | 
C: , L   < \ l   | | 

7: ´ G   7 W g   w | 
B: + K   ; [ k   { |3
D: - M   = ] m   } | 
E: . N   > ^ n   ~ | 

F: / O   ? _ o     |4
   ---  ------   -  
    1      2     3

Dies könnte sich für andere als nützlich erweisen.

Toby Speight
quelle
0

Julia 262 268

Geänderte Version nutzt praktische 'count_ones'-Funktion zum Speichern von 6 (262)

show(mapreduce(x->count_ones(x),+,map(x->int(x),collect(ARGS[1]))))

Alte Version ohne eingebaute One-Counting-Funktion (268)

show(mapreduce(x->int(x)-48,+,mapreduce(x->bits(x),*,collect(ARGS[1]))))

Verwendet ein Befehlszeilenargument für die Eingabe.

Bakerg
quelle
0

CJam 52 oder 48

Wenn die Eingabe noch nicht im Stapel ist (52)

q:i2fbs:s:i:+

Wenn die Eingabe im Stapel ist (48)

:i2fbs:s:i:+

Beispielsweise

"Hello World":i2fbs:s:i:+
Bakerg
quelle
0

Julia, HW 199

H=mapreduce;H(B->B=='1',+,H(P->bits(P),*,collect(A[:])))

Mit

A="H=mapreduce;H(B->B=='1',+,H(P->bits(P),*,collect(A[:])))"

oder durch direktes Einfügen des Strings:

julia> H=mapreduce;H(B->B=='1',+,H(P->bits(P),*,collect("H=mapreduce;H(B->B=='1',+,H(P->bits(P),*,collect(A[:])))")))
199

Die ungolfed version (HW 411) sieht so aus:

bitstring=mapreduce(x->bits(x),*,collect(teststring[:]))
mapreduce(checkbit->checkbit=='1',+,bitstring)

Und zum Spaß hier eine optimierte Version (Hamming Weight 231 ) von Bakerg's, die das Problem aufgreift:

A=mapreduce;show(A(B->int(B)-48,+,A(B->bits(B),*,collect(H[:]))))

mit

H="A=mapreduce;show(A(B->int(B)-48,+,A(B->bits(B),*,collect(H[:]))))"
ML
quelle
0

HPPPL (HP Prime Programming Language), 74

sum(hamdist(ASC(a),0))

Der HP Prime Grafikrechner verfügt über eine integrierte hamdist () -Funktion. Das Hamming-Gewicht jedes Charakters entspricht dem Hamming-Abstand von 0.

ASC (Zeichenfolge) erstellt ein Array der ASCII-Werte jedes Zeichens in einer Zeichenfolge.

hamdist (value, 0) berechnet für jeden ASCII-Wert den Hamming-Abstand von 0

sum () summiert alle Werte.

Berechnung des Hamming Weight des eigenen Quellcodes:

Hamming Weight HPPPL

ML
quelle
0

05AB1E , Gewicht 17 (4 Bytes )

ÇbSO

Probieren Sie es online aus oder überprüfen Sie einige weitere Testfälle .

Erläuterung:

Ç       # Convert the characters in the (implicit) input to their ASCII decimal values
        #  i.e. "Test" → [84,101,115,116]
 b      # Convert those values to binary
        #  i.e. [84,101,115,116] → ["1010100","1100101","1110011","1110100"]
  S     # Split it into a list of 0s and 1s (implicitly flattens)
        #  i.e. ["1010100","1100101","1110011","1110100"]
        #   → [1,0,1,0,1,0,0,1,1,0,0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,0,0]
   O    # Sum those (and output implicitly)
        #  i.e. [1,0,1,0,1,0,0,1,1,0,0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,0,0] → 16
Kevin Cruijssen
quelle
0

Perl 6 , 102

+*.ords>>.base(2).comb(~1)

Probieren Sie es online!

Während dies kein Code-Golf ist, scheint die kürzeste Lösung auch das geringste Hamming-Gewicht zu haben ...

Scherzen
quelle