KLab若手エンジニアの これなぁに？

import csv
import itertools
from collections import defaultdict

try:
    import psyco
    psyco.full()
except:
    pass

_FIELD_SIZE = 30
_INITIAL_FIELD = bytearray("_") * _FIELD_SIZE **2
_MINIMUM_LENGTH = 0

class Field(object):
    __slots__ = "_field _space _deadspace _minimum_line".split()

    def __init__(self, f=_INITIAL_FIELD, space=_FIELD_SIZE**2, deadspace=0, minimum_y=0):
        self._field = f
        self._space = space
        self._deadspace = deadspace
        self._minimum_line = minimum_y

    def put(self, pos, size, chr):
        """try put size to pos.

        Return new Field if can."""
        x,y = pos
        w,h = size
        F = _FIELD_SIZE
        if x + w > F or y + h > F:
            return None

        field = self._field
        t = b'_' * w
        for offs in xrange(F * y + x, F * (y+h), F):
            if field[offs:offs+w] != t:
                return None

        new_field = bytearray(field)
        t = chr * w
        for offs in xrange(F * y + x, F * (y+h), F):
             new_field[offs:offs+w] = t

        ret = Field(new_field, self._space - w*h, self._deadspace, self._minimum_line)
        ret._fill_dead_space()
        ret.calc_minimum_line()
        return ret

    def _fill_dead_space(self):
        F = _FIELD_SIZE
        M = _MINIMUM_LENGTH
        field = self._field
        _s = ord('_')
        _d = ord('#')

        for yoff in xrange(self._minimum_line * F, F*F, F):
            end = yoff + F
            pos = field.find('_', yoff, end)

            while 0 <= pos < end:
                pp = pos+1
                while pp < end and field[pp] == _s:
                    pp += 1
                count = pp - pos
                if count < M:
                    field[pos:pp] = '#' * count
                    self._space -= count
                    self._deadspace += count
                pos = field.find('_', pp, end)

        for x in xrange(F):
            vline = field[x:F*F:F]
            pos = vline.find('_')
            while 0 <= pos < F:
                pp = pos+1
                while pp < F and vline[pp] == _s:
                    pp += 1
                count = pp - pos
                if count < M:
                    field[x + F*pos : x + F*pp : F] = '#' * count
                    self._space -= count
                    self._deadspace += count
                pos = vline.find('_', pp)

    def calc_minimum_line(self):
        pos = self._field.find('_')
        if pos < 0:
            self._minimum_line = _FIELD_SIZE
        else:
            self._minimum_line = pos // _FIELD_SIZE

    def __str__(self):
        return '\n'.join(str(self._field[i:i+_FIELD_SIZE]) for i in xrange(0, _FIELD_SIZE**2, _FIELD_SIZE))

def read_stores():
    reader = csv.reader(open('depart_data.csv'))
    d = {}
    for row in reader:
        c, s, m = [x.strip() for x in row]
        w,h = map(int, s.split('x'))
        m = int(m)
        d[c] = (w, h, m)
    return d

def _solve(field, stores, remains, current, max_dead, dump=0, top=False):
    if dump > 0:
        print dump, remains, current

    b = remains[0]
    w, h, m = stores[b]
    min_wh = min(w,h)

    if dump > 0:
        print dump, "next store:", b, w, h

    next = current+m
    next_remains = remains[1:]

    pos = field._field.find('_')
    while 0 <= pos:
        x, y = pos % _FIELD_SIZE, pos // _FIELD_SIZE
        if top:
            if x > (_FIELD_SIZE - w) / 2:
                x = 0
                y += 1
                pos = y * _FIELD_SIZE
            if y > (_FIELD_SIZE - h) / 2:
                break
        if dump > 1:
            print dump, "x,y = ", x, y
        nf = field.put((x,y), (w,h), b)
        if nf is not None and nf._deadspace <= max_dead:
            if next_remains:
                res = _solve(nf, stores, next_remains, next, max_dead, dump-1)
                if res:
                    return res
            else:
                return nf
        if nf and x == 0 and field._deadspace + h > max_dead:
            pos += _MINIMUM_LENGTH
        else:
            pos += 1
        pos = field._field.find('_', pos)

    pos = field._field.find('_')
    while 0 <= pos:
        x, y = pos % _FIELD_SIZE, pos // _FIELD_SIZE
        if top:
            if x > (_FIELD_SIZE - h) / 2:
                x = 0
                y += 1
                pos = y * _FIELD_SIZE
            if y > (_FIELD_SIZE - w) / 2:
                break
        if dump > 1:
            print dump, "x,y = ", x, y
        nf = field.put((x,y), (h,w), b)
        if nf is not None and nf._deadspace <= max_dead:
            if next_remains:
                res = _solve(nf, stores, next_remains, next, max_dead, dump-1)
                if res:
                    return res
            else:
                return nf
        if x == 0 and field._deadspace + w > max_dead:
            pos += _MINIMUM_LENGTH
        else:
            pos += 1
        pos = field._field.find('_', pos)
    return False

def solve(stores, remains, area):
    remains = sorted(remains, key = lambda x: stores[x][0] * stores[x][1], reverse=True)
    field = Field()

    max_dead = _FIELD_SIZE**2 - area
    print "max_dead", max_dead

    global _MINIMUM_LENGTH
    _MINIMUM_LENGTH = min(min(stores[s][0], stores[s][1]) for s in remains)
    print "_MINIMUM_LENGTH", _MINIMUM_LENGTH

    return _solve(field, stores, remains, 0, max_dead, dump=2, top=True)

def _pre_research(stores):
    store_keys = stores.keys()
    num_store = len(store_keys)
    combis = defaultdict(list)
    while num_store > 0:
        for combi in itertools.combinations(store_keys, num_store):
            earn = 0
            area = 0
            for s in combi:
                st = stores[s]
                area += st[0]*st[1]
                earn += st[2]
            if area > _FIELD_SIZE**2: continue
            if earn < 450: continue
            combis[earn].append((combi, area))
        num_store -= 1

    print "earning, combination, area"
    for k in sorted(combis.keys(), reverse=True)[:5]:
        for v in combis[k]:
            print k,v
    return combis

if __name__ == '__main__':
    stores = read_stores()
    combis = _pre_research(stores)
    for earn in sorted(combis.keys(), reverse=True):
        print "target:", earn
        for comb, area in combis[earn]:
            field = solve(stores, comb, area)
            if field:
                print earn
                print str(field).replace('#', '_')
                break
        else:
            continue
        break