Zdefiniowaliśmy już tutaj numer składany .

Ale teraz zdefiniujemy Super Folding Number. Super składana liczba to liczba, która po złożeniu wystarczającej liczby razy ostatecznie osiągnie jeden mniej niż potęgę dwóch. Metoda składania jest nieco inna niż w pytaniu liczby składanej.

Algorytm składania składa się w następujący sposób:

• Weź reprezentację binarną

  np. 5882

  1011011111010
  

• Rozlano go na trzy partycje. Pierwsza połowa, ostatnia połowa i środkowa cyfra (iff ma nieparzystą liczbę cyfr)

  101101 1 111010
  

• Jeśli środkowa cyfra to zero, liczby tej nie można złożyć

• Odwróć drugą połowę i nałóż na pierwszą połowę

  010111
  101101
  

• Dodaj cyfry na miejscu

  111212
  

• Jeśli w wyniku są jakieś 2, liczby nie można złożyć, w przeciwnym razie nowa liczba jest wynikiem algorytmu składania.

Liczba jest liczbą super składaną, jeśli można ją złożyć do ciągłego ciągu jedności. (Wszystkie numery składane są również liczbami super składanymi)

Twoim zadaniem jest napisanie kodu, który pobierze liczbę i wyświetli prawdziwą wartość, jeśli liczba jest liczbą Super Folding, a fałszem w przeciwnym razie. Zostaniesz oceniony na podstawie wielkości twojego programu.

Przykłady

5200

Konwertuj na binarny:

1010001010000

Podziel na pół:

101000 1 010000

Środek jest jeden, więc kontynuujemy Nałóż połówki:

000010
101000

Dodano je:

101010

Bez dwójki, więc dzielimy dalej na pół:

101 010

Zagięcie:

010
101

111

Wynik to 111(7 po przecinku), więc jest to liczba super składana.

Przypadki testowe

Pierwsze 100 super składanych liczb to:

[1, 2, 3, 6, 7, 8, 10, 12, 15, 20, 22, 28, 31, 34, 38, 42, 48, 52, 56, 63, 74, 78, 90, 104, 108, 120, 127, 128, 130, 132, 142, 150, 160, 170, 178, 192, 204, 212, 232, 240, 255, 272, 274, 276, 286, 310, 336, 346, 370, 400, 412, 436, 472, 496, 511, 516, 518, 524, 542, 558, 580, 598, 614, 640, 642, 648, 666, 682, 704, 722, 738, 772, 796, 812, 852, 868, 896, 920, 936, 976, 992, 1023, 1060, 1062, 1068, 1086, 1134, 1188, 1206, 1254, 1312, 1314, 1320, 1338, 1386, 1440, 1458, 1506, 1572, 1596]

Oto mój pierwszy film w golfa Code:

Python 3, 167 bajtów

167 bajtów, jeśli do wcięcia używane są tabulatory lub pojedyncze spacje

def f(n):
 B=bin(n)[2:];L=len(B);M=L//2
 if'1'*L==B:return 1
 S=str(int(B[:M])+int(B[:-M-1:-1]))
 return 0if(~L%2==0and'0'==B[M])or'2'in S else{S}=={'1'}or f(int(S,2))

Edycja: Dzięki poniższej pomocy wszystkich, powyższy kod został zmniejszony z pierwotnego rozmiaru 232 bajtów!

Java 7, 202 bajty

boolean g(Integer a){byte[]b=a.toString(a,2).getBytes();int i=0,l=b.length,o=0,c,z=(a+1&a)==0?-1:1;for(;i<l/2&z>0;o+=o+c*2,z*=c>1|(l%2>0&b[l/2]<49)?0:1)c=b[i]+b[l-++i]-96;return z<0?1>0:z<1?0>1:g(o/2);}

Trwało trochę wysiłku, aby stara funkcja składania była powtarzalna, ale oto ona. Szczerze mówiąc, jest to brzydkie jak grzech. Rano muszę rzucić okiem, aby sprawdzić, czy mogę grać w golfa dalej, ponieważ ledwo mogę teraz znieść wzrok.

Z podziałami linii:

