Dropbox Challenge - 1 Packing Your Dropbox

solution.py

#!/usr/bin/python

"""
Amar Pai ([email protected])

Solution to Dropbox challenge - Packing Your Dropbox
http://www.dropbox.com/jobs/challenges#packing-your-dropbox

I've had this problem on the brain and have been unable to
stop thinking about it, so I finally hacked out a rudimentary
solution.  I need to get back to my actual job, but if time
permits I'll send in a more cleaned up version later.  The
biggest thing to consider is that bin packing is NP-Hard
so brute force solution isn't really feasible.  Thus any
solution (I think) will be an approximation using some
heuristic.  There's probably room for improvement in my
approach-- it's not guaranteed to give the smallest possible
container in all cases-- but I think this is a decent start.

No attempt is made to bulletproof/validate the input.  And
of course in real life there'd be unit tests etc.  This is
all I can do for now.  Not an easy problem!  I wonder how
many good solutions you guys get?

Usage:
  chmod a+ux rectpack.py
  cat input.txt | rectpack.py

Version 1.0 (3/23/11)
"""

import itertools
import Tkinter as tk
import random 
import sys

class Point(object):
  def __init__(self, x, y):
    self.x = x
    self.y = y

  def __repr__(self): 
    return "(%d,%d)" % (self.x,self.y)

ORIGIN = Point(0,0)

class Rect(object):
  def __init__(self, width, height, pos=ORIGIN):
    self.width = width
    self.height = height
    self.rotated=False
    self.place(pos) # calculates coords

  def calculate_coords(self):
    self.ul=self.pos
    self.ur=Point(self.ul.x+(self.width-1), self.ul.y)
    self.lr=Point(self.ur.x, self.ur.y+(self.height-1))
    self.ll=Point(self.ul.x, self.lr.y)

  def __repr__(self):
    return "w=%d h=%d ul=%s" % (self.width, self.height, self.ul)

  def rotate(self):
    self.width, self.height = self.height, self.width
    self.rotated = not self.rotated
    self.calculate_coords()

  def place(self,pos):
     self.pos = pos
     self.calculate_coords()

  def overlaps(self, other):
  	return not (self.ul.x > other.ur.x or self.ur.x < other.ul.x or self.ur.y > other.lr.y or self.lr.y < other.ur.y)


def pack_rects(input_rects):
  """ 
  Takes a list of input rects and attempts to find the arrangement with
  minimal total bounding area.  Uses simple greedy algorithm, not guaranteed
  to find the absolute minimum.
  Returns: rectlist,width,height,area (representing best config found)
  """
  rects=[Rect(r.width,r.height,r.pos) for r in input_rects]
  done = []
  open_positions = [Point(0,0),]
  bounding_x = 0
  bounding_y = 0
  total_area = 0
  for r in rects:
    #print 'placing %s'  % r
    #print 'current bounding x y: %d, %d' % (bounding_x,bounding_y)
    #print 'open positions: %s' % open_positions
    best_pos = None
    best_pos_is_rotated = None
    best_bounding_x = None
    best_bounding_y = None
    best_total_area = None
    # go through all open positions, placing cur rect (rotated/non) at each
    # pick the position/rotation combo that minimizes total bounding area
    # (skipping positions that overlap)
    for pos in open_positions: 
      for should_rotate in (0,1):
        if should_rotate:	
          r.rotate()
        r.place(pos)
        overlap = False
        for other in done:
          if other.overlaps(r):
            overlap = True
            break
        if not overlap:
          temp_bounding_x = max(bounding_x, r.ur.x)
          temp_bounding_y = max(bounding_y, r.lr.y)
          temp_total_area = (temp_bounding_x+1) * (temp_bounding_y+1)
          if not best_total_area or (temp_total_area < best_total_area):
            best_pos = pos
            best_pos_is_rotated = r.rotated
            best_bounding_x = temp_bounding_x
            best_bounding_y = temp_bounding_y
            best_total_area = temp_total_area
    # done looking at positions.   
    # place the rect at best_pos and update everything else accordingly
    if r.rotated != best_pos_is_rotated:
      r.rotate()
    r.place(best_pos)
    open_positions.remove(best_pos)
    # add two new positions - upper right corner and lower left corner of newly placed rect
    open_positions.append(Point(r.ur.x+1,r.ur.y))
    open_positions.append(Point(r.ll.x,r.ll.y+1))
    bounding_x = best_bounding_x
    bounding_y = best_bounding_y
    total_area = best_total_area
    done.append(r)
  return rects,bounding_x+1,bounding_y+1,total_area
      
