Kode Sierpinskified

47

Tulis blok teks persegi panjang yang bila disusun menjadi karpet Sierpinski , menggunakan blok ruang berukuran sama untuk bagian yang kosong, buat program yang menampilkan jumlah iterasi karpet.

Misalnya, jika blok teks Anda

TXT
BLK

kemudian jalankan program

TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

harus dikeluarkan 1karena bentuk program mewakili iterasi pertama karpet Sierpinski.

Begitu pula berlari

TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXT   TXT         TXT   TXT
BLK   BLK         BLK   BLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK

harus menampilkan 2 karena ini adalah bentuk iterasi karpet Sierpinski kedua.

Menjalankan blok teks apa adanya

TXT
BLK

harus dikeluarkan 0karena dapat dianggap iterasi nol.

Ini harus bekerja untuk semua iterasi lebih lanjut. (Setidaknya secara teoritis, anggap komputer memiliki memori dan semuanya.)

Detail

  • Program mungkin tidak membaca atau mengakses informasi tentang kode sumbernya. Perlakukan ini seperti tantangan quine yang ketat.
  • Output menuju ke stdout atau alternatif serupa. Hanya menampilkan nomor dan baris tambahan opsional. Tidak ada input.
  • Blok teks dapat berisi karakter apa pun yang tidak dianggap sebagai terminator garis . Blok teks dapat berisi spasi.
  • "Ruang kosong" di karpet harus seluruhnya terdiri dari karakter ruang .
  • Anda dapat mengasumsikan bahwa semua program memiliki baris tambahan.

Anda dapat menggunakan potongan tumpukan ini untuk menghasilkan karpet untuk blok teks yang diberikan di setiap iterasi:

<style>#o,#i{font-family:monospace;}</style><script>function c(e){e=e.split("\n");for(var n=new Array(3*e.length),t=0;t<n.length;t++){var l=t%e.length;n[t]=e[l]+(t>=e.length&&t<2*e.length?e[l].replace(/./g," "):e[l])+e[l]}return n.join("\n")}function f(){for(i=document.getElementById("i").value,n=parseInt(document.getElementById("n").value);n>0;)i=c(i),n--;document.getElementById("o").value=i}</script><textarea id='i'placeholder='code block...'rows='8'cols='32'></textarea><br>Iterations <input id='n'type='text' value='1'><br><br><button type='button'onclick='f()'>Generate</button><br><br><textarea id='o'placeholder='output...'rows='8'cols='32'style='background-color:#eee'readonly></textarea>

Mencetak gol

Kiriman yang blok teks awalnya terkecil menurut area (lebar kali tinggi) adalah pemenangnya. The TXT\nBLKcontoh adalah 3 oleh 2 untuk skor 6. (Pada dasarnya menang kode terpendek, maka tag kode-golf.)

Tiebreaker pergi ke kiriman yang menggunakan karakter berbeda paling sedikit dalam blok teks mereka. Jika masih terikat, jawab diposting kemenangan pertama.

Hobi Calvin
sumber

Jawaban:

23

CJam, 9 byte

Saya pikir ini bisa diperbaiki, tetapi untuk sekarang, mari kita lanjutkan dengan itu ...

];U):U8mL

Cara kerjanya :

];             "Wrap everything on stack in an array and discard it";
               "Before this point, the only thing on array can be the log 8 result of";
               "last updated value of U, or nothing, if its the first code";
  U):U         "Increment by 1 and update the value of U (which is pre initialized to 0)";
      8mL      "Take log base 8 of U. This is the property of Sierpinski carpet that";
               "the occurrence of the code is 8 to the power iteration count, indexed 0";

Cobalah online di sini

Pengoptimal
sumber
35

piet - 32 * 6 = 192

masukkan deskripsi gambar di sini

Saya mengisi ruang kosong dengan pola checker. Saya pikir itu membuat Sierpinski sedikit trippier.

Inilah iterasi kedua: masukkan deskripsi gambar di sini

