Una de las partes clave del algoritmo de compresión de PNG es la transformación de Paeth, que transforma la imagen de una manera que hace que se comprima mejor (generalmente). En este desafío, su tarea es escribir un programa para calcular una transformación de Paeth. La operación de una transformación de Paeth se describe a continuación.

La transformación de Paeth

La transformación de Paeth resta de cada miembro Xde una matriz bidimensional un predictor. El predictor es ese elemento del miembro de la matriz a la izquierda ( A), arriba ( B) y arriba a la izquierda ( C) de Xcuyo valor tiene la menor diferencia A + B - C.

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

Si uno de A,, Bo C, estuviera fuera de los límites, su valor se reemplaza por 0. Aquí hay un seudocódigo de la especificación PNG que describe cómo se calcula este predictor:

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

Para este desafío, los miembros de la matriz son números naturales en el rango de 0 a 255. Si la transformación de Paeth resulta en un valor fuera de ese rango, se reducirá el módulo 256 a un valor en ese rango.

Entrada y salida

La entrada es dos enteros x e y en el rango de 2 a 1023 que denota el ancho y la altura de la matriz a transformar y una matriz de elementos x × y . La entrada está formateada como números decimales separados por un carácter en blanco terminado con un salto de línea. Así es como podría verse esta entrada:

2 3 4 5 6 7 8 9

Esto representaría una matriz de 2 por 3 con las entradas:

4 5
6 7
8 9

La salida tendrá el mismo formato que la entrada con la relajación de que los números pueden estar separados por una cantidad arbitraria de caracteres de espacio en blanco no cero (espacio, tabulación horizontal o vertical, avance de línea o formulario) y terminados por una cantidad arbitraria de caracteres de espacio en blanco

La entrada se recibirá de stdin, la salida irá a stdout. Si esto no es posible, elija una forma diferente de recibir la entrada y escribir la salida que no codifique la entrada.

El comportamiento de su programa cuando se le presenta una entrada inválida no es parte de este desafío.

Juicio e implementación de referencia

Se proporciona un programa ANSI C para generar entradas de muestra, resolver instancias y verificar soluciones. Llama al programa con ga g entrada enerate, con sa s Olve una instancia de entrada y con val v erificar la corrección de una solución.

Si cree que la implementación de referencia es defectuosa, avíseme para que pueda corregirla lo antes posible.

Ejemplo de entrada y salida

Por petición popular.

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

representando la matriz

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

se transforma en

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

que está codificado como

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

Condición ganadora

Para este desafío, escriba un programa que genere la transformación correcta de Paeth de la entrada y los escriba. Este es el código de golf, el programa con la menor cantidad de caracteres en su código fuente gana. Intente adjuntar una explicación y una versión legible de su código a su envío para que otros puedan ver lo que hace.

J - 77 char

Adoptar un enfoque que se ve diferente de la respuesta de FUZxxl pero en realidad es muy similar.

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

Algunos comentarios sobre las partes interesantes.

• 1!:2&4":(...) 0".1!:1]3- Si J no era terrible acerca de E / S y análisis, esto podría ser refactorizado para usar &.".&.stdin'', para guardar 3 caracteres. Pero es así que no podemos. Descansa en paz, preciosos personajes.
• 2 ({.,|.@{.,@( ... stuff using $ ... )}.)- Esto desmonta la entrada y vuelve a ensamblar la salida. Usamos $ambos como referencia a la entrada stuff using $y como una operación que necesitamos realizar en la entrada antes de ejecutarla stuff.
• 0( blah )"1@|:- Sí, esa es una Transposición diádica: reagrupamos los tres resultados de rotación como el eje de matriz más interno, de modo que la lógica de Paeth se puede aplicar en cada conjunto por separado con "1.
• 0{[/:+`-/|@-]- La lógica de Paeth: ordenar a,b,cpor las magnitudes de ( pmenos cada uno de a,b,c) y tomar la primera.

J, 97 91 88 87 caracteres

Comencemos esto. Fíjate en lo ausente exit; J imprime una solicitud (tres espacios en blanco) después de que se haya escrito toda la salida, pero luego se activa un EOF stdin, lo que hace que finalice.

Creo que son posibles algunas mejoras en este código.

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

Aquí está el código antes de jugarlo; es mayormente igual al código actual.

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