# Paeth-transform arrays

One of the key parts of PNG's compression algorithm is the Paeth transformation, which transforms the image in a way that makes it compress better (usually). In this challenge, your task is to write a program to compute a Paeth transformation. The operation of a Paeth transformation is described below.

## The Paeth Transformation

The Paeth transformation subtracts from each member X of a 2-dimensional array a predictor. The predictor is that element of the array member to the left (A), top (B), and top-left (C) of X whose value has the least difference to A + B - C.

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


If one of A, B, or C, would be out of bounds, its value is replaced by 0. Here is pseudocode from the PNG specification outlining how this predictor is computed:

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


For this challenge, the array members are natural numbers in the range from 0 to 255. If the Paeth transformation results in a value outside of that range, it shall be reduced modulo 256 to a value in that range.

## Input and Output

The input is two integers x and y in the range from 2 to 1023 denoting width and height of the matrix to transform and an array of x × y elements. The input is formatted as decimal numbers separated by one blank character terminated with a linefeed. Here is what this input could look like:

2 3 4 5 6 7 8 9


This would represent a 2 by 3 matrix with the entries:

4 5
6 7
8 9


The output shall have the same format as the input with the relaxiation that the numbers may be separated by an arbitrary non-zero amount of whitespace characters (space, horizontal or vertical tab, line or form feed) and be terminated by an arbitrary amount of whitespace characters.

Input shall be received from stdin, output shall go to stdout. If this is not possible, choose a different way of receiving input and writing output that is not hard-coding the input.

The behaviour of your program when presented with invalid input is not part of this challenge.

## Judging and Reference Implementation

An ANSI C program is provided to generate sample input, solve instances and verify solutions. Call the program with g to generate input, with s to solve an input instance and with v to verify the correctness of a solution.

If you think the reference implementation is faulty, please let me know so I can correct it as soon as possible.

## Example input and output

By popular request.

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


representing the 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


is transformed into

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


which is encoded as

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


## Winning Condition

For this challenge, write a program that generates correct Paeth transformation of the input and writes them out. This is code-golf, the program with the least amount of characters in its source code wins. Please try to attach an explanation and a readable version of your code to your submission so others can see what it does.

• What do you mean by "If the Paeth transformation results in a value outside of that range"? Since the result is always drawn from a set of three elements, all of which are within range, this seems to be covering an impossible case. Feb 26, 2015 at 16:03
• @PeterTaylor The Paeth transformation is for each array member the difference between the value of that member and the predictor for that member, which can be negative. Feb 26, 2015 at 16:06
• @MartinBüttner That must have slipped through the copy-editing. Feb 26, 2015 at 16:22
• @FUZxxl: Truth. Didn't realize there isn't universal agreement on that until a moment ago. But that was a total aside. Nice challenge. Feb 26, 2015 at 18:25
• Btw, congratulations on posting question no. 3000! (Not counting deleted and locked questions.) Feb 26, 2015 at 19:21

# J - 77 char

Taking an approach that looks different from FUZxxl's answer but is actually very similar.

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


Some comments on the interesting bits.

• 1!:2&4": (...) 0".1!:1]3 - If J wasn't terrible about I/O and parsing, this could be refactored as to use &.".&.stdin'', to save 3 chars. But it is so we can't. Rest in peace, precious characters.
• 2 ({.,|.@{.,@( ... stuff using $... )}.) - This disassembles the input and reassembles the output. We use $ both as a reference to the input in stuff using $, and as an operation we need to perform on the input before running the stuff on it. • 0( blah )"1@|: - Yes, that's a dyadic Transpose: we regroup the three rotation results as the innermost array axis, so that the Paeth logic can apply on each set separately with "1. • 0{[/:+-/|@-] - The Paeth logic: sort a,b,c by the magnitudes of (p minus each of a,b,c), and take the first. • This is really neat. Mar 3, 2015 at 11:24 • +1 for the dyadic transpose. Very nice. Apr 13 at 0:40 ## J, 979188 87 characters Let's get this started. Notice the absent exit; J prints a prompt (three blanks) after all the output has been written, but then gets an EOF on stdin, causing it to terminate. I believe that quite a couple of improvements are possible in this code. 1!:2&4":(|.@$,,)256|((-+-/+[:(>&|{,)"0/]-"2+-/)(3 2$-*i.3)|.!.0])2(|.@{.$}.)0".1!:1]3


Here is the code before golfing it; it's mostly equal to the current code.

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

• This code gives an incorrect output: 3 2\$-*i:3 is not equivalent to 0 _1,_1 0,:_1 _1`. Mar 2, 2015 at 6:59
• @algorithmshark Sorry. better this way? Mar 2, 2015 at 7:13