Nous avons déjà défini ici un numéro de pliage .

Mais maintenant, nous allons définir un Super Folding Number. Un nombre Super Folding est un nombre qui, s'il est plié suffisamment de fois, finira par atteindre un de moins qu'une puissance de deux. La méthode de pliage est légèrement différente de celle de la question du nombre de pliage.

L'algorithme de pliage se déroule comme suit:

• Prenez la représentation binaire

  par exemple 5882

  1011011111010
  

• Je l'ai renversé en trois partitions. Première moitié, dernière moitié et chiffre du milieu (si elle a un nombre impair de chiffres)

  101101 1 111010
  

• Si le chiffre du milieu est zéro, ce nombre ne peut pas être plié

• Inverser la seconde moitié et superposé à la première moitié

  010111
  101101
  

• Ajouter les chiffres en place

  111212
  

• S'il y a des 2 dans le résultat, le nombre ne peut pas être plié, sinon le nouveau nombre est le résultat de l'algorithme de pliage.

Un nombre est un nombre Super Folding s'il peut être plié en une chaîne continue de uns. (Tous les numéros pliants sont également des numéros super pliants)

Votre tâche consiste à écrire du code qui prend un nombre et génère une valeur véridique si le nombre est un nombre Super Folding et faux sinon. Vous serez noté sur la taille de votre programme.

Exemples

5200

Convertir en binaire:

1010001010000

Divisé en deux:

101000 1 010000

Le milieu est un donc nous continuons de superposer les moitiés:

000010
101000

Les a ajoutés:

101010

Pas de deux donc nous continuons de diviser en deux:

101 010

Plier:

010
101

111

Le résultat est 111(7 en décimal), il s'agit donc d'un Super Folding Number.

Cas de test

Les 100 premiers numéros super pliants sont:

[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]

Voici mon tout premier tir au code golf:

Python 3, 167 octets

167 octets si des tabulations ou des espaces simples sont utilisés pour l'indentation

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

Edit: Grâce à l'aide de tout le monde ci-dessous, le code ci-dessus a été réduit d'une taille d'origine de 232 octets!

Java 7, 202 octets

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);}

Il a fallu un peu d'effort pour rendre l'ancienne fonction de pliage récursive, mais la voici. C'est moche comme péché, pour être honnête. Je vais devoir jeter un coup d'œil le matin pour voir si je peux jouer au golf plus loin, car je peux à peine me lever pour le regarder en ce moment.

Avec des sauts de ligne:

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 octets

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

Essayez-le en ligne! ou générer une liste de super numéros pliables jusqu'à un nombre donné.
Les tentatives de golf peuvent être vues ici .

Le code se décompose selon les phases suivantes:

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

EDIT: Cette version reprend plus ou moins une approche de De Morgan's Law par rapport à la version précédente.

* Le problème avec l'exécution sur singletons est que nous sommes coincés avec une chaîne vide après la tranche.

** Si un nombre binaire est super pliant, son image miroir (avec des 0 en tête si nécessaire) l'est. Cela permet d'économiser un octet sur la prise de la moitié droite.

JavaScript, 149 octets

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``+"")

Définit une fonction récursive.

Explication:

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 octets

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

Formaté et commenté

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

Démo

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 octets

Comprend +1 pour -p

Donner un numéro sur STDIN

superfolding.pl:

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

Python 2, 151 octets

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

Une fonction doublement récursive qui prend un entier,, net retourne 0ou 1.

Une variable rest maintenue pour permettre à la fois le résultat du repliement et savoir si nous avons actuellement: un entier (en premier seulement); avoir une nouvelle chaîne binaire pour essayer de plier (externe); ou se replient (intérieur).

Lors de la première passe, nest et entier, qui est <''en Python 2, donc la récursivité commence par le transtypage en chaîne binaire.

La prochaine exécution a r=''et donc le test {'1'}==set(n)est exécuté pour vérifier une chaîne continue de 1s (le RHS ne peut pas être {n}comme nous pouvons avoir besoin de passer ce point plus tard avec r=''et un vide nquand ce serait un dictionnaire qui ne sera pas égal {'1'}, un ensemble).

Si cela n'est pas satisfait, le critère de queue interne est testé (même si cela n'est pas nécessaire): if n in'1'sera évalué à True quand nest une chaîne vide ou une simple 1, après quoi une nouvelle récursivité externe est commencée en plaçant r, par la chaîne binaire alors repliée, dans net ''en r. Le littéral 2est ajouté au résultat de cet appel de fonction pour ne permettre aucun passage à la partie suivante (à droite d'une logique or) qui est corrigée plus tard.

Si ce n'est pas une valeur véridique (tous les entiers non nuls sont véridiques en Python), les critères de récursivité de la queue externe sont testés: n!=0exclut le cas avec un milieu 0et les deux caractères externes sont testés, ils ne sont pas additionnés 2par la concaténation de chaîne '11'!=n[0]+n[-1]; si ces deux valeurs sont vraies, les bits externes sont supprimés de nwith n[1:-1], puis a 1est ajouté rs'il y en a un à l'extérieur, sinon a 0est, en utilisant le fait qu'en '1'>'0'Python avec max(n[0],n[-1]).

Enfin l'addition de 2à chaque récursion intérieure est corrigée avec %2.

PHP, 113 octets

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);

quitte avec erreur (code 1) si l'argument n'est pas super-pliant, code 0sinon. Courez avec -r.
L'entrée 0renverra vrai (code 0).

panne

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 octets

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]));

Étendu

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]));

Vraies valeurs <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