asli: 32 * 7

masukkan deskripsi gambar di sini

captncraig
sumber
19

> <> , 11 * 2 = 22

";n"00pbi1v
+$3*:@3-0.>

Di sini kita mengambil pendekatan yang berbeda dengan menggunakan fungsionalitas jump / teleport>>.

Program ini hanya mengeksekusi blok di baris atas, menjalankan blok 1/2, lalu blok 3/4, blok 9/10, blok 27/28, dll (naik dalam kekuatan 3). Karena baris atas memiliki 3^nblok, hanya nblok yang dieksekusi sebelum program kembali ke awal, menampilkan bagian atas tumpukan dan berhenti (karena ninstruksi ditempatkan melalui p).

Program mengeksploitasi aturan "Tidak ada input.", Karena iperintah mendorong -1 ke stack jika EOF terpenuhi. Jadi untuk menguji ini, Anda harus mem-pipe file kosong.


Pengajuan sebelumnya, 7 * 4 = 28

l"v"10p
v>:1=?v
3  ;n{<
<^}+1{,

Baris pertama secara terus menerus mendorong panjang tumpukan untuk setiap blok, dan mengubah "kutipan pertama menjadi panah bawah vmenggunakan pperintah put. Pada saat baris pertama selesai, tumpukan tampak seperti

[0, 1, 2, .., 3^n]

(Perhatikan bahwa inisial ldigunakan dua kali.)

Tiga baris terakhir lalu hitung berapa kali kita perlu membaginya dengan 3 sebelum kita menekan 1 (karena> <> tidak memiliki fungsi log). Nol bawah digunakan untuk melacak hitungan.

Sp3000
sumber
13

Perl, 26

$_+=.91/++$n;
die int."\n";

Ini menggunakan seri harmonik untuk mendekati logaritma basis 3. Saya pikir itu berhasil, tetapi saya hanya mencobanya untuk jumlah kecil. Terima kasih kepada sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssrrrrrrrrrrrrrrrrrrrrrrrrrrrr untuk gagasan menggunakan die.

Versi lama (34):

$n--or$n=3**$s++;
print$s-1if!$o++;
grc
sumber
Itu sangat rapi!
ossifrage pelit
10

Perl, 30 (15 × 2)

Pertama-tama, saya akan mengklaim bahwa 10 iterasi adalah batas yang masuk akal, bukan 2 32 . Setelah 10 iterasi, sebuah program yang terdiri dari N byte akan diperluas ke ( N × 3 20 ) byte (plus jeda baris), yang lebih dari 3 gigabita bahkan untuk N = 1. Arsitektur 32-bit benar-benar tidak dapat menangani 11 iterasi. (Dan jelas tidak ada cukup partikel di alam semesta selama 2 32 iterasi).

Jadi, inilah solusi saya:

$n++; $_=log$n;
print int;exit;

Ini bekerja dengan menambah variabel $npada baris pertama dan menghitung logaritma pada setiap langkah. Baris kedua mencetak bagian integer dari logaritma ini dan berhenti.

Logaritma sederhana ke basis e (2,718 ..) cukup dekat untuk memberikan hasil yang benar untuk 10 iterasi pertama.

lubang keras melengking
sumber
2
Menurut OP, itu secara teoritis harus bekerja untuk semua iterasi.
Nathan Merrill
2
@NathanMerrill Yah, oke. Tetapi untuk memenuhi spesifikasi aslinya, ia juga harus bekerja di alam semesta alternatif. Pertanyaan telah diedit sejak saat itu.
ossifrage pelit
Saya mengubah pertanyaan karena poin bagus yang dibuat di sini. Saya setuju bahwa menggunakan log alami adalah bukan wilayah abu-abu, tapi jujur aku tidak terlalu khawatir karena ini tidak menang.
Calvin Hobi
Sebagian besar kiriman ini tetap memegang kendali hanya di baris atas 3 ^ nx 1 ubin. Jika Anda hanya menghasilkan segmen karpet itu, Anda dapat mengukur sedikit lebih jauh. Hampir pasti ke tempat kesalahan pembulatan akan menghancurkan Anda.
captncraig
1
Seperti yang sudah saya sebutkan, pertanyaan awal meminta kode yang dapat menskala ke sejumlah iterasi "masuk akal" (hingga 2 ^ 32) . Jika Anda menghitungnya, Anda akan menemukan bahwa bahkan satu byte tunggal akan meluas hingga lebih dari 10 ^ 4098440370 byte setelah banyak iterasi. Saya mengusulkan jawaban yang saya pikir sedikit lebih masuk akal, tetapi sejak itu kata "masuk akal" telah hilang dari pertanyaan: - /. Dengar, aku sudah selesai di sini. Turunkan jawaban ini jika Anda tidak menyukainya.
ossifrage pelit
9

Golfscript, 9 * 2 = 18

0+       
,3base,(}

(Perhatikan bahwa baris pertama memiliki spasi tambahan untuk membuatnya persegi panjang)

Saya tidak dapat menemukan fungsi log untuk Golfscript, jadi baseharus saya lakukan.

Golfscript dimulai dengan string kosong, jadi 0+hanya menambah panjang string sebesar 1 (dengan koersi). Pada saat baris pertama selesai, tumpukan akan memiliki string panjang 3^n, yang kita ambil basis log 3 sebelum kita super komentar. nkemudian dicetak secara otomatis.

Sp3000
sumber
Anda bisa menyimpan 2 karakter dengan menggunakan bilangan bulat bukan string dan karenanya menyimpannya ,di baris kedua. Baris pertama: 0or); baris kedua 3base,(}. Target jelas lainnya adalah (pada baris kedua. Ini rumit, tetapi juga dapat dihapus dengan mengganti baris pertama dengan 1+~abs(untuk persegi panjang 7 * 2.
Peter Taylor
8

C, 12x8 = 96

Terinspirasi oleh @ciamej, saya telah menguranginya. Menggunakan membagi itu dengan 3 trik, ditambah kesadaran bahwa karpet secara efektif mengubah if menjadi loop sementara.

Kode diuji pada gcc / Ubuntu untuk iterasi hingga 3.

#ifndef A //
#define A //
x;main(a){//
a++;/*    */
if(a/=3)x++;
printf(   //
"%d",x);} //
#endif    //

Solusi Sebelumnya: C, 11x12

Bukan pemenang ukuran, tapi hei, ini C.

Ia menemukan log2 dari blockcount dengan bitshifting, kemudian menggunakan beberapa angka ajaib dan pemotongan int untuk memperkirakan log3. Matematika harus bekerja hingga 26 iterasi (angka 42 bit).

#ifndef A//
#define A//
int n=0;//_
int main//_
(v,c){//___
n+=1;/*..*/
while(n//__
>>=1)v++;//
n=.3+.62*v;
printf(//__
"%d",n);}//
#endif//__
ASHelly
sumber
Hai, saya telah memposting versi singkat dari solusi Anda.
ciamej
Trik yang bagus dengan itu jika! ;)
ciamej
6

CJam, 9 byte

Gagasan menggunakan ]berasal dari Pengoptimal, tetapi menggunakan metode yang sangat berbeda untuk menghitung.

