Micropal

from __future__ import division
from __future__ import print_function

# Read PNM file, pick colors that can be represented by Micropal, print
# out GIMP palette with those colors.

import sys


class Image(object):
    def __init__(self, w, h, data):
        self.width = w
        self.height = h
        self.data = data

    def getpixel(self, x, y):
        base = (y * self.width + x) * 3
        return (data[base], data[base + 1], data[base + 2])


def read_pnm(f):
    line = f.readline().rstrip()
    if line != 'P3':
        raise Exception('Need P3 file, got %s' % (line,))

    def read_non_comment():
        while True:
            line = f.readline()
            if len(line) > 0 and line[0] != '#':
                return line

    width, height = map(int, read_non_comment().split())
    scale = int(read_non_comment())

    def get_pieces():
        for line in f:
            for piece in line.split():
                if scale == 255:
                    yield int(piece)
                else:
                    yield int(float(piece) / scale * 256)

    size = width * height * 3
    data = [0] * size
    inator = get_pieces()
    for i in range(size):
        data[i] = inator.next()

    return Image(width, height, data)


def simple_colormap():
    # A simple colormap which does not consider the image data at all.
    colormap = []
    for b in range(4):
        for g in range(8):
            for r in range(8):
                mr = r & 1
                mg = g & 1
                mb = b
                colormap.append(((mr << 7) | (r << 4),
                                 (mg << 7) | (g << 4),
                                 (mb << 6) | (b << 4)))
    return colormap


def colormap_from_image(img):
    # Micropal provides red, green, blue (RGB) colors with 4 bits for each
    # of the components. However, the bits are not freely assignable.
    #
    # The bits are divided into major bits and minor bits. The major
    # bits are the most significant bit of red, the most significant
    # bit of green, and the most significant 2 bits of blue. The minor
    # bits are the 3 least significant bits of red and green and the 2
    # least significant bits of blue.
    #
    # Color is then encoded as follows:
    #
    #   rrrgggbb rgbb
    #   -------- ----
    #    minor   major
    #
    # where rrrgggbb is the color number, and rgbb is stored in a lookup
    # table indexed by color number.
    #
    # Every combination of minor bits always exists in the palette.
    # For every combination of minor bits, exactly one combination of
    # major bits exists in the palette.
    #
    # The task of this function, then, is to assign exactly one major
    # color to every minor color. The better a job this function does,
    # the closer to the original the image will look after conversion
    # to the resulting colormap.
    #
    # Algorithm
    #
    # Getting an optimal assignment of minor colors to major colors is an
    # Interesting Problem. The algorithm used here is not guaranteed to
    # be optimal, but it runs in a reasonable amount of time and produces
    # good results on a number of images I have tried it on.
    #
    # We assign a value to each of the minor colors based on how many pixels
    # use that minor color.
    #
    # We assign a budget to each major color based on how many pixels use that
    # major color.
    #
    # Then we auction off the minor colors, in an order that is deterministic
    # but spread out through the color space. For each minor color, all
    # major colors that want it place a bid, and the highest bidder wins.
    #
    # The function that determines the bid is currently relatively simple.
    # One way it might be improved is by considering nearby colors and
    # whether or not they are still available. For example, we may be willing
    # to bid more on a minor color if we wanted a neighboring minor color,
    # but lost the bid.
    #
    # It may also be beneficial to allow trading colors after the initial
    # auction.

    # First, we create some lookup tables.
    #
    # Bits are arranged from least significant to most significant.
    # rgb is the 12-bit red, green, blue number: rrrrggggbbb.
    # maj is the major color number. It consists of bits r...g...bb..
    # c is the minor color number. It consists of bits .rrr.ggg..bb
    #
    # count[maj][c] is the number of occurrences of each color in the image.
    # major[maj] is the budget for each major color. Initially, this is the
    # number of occurrences of the major color in the image.

    count = []
    for i in range(16):
        count.append([0] * 256)
    major = [0] * 16
    for color in colors_in_image(img):
        rgb = nearest_rrrrggggbbbb(color)
        maj = ((rgb & 8) >> 3) | ((rgb & 128) >> 6) | ((rgb & 3072) >> 8)
        c = (rgb & 7) | ((rgb & 0x70) >> 1) | ((rgb & 0x300) >> 2)
        major[maj] += 1
        count[maj][c] += 1

    def bid(m, c):
        if major[m] < 1 or count[m][c] == 0:
            return 0
        total = 0
        for i in range(256):
            total += count[m][i]
        return count[m][c] * major[m] / total

    # We cycle through the colors so that the next color to be auctioned is never
    # next to the previous color that was auctioned.
    colormap = [(0, 0, 0)] * 256
    c = 54
    for i in range(256):
        # 61 and 256 are relative primes, which guarantees that we will visit every
        # minor color in 256 steps.
        c = (c + 61) & 0xff
        best = (0, 0)
        for m in range(16):
            b = bid(m, c)
            if b > best[0]:
                best = (b, m)
        colormap[c] = (((best[1] & 1) << 7) | ((c & 7) << 4),
                       ((best[1] & 2) << 6) | ((c & 0x38) << 1),
                       ((best[1] & 0x0c) << 4) | ((c & 0xc0) >> 2))

    return colormap
    

def colors_in_image(img):
    for i in range(0, len(img.data), 3):
        yield (img.data[i], img.data[i + 1], img.data[i + 2])


def nearest_rrrrggggbbbb(rgb):
    return (to4bit(rgb[0]) |
            (to4bit(rgb[1]) << 4) |
            (to4bit(rgb[2]) << 8))


def to4bit(c):
    c = (c + 7) // 16
    if c >= 16:
        return 15
    else:
        return c

def main():
    img = read_pnm(sys.stdin)
    colormap = colormap_from_image(img)
    print('GIMP Palette')
    print('Name: test')
    print('Columns: 16')
    for c in colormap:
        print('%s %s %s' % c)


if __name__ == '__main__':
    main()