Third Homework Assignment

Third Homework Assignment
Posted 10 Feb 2004 by herman
Due by 12:00 midnight, 16th February via Email.
This is the first programming assignment. You'll learn how to write simple programs in Python. The assignment is given in homework3.pdf, and to save you some typing, here are three files associated with the first three problems (use right-button click to download):

elimchars.py
list2dict.py
gunion.py
If you modify these downloaded files, the docstring will assist you with unit tests. For instance, once you have a working elimchars program, the command
python elimchars.py
will run with no errors. During development, you should use the command
python -i elimchars.py
to get interative prompts for development and debugging.

Solutions, posted 17 Feb 2004 by herman
There are many possible solutions to the problems; I think most everyone got the last problem (simulated birth) correctly solved, so I'll present solutions just for the first three problems.
The best answer to the first problem is a function such as:
def elimchars(ref,strin):
  for c in ref: strin = strin.replace(c,'')
  return strin
However, it is also possible to build the solution iteratively:
def elimchars(ref,strin):
  newstring = ''
  for i in range(len(strin)):
    if strin[i] in ref: continue
    newstring = newstring + strin[i]
  return newstring
The best answer to the second problem is the one line answer:
list2dict = dict
Most students gave an algorithmic solution, something like:
def list2dict(L):
  d = {}
  for i in L: 
    a, b = i
    d[a] = b
  return d
Either solution is acceptable.
There were many solutions for the third problem. Most look rather complicated, such as:
def gunion(g,h):
    n = {}
    # first union h into g
    for i in g.keys():
      b = g[i]
      if i in h.keys():
        for j in h[i]:
          if j not in b:  b += [j]
      b.sort()
      n[i] = b
    # now, for any of h that was missed ...
    for i in h.keys():
      if i not in g.keys():
        b = h[i]
        b.sort()
        n[i] = b
    return n
(somewhat simpler versions of this are possible). Here's how a mathematically inclined python expert might write the function.
def noDuplicateSort(L):
    # this function removes duplicates from
    # a list and sorts the list
    r = {}
    # enter items of L as keys in a dictionary
    for m in L: r[m] = 0
    # now the keys have no duplicates
    r = r.keys()
    r.sort()
    return r

 def gunion(g,h):
    r = {}
    # define union, intersection, and complement
    # of the intersection of vertices of (g,h)
    vUnion = g.keys() + h.keys()
    vIntersect = [ k for k in g.keys() if k in h.keys() ]
    vComplement = [ k for k in vUnion if k not in vIntersect ]
    # add intersection items to r
    for x in vIntersect: r[x] = g[x] + h[x]
    # add complement items to r
    for x in vComplement:
      if x in g.keys():  r[x] = g[x]
      else:              r[x] = h[x]
    # finally, sort and remove duplicate edges
    for k in r.keys(): r[k] = noDuplicateSort(r[k])
    return r
Although this is a lengthy function definition, the logic is quite straightforward.