# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1441734744 -7200
# Node ID 3e68ec96af01a616782a4e8a0d93573ddfdd03ab
# Parent  19ad565c6647cefe95712ee585c9848711e81b86
Introduced a method for selecting colours for each line of the image.

diff -r 19ad565c6647 -r 3e68ec96af01 optimiser.py
--- a/optimiser.py	Tue Sep 08 14:42:05 2015 +0200
+++ b/optimiser.py	Tue Sep 08 19:52:24 2015 +0200
@@ -1,6 +1,8 @@
 #!/usr/bin/env python
 
 from array import array
+from itertools import combinations
+from random import randint
 import PIL.Image
 import sys
 
@@ -16,37 +18,147 @@
 def colour(i):
     return (255 * (i % 2), 255 * ((i / 2) % 2), 255 * ((i / 4) % 2))
 
+def add(d, v):
+    d[v] = (d.has_key(v) and d[v] or 0) + 1
+
+def by_frequency(d):
+    l = [(f, t) for (t, f) in d.items()]
+    l.sort(reverse=True)
+    return [i[1] for i in l]
+
+def match(b, bases):
+    return b in bases and b
+
+def match_lighter(b, bases):
+    return upward[b] in bases and upward[b]
+
+def match_darker(b, bases):
+    return downward[b] in bases and downward[b]
+
+def match_tone(t, bases):
+    return match(t[1], bases)
+
+def match_variant(t, bases, fn):
+    return fn(t[0], bases)
+
+def neutral(bases, light):
+    l = ["W", "C", "Y", "M", "G", "R", "B", "_"]
+    if not light:
+        l.reverse()
+    for b in l:
+        if b in bases:
+            return b
+    return bases[randint(0, 3)]
+
 tones = [
-    "__", "B_", "BB", # 00x
-    "G_", "C_", "CB", # 01x
-    "GG", "CG", "CC", # 02x
-    "R_", "M_", "MB", # 10x
-    "Y_", "W_", "WB", # 11x
-    "YG", "WG", "WC", # 12x
-    "RR", "MR", "MM", # 20x
-    "YR", "WR", "WM", # 21x
+    "__", "_B", "BB", # 00x
+    "_G", "_C", "BC", # 01x
+    "GG", "GC", "CC", # 02x
+    "_R", "_M", "BM", # 10x
+    "_Y", "**", "WB", # 11x
+    "GY", "WG", "WC", # 12x
+    "RR", "RM", "MM", # 20x
+    "RY", "WR", "WM", # 21x
     "YY", "WY", "WW", # 22x
     ]
 
 colours = ["_", "R", "G", "Y", "B", "M", "C", "W"]
 
+upward = {
+    "_" : ["R", "G", "B"],
+    "R" : ["Y", "M"],
+    "G" : ["Y", "C"],
+    "B" : ["C", "M"],
+    "Y" : ["W"],
+    "C" : ["W"],
+    "M" : ["W"],
+    "W" : ["W"],
+    "*" : ["W", "Y", "C", "M"],
+    }
+
+downward = {
+    "_" : ["_"],
+    "R" : ["_"],
+    "G" : ["_"],
+    "B" : ["_"],
+    "Y" : ["R", "G"],
+    "C" : ["G", "B"],
+    "M" : ["R", "B"],
+    "W" : ["Y", "C", "M"],
+    "*" : ["R", "G", "B", "_"],
+    }
+
 if __name__ == "__main__":
-
+    width = 320
+    height = 192
     input_filename, output_filename = sys.argv[1:3]
 
     im = PIL.Image.open(input_filename)
-    im = im.resize((320, 256))
+    im = im.resize((width, height))
+
+    usage = []
+    base_usage = []
+    toned = []
 
-    for row in range(0, 256):
-        for column in range(0, 320):
+    for row in range(0, height):
+        u = {}
+        usage.append(u)
+        bu = {}
+        base_usage.append(bu)
+        tr = []
+        toned.append(tr)
+        for column in range(0, width):
             rgb = im.getpixel((column, row))
             p = point(rgb)
             i = index(p)
             t = tones[i]
-            c = t[row % 2]
-            i = colours.index(c)
+            add(u, t)
+            if t[0] != "*":
+                add(bu, t[0])
+            if t[1] != "*":
+                add(bu, t[1])
+            tr.append(t)
+
+    chosen = []
+
+    light = True
+    for u, bu in zip(usage, base_usage):
+        best = 0
+        best_bases = None
+        best_missing = None
+        best_map = None
+        for bases in combinations(bu, 4):
+            count = 0
+            missing = []
+            tone_map = {}
+            for tone, freq in u.items():
+                base = match(light and tone[1] or tone[0], bases)
+                if base:
+                    tone_map[tone] = base
+                    count += freq
+                else:
+                    missing.append(tone)
+            if count > best:
+                best_bases = bases
+                best_missing = missing
+                best_map = tone_map
+                best = count
+        chosen.append((best, best_bases or bases, best_map or tone_map, best_missing or missing))
+        light = not light
+
+    output = []
+
+    for row, (tr, ch) in enumerate(zip(toned, chosen)):
+        o = []
+        for column, t in enumerate(tr):
+            best, bases, tone_map, missing = ch
+            base = tone_map.get(t) or neutral(bases, light)
+            o.append(base)
+            i = colours.index(base or "_")
             im.putpixel((column, row), colour(i))
 
+        output.append("".join(o))
+
     im.save(output_filename)
 
 # vim: tabstop=4 expandtab shiftwidth=4