The Python Blog or 15 minutes of python a day!?!

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

2007-06-22T11:54:00.000-07:00

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

2007-05-14T12:14:00.000-07:00

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

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

2007-04-27T00:43:00.000-07:00

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

Regular expressions for fun and profit!

2007-04-26T23:47:00.000-07:00

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.

FuzzXml

2007-03-06T02:34:00.000-08:00

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.

2007-03-01T11:37:00.000-08:00

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