Marching Squares adalah algoritma dari grafik komputer, yang digunakan untuk memulihkan isocontour 2D dari grid sampel (lihat juga, kakaknya Marching Cubes untuk pengaturan 3D). Idenya adalah untuk memproses setiap sel dari grid secara independen, dan menentukan kontur melewati sel berdasarkan nilai-nilai di sudut-sudutnya.

Langkah pertama dalam proses ini adalah untuk menentukan tepi mana yang dihubungkan oleh kontur, berdasarkan pada apakah sudut di atas atau di bawah nilai kontur. Untuk kesederhanaan, kami hanya akan mempertimbangkan kontur sepanjang nilainya 0, sehingga kami tertarik pada apakah sudutnya positif atau negatif. Ada beberapa kasus yang harus dibedakan:24 = 16

^{Sumber Gambar: Wikipedia}

Identifikasi putih dan hitam tidak terlalu penting di sini, tetapi untuk kepastian mengatakan bahwa putih adalah positif dan hitam adalah negatif. Kami akan mengabaikan kasus di mana salah satu sudutnya persis 0.

Poin sadel (kasus 5 dan 10) memberikan sedikit kesulitan ekstra: tidak jelas diagonal mana yang harus digunakan dengan hanya melihat sudut-sudutnya. Ini dapat diatasi dengan menemukan rata-rata empat sudut (yaitu perkiraan nilai tengah), dan memilih diagonal sedemikian rupa sehingga kontur memisahkan pusat dari sudut dengan tanda yang berlawanan. Jika rata-rata tepat 0, kedua kasus dapat dipilih.

Biasanya, 16 kasus ini hanya disimpan dalam tabel pencarian. Ini bagus untuk efisiensi, tetapi tentu saja, kami lebih suka kodenya pendek di sini. Jadi tugas Anda adalah melakukan langkah pencarian ini dan mencetak representasi ASCII dari case dalam kode sesedikit mungkin.

Tantangan

Anda diberi nilai empat sudut (bilangan bulat tidak nol) dalam urutan pilihan Anda yang tetap. Anda kemudian harus menghasilkan tata letak kontur yang benar, menyelesaikan kasus sadel dengan benar.

Anda dapat menulis suatu program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar).

Input dapat diambil dalam format string atau daftar yang nyaman.

Ke 16 kasus akan diwakili dalam seni ASCII menggunakan salah satu dari blok 5x5 berikut:

o---o  o---o  o---o
|   |  |   |  | | |
|   |  |---|  | | |
|   |  |   |  | | |
o---o  o---o  o---o

o---o  o---o  o---o  o---o
|/  |  |  \|  |   |  |   |
|   |  |   |  |   |  |   |
|   |  |   |  |\  |  |  /|
o---o  o---o  o---o  o---o

o---o  o---o
|/  |  |  \|
|   |  |   |
|  /|  |\  |
o---o  o---o

Anda tidak boleh mencetak spasi putih depan atau belakang, tetapi Anda dapat mencetak satu baris opsional tunggal.

Ini kode golf, jadi jawaban tersingkat (dalam byte) menang.

Uji Kasus

Tes kasus berasumsi masukan yang diberikan dalam rangka top-kiri , kanan atas , kiri bawah , kanan bawah . Kasus uji disajikan dalam 9 kelompok, satu sesuai dengan masing-masing dari 9 representasi yang diberikan di atas (dalam urutan yang sama, mulai dari sel kosong, berakhir dengan dua titik sadel).

[1, 2, 1, 3]
[-9, -2, -2, -7]

[4, 5, -1, -2]
[-1, -2, 3, 4]

[7, -7, 7, -7]
[-5, 5, -5, 5]

[1, -6, -4, -1]
[-2, 3, 3, 4]

[-1, 6, -4, -1]
[2, -3, 3, 4]   

[-1, -6, 4, -1]
[2, 3, -3, 4]

[-1, -6, -4, 1]
[2, 3, 3, -4]

[3, -8, -9, 2]
[-3, 8, 9, -2]

[8, -3, -2, 9]
[-8, 3, 2, -9]

Selain itu, kasus uji berikut dapat mengembalikan salah satu dari poin pelana (pilihan Anda):

[1, -4, -2, 5]
[-1, 4, 2, -5]

Ruby, 201 180 176

