Urutan Diagonal Binary Square

20

Urutan biner-kuadrat-diagonal dikonstruksi sebagai berikut:

  1. Ambil urutan bilangan asli positif: 
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...

  2. Ubah setiap angka menjadi biner: 

    1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, ...

  3. Gabungkan mereka: 

    11011100101110111100010011010101111001101111011111000010001 ...

  4. Dimulai dengan n=1, buat kotak dengan panjang sisi bertambah nyang diisi kiri-ke-kanan, atas-ke-bawah dengan elemen dari urutan di atas:

    1
    1 0
1 1
    1 0 0 
1 0 1
1 1 0
    1 1 1 1
0 0 0 1
0 0 1 1 
0 1 0 1
    0 1 1 1 1
0 0 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 1
    ...

  5. Ambil diagonal (kiri atas ke kanan bawah) setiap kotak: 

    1, 11, 100, 1011, 00111, ...

  6. Konversikan ke desimal (mengabaikan angka nol di depan):

    1, 3, 4, 11, 7, ...

Tugas

Tulis program atau fungsi yang menampilkan urutan dengan salah satu cara berikut:

  • Kembalikan atau cetak urutan tanpa batas.
  • Input yang diberikan i, kembalikan, atau cetak ielemen pertama dari urutan.
  • Input yang diberikan i, kembalikan atau cetak ielemen ke-5 dari urutan (baik 0 atau 1 diindeks).

Silakan sebutkan dalam jawaban Anda format output mana yang Anda pilih.

Ini adalah kode-golf , jawaban terpendek dalam setiap bahasa menang.

Uji kasus

Berikut adalah 50 elemen pertama dari urutan:

1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845,17129,55518,134717,151988,998642,1478099,391518,7798320,8530050,21809025,61485963,66846232,54326455,221064493,256373253,547755170,4294967295,1875876391,2618012644,24710258456,6922045286,132952028155,217801183183,476428761596,51990767390,687373028085,1216614609441,7677215985062,15384530216172,22714614479340,15976997237789,0,256145539974868,532024704777005,601357273478135
code-golf sequence binary base-conversion binary-matrix Laikoni
sumber

Jawaban:

10

Sekam , 15 14 byte

zȯḋm←CtNCİ□ṁḋN

Cobalah online!

Mencetak hasilnya secara terus-menerus sebagai daftar tanpa batas.

Penjelasan

Aku bertanya-tanya apakah ada cara yang lebih baik untuk mendapatkan setiap n th elemen dari daftar daripada membelah daftar menjadi potongan panjang n dan mengambil kepala masing-masing potongan.

      tN          Get a list of all natural numbers except 1. (A)

             N    Get a list of all natural numbers.
           ṁḋ     Convert each to its binary representation and join them 
                  all into a single list.
         İ□       Get a list of squares of all natural numbers.
        C         Cut the list of bits into chunks of corresponding sizes. (B)

zȯ                Zip (A) and (B) together with the following function.
     C            Split the bit list (from B) into chunks of the given length
                  (from A).
   m←             Get the head of each chunk. This is the diagonal of the
                  bit list arranged as a square.
  ḋ               Interpret the resulting bits as binary digits and return
                  the result.

Agar lebih jelas, kami mengekstrak diagonal dari nxn persegi dengan memecah bentuk liniernya menjadi potongan dengan panjang n +1 dan mengambil elemen pertama dari setiap potongan:

[[1 , 0 , 1 , 0
  0],[1 , 0 , 1
  1 , 0],[1 , 0
  0 , 1 , 0],[1]]
Martin Ender
sumber
5

Python 2 , 137 85 byte

lambda n:int(''.join(bin(x+1)[2:]for x in range(n**3))[n*~-n*(2*n-1)/6:][:n*n:n+1],2)

Cobalah online!

Felipe Nardi Batista
sumber
4

Python 3 , 96 94 byte