boolean g(Integer a){
    byte[]b=a.toString(a,2).getBytes();
    int i=0,l=b.length,o=0,c,z=(a+1&a)==0?-1:1;
    for(;i<l/2&z>0;o+=o+c*2,z*=c>1|(l%2>0&b[l/2]<49)?0:1)
        c=b[i]+b[l-++i]-96;
    return z<0?1>0:z<1?0>1:g(o/2);
}

CJam , 47 44 bajtów

ri2b{_W%.+__0e=)\_,1>\0-X+:*3<*&}{_,2/<}w2-!

Wypróbuj online! lub wygeneruj listę super składanych liczb do podanej liczby.
Próby gry w golfa można zobaczyć tutaj .

Kod dzieli się na następujące fazy:

ri2b                e# get input in binary
{                   e# While fold is legal
 _W%.+_             e#   "fold" the whole number onto itself
 _0e=)\             e#   count zeros and add 1 (I)
 _,1>\              e#   size check, leave 0 if singleton (II)*
 0-X+:*3<           e#   product of 2s, leave 0 if too many (III)
 *&                 e#   (II AND III) AND parity of I
}{                  e# Do
 _,2/<              e#   slice opposite to the actual fold**
}w                  e# End while
2-!                 e# return 1 if "fold" ended in all 2s

EDYCJA: Ta wersja mniej więcej przyjmuje podejście De Morgana do poprzedniej wersji.

* Problem z uruchomieniem singletonów polega na tym, że utknęliśmy z pustym łańcuchem po plastrze.

** Jeśli liczba binarna jest super składana, jej odbicie lustrzane (w razie potrzeby z wiodącymi zerami) to. Oszczędza to bajt przejęcia prawej połowy.

JavaScript, 149 bajtów

f=(i,n=i.toString(2),l=n.length,m=l/2|0)=>/^1*$/.test(n)?1:/[^01]/.test(n)|!+n[m]&l?0:f(0,+n.slice(0,m)+ +n.slice(m+l%2).split``.reverse().join``+"")

Definiuje funkcję rekurencyjną.

Wyjaśnienie:

f=(i                       //Defines the function: i is input
,n=i.toString(2)           //n is the current number
,l=n.length                //l is the length of the number,
,m=l/2|0)=>                //m is the index of the center character
/^1*$/.test(n)?1:          //returns 1 if the number is all ones
/[^01]/.test(n)            //returns 0 if the number has any chars other than 0 or 1
|!+n[m]&l?0:               //or if the middle char is 0
f(0,+n.slice(0,m)+ +n.slice(m+l%2).split``.reverse().join``+"")
                           //otherwise recurses using the first half of the number plus the second half

JavaScript (ES6), 113 109 108 bajtów

f=(n,[h,...r]=n.toString(2),b='')=>++n&-n-n?h?f(2,r,r[0]?b+(h- -r.pop()):+h?b:2):!isNaN(n=+('0b'+b))&&f(n):1

Sformatowane i skomentowane

f = (                               // given:
  n,                                // - n = integer to process
  [h, ...r] = n.toString(2),        // - h = highest bit, r = remaining low bits
  b = ''                            // - b = folded binary string
) =>                                //
  ++n & -n - n ?                    // if n is not of the form 2^N - 1:
    h ?                             //   if there's still at least one bit to process:
      f(                            //     do a recursive call with:
        2,                          //     - n = 2 to make the 2^N - 1 test fail
        r,                          //     - r = remaining bits
        r[0] ?                      //     - if there's at least one remaining low bit:
          b + (h - -r.pop())        //       append sum of highest bit + lowest bit to b
        : +h ? b : 2                //       else, h is the middle bit: let b unchanged
      )                             //       if it is set or force error if it's not
    : !isNaN(n = +('0b' + b)) &&    //   else, if b is a valid binary string:
      f(n)                          //     relaunch the entire process on it
  : 1                               // else: n is a super folding number -> success

Próbny

f=(n,[h,...r]=n.toString(2),b='')=>++n&-n-n?h?f(2,r,r[0]?b+(h- -r.pop()):+h?b:2):!isNaN(n=+('0b'+b))&&f(n):1

// testing integers in [1 .. 99]
for(var i = 1; i < 100; i++) {
  f(i) && console.log(i);
}

