Oracle generator for binary searching

binaryoracle.py

#!/usr/bin/env python
import math

class BinaryOracle(object):
  def __init__(self, min_, max_, is_int):
    self.min_ = min_
    self.max_ = max_
    self.is_int = is_int

  def get(self):
    if self.is_int:
      return int(math.floor(self._get() + 0.5))
    else:
      return self._get()

  def _get(self):
    return float(self.min_ + self.max_) / 2.0

  def lesser(self):
    self.max_ = self._get()
    return self.get()

  def greater(self):
    self.min_ = self._get()
    return self.get()


if __name__ == '__main__':
  import getopt
  import sys

  # http://stackoverflow.com/questions/1394956/how-to-do-hit-any-key-in-python
  try:
    # Win32
    from msvcrt import getch
  except ImportError:
    # UNIX
    def getch():
      import sys, tty, termios
      fd = sys.stdin.fileno()
      old = termios.tcgetattr(fd)
      try:
        tty.setraw(fd)
        ch = sys.stdin.read(1)
        if ch == "\003":
          raise KeyboardInterrupt
        return ch
      finally:
        termios.tcsetattr(fd, termios.TCSADRAIN, old)

  is_int = True
  min_ = None
  max_ = None

  try:
    opts, args = getopt.getopt(sys.argv[1:], 'if', ['int', 'float'])
    for o in opts:
      if o[0] in ('-i', '--int'):   is_int = True
      if o[0] in ('-f', '--float'): is_int = False
    if is_int:
      min_, max_ = [int(arg) for arg in args[0:]]
    else:
      min_, max_ = [float(arg) for arg in args[0:]]
  except (getopt.GetoptError, IndexError, ValueError):
    print >>sys.stderr, "usage: %s [--int|--float] <min> <max>" % sys.argv[0]
    sys.exit(2)

  oracle = BinaryOracle(min_=min_, max_=max_, is_int=is_int)
  try_ = 0
  while True:
    def help():
      print
      if is_int:
        print 'looking in [%s ... %s], current try: %s (~%d tries left)' % (oracle.min_, oracle.max_, oracle.get(), math.ceil(math.log(oracle.max_ - oracle.min_) / math.log(2)))
      else:
        print 'looking in [%s ... %s], current try: %s' % (oracle.min_, oracle.max_, oracle.get())
      print 'a: accept'
      print '1l,<-: lesser expected'
      print '2g.>+: greater expected'
      print 'r: try again'

    def limit_reached():
      print
      print 'limit reached'
      print 'a: accept'
      print 'r: try again'

    def is_oracle_effective(oracle):
      if is_int:
        return (oracle.max_ - oracle.min_ >= 1)
      else:
        return str(oracle.min_) != str(oracle.max_)

    sys.stdout.write('%s >> ' % oracle.get())
    l = getch().strip()
    if l:
      if l in 'a':
        print 'accept'
        break
      elif l in '1l,<-':
        if not is_oracle_effective(oracle):
          limit_reached()
        else:
          print 'lesser'
          oracle.lesser()
          try_ += 1
        continue
      elif l in '2g.>+':
        if not is_oracle_effective(oracle):
          limit_reached()
        else:
          print 'greater'
          oracle.greater()
          try_ += 1
        continue
      elif l in 'r':
        print 'try again'
        oracle = BinaryOracle(min_=min_, max_=max_, is_int=is_int)
        try_ = 0
        continue

    help()