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ś 2s 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, 201i 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

GolfScript (25 bajtów) / CJam ( 19 17 bajtów)

GolfScript:

{:^.*,{3base}%{2base^=},}

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)

{:X_*,3fb{2bX=},}

Sekcja

{             # Function boilerplate
  :^          # Store parameter as variable ^
  .*          # Square parameter - see detailed explanation below
  ,{3base}%   # Produce an array of 0 to ^*^-1 in ternary
  {2base^=},  # Filter to those which evaluate to ^ in binary
}

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ędze ln 3/ln 2 ~= 1.585, ale kwadrat jest znacznie krótszy.

Python 2 (59 bajtów)

S=lambda n,B="":[B][n:]or~n%2*S(n/2-1,"2"+B)+S(n/2,`n&1`+B)

(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 nrozszerzenie binarne kończy się na a 1, to każde rozszerzenie pseudobinarne („binarne, ale dwójkowe”) musi również kończyć się na 1. W przeciwnym razie może zakończyć się na 0lub 2.

Dlatego patrzymy na ostatni kawałek n, dzielimy i odpowiednio rozgałęziamy.

Sekcja

S=lambda n,B="":           # Lambda expression
[B][n:]or                  # Short circuit, return [B] if n==0 else what follows
~n%2*                      # Keep next list result if n is even else turn into []
S(n/2-1,"2"+B)             # Add a "2" to B, recurse
+
S(n/2,`n&1`+B)             # Add "0" or "1" to B depending on n's last bit, recurse

Zmienne:

• n: Liczba, dla której chcemy znaleźć pseudobinarne rozszerzenia
• B: Pseudobinarny ciąg znaków jest budowany od prawej do lewej

Bash + coreutils, 77

f()(seq `dc -e2o$1p`|sed '/[3-9]/d;s/.*/&n9P2i&pAi/'|dc|grep -Po ".*(?= $1)")

(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 dcma 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).

seqtworzy 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ępnie dcanalizuje 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:

$ f 2
2   
10  
$ f 9
121 
201 
1001    
$

Haskell, 82

t n=[dropWhile(==0)s|s<-mapM(\_->[0..2])[0..n],n==sum[2^(n-i)*v|(i,v)<-zip[0..]s]]

to tylko rozwiązanie brutalnej siły. jest bardzo nieefektywny, ponieważ oczekuje się, że przejrzy 3 możliwości.

Galaretka , 10 bajtów, wyzwanie dla postdate języka

ṗ@3Ḷ¤Ḅ=¥Ðf

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 ⁿ ).

Wyjaśnienie

ṗ@3Ḷ¤Ḅ=¥Ðf
ṗ@            Construct all lists with the given length, and elements taken from
  3Ḷ¤         the list [0,1,2]
        Ðf    then take only those elements which
     Ḅ=¥      when interpreted as binary, equal {the original number}

PHP, 138 bajtów

function p($v,$i=0,$r=""){global$a;if($v==0)$a[]=$r?:0;elseif($v>0)for(;$l<3;)p($v-2**$i*$l,$i+1,+$l++.$r);}p($argv[1]);echo join(",",$a);

Awaria

function p($v,$i=0,$r=""){
    global$a;
    if($v==0)$a[]=$r?:0;  # fill result array
    elseif($v>0) # make permutations
        for(;$l<3;)
            p($v-2**$i*$l,$i+1,+$l++.$r); #recursive
}
p($argv[1]);
echo join(",",$a); # Output

C ++, 159 bajtów

void c(int x,string r){int i,t=0,s=r.size();if(s<8){if(r[0]>48){for(i=0;i<s;i++)t+=(r[s-i-1]-48)*1<<i;if(t==x)cout<<r<<" ";}for(char n=48;n<51;n++)c(x,r+n);}}

Sprawdź to tutaj

k, 21 bajtów

Używa tej samej metody, co odpowiedź Golfscript Petera Taylora

{X@&x=2/:'X:3\:'!x*x}

Przykłady:

k) {X@&x=2/:'X:3\:'!x*x}9
(1 2 1;2 0 1;1 0 0 1)
k) {X@&x=2/:'X:3\:'!x*x}10
(1 2 2;2 0 2;2 1 0;1 0 0 2;1 0 1 0)