Utwórz program obliczający wagę hamminga z ciąg. Zwycięzcą jest program o najniższej wadze hamminga.
Reguły:
- Wagę Hamminga dla znaku ASCII definiuje się jako całkowitą liczbę bitów ustawioną na
1
w swojej reprezentacji binarnej. - Załóżmy, że kodowanie wejściowe to 7-bitowe ASCII, przekazywane przez dowolny mechanizm wejściowy, który jest normalny dla twojego języka (np. Stdin, args, itp.)
- Wypisz wynik jako liczbę na standardowe wyjście lub dowolny domyślny / normalny mechanizm wyjściowy używany w twoim języku.
- To powinno być oczywiste, ale musisz być w stanie faktycznie uruchomić program, w rzeczywistości , aby był poprawnym rozwiązaniem.
- Zwycięzcą jest rozwiązanie, którego kod ma najniższą wagę hamming.
-
Przepraszamy, brak rozwiązań w białych znakach dla tego!Ok, możesz zakodować w białych znakach, już uporządkowałem zasady 🙂
Przykłady poszczególnych znaków:
char | binary | weight -----+----------+------- a | 01100001 | 3 x | 01111000 | 4 ? | 00111111 | 6 \x00 | 00000000 | 0 \x7F | 01111111 | 7
Komentarze
Odpowiedź
J (33)
Jeden mniej niż 34!
+/,#:3 u:
Mocno zainspirowany tą odpowiedzią , ale o jedną mniejszą wagę.
+/,#:3 u:"+/,#:3 u:" 33
Odpowiedź
J, waga 34
+/,#:a.i.
Użycie – umieść ciąg mierzony w cudzysłowach na końcu:
+/,#:a.i."+/,#:a.i." 34
Alternatywnie, biorąc dane wejściowe z klawiatury (waga 54):
+/,#:a.i.1!:1[1 hello 21
Komentarze
- ' jest tylko jeden sposób, aby to napisać:)
- Nie ma ' t … Znalazłem rozwiązanie, które waży o jeden mniej.
- Nie próbuję być buzzkillem, ale zasady wymagają programu , a nie fragmentu.
Odpowiedz
J , 39
+/,#:a.i:]
To jest funkcja pobierająca jeden argument. (Lub zamień ]
bezpośrednio na ciąg; jak zauważa Gareth, to obniża koszt do 34.)
+/,#:a.i:] "hello world" 45 +/,#:a.i:] "+/,#:a.i:]" 39
Komentarze
- Wspaniałe umysły myślą podobnie. 🙂
Odpowiedź
Python, 189
print sum(bin(ord(A)).count("1")for A in raw_input())
Komentarze
- Odpowiednik Pythona 3,
print(sum(bin(ord(A)).count('1')for A in input()))
, ma wynik 180. - @ dan04: Użyj podwójnych cudzysłowów zamiast pojedynczych dla 176.
Odpowiedź
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
Rodzaj odpowiednie narzędzie do pracy, oczywiście nadal jest do niczego.
Komentarze
- +1 za używanie jednego z moich ulubionych języków wszechczasów. To ' pierwszy język, w którym nauczyłem się programować na komputerze.
Odpowiedź
Jednoargumentowe 0
Wszyscy wiedzieliście, że to nadchodzi. Najpierw program BrainFuck:
,[[>++[>>+>+<<<-]>>> [<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>> [<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-] [-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>[<<<<<<->>>->>> [-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<< [>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<< [>>+<[>>+>+<<<-]>>>[<<<+>>>-]>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>> [<<<<<<+>>>>>>-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]> [-]>[<<<<<<->>>->>>[-]<<<<<<[>>>>+>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<< [>>+>+<<<-]>>>[<<<+>>>-][-]<<[>>[-]<[>[-]+<[-]]<[-]]>[-]>]<<<<<<]>>> [>+>+<<-]>>[<<+>>-][-]+<[>[-]<<[<<->>-]<<[>>+<<-]>>>[-]]>[<<<+<[-]>>>> [-]]<<[->>>>+<<<<]<[-<<+>>]<<],]>>>>>>>.
Dodałem nowe wiersze, aby uczynić go „czytelnym”, ale ma wagę Hamminga 4066. Działa poprzez wielokrotne uzyskiwanie ilorazu / resztę ciągu wejściowego i zsumowanie wszystkich pozostałych. Oczywiście, jeśli uruchomisz go na sobie, otrzymasz: 226 (4066% 256) (technicznie \ xe2), więc wyraźnie uważa się za zwycięzcę.
Teraz konwertujemy go na Unary i otrzymujemy
000 ... 9*google^5.9 0"s ... 000
Używamy jednoargumentowej implementacji ze znakami NULL \ x00 dla „0” i boom, hamowanie wagi 0.
Pytanie dodatkowe : Dla jakich znaków ASCII c
możesz uruchomić ten program na łańcuchu składającym się z N
i wyświetl ten znak. (Np. Ciąg 32 spacji daje spację).Jakie wartości N
działają (nieskończona liczba z nich będzie działać lub żadna).
Komentarze
- Nie ' Nie wiem, czy rozumiem to rozwiązanie. Program Brainfuck ma ogromną wagę. Czy Unary akceptuje bajty zerowe jako program, czy też musiałbyś ponownie zaimplementować Unary? Jeśli ' jest tym drugim, ' nie jest odpowiednim rozwiązaniem – każdy może po prostu powiedzieć ” Definiuję język programowania, w którym każdy pojedynczy bajt wejściowy daje {result} ” i wygrywa w każdym konkursie kodu golfowego w witrynie.
- Null postać Unary byłaby w porządku. Wszystko, czego potrzebujesz, to EOF, aby powiedzieć, że przestań liczyć. W rzeczywistości ' jest pseudo-C do odczytania tego pliku:
main(){ bignum Unarynum = 0; int c; while(EOF!=(c=readchar())){ Unarynum++; } return Unarynum; }
Nie ' w ogóle nie ma znaczenia, co wybierzesz jako swój jednoargumentowy znak (o ile nie jest to ' t EOF). - Cóż tutaj ' jest jednoargumentowym kompilatorem C, który działa dobrze ze znakami zerowymi: ideone.com/MIvAg . Oczywiście plik wymagany do stworzenia tego programu nie zmieściłby się we wszechświecie, ale mamy możliwość go uruchomić.
- Jeśli możesz ' t właściwie go uruchom, to ' nie jest rozwiązaniem.
- Jako Carl Sagan kiedyś powiedział: ” Jeśli chcesz obliczyć wagę hamminga ciągu, musisz najpierw wymyślić 10 ^ 500 wszechświatów. ” (nawet miliardy i miliardy)
Odpowiedź
C, weight 322 263 256
Czy liczy się waga młotka?
main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))D+=*A%2;printf("%d",D-2);}
Używany głównie do gry w golfa technik.
Pojedyncza pętla oblicza wagę (przesuwając w prawo i dodając do zera) i skanuje ciąg (przesuwa wskaźnik do przodu po osiągnięciu zera).
Zakładając, że D
jest zainicjowany na 2 (pojedynczy parametr).
Optymalizacja Hamminga według wagi ons:
1. ABDH
, z wagą po 2, używane w nazwach.
2. *++H
preferowane zamiast H[1]
.
Komentarze
- Hah, do tej pory całkowicie nie zrozumiałem twojego pierwszego zdania.
- Wynik można obniżyć do 230, wyświetlając wynik jako liczbę jednoargumentową :
main(D,H,A)char*A,**H;{for(A=*++H;*A;A+=!(*A/=2))if(*A%2)printf("@");}
- @schnaader , Nigdy nie wiedziałem, że
@
jest cyfrą w systemie jednoargumentowym. Myślałem, że używa tylko0
..0
. Ale jeśli chcesz iść w ten sposób, sposóbprintf("@"+*a%2)
jest krótszy. - @ugoren: Zależy od konwencji / definicji języka jednoargumentowego. Na przykład. pl.wikipedia.org/wiki/Unary_numeral_system używa znaczników i mówi ” Nie ma wyraźnego symbolu reprezentującego zero w jednoargumentowym, tak jak w innych tradycyjnych bazach „.
- @schnaader, OK, ale myślę, że ' s rozciągając wymaganie ” jako liczbę ” za bardzo.
Odpowiedź
Golfscript 84 72 58
{2base~}%{+}*
(podziękowania dla Howarda i Petera Taylora za ich pomoc)
Dane wejściowe: ciąg wejściowy musi znajdować się na stosie (przekazywany jako wiersz poleceń argument lub po prostu umieszczony na stosie).
W przypadku, gdy uruchamiasz go z linii poleceń, upewnij się, że używasz echo -n
, w przeciwnym razie końcowy znak nowej linii również być policzone.
Wyjście: wypisuje wartość wagi hamminga do konsoli
Program można przetestować
tutaj .
Komentarze
- Czy w Golfscript jest rozróżniana wielkość liter? Jeśli nie, możesz zaoszczędzić kilka bitów, używając
BASE
zamiastbase
. Aktualizacja: właśnie zaznaczone,BASE
nie ' nie działa. Dobre rozwiązanie 🙂 - @Polynomial Próbowałem tego po obejrzeniu Twojego komentarza
TEST
/test
🙂 Ale tak się nie dzieje ' t działa. - Możesz pozbyć się
{...}2*
, stosując2base~
na pierwszym miejscu. Wynik spadł do 72. - @Howard dzięki za tę wspaniałą wskazówkę! ' zastosowałem go w swojej odpowiedzi.
- Twój mechanizm testowy jest nieprawidłowy, ponieważ ' zapomniałeś ważne ograniczenie strony Web GolfScript. Powinieneś mieć
;
przed ciągiem, który podstawiasz za stdin, więc(;
jest niepotrzebne. Następnie obserwacja Howarda ' sprowadza ją do 65.
Odpowiedź
Perl, 80 (22 znaki)
Gotowe i gotowe:
perl -0777nE "say unpack"%32B*""
Lub tutaj jest alternatywna wersja o wadze 77 (21 znaków):
perl -0777pE "$_=unpack"%32B*""
Jednak nie podoba mi się ta wersja tak bardzo, ponieważ jej wyjście pomija ostatni znak nowej linii.
Aby obliczyć wagę, zakładam, że liczę znaki w zwykły sposób (z wyłączeniem perl -e
/ -E
, ale z uwzględnieniem innych znaków opcji). Jeśli z jakiegoś powodu ludzie narzekają na to, najlepsze, co mogę zrobić bez opcji, to 90 (26 znaków):
$/=$,,say unpack"%32B*",<>
Przykładowe użycie:
$ perl -0777nE "say unpack"%32b*"" rickroll.txt 7071
Boom.
Odpowiedź
Pyth – 15
Zastrzeżenie: ta odpowiedź nie kwalifikuje się do wygrania, ponieważ Pyth jest młodszy niż to wyzwanie.
Używa .B
do reprezentacji binarnej i zlicza liczbę "1"
„s.
/.BQ\1
Pobiera dane wejściowe w ciągu, aby zapisać na z
w porównaniu z Q
.
Odpowiedz
Scala 231
readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum
Kod autotestu:
"""readLine().map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum""".map(_.toInt.toBinaryString).flatten.map(_.toInt-48)sum
z modyfikacją autotestującą.
Komentarze
- To ' ma wagę 495, a nie 231. Możesz ' uzyskać wagę 231 ze 126 znakami – to ' to średnio mniej niż 2 i wszystkie drukowalne znaki (z wyjątkiem
@
i spacji, których nie ' t use) mają wagę co najmniej 2. - @ugoren: Ale ' ma tylko 65 znaków. Program jest drukowany prawie dwa razy: raz kod do obliczenia wagi Hamminga i drugi raz jako statyczne dane wejściowe do obliczenia go dla programu. Jednak w części obliczeniowej brakuje elementu ” readLine () ” z przodu, ponieważ pobiera on dane wejściowe. Próbowałem wyjaśnić samą odpowiedź.
Odpowiedź
Java, weight 931 774 499 454
Myślę, że w tej chwili jest to jedyna odpowiedź o wadze powyżej około 300.
class H{public static void main(String[]A){System.out.print(new java.math.BigInteger(A[0].getBytes()).bitCount());}}
Oczekuje danych wejściowych jako argumentu wiersza poleceń.
Odpowiedź
GNU sed -r
, 467 + 1
(+1 do użycia -r
– czy powinno to być +4?)
Wyprowadza jako jednoargumentową wartość na wiersz źródłowy; aby przekonwertować na sumę dziesiętną, przekieruj dane wyjściowe do | tr -d "\n" | wc -c
. Zlicza wszystkie drukowalne znaki ASCII (32-126) oraz wysuw wiersza (10).
s@[a-z]@\U& @g s@[?{}~]@ @g s@[][/7;=>OW|^]@ @g s@[-"+.3569:<GKMNSUVYZ\\]@ @g s@[#%&)*,CEFIJL1248ORTX]@ @g s@$|[!"$(ABDH0P`]@ @g y! @!11!
Trudno jest uniknąć wyszczególnienia wszystkich znaków, ale możemy zmniejszyć zauważając, że małe litery mają wagę Hamminga o jedną większą niż odpowiadające im wielkie litery. Preferujemy znak nowej linii (punktacja 2) zamiast średnika (punktacja 5) jako separator instrukcji; wolimy @
(wynik 1) lub !
(wynik 2) powyżej /
(wynik 5) jako separator wzoru.
Uwaga – aby uzyskać odpowiednie zestawy znaków, utworzyłem tę tabelę na podstawie tabeli z man ascii
, posortowaną według wagi. Po prostu dodaj wyniki po prawej i niżej, aby uzyskać całkowitą wagę każdego znaku:
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
To może okazać się przydatne dla innych.
Odpowiedź
Julia 262 268
Zmodyfikowana wersja wykorzystuje przydatną funkcję „count_ones”, aby zaoszczędzić 6 (262)
show(mapreduce(x->count_ones(x),+,map(x->int(x),collect(ARGS[1]))))
Stary wersja bez wbudowanej funkcji zliczania jednego (268)
show(mapreduce(x->int(x)-48,+,mapreduce(x->bits(x),*,collect(ARGS[1]))))
Używa argumentu wiersza poleceń do wprowadzania danych.
Odpowiedź
CJam 52 lub 48
Jeśli dane wejściowe nie znajdują się jeszcze na stosie (52)
q:i2fbs:s:i:+
Jeśli dane wejściowe znajdują się na stosie (48)
:i2fbs:s:i:+
Na przykład
"Hello World":i2fbs:s:i:+
Odpowiedź
Julia, HW 199
H=mapreduce;H(B->B=="1",+,H(P->bits(P),*,collect(A[:])))
Z
A="H=mapreduce;H(B->B=="1",+,H(P->bits(P),*,collect(A[:])))"
lub bezpośrednio wstawiając ciąg:
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
Wersja bez golfa (HW 411) wygląda tak:
bitstring=mapreduce(x->bits(x),*,collect(teststring[:])) mapreduce(checkbit->checkbit=="1",+,bitstring)
A dla zabawy, oto zoptymalizowana wersja (Hamming Weight 231 ) piekarni zajmują się tym problemem:
A=mapreduce;show(A(B->int(B)-48,+,A(B->bits(B),*,collect(H[:]))))
z
H="A=mapreduce;show(A(B->int(B)-48,+,A(B->bits(B),*,collect(H[:]))))"
Odpowiedź
HPPPL (język programowania HP Prime), 74
sum(hamdist(ASC(a),0))
Kalkulator graficzny HP Prime ma wbudowaną funkcję hamdist ().Waga hamming każdego znaku jest taka sama jak odległość hamminga od 0.
ASC (string) tworzy tablicę wartości ASCII każdego znaku w ciągu.
hamdist ( value, 0) oblicza odległość hamminga od 0 dla każdej wartości ASCII.
sum () sumuje wszystkie wartości.
Obliczanie wagi hamminga własnego kodu źródłowego:
Odpowiedź
05AB1E , waga 17 (4 bajty )
ÇbSO
Wypróbuj online lub sprawdź więcej przypadków testowych .
Wyjaśnienie:
Ç # 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
Odpowiedź
Perl 6 , 102
+*.ords>>.base(2).comb(~1)
Chociaż nie jest to „kodowanie golfa”, wydaje się, że najkrótsze rozwiązanie ma najmniejszą wagę hamującą …
0x20
/ ASCII 32 jako odniesienie, czy nie ' t waga szumuhello world
10 zamiast 11?hello world
wynosi 11? Tylko 10 znaków różni się od spacji. Ponadto – program ' s Waga Hamminga wydaje się być po prostu jego długością, bez spacji. Nie różni się zbytnio od zwykłego golfa kodowego.~
Io
.