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?

99 problems - python - 50

Huffman codes.

We suppose a set of symbols with their frequencies, given as a list of fr(S,F) terms. Example: [fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)]. Our objective is to construct a list hc(S,C) terms, where C is the Huffman code word for the symbol S. In our example, the result could be Hs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'), hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...etc.]. The task shall be performed by the predicate huffman/2 defined as follows:

# stats: [(letter, count)]
# return: [(count, letter OR (left, right)]
def make_tree(stats):
    pool = sorted([(count, letter) for letter, count in stats])

    while len(pool) > 1:
        first = pool.pop(0)
        second = pool.pop(0)

        node = (first[0]+second[0], (first, second))
        pool.append(node)
        pool.sort()

    return pool[0]

def codes_from_tree(node, path, results):
    count, letter_or_trees = node
    letter = left = right = None
    if type(letter_or_trees) == tuple:
        left, right = letter_or_trees
    else:
        letter = letter_or_trees

    if letter:
        results.append((letter, path))
    else:
        codes_from_tree(left, path+"0", results)
        codes_from_tree(right, path+"1", results)

def huffman(stats):
    results = []
    tree = make_tree(stats)
    codes_from_tree(tree, "", results)
    
    #to sort by huffman code value
    #results.sort(key=lambda x: int(x[1], 2))
    results.sort()

    return results

That solution *feels* a little hacky for me, but I can't think of why it bothers me. It might be that the last time I wrote this was in java, and it was a lot more work. Maybe this just seems too easy.

emacs python mode from scratch: stage 15 - info look

Probably the main lesson of my explorations of the python mode is that there is a lot of functionality available that I had never heard of before. info-look is a good case in point.

