Friday, June 22, 2007

Burglars cops treasures and python, this time we got it all.

So we got these burglars who have this map that shows where the treasures are. Hmmm right, this is clear. Then we got these cops that want to stop the burglars. Now the map looks something like this.

4 3 3 3
3 -1 2
-1 -1 -1
3 12 7

The first row contains some stupid numbers showing different things, because the solution of this problem is supposed to be written in C, but hey fuck C and it's stupid libraries ( this from a guy who makes a living like a professional C programmer - me ) The most important number from the first row is the second one which shows the time ticks the burglars have before the cops show up. The rest of the numbers say what's the array height and width (useless in python and in fact in C if you take the time to code is right).

Now the rules are simple. The burglars have the map so they know where the treasures are. Each treasure is represented by a positive number showing the amount of money the gain when they reach it. The cells with negative numbers does not contain treasures and they cost money to be dug. Each cell is dug for one tick time. The cops will come in K ticks of time where K is the second number in the first row. In order to get to a cell the burglars must dug out all the cell in it's column prior to it. The burglars may start from any column and stop digging within the column whenever they want.

Make a program that finds the maximum amount of money the burglars can gain without being caught from the cops.

He he, me lazy so code in python.

#!/usr/bin/env python
import os, sys
K = 0 # edinici vreme, broi kletki koito mogat da izkopaqt

def GetData(file=''):
f = open(file, 'r')
data = f.readlines()
f.close()
params = []

for i in data[0].split():
params.append(int(i))

data = data[1:data.__len__()]
array = []
for d in data:
array.append(d.split())

return (params, array)

class PreData:
def __init__(self, t=0, m=0):
self.time = t
self.money = m
def __repr__(self):
return 'Time: '+str(self.time)+' Money: '+str(self.money)
def __str__(self):
return 'Time: '+str(self.time)+' Money: '+str(self.money)

def GetPreData():
columns = []
tmpK = 0
tmpAward = 0
r = 0
c = 0
global K


((N,K,L,D), data) = GetData('input')
for c in xrange(0, L):
treasures = []
tmpC = PreData(0,0)

for r in xrange(0, D):
tmpC.time = tmpC.time + 1
tmpC.money = tmpC.money + int(data[r][c])

if int(data[r][c]) > 0:
if tmpC.time > int(K):
break
if tmpC.money > 0:
treasures.append(PreData(tmpC.time, tmpC.money))
tmpC.time = 0
tmpC.money = 0

columns.append(treasures)
return columns

maxMoney=0
def Recursion(cols=[], c=0, r=0, money=0, time=0):
global maxMoney

if c >= cols.__len__():
return
if r >= cols[c].__len__():
return
if (cols[c][r].time+time) > K:
return

cmoney = money + cols[c][r].money
ctime = time + cols[c][r].time
if maxMoney < cmoney:
maxMoney = cmoney

Recursion(cols, c + 1, r, cmoney , ctime )
Recursion(cols, c, r + 1, cmoney , ctime )

cols = GetPreData()
for i in range(0, cols.__len__()):
Recursion(cols, i, 0, 0, 0)
print maxMoney



Now test it!
serj@tokamak ~> cat input
4 3 3 3
3 -1 2
-1 -1 -1
3 12 7
serj@tokamak ~> ./stamen.py
10

Now test it again.
serj@tokamak ~> cat input; ./stamen.py
4 3 3 3
3 -1 24
-1 -1 -1
3 12 7
30

Yes it wErks! :-D

Monday, May 14, 2007

Ok i confess i'm lazy and i like python so what good might come out of this. Yeess, oh yes an automated sudoku-python-solver. The ultimate lame implementation of a sudoku solving algorithm in python, done in an hour or two it's not capable YET of solving sudokus with more than one solution but it'll do the job for that thick whole-year-list-a-day-sudoku-calendar. So here it goes, like this:

    1 #!/usr/bin/env python
