#! /usr/bin/python
# PageCracker1c: Size pics then find best place on page. Iterate.
# 178 lines - 43 comment/blank lines = 135 lines of code
# Mike Sweeney (mjs), 07 July 05
# Minimal version - Debug and graphics code removed.
Algorithm = '''
Input, normalize, and index the pictures
While time is left:
While layout is not complete:
Find all (possibly overlapping) spaces in current layout
For each picture (in random order):
For each space:
Find best placement of a picture in a space
Add best placement to layout
If layout is best, store it
Print best layout
'''
import sys, time, operator, bisect
from string import *
from random import randint, choice, shuffle
F,T = 0,1
def sum(L): return reduce( operator.__add__, L, 0 )
def sort(s): _s=list(s); _s.sort(); return _s
def rsort(s): _s=sort(s); _s.reverse(); return _s
# General purpose class definition:
class obj:
def __init__(s,**kw): s.__dict__.update(kw)
def upd(s,**kw): s.__dict__.update(kw)
def __repr__(s): return `s.__dict__`
ARLIMIT = 0.02
def norm( p, goalarea ):
# Normalise the picture to goal area and create valid size lists:
goalarea = max( goalarea, p.minsz )
ratio = (1.0*goalarea/p.area)**.5
w,h = int(p.w*ratio), int(p.h*ratio)
p.wlist = []
maxwid = max( pg.w, pg.h )
minwid = int( (pg.area/100)**0.5 )
inc = 1 + maxwid / 2000
for pw in range(max(minwid,w-5000),min(maxwid,w+5000),inc) :
ph1 = int( pw / (p.aspect+0.02) + 1 )
ph2 = int( pw / (p.aspect-0.02) )
if ph2-ph1 >= 0:
heights = [z for z in range(ph1,ph2+1) if pw*z>=p.minsz]
if not heights: continue
p.wlist.append( (pw,rsort(heights)) )
p.ptr = bisect.bisect( p.wlist, (w,[]) )
def mkspace( layout,x,y,vert ):
# Return the largest space in the layout including (x,y):
for a in layout:
if a.x1<=x<=a.x2 and a.y1<=y<=a.y2: return 'InObj'
x1,y1,x2,y2 = 0, 0, pg.w-1, pg.h-1
if vert: x1 = x
else: y1 = y
for a in layout:
if vert:
if a.x1<=x<=a.x2:
if a.y1 > y: y2=min(y2,a.y1-1)
else: y1=max(y1,a.y2+1)
else:
if a.y1<=y<=a.y2:
if a.x1 > x: x2=min(x2,a.x1-1)
else: x1=max(x1,a.x2+1)
for a in layout:
if vert:
if a.y1 > y2 or a.y2 < y1 or a.x2 < x1: continue
x2 = min(x2,a.x1-1)
else:
if a.x1 > x2 or a.x2 < x1 or a.y2 < y1: continue
y2 = min(y2,a.y1-1)
w,h = (x2-x1+1), (y2-y1+1)
if w*h < pg.area/100: return 'TooSmall'
if min( min(w,h)*10, max(w,h) ) * min(w,h) < pg.area/100: return 'TooThin'
return obj(x1=x1,y1=y1,x2=x2,y2=y2,w=w,h=h)
def findspaces( layout ):
# Return a list of all (possibly overlapping) spaces in the layout:
if not layout: return [ obj(x1=0,y1=0,x2=pg.w-1,y2=pg.h-1,w=pg.w,h=pg.h) ]
spaces = []
for p in layout:
for x,y,vert in ((p.x1,p.y2+1,0),(p.x2+1,p.y1,1)):
space = mkspace(layout,x,y,vert)
if type(space) != type(''): spaces.append( space )
return spaces
def jam( pic, spc, bias ):
# Try to jam a picture into a space. Return placement and fitness value:
dim1,dim2 = max(spc.w,spc.h), min(spc.w,spc.h)
opt = []
wlist = pic.wlist
initptr = max( 0, pic.ptr - bias )
initptr = min( initptr, len(wlist)-1 )
for w,h in ((dim2,dim1),(dim1,dim2)):
found = F
ptr = initptr
if wlist[0][0] > w : continue
while ptr >= 0 and wlist[ ptr ][0] > w :
ptr -= 1
limit = len(wlist)
while ptr < limit and ptr < initptr+60 and wlist[ ptr ][0] <= w :
ptr += 1
ptr -= 1
while ptr >= 0 :
pw,hlist = wlist[ptr]
if hlist[-1] >= h:
ptr -= 1
continue
for ph in hlist :
if ph <= h:
found = T
break
if found: break
if found:
fit = max( 10.0*pw/w, 10.0*ph/h ) / (5+abs(ptr-initptr))
opt.append( (fit,w,h,pw,ph) )
if not opt: return None, None
fit,w,h,pw,ph = sort(opt)[-1] # Choose highest fitness
place = obj( n=pic.n, area=pw*ph, aspect=1.0*pw/ph )
if w != spc.w : pw,ph = ph,pw
place.upd( w=pw, h=ph )
place.upd( x1=spc.x1, y1=spc.y1, x2=spc.x1+pw-1, y2=spc.y1+ph-1 )
return fit, place
def getsol( piclist, pg, bias ):
# Return one layout solution for this size bias:
shuffle( piclist ) # Or order by size?
fit, layout = 1, []
while piclist:
spaces = findspaces( layout )
bestfit, bestplace = -1, None
for i in range(len(piclist)):
for spc in spaces:
pic = piclist[i]
fit, place = jam( pic, spc, bias )
if fit == None: continue
if fit > bestfit or randint(1,10)>7:
bestfit, bestplace = fit, (i,place)
if not bestplace: return []
layout.append( bestplace[1] )
del piclist[ bestplace[0] ]
return layout
if __name__ == '__main__':
endtime = time.clock() + 15
# Process inputs into objects:
lines = [split(z) for z in open(sys.argv[1]).readlines() if strip(z)]
lines = [d[:1]+[int(e) for e in d[1:]] for d in lines]
pg = obj( w=lines[0][1], h=lines[0][2] )
pg.upd( area=pg.w*pg.h )
pics = [ obj(n=a,w=max(b,c),h=min(b,c)) for a,b,c in lines[1:] ]
for p in pics: p.upd( aspect=1.0*p.w/p.h, area=p.w*p.h, minsz=pg.area/100 )
pg.picarea = sum([p.area for p in pics])
for p in pics: norm( p, pg.area/len(pics) )
# Keep finding layouts until time is up. Keep best one:
bestarea, bestlayout = -1, []
bias = 0
while time.clock() < endtime :
layout = getsol( pics[:], pg, bias )
layarea = sum( [ p.area for p in layout] )
if layarea > bestarea: bestarea, bestlayout = layarea, layout
if not layout: bias += 5
else: bias -= 1
# Print out best solution:
for n,pl in sort([ (p.n,p) for p in bestlayout ]):
print '%s %s %s %s %s' % (pl.n,pl.w,pl.h,pl.x1,pl.y1)