Super Faltnummern

10

Wir haben bereits eine klappbare Nummer definiert hier .

Aber jetzt werden wir eine Super Folding Number definieren. Eine Super Folding-Zahl ist eine Zahl, die, wenn sie genügend oft gefaltet wird, irgendwann eine Zahl weniger als eine Zweierpotenz erreicht. Die Faltmethode unterscheidet sich geringfügig von der Frage nach der Faltnummer.

Der Faltalgorithmus lautet wie folgt:

  • Nehmen Sie die binäre Darstellung

    zB 5882

    1011011111010
    
  • Verschüttete es in drei Partitionen. Erste Hälfte, letzte Hälfte und mittlere Ziffer (wenn es eine ungerade Anzahl von Ziffern hat)

    101101 1 111010
    
  • Wenn die mittlere Ziffer Null ist, kann diese Zahl nicht gefaltet werden

  • Die zweite Hälfte umkehren und die erste Hälfte überlagern

    010111
    101101
    
  • Fügen Sie die Ziffern hinzu

    111212
    
  • Wenn das Ergebnis 2s enthält, kann die Zahl nicht gefaltet werden, andernfalls ist die neue Zahl das Ergebnis des Faltalgorithmus.

Eine Zahl ist eine Super-Faltnummer, wenn sie zu einer fortlaufenden Folge von Einsen gefaltet werden kann. (Alle Faltnummern sind auch Super-Faltnummern)

Ihre Aufgabe ist es, Code zu schreiben, der eine Zahl aufnimmt und einen wahrheitsgemäßen Wert ausgibt, wenn die Zahl eine Super-Folding-Zahl ist und ansonsten falsch ist. Sie werden nach der Größe Ihres Programms bewertet.

Beispiele

5200

In Binär konvertieren:

1010001010000

Halbieren:

101000 1 010000

Die Mitte ist eine, also überlagern wir die Hälften:

000010
101000

Fügte sie hinzu:

101010

Keine Zweien, also fahren wir fort. In zwei Hälften teilen:

101 010

Falten:

010
101

111

Das Ergebnis ist 111(7 in Dezimalzahl), dies ist also eine Super-Faltzahl.

Testfälle

Die ersten 100 Super Folding Numbers sind:

[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]
Ad-hoc-Garf-Jäger
quelle
2
Wie habe ich mich 3wieder in die Testfälle geschlichen, wenn ich mich nicht irre ? Ich kann nicht sehen, wie es gefaltet werden kann, da es sich aufteilt 1 1und sofort ein gibt 2. Oder sagen Sie, dass es auch zählt, es nullmal zu falten?
Geobits
@geobits 3 soll da sein. Ich habe diesmal nachgesehen;). Drei ist 11, so dass es nur eins in null Dateien gibt
Ad Hoc Garf Hunter
Ich denke, es kann sich lohnen, eine Notiz ganz oben zu platzieren, kurz nachdem Sie auf die andere Frage zur Faltnummer verlinkt haben, die darauf hinweist, dass die einzelnen Falten in dieser Frage eine andere Methode verwenden.
Jonathan Allan

Antworten:

9

Hier ist mein erster Schuss beim Code Golf:

Python 3, 167 Bytes

167 Bytes, wenn Tabulatoren oder einzelne Leerzeichen zum Einrücken verwendet werden

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

Bearbeiten: Dank der Hilfe aller unten wurde der obige Code von einer ursprünglichen Größe von 232 Bytes reduziert!

Kapocsi
quelle
1
Willkommen bei PPCG! Sie können eine Reihe von Bytes speichern, indem Sie die Leerzeichen nach dem :s entfernen 0und 1statt Trueund zurückgeben False.
Steven H.
Danke Steven. Außerdem bin ich mir nicht 100% sicher, ob ich die Bytelänge richtig gezählt habe.
Kapocsi
1
Ich sehe 232 Bytes. Geben Sie mir eine Sekunde und ich kann versuchen, es ein wenig weiter zu spielen.
Steven H.
Früher habe ich dies zu messen: bytesizematters.com
Kapocsi
1
@Kapocsi, bytesizematters.com zählt Zeilenumbrüche falsch. Vergleichen Sie mit Mothereff.in , 5 Ziffern und 5 Zeilenumbrüche sollten 10 Bytes sein, nicht die 14, die ich auf Bytesize bekommen habe ... es ist 232.
Linus
5

Java 7, 202 Bytes

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

Es war ein wenig mühsam, die alte Faltfunktion rekursiv zu machen, aber hier ist sie. Es ist hässlich wie Sünde, um ehrlich zu sein. Ich muss am Morgen einen Blick darauf werfen, ob ich weiter Golf spielen kann, da ich es im Moment kaum ertragen kann, es mir anzusehen.

