Créez un programme qui calcule le poids de martelage de un string. Le gagnant est le programme avec le poids de frappe le plus bas.
Règles:
- Le poids de Hamming pour un caractère ASCII est défini comme le nombre total de bits mis à
1
dans sa représentation binaire. - Supposons que le codage dentrée est ASCII 7 bits, transmis par nimporte quel mécanisme dentrée normal pour votre langue (par exemple stdin, args, etc.)
- Afficher le résultat, sous forme de nombre, vers stdout ou tout autre mécanisme de sortie par défaut / normal utilisé par votre langage.
- Cela devrait aller de soi, mais vous devez pouvoir exécuter le programme, dans la vraie vie, pour que ce soit une solution valide.
- Winner est la solution dont le code a le poids le plus bas.
-
Désolé, pas de solution dans espace blanc pour celui-ci!Ok, vous pouvez coder en espace maintenant, jai trié les règles 🙂
Exemples par caractère:
char | binary | weight -----+----------+------- a | 01100001 | 3 x | 01111000 | 4 ? | 00111111 | 6 \x00 | 00000000 | 0 \x7F | 01111111 | 7
Commentaires
Réponse
J (33)
Un inférieur à 34!
+/,#:3 u:
Fortement inspiré de cette réponse , mais avec un poids de marteau inférieur dun.
+/,#:3 u:"+/,#:3 u:" 33
Réponse
J, poids 34
+/,#:a.i.
Utilisation – placez le chaîne à mesurer entre guillemets à la fin:
+/,#:a.i."+/,#:a.i." 34
Alternativement, en prenant lentrée du clavier (poids 54):
+/,#:a.i.1!:1[1 hello 21
Commentaires
- Il ny a ‘ quune seule façon décrire ceci:)
- Il ny a pas ‘ t … Jai trouvé une solution qui a un poids de marteau inférieur dun.
- Ne pas essayer dêtre un buzzkill, mais les règles demandent un programme, pas un fragment.
Réponse
J , 39
+/,#:a.i:]
Ceci est une fonction en prenant une argument. (Ou remplacez ]
par la chaîne directement; comme le note Gareth, cela réduit le coût à 34.)
+/,#:a.i:] "hello world" 45 +/,#:a.i:] "+/,#:a.i:]" 39
Commentaires
- Les grands esprits se ressemblent. 🙂
Réponse
Python, 189
print sum(bin(ord(A)).count("1")for A in raw_input())
Commentaires
- Léquivalent Python 3,
print(sum(bin(ord(A)).count('1')for A in input()))
, a un score de 180. - @ dan04: Utilisez des guillemets doubles au lieu de simples pour 176.
Answer
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
Type de le bon outil pour le travail, ça craint toujours bien sûr.
Commentaires
- +1 pour utiliser lune de mes langues préférées de tous les temps. Cest ‘ la première langue dans laquelle jai appris à coder sur un PC.
Réponse
Unaire 0
Vous saviez tous que cela allait arriver. Dabord le programme BrainFuck:
,[[>++[>>+>+<<<-]>>> [<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>> [<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-] [-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>[<<<<<<->>>->>> [-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<< [>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<< [>>+<[>>+>+<<<-]>>>[<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>> [<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]> [-]>[<<<<<<->>>->>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<< [>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<<]>>> [>+>+<<-]>>[<<+>>-][-]+<[>[-]<<[<<->>-]<<[>>+<<-]>>>[-]]>[<<<+<[-]>>>> [-]]<<[->>>>+<<<<]<[-<<+>>]<<],]>>>>>>>.
Jai ajouté des nouvelles lignes pour le rendre « lisible » mais il a un poids de Hamming de 4066. Il fonctionne en obtenant à plusieurs reprises le quotient / les restes dune chaîne dentrée et laddition de tous les restes. Bien sûr, si vous lexécutez sur lui-même, vous obtenez: 226 (4066% 256) (techniquement \ xe2) si clairement quil se déclare vainqueur.
Maintenant, nous le convertissons en Unary et obtenons
000 ... 9*google^5.9 0"s ... 000
Nous utilisons une implémentation unaire avec des caractères NULL \ x00 pour « 0 » et boom, poids de martelage de 0.
Question bonus : Pour quels caractères ASCII c
pouvez-vous exécuter ce programme sur une chaîne composée de N
répétitions et faites-lui afficher ce caractère. (Par exemple, une chaîne de 32 espaces donne un espace).Quelles valeurs de N
fonctionnent (soit un nombre infini dentre elles fonctionnera, soit aucune ne fonctionnera).
Commentaires
- Je ‘ ne suis pas sûr de comprendre cette solution. Le programme brainfuck a un poids énorme. Unary accepte-t-il les octets nuls en tant que programme, ou auriez-vous besoin de réimplémenter Unary? Si ce ‘ est ce dernier, ce ‘ nest pas vraiment une solution valable – nimporte qui pourrait simplement dire » Je définis un langage de programmation où nimporte quel octet dentrée donne {result} « , et gagne chaque défi de golf de code sur le site.
- Un null le caractère Unary serait très bien. Tout ce dont vous avez besoin est un EOF pour dire arrêter de compter. En fait, voici ‘ quelques pseudo-C pour lire ce fichier:
main(){ bignum Unarynum = 0; int c; while(EOF!=(c=readchar())){ Unarynum++; } return Unarynum; }
Doesn ‘ Peu importe ce que vous choisissez dêtre votre caractère unaire (tant quil nest pas ‘ t EOF). - Eh bien ici ‘ est un compilateur unaire vers C qui fonctionne très bien avec des caractères nuls: ideone.com/MIvAg . Bien sûr, le fichier requis pour créer ce programme ne rentrerait pas dans lunivers, mais nous avons la capacité de lexécuter.
- Si vous pouvez ‘ t en fait exécutez-le, cela ‘ nest pas vraiment une solution.
- Comme Carl Sagan a dit une fois: » Si vous souhaitez calculer le poids de frappe dune chaîne, vous devez dabord inventer 10 ^ 500 univers. » (milliards et milliards, même)
Réponse
C, poids 322 263 256
Le poids du marteau compte-t-il?
main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))D+=*A%2;printf("%d",D-2);}
Utilisé principalement le golf standard techniques.
Une seule boucle calcule le poids (déplacement vers la droite et addition jusquà zéro) et scanne la chaîne (avance le pointeur lorsque zéro atteint).
En supposant que D
est initialisé à 2 (paramètre unique).
Optimisation spécifique au poids de Hamming ons:
1. ABDH
, avec un poids de 2 chacun, utilisé pour les noms.
2. *++H
préféré à H[1]
.
Commentaires
- Hah, je nai absolument pas compris votre première phrase jusquà maintenant.
- Vous pouvez réduire le score à 230 en affichant le résultat sous forme de nombre unaire :
main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))if(*A%2)printf("@");}
- @schnaader , Je nai jamais su que
@
était un chiffre dans le système unaire. Je pensais quil nutilisait que0
..0
. Mais si vous voulez aller dans ce sens,printf("@"+*a%2)
est plus court. - @ugoren: Dépend de la convention / définition de unaire. Par exemple. en.wikipedia.org/wiki/Unary_numeral_system utilise des marques de pointage et dit » Il ny a pas de symbole explicite représentant zéro en unaire comme il y en a dans dautres bases traditionnelles « .
- @schnaader, OK, mais je pense que cest ‘ s étirant lexigence » sous la forme dun nombre » trop loin.
Réponse
Golfscript 84 72 58
{2base~}%{+}*
(merci à Howard et Peter Taylor pour leur aide)
Entrée: la chaîne dentrée doit être sur la pile (passée en ligne de commande argument, ou simplement placé sur la pile).
Si vous lexécutez à partir de la ligne de commande, assurez-vous dutiliser echo -n
, sinon la nouvelle ligne de fin sera également être comptés.
Sortie: imprime la valeur du poids de martelage sur la console
Le programme peut être testé
ici .
Commentaires
- Golfscript est-il sensible à la casse? Sinon, vous pouvez enregistrer quelques bits en utilisant
BASE
au lieu debase
. Mise à jour: Vient de vérifier,BASE
ne fonctionne ‘. Bonne solution 🙂 - @Polynomial Jai essayé ça après avoir vu votre commentaire de
TEST
/test
🙂 Mais ça ne ‘ t fonctionne. - Vous pouvez vous débarrasser de
{...}2*
en appliquant2base~
en premier lieu. Obtient le score à 72. - @Howard merci pour ce bon conseil! Je ‘ lai appliqué dans ma réponse.
- Votre mécanisme de test est erroné, car vous ‘ avez oublié un limitation importante de votre page Web GolfScript. Vous devez avoir un
;
avant la chaîne que vous remplacez par stdin, afin que(;
ne soit pas nécessaire. Ensuite, lobservation de Howard ‘ le ramène à 65.
Réponse
Perl, 80 (22 caractères)
Terminé et terminé:
perl -0777nE "say unpack"%32B*""
Ou voici une version alternative avec un poids de 77 (21 caractères):
perl -0777pE "$_=unpack"%32B*""
Je naime pas autant cette version, cependant, parce que sa sortie omet le saut de ligne final.
Pour calculer le poids, je suppose que je compte les caractères de la manière habituelle (à lexclusion des perl -e
/ -E
, mais en incluant dautres caractères doption). Si, pour une raison quelconque, les gens se plaignent de cela, le mieux que je puisse faire sans les options est 90 (26 caractères):
$/=$,,say unpack"%32B*",<>
Exemple dutilisation:
$ perl -0777nE "say unpack"%32b*"" rickroll.txt 7071
Boum.
Réponse
Pyth – 15
Clause de non-responsabilité: Cette réponse nest pas admissible à gagner car Pyth est plus jeune que ce défi.
Utilise .B
pour la représentation binaire et compte le nombre de "1"
« s.
/.BQ\1
Prend une entrée dans une chaîne à enregistrer sur z
par rapport à Q
.
Réponse
Scala 231
readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum
Code dauto-test:
"""readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum""".map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum
avec modification dauto-test.
Commentaires
- Il ‘ s poids 495, pas 231. Vous pouvez ‘ t obtenir le poids 231 avec 126 caractères – que ‘ est une moyenne inférieure à 2 et tous les caractères imprimables (sauf
@
et lespace, dont vous ne disposez pas ‘ t use) ont au moins le poids 2. - @ugoren: Mais il ‘ ne comporte que 65 caractères. Le programme est imprimé presque deux fois: une fois le code pour calculer le poids de martelage, et une seconde fois comme entrée statique pour le calculer pour le programme. Mais il manque à la partie calculatrice le » readLine () » devant, car il prend lentrée littérale. Jai essayé de clarifier la réponse elle-même.
Réponse
Java, poids 931 774 499 454
Je pense que cest la seule réponse pour le moment avec un poids supérieur à 300 environ.
class H{public static void main(String[]A){System.out.print(new java.math.BigInteger(A[0].getBytes()).bitCount());}}
Attend une entrée comme argument de ligne de commande.
Réponse
GNU sed -r
, 467 + 1
(+1 pour lutilisation de -r
– ou devrait-il être +4?)
Sortie sous forme de valeur unaire par ligne source; pour convertir en un total décimal, redirigez la sortie vers | tr -d "\n" | wc -c
. Compte tous les caractères ASCII imprimables (32-126), plus le saut de ligne (10).
s@[a-z]@\U& @g s@[?{}~]@ @g s@[][/7;=>OW|^]@ @g s@[-"+.3569:<GKMNSUVYZ\\]@ @g s@[#%&)*,CEFIJL1248ORTX]@ @g s@$|[!"$(ABDH0P`]@ @g y! @!11!
Il est difficile déviter de lister tous les caractères, mais nous pouvons réduire ceci en observant que les lettres minuscules ont un poids de Hamming de plus dun par rapport aux lettres majuscules correspondantes. Nous préférons le retour à la ligne (score 2) au point-virgule (score 5) comme séparateur dinstruction; nous préférons @
(score 1) ou !
(score 2) sur /
(score 5) comme délimiteur de motif.
Remarque – pour obtenir les bons jeux de caractères, jai créé ce tableau à partir de celui de man ascii
, trié par poids. Il suffit dajouter les scores à droite et ci-dessous pour obtenir le poids total de chaque caractère:
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
Cela peut savérer utile pour dautres.
Réponse
Julia 262 268
La version modifiée utilise la fonction pratique « count_ones » pour une économie de 6 (262)
show(mapreduce(x->count_ones(x),+,map(x->int(x),collect(ARGS[1]))))
Ancien version nutilisant pas de fonction de comptage unique intégrée (268)
show(mapreduce(x->int(x)-48,+,mapreduce(x->bits(x),*,collect(ARGS[1]))))
Utilise un argument de ligne de commande pour lentrée.
Réponse
CJam 52 ou 48
Si lentrée nest pas déjà sur la pile (52)
q:i2fbs:s:i:+
Si lentrée est sur la pile (48)
:i2fbs:s:i:+
Par exemple
"Hello World":i2fbs:s:i:+
Réponse
Julia, HW 199
H=mapreduce;H(B->B=="1",+,H(P->bits(P),*,collect(A[:])))
Avec
A="H=mapreduce;H(B->B=="1",+,H(P->bits(P),*,collect(A[:])))"
ou en insérant directement la chaîne:
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
La version non golfée (HW 411) ressemble à ceci:
bitstring=mapreduce(x->bits(x),*,collect(teststring[:])) mapreduce(checkbit->checkbit=="1",+,bitstring)
Et pour le plaisir, voici une version optimisée (Hamming Weight 231 ) de lopinion de Bakerg sur le problème:
A=mapreduce;show(A(B->int(B)-48,+,A(B->bits(B),*,collect(H[:]))))
avec
H="A=mapreduce;show(A(B->int(B)-48,+,A(B->bits(B),*,collect(H[:]))))"
Réponse
HPPPL (HP Prime Programming Language), 74
sum(hamdist(ASC(a),0))
La calculatrice graphique HP Prime possède une fonction hamdist () intégrée.Le poids de martelage de chaque caractère est le même que la distance de frappe à partir de 0.
ASC (chaîne) crée un tableau des valeurs ASCII de chaque caractère dans une chaîne.
hamdist ( value, 0) calcule la distance de frappe à partir de 0 pour chaque valeur ASCII
sum () résume toutes les valeurs.
Calcul du poids de martelage de son propre code source:
Réponse
05AB1E , poids 17 (4 octets )
ÇbSO
Essayez-le en ligne ou vérifiez dautres cas de test .
Explication:
Ç # 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
Réponse
Perl 6 , 102
+*.ords>>.base(2).comb(~1)
Bien que ce ne soit pas du code de golf, la solution la plus courte semble aussi avoir le plus petit poids de martelage …
0x20
/ ASCII 32 comme référence, nest-ce pas ‘ t le poids bourdonnant dehello world
10 au lieu de 11?hello world
est-il de 11? Seuls 10 caractères sont différents dun espace. Aussi – le poids de Hamming dun programme ‘ semble être juste sa longueur, sans les espaces. Pas si différent du code de golf normal.~
ETo
.