def pack_rects_n(input_rects,n):
  """ 
  Do n passes of packrects, randomly shuffling inputs each time.
  Return rectlist,width,height,area (best config found)
  TODO: save and return all configs w/ area=minarea, instead of just one.  
  """
  min_rects=min_width=min_height=min_area=None
  for i in xrange(0,n):
    random.shuffle(input_rects) 
    positioned_rects,width,height,area=pack_rects(input_rects)
    if not min_area or area<min_area:
	    min_rects,min_width,min_height,min_area= positioned_rects,width,height,area
  return min_rects,min_width,min_height,min_area


def draw_using_stderr(rects,w,h):
  """ Draw rects that have been arranged into wxh box to stderr """
  rects_by_y = {}
  rects.sort(key=lambda r:(r.ul.y,r.ul.x))
  for y, rectgroup in itertools.groupby(rects,lambda r: r.ul.y):
    rects_by_y[y] = [r for r in rectgroup]
  sys.stderr.write('%dx%d:\n'%(w,h))
  cur_rects = []
  for y in xrange(0,h):
    s = list(" " * w)
    finished_rects = []
    for r in cur_rects:
      # first draw existing rects
      if r.lr.y == y:
        # bottom edge - schedule for removal
        s[r.ll.x] = "+"
        s[r.lr.x] = "+"
        for x in range(r.ll.x+1,r.lr.x):
          s[x] = "-"
        finished_rects.append(r)
      else:
        # left or right in-between edge
        s[r.ul.x] = "|"
        s[r.ur.x] = "|"
    for r in finished_rects:
      cur_rects.remove(r)
    # add any new rects with upper edge starting at current y
    if y in rects_by_y:
      for r in rects_by_y[y]:
         s[r.ul.x] = "+"
         s[r.ur.x] = "+"
         for x in range(r.ul.x+1,r.ur.x):
           s[x] = "-"
         cur_rects.append(r) 
    padded_s = [" %s " % item for item in s]
    sys.stderr.write("%s\n" % ''.join(padded_s))

def dropbox_main():
  """ 
  Read input rects from stdin, find arrangement w/ minimal total area
  Output: area (stdout), arrangement (stderr)
  """
  lines = [line.strip() for line in sys.stdin.readlines()]
  expected=int(lines[0])
  input_rects=[]
  if len(lines)-1 != expected:
    sys.exit('Error!  Expected %d lines, got %d' % (expected,len(lines)-1))
  for l in lines[1:]:
     s_width,s_height=l.split(' ')
     input_rects.append(Rect(width=int(s_width),height=int(s_height),pos=Point(0,0)))
  rects,w,h,area=pack_rects_n(input_rects,100) # TODO make num_passes configurable
  draw_using_stderr(rects,w,h)
  if w*h != area:
    raise Exception("wha? %dx%d != %d" % (w,h,area))
  print area

if __name__ == "__main__":
  dropbox_main()

##### junk to clean up /incorporate later #####

BIG_INPUT_RECTS=[Rect(*tup) for tup in [(100,75),(40,99),(35,72),(77,22),(77,11),(13,36),(102,66),(83,71),(70,60),(30,10),(104,34),(60,110),(60,120),(140,90),(30,30),(30,30),(30,30),(30,30),(40,20),(70,10),(90,15),(30,30),(30,30), (30,30), (40,150),(30,90),(20,20),(25,55),(70,10), (10,80), (50,60),(30,30),(30,30), (10,110)]]

def bigtest():
	inputrects=BIG_INPUT_RECTS 
	#rects= [Rect(*tup) for tup in [ (10,80), (10,110)]]
	print "Before:"
	for i, r in enumerate(inputrects):
	   print "rect[%d]: %s" % (i, r)

	print "Packing..."
	rects,width,height,area = packrects_n(inputrects,100)
	print "Packed into rectangle, w=%d, h=%d, area=%d" % (width,height,area)
	print "After:"
	for i, r in enumerate(rects):
	   print "rect[%d]: %s" % (i, r)

	for i in rects:
	   for j in rects:
	      if i != j:
		if i.overlaps(j):
		  print 'Error! %s overlaps %s' % (i,j)

	draw_using_tk(rects)

def randcolor():
 # create hex random color string acceptable to Tkinter eg. #ff0507
 rcolor = '#' + "".join(["%02x"%random.randrange(256) for x in range(3)])
 return rcolor


def draw_using_tk(rects):
	root = tk.Tk()
	canvas=tk.Canvas(root,width=width,height=height,bd=0,highlightthickness=0,highlightbackground="black")
	canvas.pack(expand=0,fill=tk.NONE,side=tk.TOP)
	for r in rects: 
	  canvas.create_rectangle(r.ul.x, r.ul.y, r.lr.x, r.lr.y, outline="black",fill=randcolor(),width=1)
	root.mainloop()


def sort_by_longest_edge(rects, reverse=True):
   """ sort rects by longest edge.  descending order by default """
   rects.sort(key=lambda x:max(x.height, x.width), reverse=reverse)