Salah satu bagian penting dari algoritma kompresi PNG adalah transformasi Paeth, yang mengubah gambar dengan cara yang membuatnya lebih baik (biasanya). Dalam tantangan ini, tugas Anda adalah menulis program untuk menghitung transformasi Paeth. Operasi transformasi Paeth dijelaskan di bawah ini.

Transformasi Paeth

Transformasi Paeth mengurangi dari masing-masing anggota Xarray 2 dimensi sebagai prediktor. Prediktornya adalah elemen anggota larik di sebelah kiri ( A), atas ( B), dan atas-kiri ( C) Xyang nilainya paling sedikit berbeda A + B - C.

┼─┼─┼
│C│B│
┼─┼─┼
│A│X│
┼─┼─┼

Jika salah satu dari A,, Batau C, akan di luar batas, nilainya diganti dengan 0. Berikut adalah kodesemu dari spesifikasi PNG yang menguraikan bagaimana prediktor ini dihitung:

function PaethPredictor (a, b, c)
begin
     ; a = left, b = above, c = upper left
     p := a + b - c        ; initial estimate
     pa := abs(p - a)      ; distances to a, b, c
     pb := abs(p - b)
     pc := abs(p - c)
     ; return nearest of a,b,c,
     ; breaking ties in order a,b,c.
     if pa <= pb AND pa <= pc then return a
     else if pb <= pc then return b
     else return c
end

Untuk tantangan ini, anggota array adalah bilangan asli dalam kisaran dari 0 hingga 255. Jika transformasi Paeth menghasilkan nilai di luar rentang itu, itu harus dikurangi modulo 256 ke nilai dalam rentang itu.

Masukan dan keluaran

Inputnya adalah dua bilangan bulat x dan y dalam rentang 2 hingga 1023 yang menunjukkan lebar dan tinggi matriks untuk ditransformasikan dan sebuah array elemen x × y . Input diformat sebagai angka desimal yang dipisahkan oleh satu karakter kosong yang diakhiri dengan umpan baris. Di sini terlihat seperti apa input ini:

2 3 4 5 6 7 8 9

Ini akan mewakili matriks 2 dengan 3 dengan entri:

4 5
6 7
8 9

Keluaran harus memiliki format yang sama dengan input dengan relaksasi bahwa angka-angka dapat dipisahkan dengan jumlah karakter spasi kosong yang tidak nol (spasi, tab horizontal atau vertikal, umpan garis atau bentuk) dan diakhiri dengan jumlah sewenang-wenang dari karakter spasi putih.

Input akan diterima dari stdin, output akan pergi ke stdout. Jika ini tidak memungkinkan, pilih cara berbeda untuk menerima input dan menulis output yang tidak mengkodekan input.

Perilaku program Anda ketika disajikan dengan input yang tidak valid bukan bagian dari tantangan ini.

Penilaian dan Implementasi Referensi

Program ANSI C disediakan untuk menghasilkan input sampel, menyelesaikan contoh dan memverifikasi solusi. Panggil program dengan guntuk g masukan enerate, dengan ske s olve sebuah contoh masukan dan dengan vke v erify kebenaran solusi.

Jika menurut Anda implementasi referensi salah, harap beri tahu saya agar saya dapat memperbaikinya sesegera mungkin.

Contoh input dan output

Dengan permintaan populer.

10 5 166 156 108 96 63 227 122 99 117 135 125 46 169 247 116 55 151 1 232 114 214 254 6 127 217 88 206 102 252 237 75 250 202 145 86 198 172 84 68 114 58 228 66 224 186 217 210 108 11 179

mewakili array

166 156 108  96  63 227 122  99 117 135
125  46 169 247 116  55 151   1 232 114
214 254   6 127 217  88 206 102 252 237
 75 250 202 145  86 198 172  84  68 114
 58 228  66 224 186 217 210 108  11 179

ditransformasikan menjadi

166 246 208 244 223 164 151 233  18  18
215 177 123  78 125  84  96 135 231 138
 89 129   8 121 101 228  55 101  20 123
117 175 196 199 125 112 222 238  72  46
239 234 120 158  41  19  12  24 183 111

yang dikodekan sebagai

10 5 166 246 208 244 223 164 151 233 18 18 215 177 123 78 125 84 96 135 231 138 89 129 8 121 101 228 55 101 20 123 117 175 196 199 125 112 222 238 72 46 239 234 120 158 41 19 12 24 183 111

Kondisi Menang

Untuk tantangan ini, tulislah sebuah program yang menghasilkan transformasi input Paeth yang benar dan catat. Ini adalah kode-golf, program dengan jumlah karakter paling sedikit dalam kode sumbernya yang menang. Coba lampirkan penjelasan dan versi kode Anda yang dapat dibaca ke kiriman Anda sehingga orang lain dapat melihat apa yang dilakukannya.

J - 77 char

Mengambil pendekatan yang terlihat berbeda dari jawaban FUZxxl tetapi sebenarnya sangat mirip.

1!:2&4":2({.,|.@{.,@(256|$-0(0{[/:+`-/|@-])"1@|:(-#:1 2 3)|.!.0$)}.)0".1!:1]3

Beberapa komentar tentang bit yang menarik.

• 1!:2&4":(...) 0".1!:1]3- Jika J tidak buruk tentang I / O dan parsing, ini bisa di refactored untuk digunakan &.".&.stdin'', untuk menghemat 3 chars. Tapi begitulah kita tidak bisa. Beristirahatlah dengan tenang, karakter yang berharga.
• 2 ({.,|.@{.,@( ... stuff using $ ... )}.)- Ini membongkar input dan memasang kembali output. Kami menggunakan $keduanya sebagai referensi ke input stuff using $, dan sebagai operasi kami perlu melakukan input sebelum menjalankannya stuff.
• 0( blah )"1@|:- Ya, itu adalah Transpose diad: kami menyusun kembali tiga hasil rotasi sebagai sumbu array terdalam, sehingga logika Paeth dapat diterapkan pada setiap set secara terpisah "1.
• 0{[/:+`-/|@-]- Logika Paeth: urutkan a,b,cberdasarkan besaran ( pminus masing-masing a,b,c), dan ambil yang pertama.

J, 97 91 88 87 karakter

Mari kita mulai ini. Perhatikan yang absen exit; J mencetak prompt (tiga kosong) setelah semua output telah ditulis, tetapi kemudian mengaktifkan EOF stdin, menyebabkannya berhenti.

Saya percaya bahwa beberapa perbaikan dimungkinkan dalam kode ini.

1!:2&4":(|.@$,,)256|((-+`-/+[:(>&|{,)"0/]-"2+`-/)(3 2$-*i.3)|.!.0])2(|.@{.$}.)0".1!:1]3

Ini kode sebelum bermain golf; sebagian besar sama dengan kode saat ini.

NB. A, B, and C values
abc =: (0 _1 , _1 0 ,: _1 _1)&(|.!.0)
p =: +`-/@abc
NB. minimum of magnitudes
mmin =: (>&| { ,)"0
pred =: p + [: mmin/ abc -"2 2 p
paeth =: 256 | ] - pred
input =: [: (2&}. $~ 2 |.@{. ]) 0 ". 1!:1
output =: [: 1!:2&4 LF ,~ [: ": |.@$ , ,
output paeth input 3
exit 0