Matriks Hilbert-Curvify

19

Terinspirasi oleh pertanyaan ini

Cara lain untuk membuka gulungan gambar 2D menjadi string 1D adalah dengan menggunakan Hilbert Curve.

Ada banyak versi kurva ini, tergantung pada jumlah iterasi yang digunakan saat menghitungnya. Berikut ini contoh Curves Hilbert dari urutan pertama hingga urutan kelima.

masukkan deskripsi gambar di sini

Cara menghitung kurva ini adalah sebagai berikut. Pertama kita mendefinisikan urutan pertama Hilbert Curve sebagai yang ditunjukkan pada gambar (satu untuk n = 1), sehingga cocok dalam 1x1 kotak. Kami kemudian membuat empat salinan kurva ini, menempatkannya dalam bujur sangkar 4x4, sehingga semuanya menyajikan "cekungan" ke arah sisi kiri. Kami kemudian membalik dua kurva urutan paling kiri 1, sehingga bagian atas cekung menghadap ke atas, sedangkan bagian bawah menghadap ke bawah. Kami akhirnya menghubungkan sudut-sudut Kurva Hilbert yang berdekatan. Jika ingin mendapatkan Kurva orde (n +1), kita hanya perlu mengulangi proses dengan empat Kurva n-order. Kita dapat melihat visualisasi proses di sini (saya juga akan menambahkan gambar yang merinci prosesnya segera)

Tugas Anda dalam tantangan ini adalah membuka gulungan matriks bilangan bulat di sepanjang urutan terendah Hilbert Curve untuk matriks itu.

Demi kesederhanaan, kita akan memiliki kurva mulai dari sudut kiri atas matriks.

Anda dapat menerima input baik sebagai daftar daftar bilangan bulat, di mana setiap sub-daftar mewakili baris matriks.

Anda dapat mengasumsikan bahwa input akan berupa matriks kuadrat (n * n).

Sebagai contoh:

Memasukkan:

[[ 1, 2,]
 [ 3, 4 ]]

Keluaran:

[ 1, 2, 4, 3 ]

Karena kita menggunakan urutan pertama Hilbert Curve yang ditunjukkan pada gambar

Memasukkan:

[[ 1, 2, 3, 4,    ]
 [ 5, 6, 7, 8,    ]
 [ 9, 10, 11, 12, ]
 [ 13, 14, 15, 16 ]]

Keluaran:

[ 1, 5, 6, 2, 3, 4, 8, 7, 11, 12, 16, 15, 14, 10, 9, 13 ]

Menggunakan urutan kedua Hilbert Curve

Seperti biasa, celah standar tidak diizinkan.

Ini adalah kode-golf, jadi jawaban tersingkat dalam byte menang.

WizardOfMenlo
sumber
1
Terkait
ETHproduk
@StewieGriffin yakin, saya
siap
1
@StewieGriffin Saya telah menambahkan ringkasan singkat, saya akan melakukan pekerjaan yang lebih menyeluruh dalam satu jam berikutnya, setelah menyelesaikan pelajaran
WizardOfMenlo
Matriks kebutuhan untuk tidak hanya menjadi satu persegi, itu juga perlu n menjadi kekuatan 2.
mbomb007

Jawaban:

5

MATL , 86 85 byte

Solusi ini didasarkan pada entri File Exchange Jonas Lundgren yang menggunakan bilangan kompleks untuk menghasilkan kurva Hilbert. Bilangan kompleks ini kemudian dikonversi ke nilai indeks untuk mengambil elemen matriks yang berada di sepanjang kurva.

nZl2/1XLJQXH1J-XI0,1L:"XJJZj1j*XKKH-JI-JH+IK-,4$h2/]XJJ1L*XJJH+J1)-XHGHXjHYj3$)1$Xd1$

Cobalah online!

Penjelasan

%--- Define some numbers to be used throughout ---%
n                   % Retrieve the number of elements in the input matrix
Zl2/                % Compute the order of the curve (log2(numel(i))/2)
1XL                 % Store the order in the 1L clipboard
JQ XH               % Store 1 + j in H clipboard
1J- XI              % Store 1 - j in I clipboard
0                   % Place 0 onto the stack

%--- Compute the hilbert curve ---%
1L:"                % For k = 1:order
    XJ                   % Store the top of the stack (z) in J clipboard
    JZj                  % Compute the conjugate of z (stored in J)
    1j*                  % Multiply by j to get conj(z) * j
    XK                   % Store result in K clipboard
    KH- JI- JH+ IK- 4$h  % Horizontal concatenation of K-H, J-I, J+H, and I-K
    2/                   % Divide entire array by 2
]                   % End for loop
XJ                  % Store z in J clipboard

%----- Convert complex decimal values to complex integer indices ----%
J1L*                % Multiply z by the order
XJ                  % Store result in clipboard J
JH+                 % Add 1 + j to H
J1)-                % Subtract the first element of z
XH                  % Store integer complex numbers in H