X~]:X,8mL

Cobalah online

Bagaimana itu bekerja:

X~          "push X and dump its contents.  On the zeroth iteration, X is a single number, but later is it an array.";
  ]         "wrap everything into an array.  The stack would contain the contents of X plus the result of the previous instance of the code";
   :X       "store this array back into X.  X is now 1 element longer";
     ,      "take the length of X";
      8mL   "do a base-8 logarithm of it";

Dua solusi 9 byte lainnya

]X+:X,8mL

],X+:X8mL
PhiNotPi
sumber
Ini benar-benar mengikat Pengoptimal, bahkan dengan tiebreak. : P Tiebreakerbreaker: posting sebelumnya menang.
Calvin Hobbies
Saya pikir itu adalah solusi yang baik. Saya belum bisa mengalahkan 9 karakter.
PhiNotPi
Saya pikir pendekatan umum hanya sama (dan yang merupakan satu-satunya pendekatan yang masuk akal) - Memiliki variabel, naikkan dengan 1 entah bagaimana.
Pengoptimal
4

Python 2, 15 * 3 = 45

m=n=0;E=exit  ;
m+=1;n+=m>3**n;
print n;E()   ;

Implementasi lain dari ide count-first-row-then-log-three-and-exit. Mungkin masih bisa bermain golf sedikit lebih adil.

