Aby znaleźć twardość cyfrową liczby całkowitej, weź jej reprezentację binarną i policz, ile razy wiodący i końcowy
1
można usunąć, dopóki nie zacznie się lub nie zakończy na0
. Całkowita liczba usuniętych bitów to jego twardość cyfrowa.
To dość dziwne wytłumaczenie - podzielmy to na działający przykład.
W tym przykładzie użyjemy liczby 3167. Binarnie jest to:
110001011111
(Należy pamiętać, że podczas konwersji na binarną należy pamiętać o usunięciu wiodących zer)
Nie zaczyna się i nie kończy 0
, więc usuwamy 1 parę bitów:
1 1000101111 1
I kolejny:
11 00010111 11
Ale teraz na początku jest 0, więc nie możemy już usunąć 1
par. W sumie usunęliśmy 4 bity, a więc 4 to twardość cyfrowa 3167.
Jednak w przypadku liczb, które można zapisać jako 2 n -1 dla dodatniej n (tj. Zawierają tylko 1
reprezentację binarną), 0 nigdy nie zostanie osiągnięte, więc wszystkie bity można usunąć. Oznacza to, że twardość jest po prostu liczbą bitową liczby całkowitej.
Wyzwanie
Twoim zadaniem jest napisanie programu lub funkcji, która przy nieujemnej liczbie całkowitej n >= 0
określa jej twardość cyfrową.
Możesz przesłać pełny program wykonujący operacje we / wy lub funkcję zwracającą wynik. Przesłanie powinno działać w przypadku wartości n
mieszczących się w standardowym zakresie liczb całkowitych w Twoim języku.
Przypadki testowe
Powiadom mnie, jeśli któreś z nich są niepoprawne lub jeśli chcesz zasugerować jakieś przypadki brzegowe do dodania.
0 -> 0
1 -> 1
8 -> 0
23 -> 2
31 -> 5
103 -> 4
127 -> 7
1877 -> 2
2015 -> 10
Oto nierozwinięte rozwiązanie Pythona, którego użyłem do wygenerowania tych przypadków testowych (nie ma gwarancji, że nie zawiera błędów):
def hardness(num) -> int:
binary = bin(num)[2:]
if binary.count('0') == 0:
return num.bit_length()
revbin = binary[::-1]
return min(revbin.find('0'), binary.find('0')) * 2
1
zwraca 1, gdy nie ma0
go w ogóle? Mam na myśli, że nie możesz usunąć wystarczającej liczby 1 z ciągu, aby rozpocząć lub zakończyć0
.Odpowiedzi:
Galaretka ,
1110 bajtówWypróbuj online!
Jak to działa
źródło
Python ,
76696863626057 bajtówWypróbuj online!
Jak to działa
Jest to rozwiązanie rekurencyjne, które przyjmuje dane wejściowe n i stale zwiększa k - zaczynając od 0 - podczas gdy zarówno LSB k (n) (bit o indeksie k od prawej), jak i MSB k (n) (bit o indeksie k od lewej) są ustawione. Po zakończeniu zwraca k, jeśli wszystkie bity n są ustawione, a 2k, jeśli nie.
Zacznijmy od przepisania lambda f jako funkcji o nazwie F , ze zmienną pomocniczą t .
Przy każdym wywołaniu F , najpierw przesuwamy bitem n łącznie k jednostek w prawo i zapisujemy wynik w t . W ten sposób LSB 0 (t) = LSB k (n) , więc t jest nieparzyste wtedy i tylko wtedy, gdy ustawiono LSB k (n) .
Ustalenie, czy MSB k (n) jest ustawione, jest nieco trudniejsze; właśnie to
n & t > t >> 1
osiąga. Aby zilustrować, jak to działa, rozważmy liczbę całkowitą n = 1αβγδεζη 2 o długości bitu 8 i przeanalizujemy wywołanie funkcji F (n, 3) , tj. K = 3 .Próbujemy ustalić, czy MSB 3 (n) = γ jest ustawiony, badając wartość prawdziwości porównania (n & t> t >> 1) = (1αβγδεζη 2 i 1αβγδ 2 > 1αβγ 2 ) . Sprawdźmy zaangażowane liczby całkowite.
Twierdzimy, że γ = 1 wtedy i tylko wtedy, gdy n & t> t >> 1 .
Jeśli γ = 1 , to n & t ma długość bitu 5, zaś t >> 1 ma długość bitu 4 , więc n & t> t >> 1 .
Dowodzi to, że γ = 1 implikuje n & t> t >> 1 .
Jeśli n & t> t >> 1 , istnieją dwie opcje: albo γ = 1, albo γ = 0 . W pierwszym przypadku nic nie zostało do udowodnienia.
W drugim przypadku ma to αβγδ 2 ≥ n t t> >> 1 = 1αβγ 2 .
Od αβγδ 2 > 1αβγ 2 , musimy MSB 0 (αβγδ 2 ) ≥ MSB 0 (1αβγ 2 ) , co oznacza, że a = 1 .
W ten sposób 1βγδ 2 > 11βγ 2 , więc musimy mieć MSB 1 (1βγδ 2 ) ≥ MSB 1 (11βγ 2 ) , co oznacza, że p = 1 .
To z kolei oznacza, że 11γδ 2 > 111γ 2 . Pamiętając, że γ = 0 w drugim przypadku, otrzymujemy nierówność 110δ 2 > 1110 2 , co jest fałszem, ponieważ MSB 2 (110δ 2 ) = 0 <1 = MSB 2 (1110 2 ) .
Zatem możliwy jest tylko pierwszy przypadek, a n & t> t >> 1 implikuje γ = 1 .
Reasumując, jeśli zarówno LSB k (n) i MSB k (n) są ustawione, t będzie dziwne i n t> t >> 1 będzie prawda , więc t (n & t> t >> 1) będzie wydajność 1 . Jeśli jednak LSB k (n) lub MSB k (n) nie jest ustawione (lub jeśli oba są), t będzie parzyste lub n & t> t >> 1 będzie False , więc t & (n & t> t> > 1) da 0 .
Wywołanie F z jednym argumentem inicjuje k = 0 . Podczas gdy warunek, który omówiliśmy wcześniej,
and
jest spełniony, wykonywany jest kod after , który (między innymi) rekurencyjnie wywołuje F z przyrostem k .Po rozbrojeniu LSB k (n) lub MSB k (n) warunek kończy się niepowodzeniem, a F (n, k) zwraca 0 . Każde z poprzednich wywołań funkcji k dodaje (n & (n + 1)> 0) + 1 do F (n, k) = 0 , więc F (n) zwraca ((n & (n + 1)> 0) + 1) k .
Teraz, jeśli wszystkie bity n są równe (tj. Jeśli n jest albo 0 albo wszystkie jego bity są ustawione), n + 1 nie będzie mieć żadnych bitów wspólnych z n , więc n & (n + 1) = 0 i F (n) zwraca k . Jeśli jednak n ma ustawione i nieuzbrojone bity, n & (n + 1)> 0, a F (n) zwraca 2k .
źródło
input()
,while
iprint
ma już 17 bajtów ...MATL ,
1312 bajtówWypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie
Kod powtarza każdą cyfrę binarną i liczy, ile razy można usunąć dwie zewnętrzne.
źródło
Python, 82 bajty
Wydaje mi się, że nadal można grać w golfa, ale spędziłem trochę czasu próbując różnych metod i to było najkrótsze.
Wypróbuj online
Chociaż działa to podobnie do programu Python OP, stworzyłem to przed opublikowaniem pytania, po przejrzeniu pytania w piaskownicy, które nie zawierało takiego programu.
źródło
Python 2, 66 bajtów
Dzieli binarną reprezentację danych wejściowych na porcje 1. Zlicza liczbę 1 w mniejszej z pierwszej i ostatniej porcji, a następnie podwaja ją, chyba że istnieje jedna porcja, która by się podwoiła.
źródło
PowerShell ,
109106 bajtówWypróbuj online!
Zajmuje wejście
$args[0]
, wykorzystuje połączenie .NET doconvert
niegotoString
z bazy2
(czyli uczynić go binarne), a następnie-split
z którą napis na0
s, sklepy, które w$a
. Ważne, aby pamiętać: wywołanie .NET nie zwraca zer wiodących, więc pierwszą cyfrą jest zawsze cyfra1
.Istnieją zatem dwie możliwości - ciąg binarny jest wszystkim, lub było co najmniej jedno zero. Rozróżniamy te z pseudo-trójskładnikiem indeksowanym przez
$a.count-eq1
. Jeśli plik binarny ma co najmniej jedno zero, w lewym przypadku, bierzemy minimalną długość pierwszego[0]
ciągu1
s i ostatniego[-1]
ciągu (znalezionego do|sort
tego czasu[0]
). Im krótsza z nich, tym więcej par możemy usunąć, więc pomnożymy to przez2
. Zauważ, że jeśli oryginalny ciąg binarny kończy się na0
, jak na wejściu8
, to[-1].length
również będzie0
(ponieważ jest to pusty ciąg), który po pomnożeniu2
jest nadal0
.W przeciwnym razie, biorąc pod uwagę ciąg binarny wszystkie, bierzemy tylko
$b
(która wcześniej była ustawiona na długość pierwszego[0]
ciągu, w tym przypadku całość ciągu binarnego).W obu przypadkach wynik pozostaje w potoku, a dane wyjściowe są niejawne.
źródło
JavaScript (ES6), 57 bajtów
Pobiera plik binarny i próbuje dopasować wszystkie
1s
lub, jeśli nie, taką samą liczbę wiodących i końcowych1s
.źródło
Siatkówka , 48 bajtów
Wypróbuj online
Wyjaśnienie:
źródło
C #, 133 bajty
Funkcja, która zwraca twardość. Bierze liczbę całkowitą z argumentu.
Cóż, dzisiaj dowiedziałem się
'1' + '1' = 98
w C #.źródło
'1'
jest znak ASCII 49, a 49 + 49 = 98.1 + 1 = 2
nie działa. @FlipTackC,
898885 bajtówZapisano dwa bajty dzięki @FlipTack wskazując na bezużyteczną deklarację.
Zadzwoń
f()
z numerem do przetestowania, wynik jest zwracany z funkcji.Wypróbuj na ideone .
źródło
JavaScript (ES6),
5958 bajtówPrzypadki testowe
Pokaż fragment kodu
źródło
Galaretka , 14 bajtów
Wypróbuj online!
źródło
C,
1371321221191171149894928785 BajtówCzas zacząć grać w golfa B-)
Oto dowód
i wynik;
źródło
Java (OpenJDK) ,
181156150 bajtówWypróbuj online!
źródło
Mathematica,
6356 bajtówWyjaśnienie
Wygeneruj reprezentację danych wejściowych base-2, opakowaną w a
List
. Przechowuj to wl
Jeśli min. Element
l
to 1, wyślij 1. Jeśli nie, wyślij 2. Pomnóż to przez ...Podziel
l
na przebiegi.Weź pierwszy i ostatni element.
Weź sumę obu.
Znajdź mniejszy między nimi.
(Pomnóż pierwszy wynik (1 lub 2) przez ten wynik).
źródło
Oktawa,
5654 bajtówWypróbuj online!
Wyjaśnienie:
binarna reprezentacja
n
Weź skumulowaną min
d
i skumulowaną min odwróconejd
wykonaj mnożenie macierzy
pomnóż przez 2, jeśli wszystkie cyfry to 1;
źródło
Pyth, 18 bajtów
Program, który pobiera liczbę całkowitą i wypisuje wynik.
Zestaw testowy (pierwsza linia do formatowania)
Jak to działa
źródło
APL, 26 bajtów
Przypadki testowe:
Wyjaśnienie:
źródło
J, 22 bajty
Jest to oparte na zgrabnej sztuczce wyuczonej z tego wyzwania .
Wypróbuj online!
Wyjaśnienie
źródło
PHP,
8374 bajty3 + 6 bajtów zapisanych przez Jörga
pobiera dane wejściowe z STDIN; biegać z
-nR
.awaria
źródło
<?=~($s=decbin($argn))[$a=strspn($s,1)]?2*min($a,strspn(strrev($s),1)):$a;
JavaScript (ES6), 83 bajtów
Nie golfowany:
źródło
Mathematica, 62 bajty
Czysta funkcja, gdzie
#
reprezentuje pierwszy argument.(h=0;...;h)&
ustawiah=0
, robi kilka rzeczy...
, a następnie zwracah
(twardość). Spójrzmy na kilka rzeczy:Dzięki Gregowi Martinowi za zapoznanie mnie z tą sztuczką .
źródło
Haskell ,
9492 bajtyWypróbuj online! Stosowanie:
Objaśnienie:
b
konwertuje liczbę na binarną i zwraca listę zer i pierwszych z najmniej znaczącym bitem. Wh
tej lista jest odwrócona i elementarnie pomnożona z pierwotną listą, a następniespan(>0)
dzieli się po początkowych1
s:Powstała krotka jest dopasowywana do wzorca,
(c,_:_)
gdzie_:_
pasuje do dowolnej niepustej listy, więcc = [1,1]
. Ponieważ bajty są usuwane z przodu iz tyłu,c++c = [1,1,1,1]
są zwracane i ostatecznie sumowane, aby uzyskać twardość cyfrową .Jeśli druga lista krotki jest pusta, wówczas reprezentacja binarna zawiera tylko je, a ich liczba to twardość cyfrowa. Dopasowanie wzorca zakończyło się niepowodzeniem,
h
po prostu zwracan
, co jest ponownie sumowane.źródło
Perl, 61 bajtów
Sercem tego jest wyrażenie regularne, w
/^(1+).*\1$/
którym odpowiedź stanowi dwukrotność długości$1
. Reszta kodu jest narzutem i zajmuje się specjalnym przypadkiem wszystkich 1.źródło
sprintf
argumentów. Również użycie-p
flagi pozwoli ci napisać pełny program, który będzie krótszy niż twoja funkcja, ponieważ będziesz mógł pominąćsub f{...}
(zamiast tego będziesz musiał zakończyć,$_=...
ale to wciąż poprawa o 4 bajty). Wreszcie, zamiast swojegolength(...)
, możesz to zrobić/0/&&s/^(1+).*\1$/$1$1/;$_=y///c
. Powinno to doprowadzić Cię do 51 bajtów.PHP, 65 bajtów
Wersja online
źródło
CJam, 14 bajtów
Wyjaśnienie:
źródło