%--- Retrieve the elements from the input along the curve ---%  
G HXj HYj 3$)       % Index into input using real/imag components input(real, imag)
                    % This will yield an numel(real) x numel(imag) matrix where 
            % the diagonal values are the values we want
1$Xd                % Extract the diagonals using diag with one input
1$                   % Display only the top element on the stack
Suever
sumber
@ DonMuesli Saya sedang mengerjakan cara yang lebih baik untuk menangani ini. Ini jelas jauh dari anggun! Terima kasih untuk petunjuknya. Diperbarui!
Suever
Saya belum melihat tantangan spesifik ini. Terkadang clipboard tidak dapat dihindari
Luis Mendo
5

APL (Dyalog Unicode) , 41 byte SBCS

Disimpan 30 byte (!) Dengan berkonsultasi dengan kebijaksanaan APL Orchard, terutama @ngn dan @ Sherlock9.

{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵}

Cobalah online!

Penjelasan sebagai berikut:

{0::⍵⋄∊∇¨⌽∘⊖¨@4,⌽@1⊢∘⍉\⌽↑∘⍵¨∘.,⍨2 ¯2÷⍨≢⍵}  Recursive function - takes input as an
                                           n*n square matrix
 0::⍵                                      Our base case - this is an error guard
                                           If there's any error, catch it and
                                          ⍝ return the function's input
                                      ≢⍵   Find the number of rows in the input
                                2 ¯2÷⍨     Divide the above by 2 and negative 2,
                                           resulting in a 2-element vector
                            ∘.,⍨           Outer product - take the above vector and
                                           apply concatenation (,) with each element
                                           against all elements in the vector. Since
                                           we have a 2-element vector, this results in
                                           a 2-by-2 matrix, e.g.
                                           [[(2,2),(22)],[(¯2,2),(¯22)]]
                        ↑∘⍵¨               For each element in the matrix, we apply
                                           "take" against our original input matrix.
                                           Take, given a negative number, will take
                                           elements from the end of a particular rank.
                                           With our argument above, this means that we end
                                           up with our original original input matrix
                                           split by quadrant into a 2-by-2 matrix.
                                           It is also worth noting that take expects
                                           an integer argument, so for matrices whose
                                           rowcount divided by two results in a decimal
                                           (i.e., 1-by-1 matrices), we throw an error
                                           which is caught by the guard above, returning
                                           the original input.
                                          Flip the above matrix about the vertical axis.
                   ⊢∘⍉\                    Apply a "monadic transpose scan". More details
                                           on how this works below, but for our purposes
                                           this applies transpose to each of the two 
                                           sub-matrices on the right half.
                ⌽@1                        Swap the two upper sub-matrices. Given our
                                           flip for the overall matrix above, this returns
                                           the two upper quadrants to their original
                                           positions.
               ,                           Ravel: flatten the 2-by-2 matrix into a
                                           4-element vector
         ⌽∘⊖¨@4                            Take the last element of the list (the lower
                                           right quadrant originally) and flip it
                                           along the vertical and horizontal axes. Given
                                           the transposition above, this has the final
                                           effect of transposition along the antidiagonal.
       ∇¨                                  For each element in the above vector, recurse.
                                          Recursively flatten the results into a single
                                           vector.

Lebih detail tentang " pemindaian transpose monadik ".

Dokumentasi Dyalog tentang penjaga kesalahan .

voidhawk
sumber
3

Mathcad, 302 byte

Program Mathcad di bawah ini didasarkan pada program @ Sherlock9 Python. Ini berbeda dengan melengkung matriks persegi panjang dengan mengabaikan bagian-bagian dari Kurva Hilbert yang terletak di luar batas matriks. Perhatikan bahwa karena Mathcad memiliki penanganan string yang relatif buruk, saya telah memetakan simbol Lindenmayer ke integer dalam fungsi Hilbert.

masukkan deskripsi gambar di sini

