- You need to find the
Python, 201 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 | '''
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()
|
Someone recently asked me to complete this test in 30 minutes. It took me around 45 in the end.
