# improv.py - a framework for improvisational space-filling algorithms

'''

NAME

    improv - a framework for improvisational space-filling algorithms

WHAT IS IMPROVISATION?

    "Improvisation: a creation spoken or written or composed
    extemporaneously without prior preparation."

    "To improvise: to manage in a makeshift way; to make do with whatever
    is at hand."

    "Improvisation: The spontaneous creation (e.g., of music) in the
    course of extempore performance. There is, however, always a model or
    framework that determines the scope within which the artist may
    create."

        -- definitions from various sources from Princeton University

    Improvisation, in computing terms, can be described as a
    space-filling problem.  More specifically, improvisation refers to
    the class of space-filling problems where the runtime is long enough
    that (1) outside observing processes can see the partial results at
    any time during the run, and (2) the set of types of space-filling
    pieces and their compatibility factors may be modified during the run
    to influence future filling decisions.

NOMENCLATURE

    We refer to the improvisational space-filling problem space as a
    "tableau," which must be filled with "constructs" that interrelate to
    each other without conflicts.  To achieve this, the tableau
    identifies "opportunities" with border constraints, and consults a
    dynamic "playbook" of template constructs for potential matches.

EXAMPLES

    The term "improvisation" is often equated to the theater, especially
    comedy, where a performer must entertain the audience without
    apparent preparation.  The tableau is the period of time she must
    entertain; she knows a wide-ranging set of jokes or scene constructs
    she can employ; she also adapts her routine while on stage to any new
    opportunities as presented by reactions or suggestions from her
    audience.  A good routine has an overarching theme or recalls earlier
    setups for later punchlines.

    Outside the arts, the ongoing task of city planning is also a "work
    in progress" or improvisational kind of problem.  Each land
    transaction presents new opportunities for zoning decisions, and over
    the years new land uses become popular while others fall out of
    favor.  A city will thrive if it maintains a good balance of
    residential, commercial and industrial revenue bases while also
    maintaining adequate infrastructure.

'''

#----------------------------------------------------------------------------

import random
import copy

