Twoim zadaniem jest, biorąc pod uwagę liczbę całkowitą bez znaku n
, znaleźć największą liczbę, którą można utworzyć, usuwając pojedynczy bajt (8 kolejnych bitów) danych.
Przykład
Biorąc pod uwagę liczbę 7831
, najpierw konwertujemy ją na binarną (usuwając wszelkie zera na początku):
1111010010111
Następnie znajdujemy kolejną grupę 8 bitów, które po usunięciu dają największy nowy wynik. W tym przypadku istnieją 3 rozwiązania pokazane poniżej
1111010010111
^ ^
^ ^
^ ^
Usuwając to dowolne z tych zbiorów 11111
, które następnie przeliczamy z powrotem na wartość dziesiętną 31
dla odpowiedzi.
Przypadki testowe
256 -> 1
999 -> 3
7831 -> 31
131585 -> 515
7854621 -> 31261
4294967295 -> 16777215 (if your language can handle 32 bit integers)
Zasady
- Gwarantujemy, że długość bitu
n
będzie większa niż 8. - Twoje rozwiązanie powinno teoretycznie działać na dowolnej długości bitów
n
większej niż 8, ale w praktyce wymaga pracy tylko dla liczb całkowitych 255 <n <2 16 - Dane wejściowe / wyjściowe powinny być dziesiętne.
- Możesz przesłać pełny program lub funkcję.
- To jest golf golfowy , więc wygrywa najkrótszy program (w bajtach)!
Odpowiedzi:
Galaretka , 6 bajtów
Monadyczny link pobierający numer i zwracający numer.
Wypróbuj online!
W jaki sposób?
Używa miłym szybkie ,
Ƥ
opracowany przez mil ...źródło
J , 12 bajtów
Wypróbuj online!
źródło
&.
; jest to idealny rodzaj problemu.Python 2 , 41 bajtów
Wypróbuj online!
źródło
JavaScript (ES6), 54 bajty
Działa do 2 ** 31-1. Ponieważ ktoś poprosił o nieco kręcącą się odpowiedź ...
źródło
Pyth , 21 bajtów
Jest to funkcja rekurencyjna (należy ją wywołać za pomocą
y
lub zobaczyć link).Wypróbuj tutaj!
źródło
Mathematica, 69 bajtów
Wypróbuj online!
To rozwiązanie działa na duże liczby Wypróbuj online!
-3 bajty od KellyLowder
źródło
Max[c=#~RealDigits~2;Array[Drop[c[[1]],#;;#+7]~FromDigits~2&,Last@c-7]]&
Python 3 ,
686660 bajtów-2 bajty dzięki Mr. Xcoder!
-4 bajty dzięki ovs!
-2 bajty dzięki Erikowi Outgolfer!
Wypróbuj online!
źródło
n.bit_length()-8
jest równoważne zlen(bin(n))-10
.Wolfram Language (Mathematica) , 46 bajtów
Wypróbuj online!
Ta wersja obsługuje tylko dane wejściowe do 2 518 -1, w przeciwnym razie napotkamy limit wielkości stosu Mathematiki. (Granice mogą się różnić w zależności od instalacji Mathematica). Drugie rozwiązanie w tej odpowiedzi pozwala tego uniknąć.
Jak to działa
Podejście rekurencyjne oparte na następującej logice:
0
dla każdego wejścia mniejsza niż256
, ponieważ usunięcie bajtu z liczby zjada całą liczbę. To jest nasz podstawowy przypadek, dlatego został uwzględniony, mimo że specyfikacje obiecują nam, że nie będziemy musieli obsługiwać takich danych wejściowych.Max
dwie opcje: zjedz najniższy bajt (dzieląc się z nami danymi wejściowymi256
) lub odetnij najniższy bit, powtórz na pozostałej liczbie całkowitej i dołącz ponownie najniższy bit, gdy skończymy.Wolfram Language (Mathematica) , 55 bajtów
Wypróbuj online!
Alternatywna wersja, która buduje tabelę zamiast rekurencji, więc działa dla liczb dowolnej wielkości, które Mathematica może obsłużyć.
źródło
Retina ,
716764 bajtówWypróbuj online! Link zawiera tylko szybsze przypadki testowe, aby nie nadmiernie przeciążać serwera Dennisa. Edycja: Zapisano 3 bajty dzięki @MartinEnder. Wyjaśnienie:
Konwertuj z dziesiętnego na dwójkowy.
Zbuduj listę ciągów znaków, usuwając 8 kolejnych cyfr na wszystkie możliwe sposoby.
Posortuj je w odwrotnej kolejności i wybierz pierwszą (największą).
Konwertuj z powrotem na dziesiętne. (Zobacz wyjaśnienie @ MartinEnder .)
źródło
Java (OpenJDK 8) ,
138134 bajtówWypróbuj online!
źródło
i.toBinaryString(i)
może byći.toString(i,2)
.ReRegex ,
294275 bajtówZaoszczędzono 19 bajtów dzięki lepszym definicjom „funkcji”
Powiedziałbym, że jest to całkiem dobre dla języka opartego tylko na Regex.
Podstawowa biblioteka lib pozwala na konwersję między jednostkową i dziesiętną (co jest potrzebne, ponieważ specyfikacja wyzwania wyraźnie określa dziesiętną), ale nie obsługuje wersji binarnej; Musiałem więc napisać to jako część skryptu, dodając do niego 120 bajtów.
Wypróbuj online!
Według poszczególnych regeksów.
Kroki
Po pierwsze, importujemy bibliotekę „podstawową”, która daje dwa wyrażenia regularne. Ten, który konwertuje
u<numbers>
w jedność. I taki, który konwertuje zd<unary_underlines>
powrotem na dziesiętne. Wynika to z faktu, że wyzwanie wymaga IO w bazie 10.Następnie definiujemy garść wyrażeń regularnych, które przekształcają jednoargumentowy na binarny.
Pierwsza z nich
b(\d*):(_*)\2_b/b1$1:$2b/
wyszukujeb
, opcjonalnie następuje kilka cyfr binarnych, następnie a:
, Następnie dowolna liczba podkreśleń, następnie dokładnie taka sama ilość podkreśleń plus jeden, a na końcu kolejnyb
.Następnie zamieniamy to na
b1
poprzedzone cyframi binarnymi z poprzedniej:
, i tylko pierwszą połowę podkreślenia, a na koniec ostatniąb
.Sprawdza to, czy jednostka jednoargumentowa nie jest podzielna przez dwa, a jeśli tak, wstawia 1 do cyfr binarnych, a następnie dzieli ją minus jeden przez dwa.
Drugi
b(\d*):(_+)\2b/b0$1:$2b/
jest prawie identyczny, jednak nie sprawdza dodatkowych_
, co oznacza, że pasuje tylko wtedy, gdy można go podzielić przez dwa, aw tym przypadku wstawia0
zamiast niego.Trzeci sprawdza, czy brakuje nam jednoznacznych cyfr, a jeśli tak, to usuwa dopełnienie, aby po prostu zostawić cyfry binarne.
Ostatni sprawdza, czy nigdy nie podano żadnych cyfr binarnych, i w takim przypadku po prostu wychodzi
0
.Następna grupa Regexów, którą definiujemy, polega na konwersji plików binarnych z powrotem na jednoargumentowe i są nieco prostsze.
Pierwsza z tej grupy,
B(_*):1/B$1$1_:/
podobnie jak jej antyteza, wykrywa aB
, a następnie dowolną liczbę Unary cyfr:1
. Nie sprawdza dopasowaniaB
tym przypadku , ponieważ szuka tylko jednej cyfry na raz. Jeśli jest to dopasowane, podwaja poprzednio dopasowaną liczbę jednoargumentowych cyfr i dodaje jedną, a następnie usuwa jedną.Drugi
B(_*):0/B$1$1:/
,, jest prawie identyczny z pierwszym, z wyjątkiem dopasowań0
raczej niż a1
i nie dodaje dodatkowej jednoznacznej cyfry.Ostatni z nich
B(_*):B/$1/
sprawdza, czy nie ma już cyfr binarnych, a jeśli tak, to rozpakowuje unary. W przeciwieństwie do jego antytezy, nie wymaga specjalnego przypadku 0.Następnie definiujemy
j
wyrażenia regularne, które działają jak funkcja dzielenia.Pierwszy
j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/
robi większość ciężkiego podnoszenia. Wyszukujej
, opcjonalnie po nich cyfry binarne, które są „inkrementatorem”, następnie przecinek, po którym następuje inkrementator, a następnie dokładnie 8 cyfr binarnych, po których następuje reszta liczby binarnej, a następnie a:
. Pierwsza z 8 cyfr jest dołączana do inkrementatora, zwiększając go, a następnie wszystko oprócz tych 8 cyfr z wejścia binarnego jest dołączane po:
następującym a,
. Tak więc (gdybyśmy używali 2 cyfr zamiast 8)j,1001:
stałoby sięj1:1001:,01
wtedyj10:1001,01,11
. Dodatkowo dołączone elementy tablicy są owinięte wB
s, aby przekonwertować je z powrotem na jednoargumentowe.Drugi
j(\d*),\1\d{0,7}:,?(.*)/,$2,/
sprawdza, czy pozostało mniej niż 8 cyfr binarnych do sprawdzenia za inkrementatorem, a jeśli tak, usuwa wszystko inne niż tablicę owiniętą w,
s. Na przykład.,_,___,
Podczas i po utworzeniu tablicy definiujemy wyrażenia regularne porównania.
Pierwszy z nich
,((_+)_+),(\2),/,$1,/
sprawdza przecinek, po którym następuje pewna liczba znaków podkreślenia, potem jeszcze kilka, następnie przecinek, a następnie pierwsza liczba znaków podkreślenia, niż przecinek. Następnie zastępuje go całkowitą liczbą znaków podkreślenia w pierwszym elemencie otoczonym przez,
s.Ten ostatni
,(_+),(\1_*),/,$2,/
sprawdza przecinek, po którym następuje pewna liczba znaków podkreślenia, po których następuje kolejny przecinek, następnie ta sama liczba lub więcej znaków podkreślenia i ostatni przecinek. To zamiast tego pozostawi właściwy element.Na koniec, gdy pozostanie element pasujący w ten sposób
^,(_*),$
, usuwamy otaczające go przecinki i przekształcamy z powrotem na dziesiętny przezd<>
. Wtedy nie będzie już więcej wyrażeń regularnych, a wynik zostanie przedstawiony.Dane wejściowe są początkowo umieszczane w szablonie
j,b:u<(?#input)>b:
, który najpierw przekształca dane dziesiętne na jednoargumentowe, np.5
->j,b:_____b:
, a następnie wynikowe jednostkowe na binarne, aj,101:
następnie dzieli binarne (co nie działa w tym przykładzie), pobiera największy element, konwertuje powrót do miejsca po przecinku i gotowe.źródło
C (gcc),
91bajtów-23 bajty od Colera Su
Obsługuje do
2**31-1
Wypróbuj online!
Zaczyna się od niskich 8 bitów
(j=0)
, a następnie idzie w górę, zmieniając moc wyjściową, jeśli liczba z[j,j+8)
odciętymi bitami jest większa niż nasz prąd, i kontynuowana, aż x nie będzie miało bitów powyżejj+8
źródło
x>>j+8
ix>>j+8<<j|x%(1<<j)
w zmiennej (usunięte nawiasy) zmniejszy ją do 68 bajtów .Galaretka , 12 bajtów
Wypróbuj online!
Oszczędzone bajty dzięki Jonathanowi Allanowi !
źródło
JavaScript (ES6),
9491 bajtów-3 bajty dzięki Justinowi Marinerowi
Po prostu wyrzucam rozwiązanie oparte na łańcuchach JavaScript, ale mam nadzieję, że ktoś opublikuje osobne rozwiązanie oparte na bitach, abym mógł się czegoś nauczyć.
Moje rozwiązanie rekurencyjnie pobiera 8-bitową porcję z łańcucha, przyjmując maksymalną znalezioną wartość.
Pokaż fragment kodu
źródło
+(...)
konwertujący'0b'+c[1]+c[2]
na liczbę, ponieważMath.max
już to robi. Wypróbuj online! ( specyfikacja do wykorzystania w przyszłości )C # (.NET Core) ,
122 + 13 = 135120 + 13 = 133 bajtówWypróbuj online!
+13 dla
using System;
Wyobrażam sobie, że istnieje sposób na zrobienie tego bez użycia
Convert
. Tak czy inaczej, jestem pewien, że można to zmniejszyć.Podziękowanie
-2 bajty dzięki Kevin Cruijssen
UnGolfed
źródło
while
sięfor
i kładzenievar b
się w nim:for(var b=Convert.ToString(n,2);i<b.Length-7;)
,t
i nieużywającMath.Max
, ale zamiast tego sprawdzając ręcznie:n=>{int m=0,i=0,t;for(var b=Convert.ToString(n,2);i<b.Length-7;m=t>m?t:m)t=Convert.ToInt32(b.Remove(i++,8),2);return m;}
( 120 + 13 bajtów )PHP, 67 + 1 bajtów
Uruchom jako potok z
-nR
lub spróbuj online .źródło
Pyth, 19 bajtów
Alternatywna odpowiedź:
Wyjaśnienie:
Druga odpowiedź wykorzystuje podobne podejście, z tym wyjątkiem, że najpierw obraca się w prawo i otrzymuje wszystkie bity oprócz ostatnich 8.
źródło
MATL ,
2321 bajtówWypróbuj online!
Niestety
Bn8-:8:!+q&)
produkuje tylko plastry do usunięcia, a nie resztę, którą chcielibyśmy zachować.źródło
Bn8-:"GB[]@8:q+(XBvX>
(przypisuj za[]
pomocą(
zamiast&)
, i zastępuj&:
przez:
i dodawanie)Java (OpenJDK 8) , 73 bajty
Wypróbuj online!
źródło
Oktawa ,
8180 bajtówWypróbuj online!
Jest to inne rozwiązanie niż moja pierwotna próba, oszczędzając kolejne 14 bajtów.
Kod jest podzielony w następujący sposób:
W szóstym wierszu liczba grup jest obliczana przez znalezienie wykładnika następnej potęgi dwóch większych niż wejściowa (liczba bitów w liczbie wejściowej) i odjęcie 7, ponieważ usuwamy 8 bitów z każdej grupy - otrzymana liczba jest przechowywane
b
na później.Następnie obliczamy tablicę potęg dwóch w piątej linii, która jest wystarczająco duża dla wszystkich możliwych grup, które można usunąć. Zapisujemy to w zmiennej
c
na później.W następnym wierszu w górę (czwarta linia) mnożymy dane wejściowe przez tablicę potęg dwóch (zasadniczo bitowo przesuwamy każdą liczbę w górę) i przekształcamy wynik na binarny. Jeśli weźmiemy przykład 7831, wynikiem jest tablica 2D zawierająca:
Jeśli następnie wycinamy środkowe 8 bitów, jest to równoważne usunięciu każdej z grup 8 bitów. Odbywa się to przez trzecią linię.
Powstała tablica jest konwertowana z powrotem na dziesiętne w drugim wierszu. Musimy również podzielić przez,
c
aby cofnąć skalowanie, które zostało początkowo wykonane dla każdej grupy.Wreszcie w pierwszym wierszu deklarowana jest funkcja anonimowa i obliczana jest maksymalna wartość ze wszystkich grup.
nextpow2(x+1)
zamiastnnz(bin2dec(x))
Oryginalna próba -
120 9895 bajtówWypróbuj online!
Kod dzieli się w następujący sposób:
Zasadniczo oblicza macierz zawierającą możliwe grupy wartości, które można usunąć, a następnie oblicza, co daje największą liczbę.
Działająca linia po linii, piąta linia oblicza grupy, które można usunąć. Na przykład weź 7831. Jest to liczba 13-bitowa, która daje grupom:
Wynikiem piątej linii jest dwuwymiarowa tablica logiczna, której można użyć do indeksowania.
Czwarty wiersz kodu konwertuje dane wejściowe na tablicę bitów (przedstawionych jako znaki „0” i „1”), a następnie powtarza je
n
-7 razy (gdzien
w liczbie bitów), dając jedną linię dla każdego możliwego grupowania. Powyższa maska grupy służy do usuwania każdej z możliwych grup.W trzecim wierszu wynik jest następnie przekształcany w celu cofnięcia niechcianego spłaszczenia wynikającego z zastosowania maski grupy. Drugi wiersz konwertuje z powrotem na tablicę wynikowych liczb dziesiętnych. Pierwszy wiersz definiuje funkcję anonimową jako maksymalną wartość tablicy możliwych grup.
źródło
Perl 5 , 78 + 1 (
-p
) = 79 bajtówWypróbuj online!
źródło
Rubinowy , 55 bajtów
Wypróbuj online!
źródło
Perl, 53 bajty
(
use 5.10.1
przeniesienie perla na poziom językowy 5.10.1 jest bezpłatny)Podaj numer wejściowy na STDIN. W przypadku dużych liczb zabraknie pamięci, ale liczba 32-bitowa na wejściu nie jest jeszcze problemem
źródło