Pastebin

import random
import math
import sys
import show_hall
from copy import deepcopy
from time import strftime

seats_file = "seats"
reservations_file = "reservations"

HINT = 5
NOTE = 4
WARN = 3
ERROR= 2
FATAL= 1
NONE = 0
DEBUG_LEVEL = NOTE

def log(msg, level=NOTE):
    if level <= DEBUG_LEVEL:
        #print "%s [%s] %s" % (strftime("%Y-%m-%d %H:%M:%S"), level, msg)
        print msg

class seat:
    def __init__(self, id, score):
        self.sold = 0  # Number of times this seat has been sold
        self.id = id   # Seat id number (written on the seat in the theatre hall)
        self.score = score # 

    def __str__(self):
        return "seat(id:%s,score:%s,sold:%s)" % (self.id, self.score, self.sold)

    def __repr__(self):
        return str(self)

    def pp(self):
        return str(self)

    def __cmp__(self, other):
        return cmp(other.score, self.score)

class hall:
    def __init__(self, rows):
        self.rows = rows

    def __str__(self):
        return "hall(rows:%s)" % self.rows

    def __repr__(self):
        return str(self)

    def pp(self):
        """Return hall as a pretty string"""
        res = "hall("
        for r in self.rows:
            res += "\n  %s" % r.pp()
            
        res += "\n)"
        return res

class row:
    def __init__(self, id, seats):
        self.id = id
        self.seats = []
        self.vacant = 0
        for s in seats:
            self.seats.append(s)
            self.vacant += 1

    def __str__(self):
        return "row(id:%s,seats:%s,vacant:%s)" % (self.id, self.seats, self.vacant)

    def __repr__(self):
        return str(self)

    def next_available(self):
        return len(self.seats) - self.vacant

    def pp(self):
        res = "row( id: %s, vacant: %s, " % (self.id, self.vacant)
        for s in self.seats:
            res += "\n    %s" % (s.pp())
        res += "\n  )"
        return res

class reservation:
    def __init__(self, id, len):
        self.len = len
        self.id = id
        self.seats = []
    
    def __str__(self):
        return "reservation(len:%s,seats:%s)" % (self.len, self.seats)
    
    def __repr__(self):
        return str(self)

    def pp(self):
        res = "reservation(id: %s, len: %s" % (self.id, self.len)
        for s in self.seats:
            res += "\n  %s" % s.pp()
        res += "\n)"
        return res

def load_hall(filename):
    row_num = 0
    seat_num = 0
    rows = []
    for s in open(filename).readlines():
        row_num += 1
        seats = []
        for ss in s.strip().split(","):
            seat_num += 1
            seats.append(seat(seat_num, int(ss)))
        rows.append(row(row_num, seats))
    return hall(rows)
    
def load_reservations(filename):
    reservations = []
    rn = 0
    for r in open(filename).readlines():
        rn += 1
        reservations.append(reservation(rn, int(r.strip())))
    return reservations

def firstfit(hall, reservations):
    for r in reservations:
        log("Finding place for reservation %s with length %s" % (r.id,r.len), HINT)
        for row in hall.rows:
            log("checking row.id %s; len(row.seats) %s; r.len %s" % (row.id, len(row.seats), r.len), HINT)
            if row.vacant >= r.len:
                log("  adding reservation %s to row %s" % (r.id, row.id), HINT)
                log("Placing reservation %s" % reservation, HINT)
                start = row.next_available()
                for x in range(0, r.len):
                    idx = start + x
                    log("  x=%s, start=%s idx=%s" % (x, start, idx), HINT)
                    s = row.seats[idx]
                    s.sold += 1 
                    r.seats.append(s)
                    row.vacant -= 1
                break
    return (hall, reservations)


#============== SIMULATED ANNEALING ===============

def temp(r):
    """yield the temperature to use, given the fraction r of the time budget 
 that has been expended so far"""
    if r == 0:
        return 1
    else: 
        return 1/r

def neighbour(s):
    """Find a neighbour state"""
    (h, reservations) = s
    # Pick a random reservation
    idx = int(rand() * len(reservations))
    r = reservations[idx]
    rsize = len(r.seats)
    #print """We randomly selected reservation %s, with %s seats""" % (r.id, rsize)
    #print r.pp()

    # Pick random row with enough seats
    row = None
    while not row:
        crow = int(rand() * len(h.rows))
        if len(h.rows[crow].seats) >= rsize:
            row = h.rows[crow]
    #print """We will now put this reservation in row %s with size %s""" % (crow, len(h.rows[crow].seats))
    # Pick a random start seat in this row
    new_idx = int(rand() * (len(h.rows[crow].seats)-rsize))
    # Delete the old reservation
    for ts in r.seats:
        ts.sold -= 1
    r.seats = []
    for x in range(0, rsize):
        r.seats.append(row.seats[x+new_idx])
        row.seats[x+new_idx].sold += 1
    # Place the new reservation
    return (h, reservations)
    
def E(s):
    (h, reservations) = s
    energy = 0
    for r in reservations:
        for seat in r.seats:
            energy -= seat.score
            if seat.sold > 1:
                energy += seat.sold * seat.score
    return energy

def P(e, en, t):
    if en < e:
        return 1
    else:
        return math.exp((e-en)/t)

def rand():
    return random.random()

def calc_emax(num_guests, h):
    seats = []
    for x in h.rows:
        for s in x.seats:
            seats.append(s)
    ss = sorted(seats)
    res = 0
    for x in range(0, num_guests):
        res += ss[x].score
    return res

def num_guests(reservations):
    res = 0
    for r in reservations:
        res += r.len
    return res
    
reservations = load_reservations(reservations_file)
h = load_hall(seats_file)

# make initial state with ff
s0 = firstfit(h, reservations)

s = s0; e = E(s)                         # Initial state, energy.
sb = deepcopy(s); eb = e                 # Initial "best" solution
k = 0                                    # Energy evaluation count.

kmax = 1600
#kmax = len(reservations) * 10
emax = 0-calc_emax(num_guests(reservations), h)

i = 0
while k < kmax and e > emax:                 # While time remains & not good enough:
    i+=1
    sn = neighbour(deepcopy(s))              #   Pick some neighbour.
    en = E(sn)                               #   Compute its energy.
    if en < eb:                              #   Is this a new best?
        sb = deepcopy(sn); eb = en           #     Yes, save it.
    if P(e, en, temp(k/kmax)) > rand():      #   Should we move to it?
        s = deepcopy(sn); e = en             #     Yes, change state.
    k = k + 1                                #   One more evaluation done
    log("""Status: en: %s, eb: %s, e: %s""" % (en, eb, e), HINT)
log(80*"=" + "\n" + str(sb), NOTE)           # Return the best solution found.

#log(h.pp(), NOTE)
log("----------- ", NOTE)
log("sb: ", NOTE)
(h, reservations) = sb
for r in reservations:
    log(r.pp(), NOTE)

log("Iterations: %s" % i, NOTE)
log(e, NOTE)
log(emax, NOTE)

hall_dr = show_hall.hall_drawer(h, reservations)
hall_dr.draw_hall()