class Tableau (object):
    '''A complete problem-space where improvised constructs are committed.

    The space must be addressable; that is, a given address string or
    tuple refers to a single specific location in the space to be filled.
    This can be numeric in one or several dimensions, or even a symbolic
    form of address that describes relationships between existing
    constructs in the space.

    Given an address, there should be only two possible conditions: the
    address is filled by a construct, or the address is not filled by a
    construct.  A single construct may fill one or many addresses, but
    two constructs cannot overlap a given address.  Addresses must be
    orderable and traversable, and not continuous (e.g., do not use real
    numbers) so as to find neighboring legal addresses.

    The improvised tableau is scanned for any opportunities to fill with
    constructs.  Opportunities are usually boundaries in the space
    between filled and non-filled areas, but can also be discovered in
    empty unfilled areas.

    Once an opportunity is found, templates for potential new constructs
    can be consulted for a fit against this opportunity.  This includes
    checking against constraints in neighboring addresses, if any.

    Potentially, this search may find many suitable templates that will
    fit the opportunity.  A selection process must decide on one
    template, and then a real construct must be built from the winning
    template.

    Existing constructs in the tableau are monitored for their value over
    their lifetime.  This in turn can raise or lower the parameters used
    to select future templates in other opportunities as they arise.

    If there is ever a situation where no template fits a given
    opportunity, the opportunity is left open and a signal is raised to
    describe the situation (the salient opportunity and nearby
    constraints) that cannot be fulfilled.  In some types of improv, this
    can create a call to action for outside participants to solve the
    problem by adding new template types during the run or performance.

    '''

    COUNT = 0

    def __init__(self, playbook=None):
        self.opportunities = { } # addr: opportunity
        self.constructs = { } # addr: construct
        self.deadends = set([]) # addrs
        self.playbook = playbook
        self.recent = [ ]

    #------------------------------------------------------------------------
    # addressing

    def occupant(self, address):
        '''Returns the construct found at a given address, or None.
        Base version checks an internal mapping of addresses to constructs.
        This may not be sufficient if an extension uses sparse storage.
        '''
        if address in self.constructs:
            return self.constructs[address]
        return None

    def occupied(self, address): return True and self.occupant(address)

    def neighbors(self, address):
        '''Returns a set of all legal neighboring addresses from one given.
        Base version always returns [ ]; override in your special Tableau.
        '''
        return [ ]

    def occupied_neighbors(self, address):
        '''Returns all legal neighboring addresses occupied with constructs.
        A convenience which filters self.neighbors() through self.occupant().
        '''
        return [ neighbor for neighbor in self.neighbors(address)
                 if self.occupant(neighbor) ]

    def vacant_neighbors(self, address):
        '''Returns all legal neighboring addresses with no constructs.
        A convenience which filters self.neighbors() through self.occupant().
        '''
        return [ neighbor for neighbor in self.neighbors(address)
                 if not self.occupant(neighbor) ]

    #------------------------------------------------------------------------
    # opportunities

    def knock(self, address):
        '''Register an address or its vacant neighbors as opportunities.'''
        if address in self.opportunities:
            return address
        if self.occupied(address):
            neighbor = None
            for neighbor in self.vacant_neighbors(address):
                self.knock(neighbor)
            return neighbor
        opportunity = Opportunity()
        self.opportunities[address] = opportunity

    def discover(self, address=None):
        '''If possible, creates a new opportunity where a new construct should
        eventually be built.  If an address is given, the opportunity
        should be "near" that spot.  Base version simply calls knock() at
        the given address; override for more specialized .
        '''
        return None

    def consult(self, address):
        '''Consults the playbook for templates that might apply to the
        given address; whether it would legally fit, or conflict, or not.
        Base version simply returns all templates straight from a playbook.
        '''
        templates = [ ]
        if self.playbook:
            templates = self.playbook.consult()
        return templates

    def select(self, address, templates):
        '''Selects one suitable template from the given legal choices.
        Base version uses random.choice() to select from the given set.
        '''
        if not templates:
            raise IndexError, 'cannot select a template from empty list'
        return random.choice(templates)

    def scout(self):
        '''Find the opportunity which is the best for attempted building.
        Base version selects an opportunity at random.
        '''
        return random.choice(self.opportunities.keys())

    def acceptable(self, address, template):
        '''Determines if the given template could legally be built into
        the address given in the tableau, checking all possible rules or
        integrity constraints.  Base version only checks for vacancy
        throughout the potential footprint.
        '''
        addresses = template.footprint(address)
        for address in addresses:
            if self.occupied(address):
                return False
        return True

    def build(self, address, template):
        '''Turns a template into a real construct and commits it to the space.
        Base version installs a realized copy of the template as the
        construct, and fills the whole footprint of the new construct.
        '''
        if not self.acceptable(address, template):
            raise KeyError, 'cannot build a construct to this address'
        if not template:
            raise ValueError, 'cannot create a construct without template'
        construct = template.realize(self, address)
        addresses = construct.footprint()
        for address in addresses:
            self.constructs[address] = construct
            if address in self.opportunities:
                del self.opportunities[address]
        return construct

    #------------------------------------------------------------------------
    # improvisation

    def trapped(self, address, template, levels=None):
        '''Determines any conflicts which would rule out a new construct.
        If levels is given and greater than zero, then conflict detection
        can recurse by attempting to improvise on all known opportunities
        on a temporary scratch copy of the current tableau.
        '''
        if not self.acceptable(address, template):
            return True
        if levels is not None and levels > 0:
            scratch = copy.deepcopy(self)
            scratch.build(address, template)
            ops = scratch.opportunities.keys()
            for each in ops:
                if scratch.improvise(each, levels-1) is None:
                    return True
        return False

    def improvise(self, address=None, levels=None):
        '''If possible, fulfills an opportunity with a new construct.
        If no address is given, a known or discovered opportunity is used.
        '''
        if not self.opportunities:
            if address:
                self.knock(address)
            if not self.opportunities:
                raise KeyError, 'create at least one opportunity first'
        if address is None:
            if self.recent:
                address = self.scout(self.recent[-1])
            else:
                address = self.scout()
            if not address:
                return None
        if not address in self.opportunities:
            raise KeyError, 'cannot improvise an undiscovered opportunity'
        templates = self.consult(address)
        if not templates:
            self.deadends.add(address)
            return None
        template = self.select(address, templates)
        if not template:
            return None
        if self.trapped(address, template, levels):
            return None
        construct = self.build(address, template)
        self.recent.append(address)
        self.recent = self.recent[-20:]
        Tableau.COUNT += 1
        return construct

#----------------------------------------------------------------------------

class Playbook (object):
    '''A reference collection of templates for potential constructs.

    The playbook is scanned for appropriate templates fitting one or more
    opportunities.
    '''
    def __init__(self):
        self.templates = { } # counter: construct

    def record(self, templates):
        if not isinstance(templates, (list, tuple, set)):
            self.record( [ templates ] )
        counter = len(self.templates)
        while counter in self.templates:
            counter += 1
        for each in templates:
            self.templates[counter] = each
            while counter in self.templates:
                counter += 1

    def consult(self):
        return self.templates.values()

