Solutions to Homeworks

The following sample solutions are not the only possible solutions, they are just one way to solve a homework problem.

Homework 6

A simple webserver.py (but not shown are the image and HTML files)

   1 import BaseHTTPServer
   2 pageTable = '''index.html index2.html index3.html
   3                image1.jpg image2.jpg image3.jpg
   4             '''.split()
   5 index  = "image1.jpg", "index2.html", "Link to Index2", "beige" 
   6 index2 = "image2.jpg", "index3.html", "Link to Index3", "tan" 
   7 index3 = "image3.jpg", "index.html", "Link to Index", "yellow" 
   8 indexTable = { pageTable[0]:index, pageTable[1]:index2, pageTable[2]:index3 }
   9 class MyHandler(BaseHTTPServer.BaseHTTPRequestHandler):
  10    def servepage(self,page,ptype):
  11      self.send_response(200)
  12      self.send_header('Content-type',ptype)
  13      self.end_headers()
  14      self.wfile.write(page)
  15    def serveHTML(self,name):
  16      F = open("skeleton.html")
  17      page = F.read()
  18      F.close()
  19      page = page.format(indexTable[name]) 
  20      self.servepage(page,"text/html")
  21    def serveImage(self,name):
  22      F = open(name,'rb')
  23      page = F.read()
  24      F.close()
  25      self.servepage(page,"image/jpeg")
  26    def do_GET(self):
  27      name = self.path.split("/")[-1]
  28      if name in pageTable and name.endswith("html"):
  29         return self.serveHTML(name)
  30      if name in pageTable and name.endswith("jpg"):
  31         return self.serveImage(name)
  32      else:
  33         self.send_response(404)
  34         self.send_header('Content-type','text/html')
  35         self.end_headers()
  36         self.wfile.write("<html><body>Not Found</body></html>\n")

Here is a minimal solution to the maze problem. The first part is the maze representation and a class with methods to navigate this representation:

   1 Rooms = list("ABCDEFGHIJKLMNOP")
   2 Halls0 = '''AeB AsE BeC CsG GeH FeG FsJ 
   3             HsL JeK KeL LsP OeP IeJ IsM MeN'''
   4 Halls1 = '''AsE EsI IsM EeF FsJ JsN BeC FeG
   5             JeK CsG GsK KsO CeD KeL OeP HsL'''
   6 Dragon0, Sword0, Treasure0 = "IKN"
   7 Dragon1, Sword1, Treasure1 = "CJH"
   8 # Would be easy to add Halls2, Dragon2, etc  
   9 def makeHallDict(halls):
  10   strhalls = halls.split()
  11   halldict = { room:[] for room in Rooms }  
  12   for room1, direction, room2 in strhalls:
  13     if direction == "s":
  14        halldict[room1].append( ("s",room2) )
  15        halldict[room2].append( ("n",room1) )
  16     if direction == "e":
  17        halldict[room1].append( ("e",room2) )
  18        halldict[room2].append( ("w",room1) )
  19   return halldict
  20 HallsDict0 = makeHallDict(Halls0)
  21 HallsDict1 = makeHallDict(Halls1)
  22 class Game():
  23   def __init__(self,halls,dragon,sword,treasure):
  24      self.position = "A"  # always start at room A
  25      self.halls, self.dragon, self.sword, self.treasure = halls, dragon, sword, treasure
  26      self.hasSword = False
  27   def available(self):
  28      R = ''
  29      if not(self.lost() or self.won()):
  30        for direction, other in self.halls[self.position]:
  31          R += direction
  32      return R
  33   def lost(self):
  34      return self.position == self.dragon and not self.hasSword
  35   def won(self):
  36      return self.position == self.treasure
  37   def move(self,direction):
  38      for d,new in self.halls[self.position]:
  39        if d == direction:
  40          self.position = new
  41      if self.position == self.sword:
  42        self.hasSword = True
  43 game0 = Game(HallsDict0,Dragon0,Sword0,Treasure0)
  44 game1 = Game(HallsDict1,Dragon1,Sword1,Treasure1)