2
3 class box:
4 #value 0 means empty
5 #numP
6 pass
7
8
9 class Board:
10 def __init__(self, rows=9, cols=9):
11 self.rows = rows
12 self.cols = cols
13 print av
14 self.board = []
15 for i in range(0, rows):
16 self.board.append( self.MakeRow(size=cols) )
17
18 def MakeRow(self, size=9):
19 r = []
20 for i in range(0, size):
21 r.append( box() )
22
23 return r
24
25 def InitBoard(self, data=[]):
26 rw = 0
27 cl = 0
28
29 for e in data:
30 self.board[rw][cl].value = e
31 cl = cl + 1
32
33 if cl == self.cols:
34 cl = 0;
35 rw = rw + 1
36
37 def GetRCInfo(self, row, col):
38 r = []
39 c = []
40 sq = []
41
42 for i in range(0, self.cols):
43 r.append( self.board[row][i].value )
44
45 for i in range(0, self.rows):
46 c.append( self.board[i][col].value )
47
48 br = (row/3)*3
49 bc = (col/3)*3
50
51 for sqR in range(br, br+3):
52 for sqC in range(bc, bc+3):
53 sq.append( self.board[sqR][sqC].value )
54
55 all = []
56
57 for i in r:
58 if all.__contains__(i):
59 continue
60 all.append(i)
61
62 for i in c:
63 if all.__contains__(i):
64 continue
65 all.append(i)
66
67 for i in sq:
68 if all.__contains__(i):
69 continue
70 all.append(i)
71
72 all.sort()
73 all.remove(0)
74
75 left = [1,2,3,4,5,6,7,8,9]
76 for i in all:
77 left.remove(i)
78
79 return left
80
81 def PrintBoard(self):
82 for rw in range(0,self.rows):
83 for cl in range(0, self.cols):
84 print self.board[rw][cl].value, " ",
85 print
86 print
87
88
89 def Solve(self):
90 done = False
91 while done != True:
92
93 for r in range(0, self.rows):
94 for c in range(0, self.cols):
95 if self.board[r][c].value == 0:
96 av = self.GetRCInfo(r,c)
97 if av.__len__() == 1:
98 self.board[r][c].value = av[0]
99 print "Adding ", av, " coords row:", r, " col:", c
100 self.PrintBoard()
101
102
103 done = True
104 for r in range(0,self.rows):
105 for c in range(0, self.cols):
106 if self.board[r][c].value == 0:
107 done = False
108 break
109
110 b = Board(9,9)
111 b.InitBoard([ 0,6,0,0,0,1,3,0,0,
112 0,5,0,6,0,9,1,0,0,
113 0,0,0,5,2,0,0,7,0,
114 0,0,0,0,0,2,6,0,7,
115 5,4,8,0,0,7,2,0,0,
116 0,0,0,9,1,8,0,5,0,
117 6,0,0,0,0,0,0,0,2,
118 0,0,5,0,0,0,7,0,0,
119 9,1,7,0,0,0,0,6,8
120 ])
121
122 b.PrintBoard()
123 print b.Solve()
124
125

Friday, April 27, 2007

More on reg exps. Parsing a C or C++ file with regexps in Python

Ok, so while i'm on the regexp wave. It's plain dumb but works fine. I know i could have used ctags or smth else, but for the sake of it. Also I googled for an example like this one but found nothing. It's always a good idea to have smth like this i case you need to generate prototypes for a long C file or nomatter what.


1 #!/usr/bin/env python
2
3
import os, re, sys
4
5 class Cexploder():
6 Body = re.compile("{[^{}]*}", re.DOTALL|re.MULTILINE)
7 Func = re.compile("(\w+\s+)*\w+\s*\(.*?\)", re.DOTALL| re.MULTILINE)
8 MultiLineComment = re.compile("/\*.*?\*/", re.DOTALL|re.MULTILINE)
9 OneLineComment = re.compile("//.*?$", re.DOTALL|re.MULTILINE)
10 CppDirectives = re.compile("^\s*#.*?$", re.DOTALL|re.MULTILINE)
11 #^\s*#(.*?(\\\n)*)+\n
12
13
def __init__(self, File=''):
14 f = open(File, 'r')
15 self.data = f.read()
16 f.close()
17
18 def GetPrototypes(self):
19 FuncList = []
20 pdata = self.data
21 pdata = self.OneLineComment.sub('', pdata)
22 pdata = self.MultiLineComment.sub('', pdata)
23 pdata = self.CppDirectives.sub('', pdata)
24
25 while self.Body.search(pdata) != None:
26 pdata = self.Body.sub('', pdata)
27
28 fiter = self.Func.finditer(pdata)
29 for i in fiter:
30 FuncList.append( pdata[i.start() : i.end()] )
31
32 return FuncList
33
34 c = Cexploder(sys.argv[1])
35 f = c.GetPrototypes()
36 for i in f:
37 print i

