Acak Seni ASCII Hari # 5: Diamond Tilings

21

Hancurkan Waktu!

Ini adalah angsuran # 5 dari seri Random Golf of the Day dan ASCII Art of the Day dari Pengoptimal . Kiriman Anda dalam tantangan ini akan diperhitungkan di kedua papan peringkat (yang dapat Anda temukan di kiriman yang tertaut). Tentu saja, Anda dapat memperlakukan ini seperti tantangan golf kode lainnya, dan menjawabnya tanpa khawatir tentang kedua seri sama sekali.

Lubang 5: Diamond Tilings

Hexagon biasa selalu dapat dilapisi dengan berlian seperti:

Kami akan menggunakan representasi seni ASCII dari tilings ini. Untuk segi enam sisi-panjang 2, ada 20 sudut seperti:

   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \_\/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/   \_\/_/   \_\/_/ 
   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /_/_/\   /\_\_\   /_/\_\   /_/_/\   /_/\_\   /_/\_\   /_/_/\   /_/_/\   /_/_/\   /_/_/\ 
 /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
 \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
  \/_/_/   \_\_\/   \_\/_/   \_\/_/   \_\_\/   \_\_\/   \_\/_/   \_\_\/   \_\_\/   \_\_\/ 

Dengan panjang sisi yang sama N, Anda harus membuat ubin seperti segi enam dengan panjang sisi Nsecara acak. Distribusi yang tepat tidak masalah, tetapi setiap ubin harus dikembalikan dengan probabilitas tidak nol.

Sebab N ≤ 4, kiriman Anda harus menghasilkan ubin dalam waktu 1 menit setidaknya 80% dari waktu dan setidaknya 80% dari ubin harus berpotensi dihasilkan dalam 1 menit. Sebagian besar pendekatan tidak perlu khawatir tentang aturan ini (ini sangat lunak) - ini hanya untuk mengesampingkan algoritma berbasis penolakan yang sangat naif yang menghasilkan string arbitrer sampai satu terjadi ubin.

Anda mungkin ingin tahu bahwa jumlah total kemiringan yang mungkin untuk N yang diberikan dapat ditemukan di OEIS A008793 .

Anda dapat menulis program atau fungsi lengkap dan mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan menghasilkan output melalui STDOUT (atau alternatif terdekat), mengembalikan nilai fungsi atau parameter fungsi (keluar).

Anda tidak boleh mengeluarkan lebih banyak spasi utama dari yang diperlukan untuk menyelaraskan segi enam (yaitu sudut kiri segi enam seharusnya tidak memiliki spasi di depannya). Setiap baris dapat berisi hingga Nspasi tambahan (tidak harus konsisten, sehingga Anda bisa misalnya memiliki keluaran persegi panjang, mencetak kotak pembatas hexagon).

Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang. Dan tentu saja, pengiriman terpendek per pengguna juga akan masuk ke papan peringkat keseluruhan seri.

Papan peringkat

Pos pertama dari setiap seri menghasilkan papan peringkat.

Untuk memastikan jawaban Anda muncul, mulailah setiap jawaban dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda bisa menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(Bahasa saat ini tidak ditampilkan, tetapi cuplikan memang membutuhkan dan menguraikannya, dan saya dapat menambahkan leaderboard berdasarkan bahasa di masa mendatang.)

Martin Ender
sumber
3
Apakah hanya saya yang terus melihat contoh gambar dalam 3D?
LegionMammal978
3
@ LegionMammal978 Tidak, itu sangat normal. ;) (Dan mungkin juga cara yang baik untuk mendekati tantangan.)
Martin Ender
For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time.terlalu mudah: 80% dari waktu ubin yang sama, dasar, kalau tidak saya menemukan ubin lain di waktu apa pun yang saya inginkan
edc65
@ edc65 Poin bagus, izinkan saya ulangi.
Martin Ender

Jawaban:

10

CJam, 105 byte

