Skip to content

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
You can’t perform that action at this time.