quads into quads @ output2012

quads.py

#!/usr/bin/env python

import sys
import random
import json

class QuadPuzzle:

    def __init__(self, big, data, rand=True):
        self.big = big
        self.spaces = [(0, 0, big, big)]
        self.fitted = []
        self.data = list(data)

        if rand:
            random.shuffle(data)

    def solve(self):
        spaces = self.spaces
        data = self.data

        while data:
            block = data.pop()

            #print "block:", block

            for index, space in enumerate(spaces):
                if min(space[2:]) >= block:
                    self.fit_block(block, index)
                    break

            self.refit_spaces()

    def fit_block(self, block, index):
        spaces = self.spaces

        #print "fit", block, "into", spaces[index]

        x, y, width, height = spaces[index]
        del spaces[index]

        self.fitted.append((x, y, block))

        if x > y:
            self.insert_space((x + block, y, width - block, height))
            self.insert_space((x, y + block, block, height - block))
        else:
            self.insert_space((x + block, y, width - block, block))
            self.insert_space((x, y + block, width - block, height - block))

    def insert_space(self, space):
        spaces = self.spaces

        #print space

        if space[0] + space[2] > self.big or space[1] + space[3] > self.big:
            raise Exception("unfitting space")

        size = max(space[2:])

        for index, test in enumerate(spaces):
            if max(test[2:]) < size:
                spaces.insert(index, space)
                return
        else:
            spaces.append(space)
            return

    def refit_spaces(self):
        return

        spaces = self.spaces

        for a in spaces:
            for b in spaces:
                if max(a[:2]) > max(b[:2]):
                    bigger = a
                    smaller = b
                else:
                    bigger = b
                    smaller = a

    def show(self):
        self.show_details()

        print "=" * 30

        self.show_stats()

    def show_details(self):
        big = self.big
        fitted = self.fitted

        out = [[' '] * big for _ in range(big)]

        print "-" * big + '+'

        for i, (x, y, size) in enumerate(fitted):
            for n in range(size):
                for m in range(size):
                    out[x+n][y+m] = chr(i + ord('0'))

        for line in out:
            print ''.join(line) + "|"

        print "-" * big + '+'

        print

        for x, y, size in fitted:
            print "%2i x %2i: %i" % (x, y, size)

    def show_stats(self):
        print "Size:\t\t%i" % self.size()
        print "Missing:\t%i" % self.missing()

    def size(self):
        return sum(s**2 for _, _, s in self.fitted)

    def missing(self):
        return self.big ** 2 - self.size()

def brute_solve(big, data):
    puzzles = []

    puzzles.append(QuadPuzzle(big, data, False))

    for i in range(1000):
        puzzles.append(QuadPuzzle(big, data, True))

    for puzzle in puzzles:
        puzzle.solve()

    puzzles.sort(key=lambda p: p.size())

    #for puzzle in puzzles:
        #print "%s:\t%i" % (puzzle.mode, puzzle.size())

    return puzzles[-1]

def main(args=sys.argv[1:]):
    if len(args) >= 1:
        inp = open(args[0])
    else:
        inp = sys.stdin

    for line in ('[%s]' % l.strip()[1:-1] for l in inp):
        big, data = json.loads(line)

        solution = brute_solve(big, data)

        print "===> ", line
        solution.show()

if __name__ == '__main__':
    sys.exit(main())