ri:A" __"e*A,2f*:B,[W1]{J+B:):B,{N1$S*"\/"J%A2*4$-:D*
0{;B{_1&!2mr+J*m1e>D(2*e<}%__:)&}g:B{'_t}/+@J+}*}fJ;

Baris baru ditambahkan untuk menghindari pengguliran. Cobalah online

Penjelasan:

Solusi ini memulai setiap baris sebagai zigzag, kemudian menempatkan N menggarisbawahi di atasnya, berdasarkan posisi mereka pada baris sebelumnya dan beberapa aturan. Saya mendapatkan ini dari serangkaian pengamatan sambil melihat output sebagai matriks 2D karakter sederhana:

  • setiap baris memiliki garis bawah N persis
  • garis bawah dapat diganti dengan / atau \ untuk membuat pola zigzag berulang sempurna ( /\di bagian atas, \/di bagian bawah)
  • garis bawah tidak dapat menyentuh sisi, dan tidak dapat berdekatan dengan garis bawah lainnya
  • saat menuju ke baris berikutnya, posisi setiap garis bawah berubah sebesar -1, 0 atau 1
  • lebih dari itu, /_/hanya bisa berubah -1 atau 0, dan \_\hanya bisa berubah 0 atau 1
  • untuk posisi garis bawah awal kita bisa menggunakan "_ "pola atau " _"pola, keduanya baik-baik saja
  • aturan di atas cukup untuk mendapatkan semua tilings

Jadi saya memutuskan untuk mengimplementasikannya dengan mempertahankan posisi garis bawah sebelumnya, memodifikasinya dengan faktor acak (2 pilihan untuk setiap garis bawah) dan mengulangi sampai aturan terpenuhi. Dalam proses pengoptimalan, saya beralih ke posisi garis bawah relatif ke sisi kiri segi enam (tidak termasuk spasi).

ri:A" __"e*       read the input (A) and generate the top line
A,2f*:B           make an array [0 2 4 ... 2A-2] and store in B
                  these are the initial positions for the underscores
,                 B's length = A, used as the initial number of leading spaces
                  let's call it C
[W1]{…}fJ         for J in [-1 1] (top half, bottom half)
  J+              add J to C
  B:):B           increment the underscore positions (adjustment before each half)
  ,{…}*           repeat A times
    N1$S*         add a newline and C spaces
    "\/"J%        take "\/" and reverse it if J=-1 (zigzag pattern)
    A2*4$-:D*     calculate D=A*2-C and repeat the pattern
    0             dummy value (for the next loop)
    {…}g          do-while
      ;B          pop last value and push B
      {…}%        apply block to each item (say x)
        _1&!      duplicate x and calculate !(x&1) (for /_/ vs \_\)
        2mr+      randomly add 0 or 1
        J*m       multiply by J and subtract from x
        1e>       limit the minimum value to 1
        D(2*e<    and the maximum value to 2*(D-1)
      __:)&       check if the modified array has any adjacent values
    :B            store the new positions in B
    {'_t}/        place underscores over the zigzag pattern
    +@J+          bring C to the top and add J to it
;                 pop C

Versi "3D" lama, 189 byte:

ri:A" __"e*aA4*S*aA2**+[0-2XXW1]:C;"/\_\\\/_/":D;A3m*{{C2/.f*:.+~
A(2*+:V;A+:U;2{UI+1$1$=4{_V+D4/I=@=t}/t}fI}:F~}/[0Y1WWW]:C;
"/_/\\\_\/":D;AaA*:B;A{A[_{_BI=e<)mr}fI]:B;{BQ={[PQR]F}fR}fQ}fPN*

Cobalah online

aditsu
sumber
Memberi +1 untuk pekerjaan yang luar biasa dan juga karena satu suara lagi akan memberi Anda 10 ribu rep, tetapi sebagian besar untuk pekerjaan yang luar biasa. (Oh, hei, lihat itu. Selamat atas 10k :))
Alex A.
Analisis yang bagus tentang polanya! Saya akan menggunakannya untuk jawaban saya.
anatolyg
6

Python 2, 337 335 324 318 311 300 296 byte

from random import*
n=input()
R=range(n*2)
b=[]
l=[]
for i in R:o=abs(i-n)-(i<n);b+=[o];l+=[list(' '*o+'\//\\'[i<n::2]*(n*2-o))]
for i in R[:n]:
 o=1;p=n+i*2
 for j in R:r=randint(0,p<n*3+i*2-j);p+=(r or-1)*(o==r);q=p<=b[j];o=r|q;p+=q;l[j][p]='_';b[j]=p+1
for s in[' '*n+'__'*n]+l:print''.join(s)

Idenya adalah untuk pertama-tama membuat berlian segi enam, seperti ini:

  ____
 /\/\/\
/\/\/\/\
\/\/\/\/
 \/\/\/

Dan kemudian mengisinya dengan jalan bawah garis bawah, seperti ini:

  ____                          ____
 /_/\/\                        /\_\/\
/_/\/\/\    or maybe this:    /\/_/\/\
\_\/\/\/                      \/_/\/\/
 \_\/\/                        \_\/\/

Hasil akhir dengan semua jalur yang ditambahkan akan terlihat seperti ini:

  ____                          ____  
 /_/\_\                        /\_\_\ 
/_/\/_/\    or maybe this:    /\/_/\_\
\_\/_/\/                      \/_/\/_/
 \_\_\/                        \_\/_/ 

Cukup banyak kode untuk memastikan jalur ini tidak keluar dari batas atau saling silang.

Kode yang tidak dipisahkan:

# Initialize l with all diamonds
blocked = []
l = [[] for _ in range(n*2)]
for i in range(n*2):
    offset = n-i-1 if i<n else i-n
    blocked.append(offset)
    l[i] += ' '*offset + ('/\\' if i<n else '\/')*(2*n - offset)

# Generate the random _'s
for i in range(n):
    oldright = True
    pos = n + i*2
    for j in range(n*2):
        # Go randomly right (true) or left (false), except when you out of bounds on the right side
        right = randint(0, 1) and pos < n*3 + i*2 - j
        if right == oldright:
            pos += 1 if right else -1
        if pos <= blocked[j]:
            right = True
            pos += 1
        l[j][pos] = '_'
        blocked[j] = pos + 1
        oldright = right

# Print the result
print ' '*n + '__'*n
for s in l:
    print ''.join(s)
Matty
sumber
1
Saya hanya memperhatikan bahwa output Anda tampaknya salah. Anda memiliki segitiga di dua hasil exaple Anda (kanan atas dan kanan bawah).
Martin Ender
1
@ MartinEnder Contoh-contoh hanya menunjukkan satu 'jalur garis bawah', untuk menunjukkan gagasan algoritma. Hasil akhir memiliki semua jalur (dalam hal ini 2), yang menghilangkan segitiga. Saya menambahkan dalam contoh hasil akhir juga.
Matty
Ohhh begitu, masuk akal. Terimakasih atas klarifikasinya.
Martin Ender
2
Saya pikir Anda dapat mempersingkat randint(0,1)*(p<n*3+i*2-j)untuk randint(0,p<n*3+i*2-j).
12Me21
Oooh ya terima kasih!
Matty
4

Perl, 174 168 166 161

#!perl -n
for$l(-$_..$_){$t=/_/?join'',map'/_'x($%=rand
1+(@z=/__?/g)).'/\\'.'_\\'x(@z-$%),split/\/\\/:__
x$_;$l>0&&$t!~s!^.(\\.*/).$!$1!?redo:print$"x abs$l-.5,$_=$t.$/}

Coba saya .

nutki
sumber
Tampaknya selalu menghasilkan ubin yang sama (setidaknya pada ideone)
aditsu
@aditsu, Ideone menampilkan hasil cache jika Anda cukup mengeklik tautannya. Anda perlu garpu untuk benar-benar menjalankannya lagi.
nutki
2

JavaScript ( ES6 ), 376 416 494

Hanya untuk berada di sana ...

Ini membangun semua tilings, lalu pilih yang acak. Waktu untuk tilings 232848 untuk N = 4 adalah ~ 45 detik di laptop saya. Saya tidak mencoba N = 5.

Menjadi EcmaScript 6 hanya berjalan di Firefox.

F=n=>{
  for(i=s=r=b='';i<n;i++)
    s='\n'+b+'/\\'[R='repeat'](n-i)+'_\\'[R](n)+s,
    r+='\n'+b+'\\/'[R](n-i)+'_/'[R](n),
    b+=' ';
  for(h=[t=0],x=[s+r];s=x[t];t++)
    for(d='';!d[n*3];d+='.')
      if(l=s.match(r=RegExp("(\n"+d+"/)\\\\_(.*\n"+d+"\\\\)/_","g")))
        for(j=2<<l.length;j-=2;h[z]||(h[z]=x.push(z)))
          z=s.replace(r,(r,g,h)=>(k+=k)&j?g+'_/'+h+'_\\':r,k=1);
  return b+'__'[R](n)+x[Math.random()*t|0]
}


function go()
{
  var n = N.value | 0,
  t0 = performance.now(),
  r = F(n),
  t1 = performance.now();
  
  O.innerHTML = r+'\n\nTime (msec): '+(t1-t0)
}
N: <input id=N value=3><button onclick="go()">GO</button>
<pre id=O></pre>

edc65
sumber
Di Chromium 42 saya mendapatkan "Uncaught SyntaxError: Token tak terduga =>" dan "Uncaught ReferenceError: go tidak ditentukan"
aditsu
1
@aditsu itu ES6, Chrome: tidak ada Firefox: ya. Bukankah ini fakta yang sudah diketahui?
edc65
Saya tidak tahu, saya mengharapkan Chromium untuk menggunakan javascript terbaru dan terhebat apa pun yang disebutnya. Terima kasih telah menjelaskan.
aditsu
Saya menjalankannya sekarang di firefox (31.5.3) dan bekerja untuk N = 1, 2 atau 3, tetapi untuk N = 4 ini berjalan sekitar 10 detik, selesai dan tidak menunjukkan apa-apa (dan tidak ada kesalahan di konsol )
aditsu
@aditsu tidak yakin ... mungkin javascript di kotak pasir diam - diam terbunuh saat melebihi batas waktu dom.max_script_run_time. Ini adalah preferensi global dalam tentang: config, milikku disetel ke 30.
edc65
1

SmileBASIC, 241 byte

INPUT N
T=N*2CLS?" "*N;"__"*N
DIM B[T]FOR I=-1TO N-1O=1P=N+I*2FOR J=0TO T-1IF I<0THEN O=ABS(J0N+.5)<<0B[J]=O?" "*O;MID$("\/\",J<N,2)*(T-O)ELSE R=P<N*3+I*2-J&&RND(2)P=P+(R*2-1)*(O==R)A=P<=B[J]R=R||A:P=P+A:LOCATE P,J+1?"_"B[J]=P+1O=R
NEXT
NEXT

Sangat didasarkan pada jawaban Matty

12Me21
sumber