class Construct (object):
    '''A construct is a building-block to complete a project.

    Over the course of the project, templates are committed as new
    constructs.  Over the lifetime of a construct, it may increase or
    decrease in value.

    The construct, when built into a tableau, has one "main" address, but
    the footprint may span multiple discrete addresses in the tableau.
    '''
    def __init__(self):
        self.appraisal = 0
        self.tableau = None
        self.address = None

    def __nonzero__(self): return True

    def realize(self, tableau, address):
        if self.tableau:
            raise Error, 'cannot realize an already-real construct'
        construct = copy.deepcopy(self)
        construct.tableau = tableau
        construct.address = address
        return construct

    def footprint(self, address=None):
        '''Return all addresses that are occupied by this construct.  If
        requesting the footprint of a construct that hasn't been built
        into a tableau, you must specify a potential address from which
        to measure the footprint.
        '''
        if not self.tableau:
            return [ address ]
        return [ self.address ]

class Opportunity (object):
    '''A site within a project which might fit certain constructs.

    A project may identify opportunities at any time, and then seek
    templates that would fulfull them as new constructs.
    '''
    def __init__(self):
        pass

    def copy(self):
        new = self.__class__()
        return new

#----------------------------------------------------------------------------

def north(addr): return (addr[0],addr[1]-1)
def east(addr): return (addr[0]+1,addr[1])
def south(addr): return (addr[0],addr[1]+1)
def west(addr): return (addr[0]-1,addr[1])

class lot (Construct):
    def __init__(self, name=None, plugs=None):
        super(lot, self).__init__()
        self.name = '--'
        if name is not None: self.name = name
        self.plugs = [ None, None, None, None ]
        if plugs is not None: self.plugs = plugs
    def __str__(self):
        return self.name
    def copy(self):
        new = super(lot, self).copy()
        new.name = self.name
        return new

class neighborhood (Tableau):
    def __init__(self, playbook=None):
        super(neighborhood, self).__init__(playbook)
        global pb
        self.nw = None
        self.se = None
    def neighbors(self, addr):
        return [ north(addr), east(addr), south(addr), west(addr) ]
    def distance(self, here, there):
        return abs(here[0]-there[0]) + abs(here[1]-there[1])
    def build(self, addr, template):
        construct = super(neighborhood, self).build(addr, template)
        self.include(addr)
        self.knock(addr)
        return construct
    def include(self, addr):
        if not self.nw: self.nw = list(addr)
        if not self.se: self.se = list(addr)
        self.nw[0] = min(self.nw[0], addr[0])
        self.nw[1] = min(self.nw[1], addr[1])
        self.se[0] = max(self.se[0], addr[0])
        self.se[1] = max(self.se[1], addr[1])
    def discover(self, addr=None):
        if not self.constructs:
            self.knock(addr)
            return addr
        if not addr:
            addr = random.choice(self.constructs.keys())
        if self.occupied(addr):
            vacancies = self.vacant_neighbors(addr)
            if vacancies:
                addr = random.choice(vacancies)
                self.knock(addr)
                return addr
            return None
        if self.occupied_neighbors(addr):
            self.knock(addr)
            return addr
        return None
    def scout(self, address=None):
        ops = [ ]
        for op in self.opportunities:
            if address and self.distance(address, op) > 8:
                continue
            if random.random() < 0.5:
                continue
            ops.append( (op, len(self.occupied_neighbors(op))) )
        ops.sort(cmp=lambda x,y: y[1]-x[1])
        return ops[0][0]
    def dlot(self, addr):
        construct = self.occupant(addr)
        if construct is None:
            if addr in self.opportunities:
                return '..'
            return '  '
        return str(construct)[:2]
    def dump(self, nw=None, se=None):
        if not self.nw: return '(empty)'
        if nw is None: nw = self.nw
        if se is None: se = self.se
        dump = [ str(nw) ]
        for ns in xrange(nw[1], se[1]+1):
            row = ''
            for ew in xrange(nw[0], se[0]+1):
                row += self.dlot((ew,ns))
            dump.append('[%s]' % row)
        wide = len(dump[-1])
        dump.append( (" " * wide + str(se))[-wide:] )
        return '\n'.join(dump)

if __name__ == '__main__':
    pb = Playbook()
    pb.record( [ lot('<>', ['  ','  ','  ','  ']),
                 lot('{}', ['  ','  ','  ','  ']),
                 lot('[]', ['  ','  ','  ','  ']),
                 ])
    n = neighborhood(pb)
    l = lot() ; l.name = '##'
    n.build( (30,40), l)
    n.build( (35,45), l)
    import os
    for i in xrange(3000):
        dump = n.dump()
        os.system('clear')
        print dump
        n.improvise()

    m = copy.deepcopy(n)
    assert m is not n
    assert (30,40) in m.constructs
    assert m.constructs[ (30,40) ] is not n.constructs[ (30,40) ]
    assert m.constructs[ (30,40) ].tableau is m

    print Tableau.COUNT