Thursday, April 26, 2007

Regular expressions for fun and profit!

So the year is 2007 the century 21-th, but still there are ppl who deny using regular expressions to do the job. Why? I don't know. May be they just don't know how to do it, may be they think it's slow, or they just never heard of it. But it makes me sick looking at lame pseudo parsers their awkward logic and tons of stupid useless code around for something as simple as digging a file for a pattern. I've seen guys spending a day writing code that can be replaced with just one line using a regular expression, and why? Do they gain something out of this? Performance? Speed? No, they usualy do this for a lame script to automate something and they don't care much if it's gonna take 10mS ot a second. The truth is they realy don't know how much easier it just because they have never done it before.

So for all of them here's a example of a quick and dirty script I used to generate a report. It simply goes through every file in a directory and looks for the following pattern "/*#.*?#*/". It's a bracket structure taken as a comment within C files. It's simple and i use it to write stuff about something that later might end up in a report. Sometimes i write in there something like "See line 1923" or "Line 192" wich ofcourse means a reference to that line, that's why i made my script look for such patterns and if one exists it'll dump it.

So enough goofing around this is the script:

1 #!/usr/bin/env python
2
3
import os, re, sys
4
5 Cover = re.compile("/\*\#.*?\#\*/", re.DOTALL|re.MULTILINE)
6 SeeAlso = re.compile("(see|line)+.*?\d+", re.DOTALL|re.MULTILINE|re.IGNORECASE)
7 Number = re.compile("\d+")
8
9 class Result:
10 pass
11
12 def GetLinesAround(Data = '', Line = 0, LinesAround = 5):
13 ret = ''
14 d = Data.split('\n')
15
16 if Line >= LinesAround/2:
17 upper = Line - LinesAround/2
18 else:
19 upper = 0;
20
21 lower = Line + LinesAround/2 + 1
22 if lower > d.__len__():
23 lower = d.__len__()
24
25 try:
26 d = d[upper : lower]
27 except Exception:
28 return ret
29
30 for s in d:
31 ret = ret + str(s) + '\n'
32
33 return ret
34
35 def GenUtReport(File = '', RelativePath=''):
36 f = open(File, 'r')
37 data = f.read()
38 f.close()
39
40 ret = []
41
42 utIter = Cover.finditer(data)
43 for i in utIter:
44 res = Result()
45
46 avLine = data[0:i.start()].count('\n') + (data[i.start():i.end()].count('\n')/2)
47
48 res.fInfo = "File: " + str(RelativePath) + " Line: " + str(avLine)
49 res.utInfo = data[i.start():i.end()].split(':')[1].replace('#*/', '')
50 res.codeAroundUt = GetLinesAround(data, avLine)
51
52 res.seeAlsoInfo = []
53 seeIter = SeeAlso.finditer(res.utInfo)
54 for si in seeIter:
55 seeLine = Number.findall(res.utInfo[si.start():si.end()])
56 if seeLine != None:
57 seeLine = seeLine[0]
58 res.seeAlsoInfo.append( ( seeLine, 10, GetLinesAround(data, int(seeLine), 10) ) )
59
60 ret.append(res)
61
62 return ret
63
64 def PrityPrint(ret = []):
65 tmpStr = ''
66
67 for res in ret:
68 tmpStr = tmpStr + "<tr>"
69 tmpStr = tmpStr + "<td>" + res.fInfo + "</td>"
70 tmpStr = tmpStr + "<td>" + res.utInfo + "</td>"
71 tmpStr = tmpStr + "<td>" + res.codeAroundUt + "</td>"
72 tmpStr = tmpStr + "<td>"
73 for i in res.seeAlsoInfo:
74 tmpStr = tmpStr + "See Also. Code around LINE: " + i[0] + " (+/-)"+ str(i[1]/2) +"\n\n"+ str(i[2])
75 tmpStr = tmpStr + "</td>"
76 tmpStr = tmpStr + "</tr>"
77
78 return tmpStr.replace('\n', '<br>')
79
80 tmpStr = """<html><head></head><body><table border="1">
81 <tr>
82 <td><b>Filename, Line number</b></td>
83 <td><b>UT not covered reason</b></td>
84 <td><b>Related code</b></td>
85 <td><b>See also</b></td>
86 </tr>"
""
87
88 for r, d, f in os.walk(sys.argv[1]):
89 for file in f:
90 tmpStr = tmpStr + PrityPrint(GenUtReport( os.path.join(r, file) , file))
91
92 tmpStr = tmpStr + "</table></body></html>"
93 print tmpStr



So you see in less than 100 lines I did it all. Parsing, referencing, generating a report in html. It took me less than 2 hours to finish this.

Tuesday, March 6, 2007

FuzzXml

Ok si i was playing around the other day with a Jabber server written in java. I don't quite remember the name but it had a nice web configuration interface. I remember thinking "why not just throw some garbage at this little server of ours?" Yeah sounds like a nice idea! Lets proceede in python of course. First we know jabber is based on XML, second we know it can work without encryption. How much easier could it be? I made a list of all the xml files i could find in my home dir. From all the browsing on the net for this year and a half since i got this laptop i had a hell of alot of them. I did "cat" them all into one big.blob, then refined it with "strings" and the resulting pile of XML stored as good.blob.

serj@tokamak:~$ du -h good.blob
2.4M good.blob

Now all i need is a bit of python to make this work.

#!/usr/bin/env python

import sys
import time
import random
import socket
import string
import threading

def fuzzFile(file, iter, chunkLen):
f = open(file, 'r')
data = f.read()
f.close()

retStr = ""
for i in range(0, int(iter)):
x = random.randint(0,data.__len__());
retStr = retStr + str( data[ x : x+random.randint(0, int(chunkLen)) ] ) + "\n\n"
for i in range( 0, int(random.randint(0, 3)) ):
retStr = retStr + "\n"

return retStr


class FuzzAServer(threading.Thread):
def __init__(self, addr, port, file, iter, chunkLen):
threading.Thread.__init__(self, name="Producer")
self.addr = addr;
self.port = port;
self.file = file;
self.iter = iter;
self.chunkLen = chunkLen;

def run(self):
while 1:

try:
sox = socket.socket ( socket.AF_INET, socket.SOCK_STREAM )
sox.connect((self.addr,int(self.port)))

while sox.send(fuzzFile(self.file, self.iter, self.chunkLen)):
pass

sox.close()
except Exception, err:
print err

time.sleep(10)


class FuzzAClient(threading.Thread):
def __init__(self, addr, port, file, iter, chunkLen):
threading.Thread.__init__(self, name="Producer")
self.addr = addr;
self.port = int(port);
self.file = file;
self.iter = iter;
self.chunkLen = chunkLen;

def run(self):
while 1:

try:
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind((self.addr, self.port))
s.listen(1)
conn, addr = s.accept()
print 'Connected by', addr
while 1:
data = conn.recv(1024)
print data,

if not data:
break


data = fuzzFile(self.file, self.iter, self.chunkLen)
print data

conn.send(data)

conn.close()
except Exception, err:
print err

s.shutdown(2)
s.close()

for i in range(0, 1000):
t = FuzzAServer(sys.argv[1], sys.argv[2], sys.argv[3], sys.argv[4], sys.argv[5])
t.start()
# print "thread ", i




The idea is simple. Connect to the server build some random string of XML-ish garbage and send it back. And like this as fast as you can. And yeah lets spawn a couple of more in parallel.

As you can see i also included a server who can handle a client a time and send bad XML. I decided to test not just the server but the clients also.

The results? Well after about 10-30 seconds the java Jabber server eat about 1.2G ram and 98%cpu for more than 20 minutes (at least i killed it after 20 mins). The clients that i tested were examples from the XmlRpc++ library. The did handle the server without problems.

Thursday, March 1, 2007

Ok so i've played some more with the idea.
In this release of the previous client-server thing up there.
- Turbo charged Function for getting the queue length. ( based on my 67 seconds research with strace over exim )
- Server Implementation in C++ WooooW.
- Client Implementation in C++ even more WOOOOWWW!

now this is what my screen looks like. The lines with one more blank unerneath are C++ Servers
the others Python servers ;)

Thu Mar 1 21:34:29 2007
XXX 1 : Mail Queue: 2545
XXX 3 : Mail Queue: 4030
XXX 7 : Mail Queue: 89653
XXX 8 : Mail Queue: 238

XXX 9 : Mail Queue: 123

XXX12 : Mail Queue: 1767

XXX14 : Mail Queue: 567

XXX15 : Mail Queue: 567

XXX16 : Mail Queue: 717

XXX20 : Mail Queue: 477
XXX21 : Mail Queue: 477