• python-after-info-look
  

  This function essentially let's you hook into the info system to look for documentation.
  

  As far as I can tell the main use is for calling info-lookup-symbol (C-h S) and having the info page for the python entity show up.
  

  You need to make sure the info flavor of python documentation is installed on your system. (And hopefully it takes you less time than it did me to realize it wasn't).
  

Not much else to say on this.

emacs python mode from scratch: stage 14 - context sensitive help

Here are the relevant variables and function in the context-sensitive help section

VARS:
(defconst db-python-dotty-syntax-table
(defvar view-return-to-alist)
(defvar db-python-imports)

FUNCS:
python-describe-symbol
python-send-receive
python-eldoc-function

• db-python-dotty-syntax-table
  

  This creates an altered syntax table that treats "." as "symbol constituent". In other words, "." is treated as part of the variable name rather than as an other type of syntax.
  

• view-return-to-alist
  

  Used by python-describe symbol. Consists of a window and help-return-method
  

• db-python-imports
  

  Used below when calling emacs.* helper functions.
  

• python-describe-symbol
  

  C-c C-f is bound to this and will do a python help(module|func|etc) for thing at point. It dumps out the standard python documentation in another temporary buffer. It uses emacs.py to get the help. Somewhat useful, but i usually have a python prompt open already.
  

• python-send-receive
  

  Convenience function for sending a command to the python interpreter and reading the result.
  

• python-eldoc-function
  

  Use emacs's own documentation reader to populate the message line with brief description of function and args. this is something that I had not noticed before and am glad I came across it while perusing the code.
  

  If you have a python session going and you either run M-x eldoc-mode or you set up a hook such as
  

  
    (add-hook 'python-mode-hook 'turn-on-eldoc-mode)
  

  
  

  then this will automatically run the eldoc help facility. Not sure how useful it will be day to day (maybe it's just developer eye candy), but I've seen this sort of thing while running in slime or in the haskell mode and now at least I see where it is coming from. Seems like it only really works with core python libraries. Strangely doesn't seem to know about the functions in the actual file you are currently working in.
  

Only 4 sections left to walk through. I'm actually pretty eager to be done with this, but I definitely want to finish (however shallow my exploration of this mode is).

Brains games that make you cry

I think almost as long as I've been a programmer I've tried making little games to test my reflexes and challenge my memory and other cognitive faculties. It's just been a given to me that: (a) you can train your brain in a manner similar to lifting weights or jogging and (b) this is a highly desirable goal.

The problem is that I've never really had enough faith in the games that I created that the effort I put into them (both writing and training with them) would be worth it. Doesn't stop me from getting interested in the idea anew every once in a while. And it seems that there is a general growing interest in these types of games, growing research that they work and (best of all) an increasing number of open source games that are created specifically to help you train your brain.

Of these sorts of games and research results it *seems* that the one with the most credibility is the "n-back task" as described in this wired article and as implemented in Brain Workshop.

Besides the research, one of the things that gives this game credibility is that it is really challenging and not very game like. It really does feel like exercise (in the sense of forcing yourself to go to the gym because you know it is good for you, a necessary evil). And honestly the first few passes through are almost laughably hard. You are trying to maintain a memory of positions and letter values being thrown out you and notice if the position or letter value is the same as n turns ago.

And the funny thing is that even after a couple of days of not really spending too much time on it, I'm definitely getting better at it. It's actually a weird feeling. The first few times through is just chaos and then all of a sudden you start moving from a slight guess that, yes, I think they did say "C" 2 turns ago and are now repeating it, to being really confident. But of course as soon as you get good at 2-back, it graduates you to 3-back.

Now the problem is how do I test if I am indeed getting smarter? I'll let you know if my brain seems like it has kicked it up a notch or two.

emacs python mode from scratch: stage 13 - python inferior mode

My plan was to look at context sensitive help next but it dependeds on a python inferior process so let's get that working next.

Here are the function/variables of relevance:

(defcustom python-python-command "python"
(defcustom python-jython-command "jython"
(defvar python-command python-python-command
(defvar python-buffer nil
(defconst python-compilation-regexp-alist
(defvar inferior-python-mode-map
(defvar inferior-python-mode-syntax-table
(define-derived-mode inferior-python-mode comint-mode "Inferior Python"
(defcustom inferior-python-filter-regexp "\\`\\s-*\\S-?\\S-?\\s-*\\'"
(defun python-input-filter (str)
(defun python-args-to-list (string)
(defvar python-preoutput-result nil
(defvar python-preoutput-leftover nil)
(defvar python-preoutput-skip-next-prompt nil)
(defun python-preoutput-filter (s)
(defun run-python (&optional cmd noshow new)
(defun python-send-command (command)
(defun python-send-region (start end)
(defun python-send-string (string)
(defun python-send-buffer ()
(defun python-send-defun ()
(defun python-switch-to-python (eob-p)
(defun python-send-region-and-go (start end)
(defcustom python-source-modes '(python-mode jython-mode)
(defvar python-prev-dir/file nil
(defun python-load-file (file-name)
(defun python-proc ()
(defun python-set-proc ()

The main mechanism for creating a python inferior process appears to be creating a derived mode based on comint-mode (defined in comint.el). Most of the code then is defining helper functions for making this mode python aware.

So without further ago, here is a brief look at the above functions:

• python-python-command
  
• python-jython-command
  

  Variables which allow customization of what command to use for invoking python (jython)
  

• python-command
  

  The actual command (probably one of the above) that will actually be executed by run-python
  

• python-buffer
  

  The python buffer that will be the target of code issued from files in python-mode
  

• python-compilation-regexp-alist
  

  compilation-error-regexp-alist is set to this value. This is set by inferior-python-mode and is used by compile.el. This regular expression basically matches a python exception stacktrace:
  

  
     Traceback (most recent call last):
       File "foo.py", line 13, in 
         1/0
     ZeroDivisionError: integer division or modulo by zero
  

  
  

  Honestly I'm a little confused by this since I don't think this regex actually matches the above and I'm not clear what purpose "compile" would need with it.
  

• inferior-python-mode-map
  

  Add a few keys for loading a file and doing pychecker. The key sequence for pychecker seems superfluous here. I never feel like kicking off pychecker while i'm in an interacive session.
  

• inferior-python-mode-syntax-table
  

  Adjust syntax table so that single quotes don't mess up the syntax coloring. "." is the syntax table entry for punctuation-like things.
  

• inferior-python-mode
  

  This is where the python interactive mode is defined. It overrides the default commint-mode. There is a comment here that the "python-mode" type things (keybindings, etc) should be inherited from python mode itself.
  

  The basic customization is to adjust some regular expressions that are used by commint to decide what sort of things get maintained in the history, what the "prompt" looks like (>>>), etc.
  

• inferior-python-filter-regexp
  

  The default is not to save things in the history if they are 3 or less in length. I hadn't noticed this behavior before.
  

  I'm not sure if there is some rhyme or reason why sometimes they use the rx style and sometime they use traditional emacs style regexps (in this case "\\`\\s-*\\S-?\\S-?\\s-*\\'").
  

• python-input-filter
  

  This basically is a wrapper for ignoring inferior-python-filter-regexp
  

• python-args-to-list
  

  This will be used by run-python below to collect args for kicking off a python process. Doesn't work with quoted white space. Don't know emacs lisp well at all but it seems like a complicated way to just tokenize on SPACE and TAB.
  

• python-preoutput-result
  

  Not sure what "_emacs_out" is about, and not sure I care to spend the time tracking this down. (Possibly for emacs.py)
  

• python-preoutput-leftover
  

  related to _emacs_out
  

• python-preoutput-skip-next-prompt
  

  This (as well as previous 2 functions) are used by python-preoutput-filter
  

• python-preoutput-filter
  

  This function appears to clean up the output a bit and prevent spurious >>> ... ... >>> from littering the output. I'm going to punt on this. I'm not especially interested in the logic here but it is interesting passing to see a complex function needed to make the python mode behave in a friendly fashion.
  

• run-python
  

  Start a new python process or use an existing one if available. runs python-command with -i.
  

• python-send-command
  

  A wrapper around python-send-string that is used by python-send-region and python-load-file
  

• python-send-region
  

  Copy a section of code to temporary file and evaluate it. Can't do it directly in the interpreter since empty lines will confuse it
  

• python-send-string
  

  Evaluate a python string in the buffer. This function checks for trailing \n or intermediate \t and throws in an extra \n so that the command is properly terminated in a way that the interpreter is expecting.
  

• python-send-buffer
  

  Wrap python-send-region but use the entire buffer as the region
  

• python-send-defun
  

  Send a region but use beginning-of-defun/end-of-defun to delimit the region
  

• python-switch-to-python
  

  Create a new python process if necessary and switch to it. Giving it an argument makes it go to the end of the buffer
  

• python-send-region-and-go
  

  Combine python-send-region and python-switch-to-python
  

• python-source-modes
  

  A list of mode names so we can automatically tell if the buffer has python code in it
  

• python-prev-dir/file
  

  A cache of the directory and file used by python-load-file so that it has a default value if necessary
  

• python-load-file
  

  Import a python file in its entirety into the python process. Uses emacs.py if the file ends in .py otherwise uses "execfile"
  

• python-proc
  

  Return to or create and move to a python process
  

• python-set-proc
  

  Associate the python-buffer with the current buffer (which is a python process). This is used by things like python-send-region so they know where to send output.
  

I think unless you understand the details of how comint works (which I don't) it's hard to get a strong feel for how the inferior-python-mode works. As always it's interesting to see all of the crazy details that have to be taken care of to get a simple looking thing like an embedded python interpreter working.

That was a very cursory overview of how the python process inferior mode works (even by my already lax standards). I admit it, I'm getting a little exhausted by this project. But I'm going to keep slogging through and finish doing at least a cursory inspection of every line in python.el.

Another thing that is becoming clear is that, while this process is helping me understand emacs and emacslisp, I have a lot of work to do, and at some point I really need to just sit down and learn emacslisp in a focused way.

Is it possible that I like sushi merely as a means to confound my wife?

Sometimes I wonder....

Choose Two

I was cracking wise with my co-workers the other day and later in the day I related the hi-jinx to my wife. I had proffered the following theory on the relative combination of desirable attributes in your mate.

"Gentleman, you've got cute, smart and nice. And you get to choose two."

My attractive, intelligent wife confirms that this is a sound theory.