// testing integers in [1500 .. 1599]
for(var i = 1500; i < 1600; i++) {
  f(i) && console.log(i);
}

Perl, 71 70 bajtów

Obejmuje +1 dla -p

Podaj numer na STDIN

superfolding.pl:

#!/usr/bin/perl -p
$_=sprintf"%b",$_;s%.%/\G0$/?2:/.\B/g&&$&+chop%eg while/0/>/2/;$_=!$&

Python 2, 151 bajtów

f=lambda n,r=0:f(bin(n)[2:],'')if r<''else(r==''and{'1'}==set(n)or(n in'1'and f(r,'')+2)or n!='0'and'11'!=n[0]+n[-1]and f(n[1:-1],r+max(n[0],n[-1])))%2

ideone

Funkcja podwójnie rekurencyjna, która przyjmuje liczbę całkowitą ni zwraca 0lub 1.

Zmienna rjest utrzymywana, aby umożliwić zarówno wynik składania, jak i wiedzieć, czy obecnie: mamy liczbę całkowitą (tylko pierwsza); mieć nowy ciąg binarny, aby spróbować złożyć (zewnętrzny); lub są składane (wewnętrzne).

W pierwszym przejściu njest liczbą całkowitą, która znajduje się <''w Pythonie 2, więc rekurencja rozpoczyna się rzutowaniem na ciąg binarny.

Następne wykonanie ma, r=''więc test {'1'}==set(n)jest wykonywany w celu sprawdzenia ciągłego ciągu 1s (RHS nie może być, {n}ponieważ być może będziemy musieli przekazać ten punkt później z r=''pustym, ngdy będzie to słownik, który nie będzie równy {'1'}, zestaw).

Jeśli nie jest to spełnione, sprawdzane są kryteria wewnętrznego ogona (nawet jeśli są niepotrzebne): jeśli n in'1'oceni na True, gdy njest pusty ciąg lub pojedynczy 1, po czym rozpoczyna się nowa rekurencja zewnętrzna poprzez umieszczenie r, następnie złożonego, dwójkowego łańcucha w ni ''do r. Literał 2jest dodawany do wyniku tego wywołania funkcji, aby nie dopuścić do przejścia do następnej części (po prawej stronie logiki or), która zostanie poprawiona później.

Jeśli nie jest to prawdziwa wartość (wszystkie niezerowe liczby całkowite są prawdziwe w Pythonie), sprawdzane są kryteria rekurencji zewnętrznego ogona: n!=0wyklucza przypadek ze środkiem 0i testowane są dwa zewnętrzne znaki, których nie sumuje 2przez konkatenację łańcucha '11'!=n[0]+n[-1]; Jeśli to prawdziwe zarówno zewnętrzne bity są usuwane z no n[1:-1], a następnie 1jest dodawany do r, jeżeli jest na zewnątrz w przeciwnym razie 0jest, wykorzystując fakt, że '1'>'0'w Pythona max(n[0],n[-1]).

Na koniec 2koryguje się dodawanie przy każdej wewnętrznej rekurencji %2.

PHP, 113 bajtów

for($n=$argv[1];$n!=$c;$n=($a=$n>>.5+$e)|($b=$n&$c=(1<<$e/=2)-1))if($a&$b||($e=1+log($n,2))&!(1&$n>>$e/2))die(1);

kończy działanie z błędem (kodem 1), jeśli argument nie jest super-zwijany, kod 0inny. Uruchom z -r.
Dane wejściowe 0zwrócą wartość true (kod 0).

awaria

for($n=$argv[1];            
    $n!=$c;                 // loop while $n is != mask
                            // (first iteration: $c is null)
    $n=                     // add left half and right half to new number
        ($a=$n>>.5+$e)      // 7. $a=left half
        |
        ($b=$n&             // 6. $b=right half
            $c=(1<<$e/=2)-1 // 5. $c=mask for right half
        )
)
    if($a&$b                // 1. if any bit is set in both halves
                            // (first iteration: $a and $b are null -> no bits set)
        ||                  // or
        ($e=1+log($n,2))    // 2. get length of number
        &
        !(1&$n>>$e/2)       // 3. if the middle bit is not set -> 1
                            // 4. tests bit 0 in length --> and if length is odd
    )
    die(1);                 // -- exit with error

