Uma das partes principais do algoritmo de compactação do PNG é a transformação Paeth, que transforma a imagem de uma maneira que a comprime melhor (geralmente). Nesse desafio, sua tarefa é escrever um programa para calcular uma transformação de Paeth. A operação de uma transformação Paeth é descrita abaixo.

A transformação de Paeth

A transformação Paeth subtrai de cada membro Xde uma matriz bidimensional um preditor. O preditor é o elemento do membro da matriz à esquerda ( A), superior ( B) e superior esquerda ( C) Xcujo valor tem a menor diferença para A + B - C.

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

Se um de A,, Bou C, estiver fora dos limites, seu valor será substituído por 0. Aqui está o pseudocódigo da especificação PNG, descrevendo como esse preditor é calculado:

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 esse desafio, os membros da matriz são números naturais no intervalo de 0 a 255. Se a transformação Paeth resultar em um valor fora desse intervalo, será reduzido o módulo 256 para um valor nesse intervalo.

Entrada e saída

A entrada é dois números inteiros x e y na gama de 2-1023 denotando largura e a altura da matriz para transformar e uma matriz de x x y elementos. A entrada é formatada como números decimais separados por um caractere em branco terminado com um avanço de linha. Aqui está a aparência dessa entrada:

2 3 4 5 6 7 8 9

Isso representaria uma matriz 2 por 3 com as entradas:

4 5
6 7
8 9

A saída deve ter o mesmo formato da entrada com a relaxação de que os números podem ser separados por uma quantidade arbitrária e diferente de zero de caracteres de espaço em branco (espaço, guia horizontal ou vertical, alimentação de linha ou formulário) e ser finalizados por uma quantidade arbitrária de caracteres de espaço em branco.

A entrada deve ser recebida de stdin, a saída deve ir para stdout. Se isso não for possível, escolha uma maneira diferente de receber entrada e gravar saída que não esteja codificando a entrada.

O comportamento do seu programa quando apresentado com entrada inválida não faz parte desse desafio.

Julgamento e Implementação de Referência

Um programa ANSI C é fornecido para gerar entrada de amostra, resolver instâncias e verificar soluções. Chamar o programa com ga g de entrada enerate, com sa s Olve uma instância de entrada e com va v erifique a exactidão de uma solução.

Se você acha que a implementação de referência está com defeito, entre em contato para que eu possa corrigi-lo o mais rápido possível.

Exemplo de entrada e saída

Por pedido 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 a 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

é transformado em

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 é 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

Condição vencedora

Para esse desafio, escreva um programa que gere a transformação Paeth correta da entrada e as grave. Isso é código-golfe, o programa com a menor quantidade de caracteres em seu código-fonte vence. Tente anexar uma explicação e uma versão legível do seu código ao seu envio para que outras pessoas possam ver o que ele faz.

J - 77 char

Adotando uma abordagem que parece diferente da resposta do FUZxxl, mas na verdade é muito semelhante.

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

Alguns comentários sobre os bits interessantes.

• 1!:2&4":(...) 0".1!:1]3- Se J não fosse terrível sobre E / S e análise, isso poderia ser refatorado quanto ao uso &.".&.stdin'', para salvar 3 caracteres. Mas é assim que não podemos. Descanse em paz, personagens preciosos.
• 2 ({.,|.@{.,@( ... stuff using $ ... )}.)- Isso desmonta a entrada e remonta a saída. Usamos $tanto como referência à entrada stuff using $quanto como operação que precisamos executar na entrada antes de executá stuff-la.
• 0( blah )"1@|:- Sim, é uma transposição diádica: reagrupamos os três resultados de rotação como o eixo mais interno da matriz, para que a lógica Paeth possa ser aplicada em cada conjunto separadamente com "1.
• 0{[/:+`-/|@-]- A lógica de Paeth: classifique a,b,cpelas magnitudes de ( pmenos cada uma a,b,c) e pegue a primeira.

J, 97 91 88 87 caracteres

Vamos começar com isso. Observe o ausente exit; J imprime um prompt (três espaços em branco) depois que toda a saída foi gravada, mas ativa um EOF stdin, fazendo com que seja finalizado.

Acredito que algumas melhorias sejam possíveis neste código.

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

Aqui está o código antes de jogá-lo; é praticamente igual ao código atual.

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