BrowserUk:
Update 2: I couldn't leave it alone (damned OCD), so I think it works now. I definitely had a few code problems, and the new version looks pretty decent to me. (The variable names could be better, but I'm a bit too tired to mess with it.
It looks like one of my previous editing passes removed the reason that I coded it in Python. At $work, I'm having to use Python and JavaScript to write some stuff. I chose the lesser of two evals.
(Believed) correct code:
#!/usr/bin/env python
import pprint
import random
import sys
# Set up your needle, haystack and alphabet size
haystack = "0000111010011100101110110111000111101011110011111011111110
+000000100010010000101001010100000110100011001001100010110101011001101
+1000000"
hay_len = len(haystack)
ruler = ""
cases = [
{ 'NDL': "100001010010101000001101", 'syms':3, 'sz':8 },
{ 'NDL': "100001010010101000001101", 'syms':4, 'sz':6 },
{ 'NDL': "100001010010101000001101", 'syms':6, 'sz':4 },
{ 'NDL': "100001010010101000001101", 'syms':8, 'sz':3 },
{ 'NDL': "000010100101010000011010", 'syms':3, 'sz':8 },
{ 'NDL': "000010100101010000011010", 'syms':4, 'sz':6 },
{ 'NDL': "000010100101010000011010", 'syms':6, 'sz':4 },
{ 'NDL': "000010100101010000011010", 'syms':8, 'sz':3 },
{ 'NDL': "1000010100101010000011010", 'syms':5, 'sz':5 }
]
case = 0
try:
case = int(sys.argv[1])
except:
pass
needle = cases[case]['NDL']
num_syms = cases[case]['syms']
symbol_size = cases[case]['sz']
def main():
global ruler
print "\n{0}\nHaystack: {1}\n Needle: {2}\n".format(syms(70, '-')
+, haystack, needle)
# Use brute force to find all matches
positions = brute_force(needle, haystack)
if len(positions)>0:
ruler = "".join([ "V" if x in positions else " " for x in rang
+e(0, len(haystack)) ])
print "Brute force:\n{0}\n{1}".format(ruler, haystack)
print "{0}{1}\n".format(spaces(positions[0]), needle)
else:
print "Brute force: not found"
if not find_needle(haystack, needle, num_syms, symbol_size):
print "**** Case failed! ****"
def find_needle(haystack, needle, num_syms, symbol_size):
sym_marker = syms(symbol_size, '^')
needle_syms = [ needle[i*symbol_size:(i+1)*symbol_size] for i in r
+ange(0, num_syms)]
max_shift = (num_syms-1)*symbol_size
print "Modified BM search: {0} syms of {1} bits: {2}".format(
num_syms, symbol_size, ", ".join(needle_syms))
# Compute delta table
dd1 = { }
for i in reversed(range(0, (1<<symbol_size))):
sym = to_binstr(i, symbol_size)
tmp = brute_force(sym, needle)
if len(tmp)>0:
bitofs = tmp[-1]
shift = max_shift - bitofs
ttt = ", ".join(map(str,tmp))
dd1[sym] = shift #bitofs
# Uncomment to see the delta table
#print pprint.pprint(dd1)
# Search loop
print "Searching for a needle in the haystack"
needle_ptr = 0
while needle_ptr + len(needle) <= len(haystack):
cmp_ptr = needle_ptr + max_shift
found = haystack[cmp_ptr:cmp_ptr+symbol_size]
print "\n{0}\n{1}".format(ruler, haystack)
print "{0}{2} (pos={1})".format(spaces(cmp_ptr), cmp_ptr, sym_
+marker)
print "{0}{1}".format(spaces(cmp_ptr), found)
print "{0}{1}".format(spaces(needle_ptr), needle)
if found in dd1:
if dd1[found] == 0:
fl_match = True
for t in range(0, num_syms):
if needle_syms[t] != haystack[needle_ptr + t*symbo
+l_size:needle_ptr + (t+1)*symbol_size]:
fl_match = False
if fl_match:
print "MATCH FOUND!"
print "\n{0}\n{1}\n{2}{3}\n".format(haystack,ruler
+,spaces(needle_ptr),needle)
return True
else:
print "Byte matched, string mismatch, trying next
+position"
needle_ptr += 1
else:
print "found {0}, delta=>{1}".format(found, dd1[found]
+)
needle_ptr += dd1[found]
else:
print "not found, big shift"
needle_ptr += len(needle)-symbol_size
return False
def to_binstr(n,len):
bv = [ "1" if n & (1<<x) else "0" for x in range(0, len)]
return "".join(bv)
def brute_force(needle, haystack):
"""Brute-force find all matching positions of needle in haystack""
+"
positions = []
for i in range(0, len(haystack)-len(needle)+1):
if needle == haystack[i:i+len(needle)]:
positions.append(i)
return positions
def syms(n, sym):
return "".join([ sym for x in range(0, n)])
def spaces(n):
return syms(n, ' ')
if __name__ == '__main__':
main()
I should probably recode it in perl at some point. Old code & such below in readmore tags, should you be interested.
(BTW: pun was intended.)
...roboticus
When your only tool is a hammer, all problems look like your thumb. |