Nomor Super Lipat

10

Kami telah mendefinisikan nomor lipat di sini .

Tapi sekarang kita akan mendefinisikan Nomor Super Lipat. Angka Super Lipat adalah angka yang jika dilipat cukup kali pada akhirnya akan mencapai satu kurang dari kekuatan dua. Metode melipat sedikit berbeda dari pada pertanyaan nomor lipat.

Algoritma lipat berjalan sebagai berikut:

  • Ambil representasi biner

    misalnya 5882

    1011011111010
    
  • Mencurahkannya menjadi tiga partisi. Paruh pertama, setengah terakhir dan digit tengah (jika memiliki angka ganjil)

    101101 1 111010
    
  • Jika angka tengah nol, angka ini tidak dapat dilipat

  • Membalikkan babak kedua dan melapiskan pada babak pertama

    010111
    101101
    
  • Tambahkan digit di tempatnya

    111212
    
  • Jika ada 2s dalam hasil angka tidak dapat dilipat kalau tidak angka baru adalah hasil dari algoritma lipat.

Angka adalah nomor Super Lipat jika dapat dilipat ke string yang terus-menerus. (Semua nomor Lipat juga Nomor Super Lipat)

Tugas Anda adalah menulis kode yang menggunakan angka dan menampilkan nilai yang benar jika nomor tersebut adalah nomor Super Lipat dan sebaliknya palsu. Anda akan dinilai berdasarkan ukuran program Anda.

Contohnya

5200

Konversi ke biner:

1010001010000

Dibagi dua:

101000 1 010000

Yang di tengah adalah satu sehingga kami melanjutkan Menumpangkan bagiannya:

000010
101000

Menambahkannya:

101010

Tidak ada dua jadi kami melanjutkan Berpisah menjadi dua:

101 010

Melipat:

010
101

111

Hasilnya adalah 111(7 dalam desimal) jadi ini adalah Nomor Super Lipat.

Uji Kasus

100 Nomor Super Lipat pertama adalah:

[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 Hunter
sumber
2
Kecuali saya salah, bagaimana 3menyelinap ke dalam kasus uji lagi? Saya tidak bisa melihat bagaimana bisa dilipat, karena terbelah 1 1, segera memberi a 2. Atau apakah Anda mengatakan bahwa melipatnya nol kali juga dihitung?
Geobits
@geobits 3 seharusnya ada di sana. Saya memeriksa kali ini;). Tiga adalah 11 sehingga hanya satu yang ada di file nol
Ad Hoc Garf Hunter
Saya pikir mungkin ada baiknya meletakkan catatan tepat di dekat bagian atas, tepat setelah Anda menautkan ke pertanyaan nomor lipat lainnya yang menunjukkan bahwa masing-masing lipatan dalam pertanyaan ini akan menggunakan metode yang berbeda.
Jonathan Allan

Jawaban:

9

Inilah pukulan pertama saya di kode golf:

Python 3, 167 byte

167 byte jika tab atau spasi tunggal digunakan untuk indentasi

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

Sunting: Terima kasih atas bantuan semua orang di bawah ini, kode di atas telah dikurangi dari ukuran asli 232 byte!

Kapocsi
sumber
1
Selamat datang di PPCG! Anda dapat menyimpan banyak byte dengan menghapus spasi setelah :s, dan kembali 0dan 1bukannya Truedan False.
Steven H.
Steven terima kasih. Juga, saya tidak 100% yakin saya menghitung panjang byte dengan benar.
Kapocsi
1
Saya melihat 232 byte. Beri saya waktu sebentar dan saya bisa mencoba golf sedikit lebih jauh.
Steven H.
Saya menggunakan ini untuk mengukur: bytesizematters.com
Kapocsi
1
@Kapocsi, bytesizematters.com menghitung baris baru salah. Bandingkan dengan mothereff.in , 5 digit dan 5 baris baru harus 10 byte, bukan 14 yang saya dapatkan bytesize ... 232.
Linus
5

Java 7, 202 byte

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

Butuh sedikit usaha untuk membuat fungsi lipat yang lama dapat didaur ulang, tetapi ini dia. Jujur saja, itu dosa. Saya harus melihat-lihat di pagi hari untuk melihat apakah saya bisa bermain golf lebih jauh, karena saya hampir tidak tahan melihatnya sekarang.

Dengan jeda baris:

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);
}
Geobit
sumber
3