lambda i:int(''.join(bin(x+1)[2:]for x in range(i**3))[sum(x*x for x in range(i))::i+1][:i],2)

Cobalah online!

ovs
sumber
4

05AB1E , 19 17 16 byte

°LbJsLn£θs>ô€нJC

°diganti dengan 3mtautan yang °cenderung menjadi sangat lambat.

Cobalah online! atau sebagai Test Suite

Penjelasan

°L                 # push the range [1 ... 10^input]
  bJ               # convert each to binary and join to string
    sLn            # push the range [1 ... input]^2
       £θ          # split the binary string into pieces of these sizes and take the last
         s>ô       # split this string into chunks of size (input+1)
            €н     # get the first digit in each chunk
              JC   # join to string and convert to int
Emigna
sumber
Tidak bisakah Anda ganti 3mdengan n?
Erik the Outgolfer
@EriktheOutgolfer: Ya saya bisa, terima kasih! Saya cukup yakin itu tidak berhasil, tapi itu mungkin karena kekusutan dalam solusi sebelumnya. Jumlah byte yang sama °tetapi lebih cepat: P
Emigna
Angka-angka dari 1 hingga input ^ 2 tidak cukup . 1 untuk memasukkan ^ 3 seperti pada jawaban python sepertinya sudah cukup.
Ovs
@ovs: Ah ya, itu sebabnya saya tidak menggunakannya sebelumnya. Saya hanya memeriksa beberapa item pertama kali ini. Saya akan kembali ke solusi sebelumnya (untungnya pada hitungan byte yang sama)
Emigna
3

Sekam , 15 byte

Ini mengambil pendekatan yang agak berbeda untuk jawaban Martin 

moḋz!NCNCṘNNṁḋN

Cobalah online!

Penjelasan:

              N   List of all natural numbers
            ṁḋ    Convert each to it's binary representation and flatten
         ṘNN      Repeat the list of natural numbers according the natural numbers:
                  [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5...]
        C         Cut the list of bits into lists of lengths corresponding to the above
      CN          Cut that list into lists of lengths corresponding to the natural numbers
moḋz!N            For each in the list, get the diagonals and convert from binary.
m                   For each list in the list
   z!N              Zip it with natural numbers, indexing.
 oḋ                 Convert to binary

Beraksi

ṁḋN : [1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1...]

ṘNN : [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8...]

C : [[1],[1,0],[1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1,1],[0,0,0,1]...]

CN : [[[1]],[[1,0],[1,1]],[[1,0,0],[1,0,1],[1,1,0]]...]

m z!N : [[1],[1,1],[1,0,0],[1,0,1,1],[0,0,1,1,1],[0,1,1,1,0,1]...]

oḋ : [1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845...]

H.Piz
sumber
3

Java (OpenJDK 8) , 215 212 206 202 197 byte

i->{String b="",t;int s=0,x=++i,j;for(;--x>0;s+=x*x);while(b.length()<s)b+=i.toString(++x,2);for(j=1,s=0;j<i;System.out.println(i.valueOf(t,2)),s+=j*j++)for(t="",x=s;x<s+j*j;x+=j+1)t+=b.charAt(x);}

Cobalah online!

Roberto Graham
sumber
i->{String b="",t;int s=0,x=++i,j;for(;--x>0;s+=x*x);while(b.length()<s)b+=i.toString(++x,2);for(j=1,s=0;j<i;System.out.println(i.valueOf(t,2)),s+=j*j++)for(t="",x=s;x<s+j*j;x+=j+1)t+=b.charAt(x);}( 197 byte )
Kevin Cruijssen
2

Python 2 , 91 byte

i=n=1;s=''
while 1:
 s+=bin(i)[2:];i+=1
 if s[n*n:]:print int(s[:n*n:n+1],2);s=s[n*n:];n+=1

Cobalah online!

mencetak urutan tanpa batas

ovs
sumber
2

Jelly , 16 byte

RBFṁ
R²SÇṫ²C$m‘Ḅ

