'''
Created on 3 Dec 2013
@author: bakera
'''
import unittest
import random
import numpy as np
from ctypes import *
import sys
if ((sys.platform == 'linux2')):
from termcolor import colored, cprint
class Line(object):
"""
class represents a line or stream of Heads or Tails that we want to search.
e.g. H H T T H H H
from line import Line
Line(verbose=True, width=60).search(n=100, tolerance=5)
"""
def __init__(self, n=5, verbose=False, tolerance=1, width=60):
"""
n : int
length of the line to create
verbose : bool
determine whether you want to see all the machinery output to the console, default False
tolerance : int
how many H or T flips can you allow in your run, default 1 as in original problem
however, seems fast at multiples. could be a benefit in this method.
"""
self.n = n
self.verbose = verbose
self.screen_width = width
self.tolerance = tolerance
self.__generate()
self.toss_map = {1:'H', 0:'T'}
# some output machinery
if (not (sys.platform == 'linux2')):windll.Kernel32.GetStdHandle.restype = c_ulong
if (not (sys.platform == 'linux2')):self.h = windll.Kernel32.GetStdHandle(c_ulong(0xfffffff5))
# something for nice look
self.colour_map = {1: 12, 2: 12, 3: 13, 4: 14, 5: 15, 6: 9, 0:4} # empty cells colour black
@property
def is_verbose(self):
return self.verbose
def prettyprintparam(self, start, end):
"""
start : int
location of the start of the match array entry in the self.line array
end : int
location of the end of the match array, relative tothe self.line array
returns : none
some way to nicely format the output, since we are on a dos command line
let's not get too fancy and just colour the H and T
"""
for i, row in enumerate(self.line.flat):
i = i + 1
color = self.colour_map[row]
if (not (sys.platform == 'linux2')):
windll.Kernel32.SetConsoleTextAttribute(self.h, color)
if i == 0:
sys.stdout.write("\n%s"%(self.toss_map[row]))
elif (i % self.screen_width == 0) :
if (i >= start+1 and i <= (start+end)):
# 13 purple, also nice, green 2 default
windll.Kernel32.SetConsoleTextAttribute(self.h, 2)
sys.stdout.write(" %s\n"%(self.toss_map[row]))
windll.Kernel32.SetConsoleTextAttribute(self.h, color)
else:
sys.stdout.write(" %s\n"%(self.toss_map[row]))
sys.stdout.flush()
elif (i >= start+1 and i <= (start+end)):
# 13 purple, also nice, green 2 default
windll.Kernel32.SetConsoleTextAttribute(self.h, 2)
sys.stdout.write(" %s"%(self.toss_map[row]))
windll.Kernel32.SetConsoleTextAttribute(self.h, color)
else:
sys.stdout.write(" %s"%(self.toss_map[row]))
if (not (sys.platform == 'linux2')):windll.Kernel32.SetConsoleTextAttribute(self.h, 15) # return to white
def check_with_tolerance(self, n, h,t, tolerance):
'''
n : int
offset position, relative to the start of the self.line array
h : obejct numpy.array
array object populated with an array that we are trying to match, represents head version
t : obejct numpy.array
array object populated with an array that we are trying to match, represents tail version
tolerance : int
controls how many flips we can tolerate in the search
for heads arrays match based on sum(h) from line = sum(h)
'''
if not len(self.line) > 0:
return [True, 1, h]
for offset in np.arange(0,len(self.line),1):
if self.verbose:
print 'offset', offset, 'n', n, 'offset+n', offset+n, 'self.line[offset:offset+n]', self.line[offset:offset+n]
if self.line[offset:offset+n].shape[0] >= h.shape[0] and \
self.line[offset:offset+n].shape[0] >= t.shape[0]:
spread = np.abs(np.sum(self.line[offset:offset+n]) - np.sum(h))
if spread <= tolerance:
return [True, offset, h]
return [False, 0, None]
def __generate(self):
"""
build me a random line, size self.n, of H and T. H ==1, T ==0
"""
self.line = np.reshape(np.array([random.randint(0,1) for a in np.arange(0,self.n,1)]), (self.n))
def search(self, n=5, tolerance=1):
"""
n : int
specify the size of the line, before generating and iterating line
"""
self.n = n
self.tolerance = tolerance
self.__generate()
self.__iterate_line()
sys.stdout.write(" \n")
sys.stdout.flush()
def __iterate_line(self):
"""
basic idea is that we generate progressively smaller h and t arrays
and try and match these to the test line, based on match properties
complexity of this might appear O(n^2) however in practice the number
of checks is very small
"""
if self.n == 0 or self.n == 1:
if self.is_verbose:
print '*********enter line size >= 1, and not 0.'
return
# start with same size and iterate down in size.
# seems unlikely that we will match from start, but possible for smaller run lengths.
for y in np.arange(self.n, 0, -1):
#value = self.check(y, np.array([1 for a in np.arange(0,y,1)]), t = np.array([0 for a in np.arange(0,y,1)]))
value = self.check_with_tolerance(y, \
np.array([1 for a in np.arange(0,y,1)]), \
np.array([0 for a in np.arange(0,y,1)]), self.tolerance)
if value[0]:
self.prettyprintparam(value[1],value[2].shape[0])
break
class Test(unittest.TestCase):
"""
simple test class
"""
def testLineTolerance(self):
"""
idea here is that the
"""
b = Line(verbose=False, tolerance=2)
b.search(n=75)
def testLineSimple(self):
b = Line()
b.search(n=48)
def testLineCorner(self):
b = Line()
b.search(n=1)
c = Line()
c.search(n=0)
def testLarge(self):
# setup some parameters
max_iteration = 1000
min_line_size = 10
max_line_size = 100
min_tolerance = 1
max_tolerance = 25
[Line(tolerance=random.randint(min_tolerance,max_tolerance)).search(n=random.randint(min_line_size,max_line_size)) for x in np.arange(0,max_iteration,1)]
if __name__ == "__main__":
#import sys;sys.argv = ['', 'Test.testBuildCross']
unittest.main()