The above makes the rest of the GUI programming easy, because the logic of how/where to move, checking for game over, and so on is already programmed.

   1 class demoFrame(Frame):
   2   def __init__(self,master):
   3      Frame.__init__(self,master) 
   4      self.pack_propagate(0)  
   5      self.pack(padx=10,pady=10)  
   6      self.config(width=400,height=150)  
   7      self.config(background="lightgreen",relief=RAISED)
   8      self.root = master 
   9      self.widgets = []  
  10      self.game = random.choice([game0,game1])  # easy to add more
  11      self.buildWidgets()  
  12 
  13   def buildWidgets(self):
  14      plabel = "Room " + self.game.position
  15      if self.game.hasSword:
  16         plabel += " +Sword"
  17      position = Label(self,text=plabel)
  18      position.pack(side="top")
  19      self.widgets.append(position)
  20      for direction in self.game.available():
  21         packside, labdir, handler = { "s":("bottom","South",self.goSouth),
  22                "n":("top","North",self.goNorth),
  23                "e":("right","East",self.goEast),
  24                "w":("left","West",self.goWest) }[direction]
  25         button = Button(self,text=labdir)
  26         button.pack(side=packside)
  27         button.bind("<Button-1>",handler)
  28         self.widgets.append(button)
  29 
  30   def clearWidgets(self):
  31      for widget in self.widgets:
  32          widget.destroy()
  33      self.widgets = []  
  34   def quit(self,mouseEvent):
  35      self.root.destroy() 
  36 
  37   def goSouth(self,mouseEvent):
  38      self.game.move("s")
  39      self.postMove()
  40   def goNorth(self,mouseEvent):
  41      self.game.move("n")
  42      self.postMove()
  43   def goWest(self,mouseEvent):
  44      self.game.move("w")
  45      self.postMove()
  46   def goEast(self,mouseEvent):
  47      self.game.move("e")
  48      self.postMove()
  49   def postMove(self):
  50      if self.game.lost():
  51         print "Congratulations, you lost."
  52         self.quit(None)
  53      elif self.game.won():
  54         print "Congratulations, you won."
  55         self.quit(None)
  56      else:      
  57         self.clearWidgets()
  58         self.buildWidgets()
  59 
  60 root = Tk()
  61 Tkobject = demoFrame(root)
  62 Tkobject.mainloop()

Homework 5

The digitcount problem:

   1 def digitcount(S,dictionary=False):
   2   D = { digit:(S.count(digit)) for digit in "0123456789"}
   3   if dictionary:
   4      return D
   5   return [D[i] for i in "0123456789"]  
   6 
   7 def noyears(line):
   8   fields = line.split()
   9   years = "2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011" 
  10   years = years.split()
  11   for yr in years:
  12      while yr in fields:
  13         fields.remove(yr)
  14   line = ' '.join(fields)
  15   return line
  16 
  17 def mergedict(D1,D2):
  18   newD = { digit:(D1[digit]+D2[digit]) for digit in "0123456789" }
  19   return newD
  20 
  21 def digitfile(filename,years=True):
  22   D, file = digitcount("",dictionary=True), open(filename)
  23   for line in file:
  24      if not years:
  25         line = noyears(line)
  26      D = mergedict(D,digitcount(line,dictionary=True))
  27   return showlist(D)
  28 
  29 def freqdist(V):
  30   if sum(V)==0:
  31      return 10*[0.0]
  32   ratios = [float(x)/sum(V) for x in V]
  33   percent = [int(100*n) for n in ratios]
  34   return percent

The wordfreq problem:

   1 def nohyphen(W):
   2   return (' '.join(W)).replace('-',' ').split()
   3 
   4 def nonumbers(W):
   5   newW = []
   6   for word in W:  
   7     if any( [digit in word for digit in "0123456789"] ):
   8        continue
   9     newW.append(word)
  10   return newW
  11 
  12 def nopunctuation(W): 
  13   from string import punctuation
  14   newW = []
  15   for word in W: 
  16     for char in punctuation: 
  17       word = word.replace(char,'')
  18     newW.append(word)
  19   return newW
  20 
  21 def noemptywords(W):
  22   newW = []
  23   for word in W:
  24     if word != '':
  25       newW.append(word)
  26   return newW
  27 
  28 def nostop(W):
  29   assert type(StopWords) == type({}) 
  30   newW = []
  31   for word in W:
  32     if word not in StopWords:
  33        newW.append(word)
  34   return newW
  35 
  36 def stem(W):
  37   import porter2 
  38   newW = [] 
  39   for word in W:
  40      newword = porter2.stem(word) 
  41      newW.append(newword)
  42   return newW
  43 
  44 def lowercase(W):
  45   newW = []
  46   for word in W:
  47     newW.append(word.lower())
  48   return newW
  49 
  50 def makeStopWords():
  51   Dict, File = { }, open("stopwords.txt")
  52   for Line in File:
  53     Dict[ Line.strip() ] = True
  54   File.close()
  55   return Dict

Homework 4

The oddouble problem:

   1 def oddouble(L):
   2   for i in range(len(L)):
   3     if L[i]%2!=0: 
   4        L[i] *= 2 

The tenabove problem:

   1 def tenabove(L):
   2    if len(L)<3:
   3      return []
   4    R = []
   5    for i in range(1,len(L)-1):
   6      if L[i]-L[i-1]>=10 and L[i]-L[i+1]>=10:
   7         R.append(L[i])
   8    return R

The count2sep problem:

   1 def count2sep(L,first,Seconds):
   2    total = 0
   3    for i in range(len(L)-2):
   4      if L[i]==first and L[i+2] in Seconds: 
   5        total += 1
   6    return total

The newjoin problem:

   1 def newjoin(L,glue):
   2    R = None 
   3    for word in L:
   4      if R != None:
   5        R += glue + word
   6      else:
   7        R = word
   8    if R == None:
   9       return ''
  10    return R