Mathcad bekerja melalui antarmuka 2D yang memungkinkan pengguna untuk menempatkan (dan secara bebas mencampur) ekspresi matematika, plot, teks, input dan output. Saya telah menyamakan satu byte ke operasi setara keyboard pengguna minimum untuk membuat simbol (misalnya, operator definisi (: =) dimasukkan dengan hanya mengetik:.

Stuart Bruff
sumber
3

Python 3, 327 289 275 271 239 234 byte

Ini adalah solusi yang saya modifikasi dari jawaban saya untuk pertanyaan kurva Hilbert lain di sini . Setiap kiat bermain golf dihargai.

Sunting: Mengubah cara gbertambah dan dikurangi. Sekarang menggunakan eval()dan str.translate. Tidak lagi menggunakan l=len(s).

def h(s):
 t=[s[0][0]];x=y=g=0;b="A"
 for j in range(len(bin(len(s)))-3):b=b.translate({65:"-BF+AFA+FB-",66:"+AF-BFB-FA+"})
 for c in b:g+=(c<"-")-(c=="-");a=c>"B";x,y=[[x,y],[[x+1-g%4,y],[x,y+g%4-2]][g%2]][a];t+=[s[x][y]]*a
 return t

Tidak Disatukan:

# the following function is implemented in the code with b=b.translate

def hilbert(it):
    s="A"
    n=""
    for i in range(it):
        for c in s:
            if c == "A":
                n += "-BF+AFA+FB-"
            elif c == "B":
                n += "+AF-BFB-FA+"
            else:
                n += c
        s=n;n=""
    return s

def matrix_to_hilbert(mat):
    length = len(mat)       # this returns the number of rows in the matrix
    if length < 2:
        return mat
    it = len(bin(length)) - 3
    hil = hilbert(it)
    output = [mat[0][0]]    # a list that starts with the first element of the matrix
    x = 0
    y = 0
    heading = 0
    for char in hil:        # navigating the Hilbert curve
        if char == "-": heading += -1
        elif char == "+": heading += 1
        elif char == "F":
            if heading % 4 == 3: y += 1
            elif heading % 4 == 2: x -= 1
            elif heading % 4 == 1: y -= 1
            else: x += 1
            output.append(mat[x][y])
    return output
Sherlock9
sumber
2

Wolfram - 233

Berdasarkan representasi sebagai sistem Lindenmayer :

f[m_]:=m[[Sequence@@Reverse[#+1]]]&/@DeleteDuplicates@AnglePath[Pi/2,List@@StringReplace[Last@SubstitutionSystem[{"A"->"-BF+AFA+FB-","B"->"+AF-BFB-FA+"},"A",Round@Sqrt@Length@m],{"A"|"B"->"","-"->{0,-Pi/2},"+"->{0,Pi/2},"F"->{1,0}}]]
desir
sumber
Bisakah Anda memposting beberapa tangkapan layar agar berfungsi, untuk pengguna yang tidak memiliki Mathematica?
WizardOfMenlo
2
Apakah "Wolfram" berbeda dari Mathematica? Jika tidak, itu harus disebut Mathematica.
mbomb007
@WizardOfMenlo Ini dia bekerja online
swish
@ harap saya pikir Anda perlu mengubah izin aplikasi Web, tampaknya diblokir
WizardOfMenlo
@ mbomb007 Wolfram adalah nama bahasa , Mathematica seperti IDE.
desir
1

Ruby, 224 221 216 byte

Jawaban ini didasarkan pada jawaban Python saya .

->s{t=[s[0][0]];x=y=g=0;b=?A;(s.size.bit_length-1).times{b=b.split("").map{|c|c==?A?"-BF+AFA+FB-":c==?B?"+AF-BFB-FA+":c}.join("")};b.each_char{|c|g+=c==?-?-1:c==?+?1:0;(g%2>0?y+=g%4-2:x+=1-g%4;t<<s[x][y])if c==?F};t}

Tidak melakukan pelanggaran:

def hilbert(mat)
  result = mat[0][0]
  x = 0
  y = 0
  heading = 0
  b = "A"
  (mat.size.bit_length-1).times do each |j| # Hilbert curve using a Lindenmayer system
    a = b.split("").map do |char|
      if char == "A"
        "-BF+AFA+FB-"
      else if char == "B"
        "+AF-BFB-FA+"
      else
        char
      end
    end
    b = a.join("")
  end
  b.each_char do |char| # navigating the matrix
    if char == "-"
      heading += -1
    else if char == "+"
      heading += 1
    else if char == "F"
      if heading % 2 == 0
        y += heading % 4 - 2
      else
        x += 1 - heading % 4
      end
      result << s[x][y]
    end
  return result
  end
Sherlock9
sumber
1

CJam, 60

Lq~:A,2mL{:B1f^0B1B2B3f^]:+}*1+{AT=U=\2md'U^_~)@2*-':@+~;}%p

Cobalah online

Penjelasan:

Saya sedang membangun fraktal sebagai serangkaian arah gerakan: 0 = kanan, 1 = bawah, 2 = kiri, 3 = atas.

L          push an empty array (level 0 fractal)
q~:A       read the input, evaluate and store in A
,2mL       get the length (number of rows) and calculate the logarithm in base 2
            (to get the desired level)
{…}*       repeat <level> times
  :B       store the previous-level fractal in B
  1f^      XOR it with 1 (top-left part)
  0        (move right)
  B        copy the fractal (top right part)
  1        (move down)
  B        copy the fractal (bottom right part)
  2        (move left)
  B3f^     copy the fractal and XOR it with 3 (bottom left part)
  ]:+      put everything in an array and concatenate the parts
1+         add a dummy move (needed for the last step)
{…}%       apply to each direction in the array
  AT=U=    push A[T][U] (T and U are initially 0)
  \2md     bring the direction to the top and get the quotient and remainder mod 2
  'U^      XOR the 'U' character with the remainder,
            to get the variable we want to modify
  _~)      make a copy of it, then evaluate it and increment
  @2*-     bring the quotient to the top, multiply by 2 and subtract
  ':@+     concatenate ':' with the variable name
  ~;       evaluate (this updates the variable) and pop the result
p          pretty-print the resulting array
aditsu
sumber