[Assorted-commits] SF.net SVN: assorted:[1795] problems/other

[<yan...@us...>]

Revision: 1795
          http://assorted.svn.sourceforge.net/assorted/?rev=1795&view=rev
Author:   yangzhang
Date:     2011-07-06 21:54:31 +0000 (Wed, 06 Jul 2011)

Log Message:
-----------
Add circular bisect problem

Added Paths:
-----------
    problems/other/circular-bisect/
    problems/other/circular-bisect/go.py

Added: problems/other/circular-bisect/go.py
===================================================================
--- problems/other/circular-bisect/go.py	                        (rev 0)
+++ problems/other/circular-bisect/go.py	2011-07-06 21:54:31 UTC (rev 1795)
@@ -0,0 +1,49 @@
+def coerce(f):
+  def wrap(*args):
+    try: return f(*args)
+    except: return -1
+  return wrap
+
+def f(xs):
+  if xs == []: raise Exception()
+  m = len(xs) / 2
+  left = xs[0]
+  mid = xs[m]
+  right = xs[-1]
+  if left <= mid <= right: return 0
+  if left > mid: return f(xs[1:m+1]) + 1
+  if mid > right: return f(xs[m+1:]) + m+1
+
+def b(x, xs):
+  if xs == []: raise Exception()
+  m = len(xs) / 2
+  if xs[m] == x: return m
+  if x < xs[m]: return b(x, xs[:m])
+  if x > xs[m]: return b(x, xs[m+1:]) + m+1
+
+def g(x, xs):
+  if xs == []: raise Exception()
+  if xs == [x]: return 0
+  m = len(xs) / 2
+  left = xs[0]
+  mid = xs[m]
+  right = xs[-1]
+  if left <= mid <= right:
+    if left <= x < mid: return g(x, xs[:m])
+    if mid <= x <= right: return g(x, xs[m:]) + m
+    raise Exception()
+  if left > mid:
+    if mid <= x <= right: return g(x, xs[m:]) + m
+    else: return g(x, xs[:m])
+  if mid > right:
+    if left <= x < mid: return g(x, xs[:m])
+    else: return g(x, xs[m:]) + m
+
+def rot(i, xs): return xs[i:] + xs[:i]
+
+for n in xrange(6):
+  for i in xrange(n):
+    xs = rot(i, range(n))
+    print 'n=%s n/2=%s i=%s xs=%s f=%s g=%s b=%s G=%s B=%s' % \
+        (n, n/2, i, xs, f(xs), g(n/2, xs), b(n/2, range(n)),
+                        coerce(g)(n/2-.5, xs), coerce(b)(n/2-.5, range(n)))


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.