PHP, 197 bajtów

function f($b){if(!$b)return;if(!strpos($b,"0"))return 1;for($n="",$i=0;$i<($l=strlen($b))>>1;)$n.=$b[$i]+$b[$l-++$i];if($l%2&&!$b[$i]||strstr($n,"2"))return;return f($n);}echo f(decbin($argv[1]));

Rozszerzony

function f($b){
    if(!$b)return; # remove 0
    if(!strpos($b,"0"))return 1; # say okay alternative preg_match("#^1+$#",$b)
    for($n="",$i=0;$i<($l=strlen($b))>>1;)$n.=$b[$i]+$b[$l-++$i]; #add first half and second reverse
    if($l%2&&!$b[$i]||strstr($n,"2"))return; #if middle == zero or in new string is a 2 then it's not a number that we search
    return f($n); #recursive beginning
}
echo f(decbin($argv[1]));

Prawdziwe wartości <10000

1, 2, 3, 6, 7, 8, 10, 12, 15, 20, 22, 28, 31, 34, 38, 42, 48, 52, 56, 63, 74, 78, 90, 104, 108, 120, 127, 128, 130, 132, 142, 150, 160, 170, 178, 192, 204, 212, 232, 240, 255, 272, 274, 276, 286, 310, 336, 346, 370, 400, 412, 436, 472, 496, 511, 516, 518, 524, 542, 558, 580, 598, 614, 640, 642, 648, 666, 682, 704, 722, 738, 772, 796, 812, 852, 868, 896, 920, 936, 976, 992, 1023, 1060, 1062, 1068, 1086, 1134, 1188, 1206, 1254, 1312, 1314, 1320, 1338, 1386, 1440, 1458, 1506, 1572, 1596, 1644, 1716, 1764, 1824, 1848, 1896, 1968, 2016, 2047, 2050, 2054, 2058, 2064, 2068, 2072, 2110, 2142, 2176, 2180, 2184, 2222, 2254, 2306, 2320, 2358, 2390, 2432, 2470, 2502, 2562, 2576, 2618, 2650, 2688, 2730, 2762, 2866, 2898, 2978, 3010, 3072, 3076, 3080, 3132, 3164, 3244, 3276, 3328, 3380, 3412, 3492, 3524, 3584, 3640, 3672, 3752, 3784, 3888, 3920, 4000, 4032,4095, 4162, 4166, 4170, 4176, 4180, 4184, 4222, 4318, 4416, 4420, 4424, 4462, 4558, 4674, 4688, 4726, 4822, 4928, 4966, 5062, 5186, 5200, 5242, 5338, 5440, 5482, 5578, 5746, 5842, 5986, 6082, 6208, 6212, 6216, 6268, 6364, 6508, 6604, 6720, 6772, 6868, 7012, 7108, 7232, 7288, 7384, 7528, 7624, 7792, 7888, 8032, 8128, 8191, 8202, 8206, 8218, 8232, 8236, 8248, 8318, 8382, 8456, 8460, 8472, 8542, 8606, 8714, 8744, 8814, 8878, 8968, 9038, 9102, 9218, 9222, 9234, 9248, 9252, 9264, 9334, 9398, 9472, 9476, 9488, 9558, 9622, 9730, 9760, 9830, 9894, 99848128, 8191, 8202, 8206, 8218, 8232, 8236, 8248, 8318, 8382, 8456, 8460, 8472, 8542, 8606, 8714, 8744, 8814, 8878, 8968, 9038, 9102, 9218, 9222, 9234, 9248, 9252, 9264, 9334, 9398, 9472, 9476, 9488, 9558, 9622, 9730, 9760, 9830, 9894, 99848128, 8191, 8202, 8206, 8218, 8232, 8236, 8248, 8318, 8382, 8456, 8460, 8472, 8542, 8606, 8714, 8744, 8814, 8878, 8968, 9038, 9102, 9218, 9222, 9234, 9248, 9252, 9264, 9334, 9398, 9472, 9476, 9488, 9558, 9622, 9730, 9760, 9830, 9894, 9984