Commits

Seonghoon Kang committed 9cdec7f

snapshot

Comments (0)

Files changed (5)

 
 # XXX this should really have to be dependent to each test case,
 # but all test cases in question use Cs/Cn ratio of 2.
+best = 999999999
 nexts = 0
-elims = gol.best_general_elimination(cells, gol.parse_rulestring(rule))
-if len(elims) + 2 < len(cells):
-    nexts = 1
-    cells = list(elims)
+for k, v in gol.best_general_elimination(cells, gol.parse_rulestring(rule)):
+    if best > k * 2 + len(v):
+        best = k * 2 + len(v)
+        cells = v
 
 print >>sys.stderr, 'writing %d NEXTs and %d SETs...' % (targetgen + nexts, len(cells))
 cells.sort()
 import sys
 import gol
 
+print >>sys.stderr, 'reading and optimizing built-in elimination rules'
 elimrules = gol.read_elimrules()
 if elimrules is None: raise SystemExit(2)
 
             continue
         patterns.setdefault(patidx, []).append(line)
 
+flags = gol.parse_rulestring(rule)
+maxnexts = 1 # we want to try at least the minimal vertex cover approach...
+i = 0
+for patidx, pat0 in patterns.items():
+    i += 1
+    if i % 100 == 0:
+        print >>sys.stderr, 'examining patterns: %d out of %d' % (i, len(patterns))
+    key = (rule, '\n'.join(pat0))
+    elims = elimrules.get(key)
+    if elims is None:
+        # use general strategies
+        pat = set((x, y) for x, line in enumerate(pat0)
+                         for y, c in enumerate(line) if c == 'o')
+        elimrules[key] = elims = gol.best_general_eliminations(pat, flags)
+    maxnexts = max(maxnexts, max(n for n, _ in elims))
+
 # try to eliminate each components with the minimal cost
-maxnexts = 1 # we want to try at least the minimal vertex cover approach...
-for patidx, pat in patterns.items():
-    pat = '\n'.join(pat)
-    try: maxnexts = max(maxnexts, max(n for n, _ in elimrules[rule, pat]))
-    except KeyError: pass
 mincost = 99999999999999
 best = None
 bestelims = None
-flags = gol.parse_rulestring(rule)
 for nexts in xrange(maxnexts + 1):
     sets = 0
     allelims = {}
     for patidx, pat0 in patterns.items():
         patcnt = patterncounts[patidx]
-        elims = elimrules.get((rule, '\n'.join(pat0)))
-        if elims:
-            isets, ielims = min((len(v), v) for k, v in elims if k <= nexts)
-            sets += isets * patcnt
-            allelims[patidx] = ielims
-        else:
-            pat = set((x, y) for x, line in enumerate(pat0)
-                             for y, c in enumerate(line) if c == 'o')
-            if nexts > 0: pat = gol.best_general_elimination(pat, flags)
-            sets += len(pat) * patcnt
-            allelims[patidx] = pat
+        elims = elimrules[rule, '\n'.join(pat0)]
+        isets, ielims = min((len(v), v) for k, v in elims if k <= nexts)
+        sets += isets * patcnt
+        allelims[patidx] = ielims
     cost = sets * cs + nexts * cn
     print >>sys.stderr, '%d sets, %d nexts -> cost %d' % (sets, nexts, cost)
     if mincost > cost:
                 v = set((x, y) for x, line in enumerate(rot(v))
                                for y, c in enumerate(line) if c == 'o')
                 elims0[k] = pat ^ v
-            gelims = best_general_elimination(pat, flags)
-            if 1 not in elims0 or len(gelims) < len(elims0[1]): elims0[1] = gelims
+            for k, v in best_general_eliminations(pat, flags):
+                if k not in elims0 or len(v) < len(elims0[k]): elims0[k] = v
             elimrules[rule, '\n'.join(pat0)] = sorted(elims0.items())
 
     # verification (duh!)
 
     return removed
 
-def best_general_elimination(s, (bflags, sflags)):
-    best = greedy_elimination(s, (bflags, sflags)) # baseline
+def best_general_eliminations(s, (bflags, sflags)):
+    elims = {0: s, 1: greedy_elimination(s, (bflags, sflags))} # baseline
 
-    # other elimination strategies are only effective for small enough patterns
+    # approximate minimal vertex cover
+    # only possibly effective for small patterns
     if len(s) < 1000:
-        # approximate minimal vertex cover
         if bflags & 0b100: # has B2
             minvc = min_vertex_cover_2(s)
         else:
             minvc = min_vertex_cover_1(s)
-        if len(best) > len(minvc):
-            best = minvc
+        if len(elims[1]) > len(minvc):
+            elims[1] = minvc
 
-        # single SET evolution
-        if len(best) > 1:
-            for xy in s:
-                ss = set(s)
-                ss.discard(xy)
+    # single SET evolution
+    # may be effective but evolution cost is very large
+    if len(s) < 100 and len(elims[1]) > 1:
+        for xy in s:
+            ss = set(s)
+            ss.discard(xy)
+            for nexts in xrange(1, 50):
                 ss = evolve(ss, (bflags, sflags))
                 if not ss:
-                    best = set([xy])
+                    elims[nexts] = set([xy])
                     break
 
-    return best
+    return sorted(elims.items())
 
 ./generate.sh 500 data/input7.rle analysis/input7-gen500.rle analysis/population7.csv
 ./leastcost.sh 2 4 < analysis/population7.csv
 
-Error: population 0 expected, 53505 actual (table size 53505)
-okay, patched. cost=155834
-
 #8
 1000000 1000000 4999980 5 700 B3/S23
 lots of gliders...
 
 ----
 
+TODO
+
+= new strategy: exhaustive
+  - general backtracking
+  - (re)sets then next then resets then ...
+  - maximum width limitation (maybe 30), board is represented as a row of uint32_t
+
+uint32_t pl, l, nl;
+uint32_t a12 = pl ^ (pl << 1), b12 = pl & (pl << 1);
+uint32_t a34 = (pl >> 1) ^ (l << 1), b34 = (pl >> 1) & (l << 1);
+uint32_t a56 = (l >> 1) ^ (nl << 1), b56 = (l >> 1) & (nl << 1);
+uint32_t a78 = nl ^ (nl >> 1), b78 = nl & (nl >> 1);
+// ...
+uint32_t g8 = ..., g4 = ..., g2 = ..., g1 = ...;
+//uint32_t lnew = (l & ~g8 & ~g4 & g2) | (~l & ~g8 & ~g4 & g2 & g1);
+//uint32_t lnew = ~g8 & ~g4 & g2 & (l | (~l & g1));
+uint32_t lnew = ~g8 & ~g4 & g2 & (l | g1);
+if (lnew & 0x80000001u) { /* overflow */ }
+
+= permanent elimination rule database
+
+----
+
 v = map(int,'''
+4 216 1499934 8178420 1020352 499250 411684 21790 5002765
 4 216 2245771 8178420 1020352 499250 436444 34020 5002855
 ''' '''
 4 166 2245528 8178420 701427 499250 436444 24392 5001495
 		POSITIONFILE=analysis/position$CASE-gen$INITNEXTS.txt
 		if [ \! -f "$PATTERNFILE" -o \! -f "$POSITIONFILE" ]; then
 			make split
-			$PYTHON fromrle.py $GEN $POP < $TARGET | ./split $PATTERNFILE $POSITIONFILE
+			$PYTHON fromrle.py $CS $CN < $TARGET | ./split $PATTERNFILE $POSITIONFILE
 		fi
 	fi
 	TEMPFILE=/tmp/$$-output.txt