The sumaxcol problem:

   1 def getcolsum(M,i):
   2    s = 0
   3    for j in range(len(M)):
   4      s += M[j][i]
   5    return s
   6 
   7 def sumaxcol(M):
   8    m = getcolsum(M,0)
   9    for i in range(len(M[0])):
  10      m = max(m,getcolsum(M,i))
  11    return m

The rotrian problem:

   1 def choose(n,m):
   2   fact = lambda n: 1 if n<2 else n*fact(n-1)
   3   return fact(n) / (fact(n-m)*fact(m))
   4 # Note: in classical Pascal Triangle, the k-th row is 
   5 #   [ choose(k,0), choose(k,1), choose(k,2), ... choose(k,k) ]
   6 #        == [ choose(k,i) for i in range(k+1) ]  
   7 # But with rotation, the k-th row is 
   8 #   [ choose(n,k), choose(n-1,k), choose(n-2,k), ... choose(n-k,k) ]
   9 # where the value k varies from 0 up to n, to get n+1 rows overall
  10 def rotrian(n):
  11   R = []
  12   for i in range(n):  # i is 0, 1, 2, ... (n-1)
  13     newrow = []
  14     for j in reversed(range(i,n)):  # j is (n-1), ... i 
  15       newrow.append(choose(j,i))
  16     R.append(newrow)
  17   return R

Homework 3

The listarr problem:

   1 def listarr(A,B):
   2   R = [ A[i] for i in B ]
   3   return R

The remlists problem:

   1 def remlists(A,B):
   2   R = [ A[i]%B[i] for i in range(len(A)) ]
   3   return R

The skiptwoeq problem:

   1 def skiptwoeq(X):
   2   R = [ X[i]==X[i+2] for i in range(len(X)-2) ]
   3   return R.count(True)

The runavg problem:

   1 def preslices(x):
   2   R = [x[:j] for j in range(len(x)+1)]
   3   return R
   4 def avg(x):
   5   if len(x)>0:
   6      return sum(x)/float(len(x))
   7   return 0.0
   8 def runavg(x):
   9   return map(avg,preslices(x))

The palindromes problem:

   1 def palindrome(T):
   2   revT = reversed(T)
   3   comT = (a==b for (a,b) in zip(T,revT))
   4   return all(comT)
   5 def palindromes(L):
   6   return filter(palindrome,L)

The commons problem:

   1 def nodups(text):
   2   R = [ text[i] for i in range(len(text)) if text[:i].find(text[i])==-1 ]
   3   return ''.join(R)
   4 def common(word1,word2):
   5   R = [ letter for letter in word1 if letter in word2 ]
   6   S = nodups(''.join(R))
   7   return ''.join(S)
   8 def commons(L):
   9   return reduce(common,L)

Another way to program nodups:

   1 def helper(left,right):
   2   return list(left) + [ c for c in right if c not in left ]
   3 def nodups(text):
   4   return ''.join( reduce(helper,text,'') )

Homework 2

The itemsel problem:

   1 def itemsel(A,(i,j)):
   2   return (A[i],A[j])

The letword problem:

   1 def letword(W,i,k):
   2   return W[i][k].upper()

The repitem problem:

   1 def repitem(F,k=1):
   2    if k%2==0:
   3       return F[0]
   4    else:
   5       return F

The revsub problem:

   1 def revsub(S):
   2   s = sum(S)
   3   t = S[3]-S[2]-S[1]-S[0]
   4   return s-t

The threesum problem:

   1 def itemsum(X,Y):
   2     if len(X)<1:
   3        return []
   4     first = X[0]+Y[0]
   5     if len(X)<2:
   6        return [first]
   7     second = X[1]+Y[1]
   8     if len(X)<3:
   9        return [first,second]
  10     third = X[2]+Y[2]
  11     if len(X)<4:
  12        return [first,second,third]

The ordercat problem:

   1 def ordercat(A,B,C):
   2   if A<=min(B,C):
   3     if B<C:
   4       return A+B+C
   5     else:
   6       return A+C+B
   7   if B<=min(A,C):
   8     if A<C:
   9       return B+A+C
  10     else:
  11       return B+C+A
  12   if C<=min(A,B):
  13     if A<B:
  14       return C+A+B
  15     else:
  16       return C+B+A

The ordercat problem can be solved many other ways, for instance:

   1 def ordercat(A,B,C):
   2   if A<=B and B<=C:
   3       return A+B+C
   4   elif A<=C and C<=B:
   5       return A+C+B
   6   elif B<=A and A<=C:
   7       return B+A+C
   8   elif B<=C and C<=A:
   9       return B+C+A
  10   elif C<=A and A<=B:
  11       return C+A+B
  12   elif C<=B and B<=A:
  13       return C+B+A

Solutions (last edited 2014-05-25 18:29:53 by localhost)