Cobalah online!

Penjelasan

RBFṁ  Helper link. Input: integer k
R     Range, [1, 2, ..., k]
 B    Convert each to a list of its binary digits
  F   Flatten
   ṁ  Mold to length k

R²SÇṫ²C$m‘Ḅ  Main link. Input: integer n
R            Range, [1, 2, ..., n]
 ²           Square each
  S          Sum
   Ç         Call helper link on the sum of the first n squares
       $     Monadic chain
     ²         Square n
      C        Complement, 1-n^2
    ṫ        Tail, take the last n^2 elements
        m    Modular indexing, take each
         ‘   (n+1)th element
          Ḅ  Convert from list of binary digits to decimal
mil
sumber
1

Mathematica, 96 byte

Output yang iunsur th urutan (1-diindeks) 

Diagonal@Partition[TakeList[Flatten@IntegerDigits[Range[#^3],2],Range@#^2][[#]],#]~FromDigits~2&


Cobalah online!

J42161217
sumber
1

Perl 5 , 92 + 1 ( -p) = 93 byte

$s.=sprintf'%b',++$"for 1..$_**3;map{say oct"0b".(substr$s,0,$_*$_,'')=~s/.\K.{$_}//gr}1..$_

Cobalah online!

Xcali
sumber
1

Jelly , 18 byte

Pendekatan yang sama sekali berbeda dibandingkan dengan solusi Erik .

Ḷ²S‘ɓ*3B€Fṫ
Çm‘ḣµḄ

Cobalah online!

Bagaimana itu bekerja

Ḷ²S'ɓ * 3B € Fṫ - Tautan pembantu (monadik).

Ḷ - Kisaran yang diturunkan, menghasilkan [0, N).
 ² - Kotak vektor (masing-masing kotak).
  S - Sum.
   '- Increment, untuk memperhitungkan 1-pengindeksan Jelly.
     ɓ - Memulai rantai diad yang terpisah.
     * 3 - Input ke kekuatan 3.
       B € - Konversi masing-masing ke biner.
         F - Ratakan.
          ṫ - Buntut. Kembalikan x [y - 1:] (1-diindeks).

Çm'ḣµḄ - Tautan utama (monadik).

Ç - Tautan terakhir sebagai monad.
 m '- Input modular + 1. Dapatkan setiap elemen "input +1" dari daftar.
   ḣ - Kepala. Kembalikan elemen di atas dengan indeks lebih tinggi daripada input yang dipangkas.
    μḄ - Konversi dari biner ke integer.

Disimpan 1 byte berkat Jonathan Allan !

Tuan Xcoder
sumber
Simpan satu menggunakan rantai diad untuk menghapus ³:Ḷ²S‘ɓ*3B€Fṫ
Jonathan Allan
@ Jonathan Allan Tentu saja, terima kasih! Saya benar-benar harus belajar trik itu
Tn. Xcoder
0

Jelly , 22 byte

²Rµ²Ṭ€Ẏ0;œṗBẎ$³ịs³ŒDḢḄ

Cobalah online!

Erik the Outgolfer
sumber
0

Pyth ,  27  20 byte

i<%hQ>s.BS^Q3s^R2QQ2

Verifikasi beberapa kasus uji pertama.

Mendapat Aku th jangka urutan, 1 diindeks.

Bagaimana itu bekerja?

i<%hQ>s.BS^Q3s^R2QQ2   - Full program. Q represents the input.

         S^Q3          - Generate the (inclusive) range [1, Q ^ 3].
       .B              - Convert each to binary.
      s                - Join into a single string.
     >                 - Trim all the elements at indexes smaller than:
               ^R2Q      - The elements of the range [0, Q) squared.
              s          - And summed.
  %hQ                  - Get each Q + 1 element of the list above.
 <                     - Trim all the elements at indexes higher than:
                   Q   - The input.
i                   2  - Convert from binary to integer.
Tuan Xcoder
sumber