Solution of Compress

Key observation: the three components of a pixel (red, green and blue) are independent from each other and can be compressed individually.

Approach #1

For one component, the range of hexadecimal values is [0, 255] (that is, from #00 to #FF). Moreover, there are only 16 candidates (compressible values): #00, #11, …, #FF.

The actual pixel component can be converted to base 10. All 16 candidates can be converted to base 10 as well: they all belong to the set {x*16+x | 0 ≤ x ≤ 15}. At this point, we choose the candidate which has the smallest absolute difference compared to the original value.

Haskell implementation:

import Numeric
import Data.Char (toUpper)

data Pixel = Pixel Int Int Int
           deriving (Eq, Show)

pixelFromList (r:g:b:_) = Pixel r g b
pixelFromList _ = error "Pixel must have 3 components"

hexToDec = fst . head . readHex
decToHex x = map toUpper $ showHex x ""

compressP (Pixel r g b) = pixelFromList $ map compress [r,g,b]

compress n = snd $ minimum $ map (\x -> (abs (x-n), x)) compressibles
    where compressibles = [x*16+x | x <- [0..15]]

showCompressedP (Pixel r g b) = '#' : (foldr  (:)  [] $ map (last . decToHex) [r,g,b])

readP s = pixelFromList $ map hexToDec [r, g, b]
    where r = take 2 $ tail s
          g = take 2 $ drop 3 s
          b = drop 5 s

main = do
    input <- getContents
    let image = map (map (showCompressedP . compressP . readP) . words) $ drop 1 $ lines input
    sequence $ map (putStrLn . unwords) image

Approach #2

Upon closer inspection, we notice that the set of candidates can be reduced to just a select few. Consider the component #XY (where X and Y are hexadecimal digits). The most natural decision is to only change Y to match X, leading to the compressible value #XX. This works well in cases such as #14 → #11 (delta = 3), but performs sub-optimally in other scenarios: #1F → #22 (delta = 2) is a better choice than #1F → #11 (delta = 14).

The optimal decision in such cases is to only change X by one unit, leading to the compressible #(X-1)(X-1) or #(X+1)(X+1). We choose whichever value is closest to #XY.

Python implementation:

#!/usr/bin/python3
import sys

def diff(x, y):
    return abs(int(x, 16) - int(y, 16))

def compress(x):
    a = max('0', '9' if x[0] == 'A' else chr(ord(x[0])-1))
    b = x[0]
    c = min('F', 'A' if x[0] == '9' else chr(ord(x[0])+1))

    return min([(diff(a+a, x), a),
                (diff(b+b, x), b),
                (diff(c+c, x), c)])[1]

def compressPixel(p):
    return "#%c%c%c" % (compress(p[1:3]), compress(p[3:5]), compress(p[5:]))

def main():
    n, m = map(int, input().split())
    for line in sys.stdin:
        print(' '.join(list(map(compressPixel, line.split()))))

if __name__ == '__main__':
    main()