Mit Zeilenumbrüchen:

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);
}
Geobits
quelle
3

CJam , 47 44 Bytes

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

Probieren Sie es online aus! oder generieren Sie eine Liste von Super-Faltnummern bis zu einer bestimmten Nummer.
Golfversuche sind hier zu sehen .


Der Code gliedert sich in folgende Phasen:

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

BEARBEITEN: Diese Version verwendet mehr oder weniger einen De Morgan's Law- Ansatz zur vorherigen Version.

* Das Problem beim Laufen auf Singletons ist, dass wir nach dem Slice mit einer leeren Zeichenfolge hängen bleiben.

** Wenn eine Binärzahl super faltbar ist, ist ihr Spiegelbild (bei Bedarf mit führenden Nullen). Dies spart ein Byte gegenüber der rechten Hälfte.

Linus
quelle
2

JavaScript, 149 Bytes

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

Definiert eine rekursive Funktion.

Erläuterung:

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
DanTheMan
quelle
m=l>>1, /2/.test(n), n.slice(l-m)(Oder die umgekehrte Zeichenfolge Scheibe). Ich denke, wenn Sie die Fehler- und Erfolgsfälle wechseln, können Sie verwenden /0/.test(n)?f(...):1.
Neil
2

JavaScript (ES6), 113 109 108 Byte

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

Formatiert und kommentiert

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

Demo

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

Arnauld
quelle
2

Perl, 71 70 Bytes

Beinhaltet +1 für -p

Geben Sie die Nummer auf STDIN an

superfolding.pl::

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

Python 2, 151 Bytes

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

Eine doppelt rekursive Funktion, die eine Ganzzahl annimmt nund 0oder zurückgibt 1.

Eine Variable rwird beibehalten, um sowohl das Ergebnis der Faltung zu ermöglichen als auch um zu wissen, ob wir derzeit: eine Ganzzahl haben (nur die erste); eine neue Binärzeichenfolge haben, um zu versuchen, zu falten (äußere); oder falten (innen).

Beim ersten Durchgang nist und eine Ganzzahl, die <''in Python 2 enthalten ist. Die Rekursion beginnt also mit der Umwandlung in eine Binärzeichenfolge.

Die nächste Ausführung hat r=''und so wird der Test {'1'}==set(n)ausgeführt, um nach einer fortlaufenden Zeichenfolge von 1s zu suchen (die RHS kann nicht so sein, {n}wie wir diesen Punkt später mit übergeben müssen, r=''und eine leere, nwenn dies ein Wörterbuch wäre, das nicht gleich ist {'1'}, eine Menge).

Wenn dies nicht erfüllt ist, werden die Kriterien für das innere Ende getestet (auch wenn dies nicht erforderlich ist): Wenn n in'1'es sich um True handelt, wenn nes sich um eine leere oder eine einzelne Zeichenfolge handelt 1, wird eine neue äußere Rekursion gestartet r, indem die dann gefaltete binäre Zeichenfolge in platziert wird nund ''in r. Das Literal 2wird zum Ergebnis dieses Funktionsaufrufs hinzugefügt, damit kein Durchfall zum nächsten Teil (rechts von einer Logik or) möglich ist, der später korrigiert wird.

Wenn dies kein wahrheitsgemäßer Wert ist (alle Ganzzahlen ungleich Null sind in Python wahrheitsgetreu), werden die Rekursionskriterien für den äußeren Schwanz getestet: n!=0Schließt den Fall mit einer Mitte aus 0und die beiden äußeren Zeichen werden getestet, zu denen sie 2durch die Zeichenfolgenverkettung nicht summieren '11'!=n[0]+n[-1]. wenn diese beide wahr halten die äußeren Bits werden aus ausrangierten nmit n[1:-1], und dann ein 1angehängt an , rwenn gibt es eine an der Außenseite sonst a 0ist, mit der Tatsache , dass '1'>'0'in Python mit max(n[0],n[-1]).

Schließlich wird die Addition 2bei jeder inneren Rekursion mit korrigiert %2.

Jonathan Allan
quelle
0

PHP, 113 Bytes

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

Beendet mit Fehler (Code 1), wenn das Argument nicht superfaltend ist, Code 0sonst. Laufen Sie mit -r.
Die Eingabe 0gibt true (Code 0) zurück.

Nervenzusammenbruch

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
Titus
quelle
0

PHP, 197 Bytes

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

Erweitert

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

Wahre Werte <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

Jörg Hülsermann
quelle