Ini adalah fungsi lambda anonim, untuk dipanggil dengan cara yang ditunjukkan pada contoh yang tidak diklik.

Ini tidak mengandung variabel s. Dalam versi yang tidak dikenali, ekspresi kompleks ditugaskan suntuk kejelasan, sebelum digunakan. 4 byte disimpan dalam versi golf dengan meletakkannya sejajar. Satu-satunya perbedaan lain antara versi adalah spasi dan komentar.

Jika diterima untuk mengembalikan output sebagai array lima string lima karakter, alih-alih mencetak ke stdout, satu byte lagi dapat disimpan.

->a{p=t=0
4.times{|i|t+=a[i]*=a[3];p+=a[i]>>9&1<<i}
q=p==6&&t>0?19:'@AC@P*10'[p].ord
puts c='o---o',(0..2).map{|i|b=p*i==3?'|---|':'|   |';b[q%4]='|/|\|/'[q%4+(i&2)];q/=4;b},c}

Saya senang dengan penguraian array, tapi saya pikir mungkin ada cara yang lebih pendek untuk membentuk output.

Keempat elemen array input dikalikan dengan elemen terakhir. Ini menjamin bahwa elemen terakhir adalah positif, dan mengurangi jumlah kasus dari 16 menjadi 8. Elemen-elemen tersebut diangkut dengan benar 9 tempat, sehingga semua angka positif menjadi 0 dan semua angka negatif menjadi -1 (setidaknya dalam kisaran input diberikan dalam kasus uji.) Mereka kemudian ANDed oleh 1<<array indexuntuk memberikan angka biner 3-bit yang menunjukkan pola (sebenarnya 4-bit, tetapi karena elemen terakhir selalu positif, bit ke-4 selalu nol.)

Angka dari 0..7 ini kemudian diumpankan ke tabel pencarian (mendesah) untuk menentukan karakter dari setiap baris yang bukan spasi. Pada tahap inilah dua tampilan berbeda untuk case saddle ditangani, dengan alternatif untuk nomor dalam tabel pencarian yang digunakan jika totalnya positif (pertanyaannya mengatakan untuk mempertimbangkan "rata-rata", tetapi karena kami hanya tertarik pada tanda, tidak masalah jika kita mempertimbangkan total sebagai gantinya.)

Cara tampilan output bekerja semoga jelas dari komentar dalam kode.

ungolfed dalam program tes

f=->a{p=t=0
  4.times{|i|                      #for each number in the input
    t+=a[i]*=a[3];                   #multiply each number by a[3]; totalize the sum in t
    p+=a[i]>>9&1<<i                  #shift right to find if negative; AND with 1<<i to build index number for pattern 
  }                                #q is a 3-digit base 4 number indicating which character of each line is non-whitespace (if any). 
  q=p==6&&t>0?19:'@AC@P*10'[p].ord #It's encoded in the magic string, except for the case of saddles with a positive total, which is encoded by the number 19.
  s=(0..2).map{|i|                 #build an array of 3 strings, indexes 0..2
    b=p*i==3?'|---|':'|   |';        #IF p is 3 and we are on row 1, the string is |---| for the horizontal line case. ELSE it is |   |.
    b[q%4]='|/|\|/'[q%4+(i&2)];      #The numbers in q indicate which character is to be modified. The characters in the string indicate the character to replace with.
    q/=4;                            #If q%4=0, the initial | is replaced by | (no change.) i&2 shifts the string index appropriately for the last row.
    b                                #divide q by 4, and terminate the loop with the expression b so that this is the object loaded into array s.  
  }
puts c='o---o',s,c}                #print the array s, capped with "o---o" above and below.


[[1, 2, 1, 3],
[-9, -2, -2, -7],

[4, 5, -1, -2],
[-1, -2, 3, 4],

[7, -7, 7, -7],
[-5, 5, -5, 5],

[1, -6, -4, -1],
[-2, 3, 3, 4],

[-1, 6, -4, -1],
[2, -3, 3, 4],

[-1, -6, 4, -1],
[2, 3, -3, 4],

[-1, -6, -4, 1],
[2, 3, 3, -4],

[3, -8, -9, 2],
[-3, 8, 9, -2],

[8, -3, -2, 9],
[-8, 3, 2, -9],

[1, -4, -2, 5],
[-1, 4, 2, -5]].each{|k|f.call(k)}