Algoritma ukiran jahitan, atau versi yang lebih kompleks, digunakan untuk mengubah ukuran gambar yang sadar konten di berbagai program grafik dan pustaka. Mari kita bermain golf!
Input Anda akan berupa array bilangan bulat dua dimensi persegi panjang.
Output Anda akan menjadi array yang sama, satu kolom lebih sempit, dengan satu entri dihapus dari setiap baris, entri-entri itu mewakili jalur dari atas ke bawah dengan jumlah terendah dari semua jalur tersebut.
https://en.wikipedia.org/wiki/Seam_carving
Dalam ilustrasi di atas, nilai setiap sel ditampilkan dalam warna merah. Angka hitam adalah jumlah dari nilai sel dan angka hitam terendah di salah satu dari tiga sel di atasnya (ditunjukkan oleh panah hijau). Jalur yang disorot putih adalah dua jalur jumlah terendah, keduanya dengan jumlah 5 (1 + 2 + 2 dan 2 + 2 + 1).
Dalam kasus di mana ada dua jalur terikat untuk jumlah terendah, tidak masalah yang Anda hapus.
Input harus diambil dari stdin atau sebagai parameter fungsi. Ini dapat diformat dengan cara yang sesuai dengan bahasa pilihan Anda, termasuk tanda kurung dan / atau pembatas. Silakan tentukan dalam jawaban Anda bagaimana input diharapkan.
Output harus stdout dalam format terbatas tegas, atau sebagai fungsi mengembalikan nilai dalam bahasa Anda setara dengan array 2d (yang mungkin termasuk daftar bersarang, dll).
Contoh:
Input:
1 4 3 5 2
3 2 5 2 3
5 2 4 2 1
Output:
4 3 5 2 1 4 3 5
3 5 2 3 or 3 2 5 3
5 4 2 1 5 2 4 2
Input:
1 2 3 4 5
Output:
2 3 4 5
Input:
1
2
3
Output:
(empty, null, a sentinel non-array value, a 0x3 array, or similar)
EDIT: Angka-angka semua akan non-negatif, dan setiap jahitan yang mungkin akan memiliki jumlah yang cocok dengan integer 32 bit yang ditandatangani.
sumber
Jawaban:
CJam,
5144 byteIni adalah fungsi anonim yang memunculkan array 2D dari tumpukan dan mendorongnya sebagai balasan.
Coba uji kasus secara online di juru bahasa CJam . 1
Ide
Pendekatan ini mengulangi semua kemungkinan kombinasi elemen baris, memfilter kombinasi yang tidak sesuai dengan jahitan, mengurutkan berdasarkan jumlah yang sesuai, memilih minimum dan menghapus elemen yang sesuai dari array. 2
Kode
1 Perhatikan bahwa CJam tidak dapat membedakan antara array kosong dan string kosong, karena string hanyalah array yang elemen-elemennya adalah karakter. Dengan demikian, representasi string dari kedua array kosong dan string kosong adalah
""
.2 Sementara kompleksitas waktu dari algoritma yang ditampilkan pada halaman Wikipedia harus dari O (nm) untuk matriks n × m , yang ini setidaknya dari O (m n ) .
sumber
{2ew::m2f/0-!},
Haskell, 187 byte
Contoh penggunaan:
Cara kerjanya, versi singkat: buat daftar semua jalur (1), per jalur: hapus elemen yang sesuai (2) dan jumlah semua elemen yang tersisa (3). Ambil kotak dengan jumlah terbesar (4).
Versi yang lebih panjang:
sumber
IDL 8.3, 307 byte
Meh, saya yakin ini tidak akan menang karena ini panjang, tapi di sini ada solusi langsung:
Tidak Disatukan:
Kami secara iteratif membuat susunan energi dan melacak ke arah mana lapisan berjalan, kemudian menyusun daftar pelepasan setelah kami mengetahui posisi akhir. Hapus jahitan melalui pengindeksan 1D, lalu reformasi kembali ke array dengan dimensi baru.
sumber
[0:n]
; jika itu benar, maka mudah untuk menggantir+=[0:z[1]-1]*z[0]
denganr+=indgen(z[1]-1)*z[0]
.JavaScript ( ES6 ) 197
209 215Langkah demi langkah implementasi algoritma wikipedia.
Mungkin bisa dipersingkat lagi.
Tes menjalankan cuplikan di Firefox.
sumber
Pip, 91 byte
Ini tidak akan memenangkan hadiah apa pun, tetapi saya senang mengerjakannya. Whitespace hanya untuk alasan kosmetik dan tidak termasuk dalam jumlah byte.
Kode ini mendefinisikan fungsi anonim yang argumen dan nilai baliknya adalah daftar bersarang. Ini mengimplementasikan algoritma dari halaman Wikipedia:
a
(argumen) adalah angka merah, danz
adalah angka hitam.Inilah versi dengan test harness:
Hasil:
Dan inilah persamaan kasar dalam Python 3. Jika ada yang menginginkan penjelasan yang lebih baik dari kode Pip, tanyakan di komentar.
sumber