CJam , 47 44 byte

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

Cobalah online! atau menghasilkan daftar nomor lipat super hingga nomor yang diberikan.
Upaya bermain golf dapat dilihat di sini .


Kode terurai ke fase berikut:

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: Versi ini kurang lebih membutuhkan pendekatan Hukum De Morgan ke versi sebelumnya.

* Masalah dengan menjalankan singleton adalah kita terjebak dengan string kosong setelah slice.

** Jika angka biner super lipat, gambar cerminnya (dengan 0s jika perlu) adalah. Ini menghemat satu byte dari mengambil bagian kanan.

Linus
sumber
2

JavaScript, 149 byte

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

Menentukan fungsi rekursif.

Penjelasan:

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
sumber
m=l>>1, /2/.test(n), n.slice(l-m)(Atau mengiris string terbalik). Saya pikir jika Anda mengganti kasus kegagalan dan kesuksesan maka Anda dapat menggunakannya /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

Diformat dan dikomentari

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
sumber
2

Perl, 71 70 byte

Termasuk +1 untuk -p

Berikan nomor pada STDIN

superfolding.pl:

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

Python 2, 151 byte

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

Fungsi ganda rekursif yang mengambil integer n,, dan mengembalikan 0atau 1.

Variabel rdipertahankan untuk memungkinkan hasil pelipatan dan untuk mengetahui apakah kita saat ini: memiliki integer (pertama saja); punya string biner baru untuk mencoba melipat (luar); atau lipat (bagian dalam).

Pada pass pertama nadalah dan integer, yang ada <''di Python 2 sehingga rekursi dimulai dengan casting ke string biner.

Eksekusi berikutnya memiliki r=''dan pengujian {'1'}==set(n)dijalankan untuk memeriksa string 1s berkelanjutan (RHS tidak dapat {n}karena kita mungkin perlu melewati titik ini nanti dengan r=''dan kosong nketika itu akan menjadi kamus yang tidak sama dengan {'1'}, satu set).

Jika ini tidak dipenuhi, kriteria ekor dalam diuji (bahkan jika tidak perlu): jika n in'1'akan mengevaluasi ke True ketika nstring kosong atau tunggal 1, dimana rekursi luar baru dimulai dengan menempatkan r, kemudian dilipat, string biner ke dalam ndan ''menjadi r. Literal 2ditambahkan ke hasil pemanggilan fungsi ini untuk memungkinkan tidak jatuh ke bagian berikutnya (di sebelah kanan logis or) yang diperbaiki kemudian.

Jika itu bukan nilai kebenaran (semua bilangan bulat bukan nol adalah benar dalam Python) kriteria rekursi ekor luar diuji: n!=0tidak termasuk case dengan tengah 0dan dua karakter luar diuji, mereka tidak dijumlahkan 2oleh penggabungan string '11'!=n[0]+n[-1]; jika keduanya benar, bit luar dibuang dari ndengan n[1:-1], dan kemudian 1ditambahkan ke rjika ada satu di luar sebaliknya a 0, menggunakan fakta bahwa '1'>'0'dengan Python max(n[0],n[-1]).

Akhirnya penambahan 2pada setiap rekursi dalam dikoreksi dengan %2.

Jonathan Allan
sumber
0

PHP, 113 byte

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

keluar dengan kesalahan (kode 1) jika argumen tidak super-lipat, kode 0lain. Jalankan dengan -r.
Input 0akan mengembalikan true (kode 0).

kerusakan

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

Diperluas

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

Nilai sebenarnya <10000

1, 2, 3, 6, 7, 8, 10, 12, 15, 20, 22, 28, 31, 34, 38, 42, 48, 52, 56, 63, 74, 78, 90, 90, 104, 108, 120, 127, 128, 130, 132, 142, 150, 160, 170, 178, 192, 204, 232, 240, 255, 272, 274, 276, 286, 310, 336, 346, 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, 1486, 1440, 1458, 1506, 1572, 1596, 1644, 1716, 1764, 1824, 1848, 1896, 1968, 2016, 2047, 2050, 2054, 2058, 2064, 2072, 2110, 2142, 2176, 2180, 2184, 2222, 2254, 2306, 2320, 2358, 2390, 2432, 2470, 2502, 2562, 2576, 2618, 2650, 2688, 2730, 2762, 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, 9068, 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, 8386, 8606, 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, 8386, 8606, 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
sumber