99 problems - python - 56

Symmetric binary trees

Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes.

# Example in Haskell:

# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
# False
# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
# True

def mirror(tree):
    if tree == None:
        return None
    else:
        val, left, right = tree
        return (None, mirror(right), mirror(left))

def symmetric_binary_tree(tree):
    return mirror(mirror(tree)) == mirror(tree)

99 problems - python - 55

Construct completely balanced binary trees

In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

Write a function cbal-tree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.

# Example:

# * cbal-tree(4,T). 
# T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
# T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
# etc......No
def completely_balanced_trees(node_count):
    if node_count == 0:
        return [None]
    else:
        right_count  = (node_count - 1) / 2
        left_count = (node_count - 1) - right_count
        left_trees = completely_balanced_trees(left_count)
        right_trees = completely_balanced_trees(right_count)

        trees = []
        for left in left_trees:
            for right in right_trees:
                trees.append(("x", left, right))
                if left_count != right_count:
                    trees.append(("x", right, left))

        return trees

OK, I'm using tuples for trees again. So sue me.

Babylon 5: not so cautious, not so optimistic

So the general rule for our tv watching these days is that we pretty much just watch tv series that are complete and available in their entirety on netflix. It turns out there are only a limited number of these. After a while you start considering things that have been on your "maybe" list for a while. One very big maybe for me has been Babylon 5. It shows up on all of these top 10 best scifi series lists and people rave about it having one of the best multi season story arcs. Ever.

Having heard that the first season is a bit weak and the things really start to get good in season 2 I asked my wife for some patience and and decided to dig in.

And, well, so far it's been worse than I could have imagined. Terrible set designs. Unbelievably bad diaglog. Very long in the tooth special effects. Unimaginitive aliens. Recycled scifi tropes. Wooden acting. And we are only two episodes away from season 2 starting. And I have to admit I'm really intrigued. Is there really any chance that things turn around *so* dramatically?

I'm a total fanboy for Farscape. In my opinion, the first season there was pretty weak (not Babylon 5 weak, but not great). And yet it slowly grew into one of my all time favorite series. And this was a show that had serious problems throughout but had some amazing highs to make up for it. So I do believe that things can turn around for B5 and that I will like it.

But man, this first season has been so extremely painful. I'm afraid my wife will get revenge on me by making me watch Sex in the City. Oh, god, the horror. The horror....

emacs python mode from scratch: stage 18 - imenu

So first of all, what *is* imenu.

... read, read ....

So it partly seems like a one file only form of etags. But if you do M-x imenu-add-menubar-index it will add an "index" menu to the menu bar with a list of all files for easy access. Being a bit of a mouse-ophobe, I'm not so sure how I'd like that. Also you have to hit rescan whenever you change the contents of the file (or set up imenu-auto-rescan).

Seems like another case of having more than one way to do things. I'll probably stick with etags, but for completeness here is a brief overview of the imenu support functions.

So there is really just one function:

• python-imenu-create-index
  

  Go to the beginning of the file. look for "def and "class" references (unless in comments or string) and add them to the list.
  

Hmm, I wonder if something else more wonderful is going on here. Doesn't really seem like functionality worth supporting.

Perhaps if you had it set up to go off a simple mouse motion as described here.

(if (featurep 'xemacs)
     (global-set-key [(shift button3)] 'imenu) ; XEmacs
   (global-set-key [S-mouse-3] 'imenu)) ; GNU Emacs

Also looks like it integrates in with ido to some extent. Maybe there is some goodness from that.

Any way, that's enough on that topic.

emacs python mode from scratch: stage 17 - ffap

This is a small bit of code, but it's another little gem that I didn't know exists. There is only one function:

• python-module-path
  

  This function uses emacs.modpath to determine the module path for use with ffap-alist
  

What this gets us is support for M-x find-file-at-point.

It's not *quite* as cool as I first anticipated because the file path finder seems to get confused about what is actually a module, but if point is on a module name on an import line then it will pop you directly over to the python lib directory and open the module. If you already have etags set up to do this then you probably won't be *too* amazed, but this is a nice extra way to accomplish the same thing.

emacs python mode from scratch: stage 16 - completion

This is a collection of functions that uses emacs.py to find a list of likely completions for module.

python-imports
python-find-imports
python-symbol-completions
python-partial-symbol 
python-complete-symbol
python-try-complete

• python-imports
  

  A list of python import statements in the buffer
  

• python-find-imports
  

  Populate the above list. search by looking for "^import" or "^from" (skipping those in comments or strings).
  

  Then reverse the list, clean out text properties and change \n to \\n so that output doesn't end up wrong.
  

• python-symbol-completions
  

  Run emacs.complete(symbol, python-imports) and return the list of completions (in another buffer)
  

• python-partial-symbol
  

  Use a regular expression to go backward and thereby find the complete symbol before point. This seems a little odd to me. I seems like it would be easier to just trust the syntax-table that has already been defined for the mode and just do backward-word from the current position (with a save-excursion). As a guess I'd say it's so that it can treat "." as part of the symbol and skip over that to the beginning of a module/class name.
  

• python-complete-symbol
  

  Find the list of completions (using python-symbol-completions) or just scroll the completions window if they've already been found.
  

• python-try-complete
  

  "hippie-expand" version for doing symbol completions. Basically "he-" does all the heavy lifting hereit just needs to be
  given the python-symbol-completions and python-partial-symbol functions.
  

99 problems - python - 54A

Check whether a given term represents a binary tree

In Prolog or Lisp, one writes a predicate to do this.

Example in Lisp:

* (istree (a (b nil nil) nil))
T
* (istree (a (b nil nil)))
NIL
def is_tree(t):
    if t == None:
        return True
    elif type(t) == tuple and len(t) == 3:
        (val, left, right) = t
        return is_tree(left) and is_tree(right)
    return False

Is using lispy tuple for representing tree cheating?