A pixel may be represented using the shorthand hexadecimal form if it has two identical digits representing its red, green and blue components, respectively. For instance, #AABBCC can be compressed down to #ABC, while #AABBCD is not compressible.
Your task is to transform some (possibly none, possibly all) of the pixels in the input image, such that all of the pixels are compressible, and the resulting image resembles the original one as closely as possible.
The difference between two pixels (R, G, B) and (R', G', B') is defined as |R-R'| + |G-G'| + |B-B'|. The difference between two images is defined as the sum of differences of all pairs of homologous pixels. The lower the difference between two images, the more they resemble each other. If a pixel can be compressed in multiple ways that yield the same minimum difference, the lexicographically lower option is preferred.
Input
The first line of input contains two space-separated values: N and M.
Each of the following N lines contains M space-separated pixels, represented using hexadecimal notation.
Output
The output should contain N lines of M space-separated pixels, each. All pixels should be represented using shorthand hexadecimal notation.
Constraints
- N * M ≤ 20 000
Sample
| Input | Output |
|---|---|
| 2 3 #FFFFFF #ABCDEF #110035 #2F0000 #FBDCEA #FF0000 | #FFF #ACE #103 #300 #FDE #F00 |
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()
