A photo in sixteen colours
The EGA graphics card showed sixteen colours at once. To display a photograph on such a screen, each pixel is replaced by the nearest colour of the palette, and then you look at which colours were needed and how many. In the same way a picture is converted to the 216 “web-safe” colours of early browsers, or to the inks a printer has.
A colour is three numbers (r, g, b) from 0 to 255. The distance between colours is the square of the ordinary distance: (r1 − r2)2 + (g1 − g2)2 + (b1 − b2)2. Each pixel goes to the nearest palette colour, and if there are several nearest, to the one that comes earlier in the palette. How many pixels went to each colour? The tests include photographs by the site’s author, among them “Water and mountains” from the article on vectorization.
Input
The first line holds the number of palette colours m (1 ≤ m ≤ 256), the second the colours themselves. A colour is written as six hexadecimal digits rrggbb, lowercase, as in CSS without the hash. Colours may repeat in the palette. Then the width W and height H of the picture (W·H ≤ 2·105) and H lines of W pixel colours in the same notation.
Output
m numbers separated by spaces: how many pixels went to each colour, in palette order.
Examples
Example 1
3 202020 e0e0e0 ff0000 3 2 101010 f0f0f0 c01010 808080 7f7f7f ff8080
3 2 1
Example 2
2 ffffff 000000 2 2 000000 404040 c0c0c0 ffffff
2 2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Count the work: a photograph is 183 thousand pixels, a palette up to 256 colours, and each pixel is compared with each colour. How many Python loop iterations is that? And what if instead of looping over pixels and colours you computed the whole “pixel × colour” table at once?
2Hint 2
Expand the squared distance: (p − c)2 = p2 − 2p·c + c2. Which part does not depend on the colour, and which on the pixel? And how do you compute all the products p·c in one operation?
3The idea
Vectorise over pixels and colours at once. For each pixel the nearest colour is the one with the smallest |c|2 − 2p·c: the term |p|2 is the same for the whole row of the table and does not change the choice. All the dot products of pixels with colours are one matrix multiplication pixels @ palette.T, the nearest colour of each row is argmin, and the count is np.bincount, the same histogram as in the article.
4Walkthrough
Parsing the input is done with whole arrays too: all pixels are glued into one hexadecimal string, bytes.fromhex turns it into bytes, and np.frombuffer into an N × 3 array. Before computing, the type must be changed to int32.
A table for all pixels at once is not needed, and with 216 colours it is already heavy: 183 thousand × 216 numbers is 158 megabytes in int32, with temporary arrays alongside. So pixels go in chunks of four thousand: a chunk’s table is three and a half megabytes, and the chunks are processed by the same vector code. The overhead of 45 numpy calls is negligible next to the work inside them.
Ties resolve themselves: argmin returns the first of equal minimums, that is, the colour that comes earlier in the palette. So in the first example the grey 808080, exactly 96 away in each channel from both 202020 and e0e0e0, goes to the first of them, and repeated colours in the palette go to the first copy.
In Go there is no reason to vectorise: a double loop over pixels and colours, 40 million comparisons, takes tenths of a second.
4+Solution
5Complexity
O(N·m) with any method, where N = W·H. A Python loop on a photograph with 216 colours runs for about 12 seconds, numpy about a third of a second, including parsing the input and loading the library. The vector solution’s memory is O(N + chunk × m).
6Common mistakes
- A loop over pixels and colours. This is
wrong.py. With sixteen colours it still fits in the time, 0.9 seconds, but with a palette of 216 colours it runs for about 12 seconds. - A three-dimensional difference. The obvious vector formulation
((pixels[:, None, :] - palette[None, :, :]) ** 2).sum(axis=2)builds an N × m × 3 array. Inint64, for a palette of 64 colours that is 268 megabytes, and the program crashes withMemoryErrorunder a 256 MB limit; for 216 colours, almost a gigabyte. Vectorization is not free: each intermediate array lies in memory whole. - Subtracting in
uint8. If the bytes are not converted to a signed integer type, the difference wraps around modulo 256: 10 − 20 gives 246, and the wrong colour turns out nearest. - Ties going your way. A comparison “≤” instead of “<” in the loop picks the last of the nearest colours, but the first is needed; the first example catches this.