Pastebin

Index: sa2-non-destructive.py
===================================================================
--- sa2-non-destructive.py      (revision 1131)
+++ sa2-non-destructive.py      (working copy)
@@ -9,8 +9,10 @@
 from copy import deepcopy
 from time import strftime

-seats_file = "seats"
-reservations_file = "reservations"
+#seats_file = "seats"
+#reservations_file = "reservations"
+seats_file = "seats_large"
+reservations_file = "reservations_large"

 HINT = 5
 NOTE = 4
@@ -18,7 +20,7 @@
 ERROR= 2
 FATAL= 1
 NONE = 0
-DEBUG_LEVEL = NOTE
+DEBUG_LEVEL = WARN

 def log(msg, level=NOTE):
     if level <= DEBUG_LEVEL:
@@ -94,6 +96,7 @@
         self.seats = []

     def __str__(self):
+#        return "reservation(len:%s)" % (self.len)
         return "reservation(len:%s,seats:%s)" % (self.len, self.seats)

     def __repr__(self):
@@ -159,6 +162,7 @@

 def neighbour(s):
     """Find a neighbour state"""
+#    print repr(s)
     (h, reservations) = s
     # Pick a random reservation
     idx = int(rand() * len(reservations))
@@ -186,23 +190,33 @@
 #    # Place the new reservation
 #    return (h, reservations)
     return  (r, row, new_idx)
-
-def E(s, patch=None):
+
+def patch_apply(s, patch):
+    (r, row, new_idx) = patch
+    seats = r.seats[:]
+
+    for ts in r.seats:
+        ts.sold -= 1
+    r.seats = []
+    rsize = len(seats)
+    for x in range(0, rsize):
+        r.seats.append(row.seats[x+new_idx])
+        row.seats[x+new_idx].sold += 1
+        return seats
+
+def patch_unapply(s, patch, seats):
+    (r, row, new_idx) = patch
+    for ts in r.seats:
+        ts.sold -= 1
+    r.seats = seats
+    rsize = len(r.seats)
+    for x in range(0, rsize):
+        row.seats[x+new_idx].sold += 1
+
+def E(s, patch):
     (h, reservations) = s
     if patch:
-        (r, row, new_idx) = patch
-        # apply patch
-        seats = r.seats[:]
-        # Delete the old reservation
-        for ts in r.seats:
-            ts.sold -= 1
-        r.seats = []
-        seats = r.seats
-        r.seats = None
-        rsize = len(r.seats)
-        for x in range(0, rsize):
-            r.seats.append(row.seats[x+new_idx])
-            row.seats[x+new_idx].sold += 1
+        seats = patch_apply(s, patch)
     energy = 0
     for r in reservations:
         for seat in r.seats:
@@ -210,13 +224,7 @@
             if seat.sold > 1:
                 energy += seat.sold * seat.score
     if patch:
-        # de-apply patch
-        for ts in r.seats:
-            ts.sold -= 1
-        r.seats = seats
-        rsize = len(r.seats)
-        for x in range(0, rsize):
-            row.seats[x+new_idx].sold += 1
+        patch_unapply(s, patch, seats)
     return energy

 def P(e, en, t):
@@ -251,23 +259,26 @@
 # make initial state with ff
 s0 = firstfit(h, reservations)

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

-kmax = 1600
+kmax = 4000
 #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:
+#    print "."
     i+=1
-    sn = neighbour(s)              #   Pick some neighbour.
+    sn = neighbour(sb)              #   Pick some neighbour.
     en = E(s, sn)                               #   Compute its energy.
     if en < eb:                              #   Is this a new best?
-        sb = deepcopy(sn); eb = en           #     Yes, save it.
+        patch_apply(sb, 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.
+        patch_apply(sb, sn); e = en
+#    print
+#        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.
@@ -275,6 +286,7 @@
 #log(h.pp(), NOTE)
 log("----------- ", NOTE)
 log("sb: ", NOTE)
+#print sb
 (h, reservations) = sb
 for r in reservations:
     log(r.pp(), NOTE)