Sp3000
sumber
2

bc, 2 * 16 + 1 = 33

+1 ekstra dalam skor adalah karena -lopsi bc diperlukan:

a+=1;          
l(a)/l(3);halt;
Trauma Digital
sumber
2

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

Ini terinspirasi oleh jawaban Sp3000 , dan khususnya oleh keinginan untuk mengoptimalkan baris kedua yang panjang. 3base,adalah sesingkat logaritma basis-3 akan masuk GS, dan super-komentar }jelas optimal.

Apa yang diperlukan untuk baris pertama adalah memetakan string kosong ''dari stdin awal ke 0, dan kemudian memetakan setiap integer non-negatif ke penggantinya. Dengan cara ini kita mengakhiri baris pertama dengan 3^n - 1di stack, dan 3base,tidak memerlukan pengurangan.

Peter Taylor
sumber
2

C, 13x8

#ifndef A//__
#define A//__
x;a;main(){//
a++;;;;;;;;;;
while(a/=3)//
x++;printf(//
"%d",x);}//__
#endif//_____
ciamej
sumber
1

Perl, 76

Saya tahu mungkin tidak ada gunanya memposting ini karena sudah dipukuli sepenuhnya, tapi ini solusi saya saat ini.

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}
PhiNotPi
sumber
@Alex Itu sepertinya tidak berhasil, bahkan pada iterasi pertama.
PhiNotPi
Ya, itu berfungsi sebagaimana mestinya. Sudahkah Anda menguji metode Anda?
PhiNotPi
Saya bekerja di ideone: ideone.com/othumP .
PhiNotPi
Gotcha. Saya melewatkan detail penting yang membuatnya tidak bekerja sebelumnya. Anda benar, saran saya salah.
Alex A.
1

> <> (Ikan), 12 * 3 = 36

Solusi yang lebih mudah> <>:

'v'00p0l1+  
>  :2-?v$1+v
^$+1$,3< ;n<

Kami pertama kali menjalankan baris atas dari blok teratas. 'v'00pmenempatkan vpada posisi paling pertama dari seluruh program mengarahkan pointer program ke bawah ketika kembali ke awal setelah mencapai akhir baris. Sebelum itu setiap blok mendorong 0 dan panjang tumpukan +1 ke atasnya. (tumpukan akan 0 2 0 4 0 6 ...)

Pada paruh pertama dari kedua dan ketiga kita menghitung berapa kali kita dapat membagi elemen tumpukan atas sebelum kita mendapatkan 2 (kita menyimpan ini di elemen kedua ke atas).

Pada akhirnya kami menampilkan elemen kedua ke atas tumpukan.

randomra
sumber
1

Lua, 3 * 17 = 51

Strategi yang sama seperti kebanyakan orang:

x=(x or 0)+1;    
y=math.log(x,3)  
print(y)os.exit()
Omar
sumber
1

PHP, 22 × 2 = 44 27 × 2 = 54

<?php $i++          ?>
<?php die(log($i,3))?>

Just another take pada count-log3-out. Tidak terlalu kecil, tapi golf pertama saya;)

Lars Ebert
sumber
Di PCG.SE seperti di tempat lain, silakan periksa dokumentasi sebelum memposting :).
Blackhole
@ Lubang Hitam Tangkapan yang bagus! Terima kasih
Lars Ebert