Opierając się na zapisie „binarnym, ale z dwójkami” wspomnianym w tym filmie liczbowym , napisz funkcję, która pobiera pojedynczą liczbę jako dane wejściowe i wyprowadza wszystkie odmiany tej liczby w systemie „binarnym”, w którym dozwolone są dwójki.
Zasady
- Kod musi być tylko funkcją / metodą, a nie pełnym programem
- Dane wejściowe to liczba całkowita przekazywana jako jedyny parametr do funkcji
- Dane wyjściowe to wszystkie poprawne odmiany liczby wejściowej przekonwertowane na notację „dwójkową, ale dwójkową”
- Dane wyjściowe są wartością zwracaną przez funkcję, ale mogą być w dowolnym dogodnym formacie, o ile jest to oczywiste (np. 3 liczby całkowite, 3 ciągi, łańcuch rozdzielany przecinkami / spacjami, tablica liczb całkowitych itp.), Kolejność jest nieistotna
- W mało prawdopodobnym przypadku, gdy język zawiera wbudowaną funkcję umożliwiającą osiągnięcie wyniku, jest on niedozwolony
- Zwycięża najkrótszy kod w bajtach
Objaśnienie danych wyjściowych
Na przykład, jeśli otrzymałeś numer 9
, możesz przekonwertować go na binarny jako 1001
, ale jeśli zezwoliłeś 2
s na każdej pozycji, możesz również zapisać go jako 201
(tj. 2*4 + 0*2 + 1*1
) Lub 121
(tj. 1*4 + 2*2 + 1*1
), Jak pokazano w tej tabeli:
+----+----+----+----+
| 8s | 4s | 2s | 1s |
+----+----+----+----+
| 1 | 0 | 0 | 1 |
| 0 | 2 | 0 | 1 |
| 0 | 1 | 2 | 1 |
+----+----+----+----+
Tak więc, jeśli przejdzie 9
, twoja funkcja będzie musiała zwrócić trzy liczby 1001
, 201
i 121
.
Format i porządek są bez znaczenia, tak długo, jak to jest oczywiste (czyli [121,201,1001]
, "0201 0121 1001"
, ("1001","121","201")
są ważne wyniki, gdy otrzyma na wejście 9
).
Przykłady
2
=>10, 2
9
=>1001, 201, 121
10
=>1010, 210, 202, 1002, 122
23
=>2111, 10111
37
=>100101, 20101, 100021, 20021, 12101, 12021, 11221
źródło
Odpowiedzi:
GolfScript (25 bajtów) / CJam (
1917 bajtów)GolfScript:
To tworzy funkcję anonimową (patrz meta dyskusja na temat dopuszczalności funkcji anonimowych ).
Demo online
Proste tłumaczenie na CJam jest (dzięki dzięki Martinowi Büttnerowi za golenie kilku znaków)
Sekcja
Powodem operacji kwadratu jest to, że musimy iterować do największej możliwej wartości, której trójskładnikowa reprezentacja interpretowana binarnie jest równa
^
. Ponieważ2 = 10
„normalna” reprezentacja binarna^
ma znaczenie. Jeśli przekonwertujemy to na trójskładnikowe, okaże się, że „najgorsze” przypadki to potęgi 2. Optymalnym podejściem byłoby przyjęcie argumentu o potędzeln 3/ln 2 ~= 1.585
, ale kwadrat jest znacznie krótszy.źródło
Python 2 (59 bajtów)
(Wielkie podziękowania dla @grc, @xnor i @PeterTaylor za pomoc na czacie)
Prosta rekurencja, połączenie z
S(23)
lub podobne.Wyjaśnienie
Ogólna idea jest taka, że jeśli
n
rozszerzenie binarne kończy się na a1
, to każde rozszerzenie pseudobinarne („binarne, ale dwójkowe”) musi również kończyć się na1
. W przeciwnym razie może zakończyć się na0
lub2
.Dlatego patrzymy na ostatni kawałek
n
, dzielimy i odpowiednio rozgałęziamy.Sekcja
Zmienne:
n
: Liczba, dla której chcemy znaleźć pseudobinarne rozszerzeniaB
: Pseudobinarny ciąg znaków jest budowany od prawej do lewejźródło
Bash + coreutils, 77
(To jest TABznak w wyrażeniu grep.)
To trochę zgina tę zasadę:
„W mało prawdopodobnym przypadku, gdy język zawiera wbudowaną funkcję umożliwiającą osiągnięcie wyniku, jest niedozwolony”
Okazuje się, że
dc
ma odwrotność tego, co jest nam potrzebne. Na przykład, jeśli ustawimy bazę wejściową na 2 i wprowadzimy dwójkową liczbę dwójkową, poprawnie ją parsuje. (Podobnie, jeśli trybem wprowadzania jest podstawa 10, wówczas AF są analizowane jako dziesiętne „cyfry” 10-15).seq
tworzy listę wszystkich liczb dziesiętnych aż do standardowej reprezentacji binarnej n, parsowanej jako dziesiętna. Następnie wszystkie liczby zawierające cokolwiek innego niż {0,1,2} są odfiltrowywane. Następniedc
analizuje pozostałe liczby jako binarne, aby zobaczyć, które wartości wracają do n.Funkcje Bash mogą „zwracać” tylko liczby całkowite skalarne 0–255. Więc pozwalam sobie wydrukować listę do STDOUT jako mojego sposobu „powrotu”. Jest to idiomatyczne dla skryptów powłoki.
Wynik:
źródło
Haskell, 82
to tylko rozwiązanie brutalnej siły. jest bardzo nieefektywny, ponieważ oczekuje się, że przejrzy 3 możliwości.
źródło
Galaretka , 10 bajtów, wyzwanie dla postdate języka
Wypróbuj online!
Rozwiązanie bruteforce do liczby hiperbit równych wejściowi (ten format jest znany jako „hyperbinary”). Jako taki jest niesamowicie nieefektywny, działa w O (3 n ).
Wyjaśnienie
źródło
PHP, 138 bajtów
Awaria
źródło
C ++, 159 bajtów
Sprawdź to tutaj
źródło
k, 21 bajtów
Używa tej samej metody, co odpowiedź Golfscript Petera Taylora
Przykłady:
źródło