Instantly share code, notes, and snippets.

Embed
What would you like to do?
The companion code to my picking colors blog post.
import math
import random
def getSuccessors(color):
def perm(l, n, str_a, perm_a):
"""Generate every permutation of length `n`, selecting from the
possible values in `l`.
"""
if len(str_a) == n:
return (str_a,) + perm_a
else:
new_perm_a = perm_a
for c in l:
new_perm_a = perm(l, n, str_a + (c,), new_perm_a)
return new_perm_a
def applyMove(color, move):
"""Given a "move" of the form (x,y,z) apply that move to `color`.
Eg, applyMove( (255,1,255), (0,1,0) ) => (255,2,255)
If the move isn't legal, return None.
"""
if move == (0,0,0):
return None
r,g,b = color
dr,dg,db = move
if 0 <= r+dr <= 255:
r = r+dr
else :
return None
if 0 <= g+dg <= 255:
g = g+dg
else :
return None
if 0 <= b+db <= 255:
b = b+db
else :
return None
return (r,g,b)
successors = []
movements = perm([1,-1,0], 3, (),())
for move in movements:
succ = applyMove(color, move)
if succ is not None:
successors.append(succ)
return successors
def euclideanDist(cur, succ):
r,g,b = cur
nr,ng,nb = succ
return math.sqrt(math.pow(r-nr,2) + math.pow(g-ng,2) + math.pow(b-nb,2))
def closestPoint(cur, point_list):
"""Find the point in the `point_list` that is closest to `cur`."""
return min(point_list, key=lambda point: euclideanDist(cur, point))
def distClosestPoint(cur, point_list):
"""Find the distance to the point in `point_list` that is closest to `cur`.
"""
return euclideanDist(closestPoint(cur, point_list), cur)
def evalSuccessor(cur, succ, point_list):
"""Find the distance to the point closest to `cur`.
Find the distance to the point closest to `succ`.
Return the difference. This tells us whether cur or succ is better.
"""
cur_closest_dist = distClosestPoint(cur, point_list)
succ_closest_dist = distClosestPoint(succ, point_list)
return succ_closest_dist - cur_closest_dist
def hillClimbColor(color_list, start):
cur_color = start
while True:
maximizing_moves = []
for succ in getSuccessors(cur_color):
next_maxi_min = evalSuccessor(cur_color, succ, color_list)
if next_maxi_min > 0:
# Only get the successors that are better than the current.
maximizing_moves.append( (succ, next_maxi_min) )
if len(maximizing_moves) == 0:
# If maximizing_moves is empty, there are no better successors.
return cur_color
else:
# Move to the best successor.
cur_color = max(maximizing_moves, key=lambda pair: pair[1])[0]
def randomRestartHillClimbColor(color_list, restarts):
"""Pick a color that contrasts well with all the colors in `color_list`
using the random-restart hill climbing algorithm. Restart `restart`
times.
"""
best_color = None
for i in xrange(restarts):
start = (
random.randint(0,255),
random.randint(0,255),
random.randint(0,255),
)
color = hillClimbColor(color_list, start)
if best_color is None:
# On the first iteration, best_color will be None, so `color` is
# trivially better.
best_color = color
else :
# Compare the color found by hillClimbColor to the current best
# color.
margin = evalSuccessor(best_color, color, color_list)
if margin > 0:
# Replace the current best color, if the new color is better.
best_color = color
return best_color
print "Hill climbing tests:"
print hillClimbColor([(0,0,0)], (0,0,0))
print hillClimbColor([(0,0,0),(255,255,255)], (0,0,0))
print hillClimbColor(
[(0,0,0),(5,5,5),(0,0,5),(0,5,0),(0,5,5),(5,0,0),(5,5,0),(5,0,5)],
(0,0,0) )
print hillClimbColor(
[(0,0,0),(5,5,5),(0,0,5),(0,5,0),(0,5,5),(5,0,0),(5,5,0),(5,0,5)],
(6,6,6) )
print "Random restart hill climbing tests:"
print randomRestartHillClimbColor(
[(0,0,0),(5,5,5),(0,0,5),(0,5,0),(0,5,5),(5,0,0),(5,5,0),(5,0,5)],
10)
used_colors = [(0,0,0)]
for i in xrange(10):
new_color = randomRestartHillClimbColor(used_colors, 10)
used_colors.append(new_color)
def rgbToHex(rgb):
return "#%02X%02X%02X" % rgb
print "11 colors:"
for color in used_colors:
print "<font color='%s'>%s</font><br>" % (rgbToHex(color), rgbToHex(color))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment