Monday, January 19, 2009

With certain unalienable Rights

I have an etymology calendar on my desk, and today's word is freedom. The author makes a serious mistake in writing, "'Liberty' … also means 'free' but in the sense of rights granted rather than any innate quality."

Liberty carries its natural-rights sense as used by enlightenment thinkers such as Locke and Bastiat, viz., government is the servant of free people and not their master.

For a contemporary example, consider Ron Paul who wrote (with emphasis added), "Democracy represented unlimited rule by an omnipotent majority, while a constitutionally limited republic was seen as the best system to preserve liberty. Inalienable individual liberties enshrined in the Bill of Rights would be threatened by the 'excesses of democracy.'"

In 1943, the U.S. supreme court declared, "One's right to life, liberty, and property, to free speech, a free press, freedom of worship and assembly, and other fundamental rights may not be submitted to vote; they depend on the outcome of no elections."

Thomas Jefferson took an even more radical position: "Rightful liberty is unobstructed action according to our will within limits drawn around us by the equal rights of others. I do not add 'within the limits of the law,' because law is often but the tyrant's will, and always so when it violates the rights of the individual."

The tenth amendment to the U.S. constitution (so-called these days) makes plain that the federal government is not the source of the people's rights, and this in turn is consistent with the Declaration's connection of government's just powers to "the consent of the governed."

Thursday, January 15, 2009

They see me rollin': a probability problem

Say you're playing 7-card stud and are dealt rolled-up deuces. If you see the case deuce as someone else's door, what is the probability that you'll bring it in?

In stud high games, the player with the lowest upcard is the bring-in. Suits break ties, with different places using different orders, so let's use bridge order, i.e., clubs, diamonds, hearts, and spades. Deuce of clubs always pays the bring-in.

The search space is small enough to use brute force. Front matter first:

> import Control.Monad
> import qualified System.IO.UTF8 as UTF8
> import Text.Printf
Modeling suits is straightforward:
> data Suit = C | D | H | S deriving (Show, Ord, Eq, Enum)
Haskell's deriving clause saves tedious definitions. For example, making Suit an instance of the Ord typeclass means that clubs are less than diamonds and so on.

We walk through all possibilities and report the probability:

> main = do
>   mapM_ display doors
>   putStrLn $ printf "Hero bringin probability: %.3f%%"
>                     (100.0 * k / n :: Float)

Simulate the deal. Automatically deriving an instance of the Enum typeclass allows us to use shorthand for all suits. From the problem statement, we know our hero will see two deuces, and the others are in the hole. Enumerating all possibilities is trivial with a list comprehension.

>   where doors = deal [C .. S]
>         deal xs = [ (h,v) | h <- xs, v <- xs, h /= v ]

Here we apply the definition of probability: the ratio of the number of times an event occurs with the total number of events:

>         hero  = [1.0 | (h,v) <- doors, h < v ]
>         (k,n) = (sum hero, fromIntegral $ length doors)

Given a pair of hero and villain door cards, pretty-print it to the standard output:

> display (h,v) = UTF8.putStrLn bringin
>   where hv = "Hero: " ++ (suit h) ++ ", Villain: " ++ (suit v)
>         bringin | h < v     = hv ++ " *"
>                 | otherwise = hv
>         suit C = "♣"
>         suit D = "♦"
>         suit H = "♥"
>         suit S = "♠"

Output:

Hero: ♣, Villain: ♦ *
Hero: ♣, Villain: ♥ *
Hero: ♣, Villain: ♠ *
Hero: ♦, Villain: ♣
Hero: ♦, Villain: ♥ *
Hero: ♦, Villain: ♠ *
Hero: ♥, Villain: ♣
Hero: ♥, Villain: ♦
Hero: ♥, Villain: ♠ *
Hero: ♠, Villain: ♣
Hero: ♠, Villain: ♦
Hero: ♠, Villain: ♥
Hero bringin probability: 50.000%

Wednesday, January 14, 2009

Sally's generosity project

When I first heard about Sally's unusual assignment for her functional area, I was standing in the Opry Mills Mall. (They have this great place there called Dave & Buster's — why in the world don't we have one of those in the Huntsvegas geek mecca?)

My cell phone rang, and I saw Jenny was calling. This was just before Christmas, and everyone at work knew I'd gone to Nashville to spend time with friends and family — and also to nearly freeze myself and my progeny to death in our 9° viewing of ice sculptures inspired by How The Grinch Stole Christmas.

I prepared for bad, bad news, but instead she asked the seemingly random question of whether I was still a coordinator for Dave Ramsey's Financial Peace University. "Uh, yeah," I stumbled, "what's up?" She clued me in and said she wanted to give an FPU scholarship. A young couple at our church are engaged to be married soon: the bride-elect also happens to be an Alabama alumna, so I figured that would mean extra warm fuzzies for the benefactress.

The next Monday (that would be December 22 for those scoring at home), Sally gave me a blue envelope with instructions to do a good deed. The only catch was that I had to write about it on my blog. When I got home, I hoped my wife would suggest a great gift, but we had a zillion other gifts flying through our heads trying to get ready for a Christmas trip to her grandmother's. So the task went into the background.

Christmas Eve at her grandmother's is completely nuts. My wife enjoys telling the story of my first ever Christmas Eve with her family. I leaned over to her, eyes no doubt wide with fright, and whispered, "Who are all these people?"

"This is my immediate family!" she proudly declared. Neices and uncles and nephews and aunts and cousins once, twice, and thrice removed. (Being around this sprawling brood is great practice for the aspiring genealogist.) You see, growing up, we didn't have any family in town, so I was used to laid-back, quiet Christmases with my parents and two brothers. Nothing like the loud bazaar over in Florence full of shouts, screeching monkeys, and goods of all sorts.

So maybe I was conserving my mental energy and couldn't spare the cycles Sally's worthy cause deserved.

When we go to Florence, my mother-in-law is great about offering to keep the kids so Sam and I can sneak out for a quiet date. One of our favorite places do go is Dale's, same brand as Dale's sauce you can buy in stores. Wonderful, delicious, scrumptuous steak, and they do everything for you but wipe your mouth when you're done. Order ribs and they even bring you warm wet towels with lemon slices. Well worth the trip, and I detest sitting in a car!

The other is Ricatoni's, an Italian restaurant on Court Street. On the drive over, we'd talked about maybe going there for lunch or dinner but didn't make firm plans. After sufficient recovery from the Christmas Eve piranha tank, cabin fever started to set in, so off we traipsed for my bride to feed her toasted-ravioli jones.

"Let's give a big tip to our waitress," Sam suggested on the way over, and the conspirators proceeded to carry out their plan. The food was outstanding as always. I had the catch, so I forgot for a while that I was six hours inland.

On the way out, I handed our waitress, probably a student at UNA, the bill folder, wished her a merry Christmas, and walked out feeling satisfied body and soul.

Monday, December 29, 2008

Whose rev is it anyway?

Recently a teammate reported an inconsistency between our code and documentation: the cloud altitude in our rain model is supposed to be in units of meters with a default of 3km, but the default in the code was 10.

We checked both snapshots we thought they had, but both were in order. The last time the default changed in the trunk was over a year ago, and that was a change in units (i.e., 3.0 to 3000.0). 'Maybe they changed the code,' I thought but then remembered that the finger-pointing game is an evil at whose very root we must strike!

Principle is great — in principle — but now I had to hunt through more than a hundred tags to clear dB's name. That's a lot of clicky-clicky in the HTTP view. Instead, I could pull copies of rain_model.c from all hundred-plus tags and grep those.

Ugh. There ought to be a quicker way.

Then I remembered importing our Subversion repository into a Git repository using git-svn. With git-grep, searching through all those revisions is straightforward:

$ git grep 'cloud_altitude *= *[^3 ]' \
  `git branch -a | grep tags` -- \
  libs/env/rain_model.c
Joy!

The [^3 ] bit in the search pattern means find a character that's neither a 3 nor a space, the latter being necessary to prevent spuriously matching a space to the left of the value being assigned — effectively asking for all assignments in all tags to cloud_altitude. Not what we want.

Unlike Subversion, Git's operations are almost all local. That means fast! The above search ran in less than a quarter of a second.

Turns out the weird default was our doing after all, from a nearly two-year-old engineering release. Here's to keeping egg off our faces!

Wednesday, December 17, 2008

SEC coaches spoof

Tuesday, December 16, 2008

Elvis + bacon =

Friday, December 05, 2008

Grrr!

My son's basketball team has a game tomorrow at Mount Carmel — tipoff at 3pm, same time as the national championship game. Our people asked the other team to reschedule, but they refused — probably a bunch of bitter Aubies.

Monday, November 17, 2008

Affordable Places to Weather the Downturn

Judged by affordability, property taxes, and job growth, Alabama's Madison County — home to deciBel Research! — tops Forbes magazine's list of places to wait out the coming storm.

Thursday, November 06, 2008

Mr. Obama, tear down this "PATRIOT" act!

Back up the campaign-trail talk about civil liberties with real action: demand that a repeal of this abomination be on your desk no later than the end of your first week in office. Given your party's control of the congress, you are the lone obstacle to blotting out this shameful spot.

If this is not an urgent priority for your administration, then congratulations for conning millions of Americans.

Monday, November 03, 2008

Friday, October 31, 2008

Accountability, one element at a time

At the end of September and beginning of October, the U.S. House of Representatives voted on a proposed bailo"rescue" plan for poorly managed Wall Street firms. HR 3997 was the first vote, and it failed so back to the drawing board! In the words of Rep. Ron Paul of Texas, "It’s amazing, you take a very, very bad bill, appropriating $700 billion, you can’t get enough votes to pass it so you take it back out, you make it much worse and take it up to over $800 billion." The "much worse" version was the one that passed, so the obvious question is which of our public servants made this possible? This post is a literate Haskell program: copy-and-paste it into a file with the extension "lhs" (say, turncoats.lhs) to get a working program! First, a bit of front matter to import libraries that we'll be using.
> {-# LANGUAGE Arrows #-}

> module Main where
> import Control.Monad
> import Data.List (groupBy, intercalate, sort)
> import qualified Data.Map as M
> import System.Environment
> import Text.XML.HXT.Arrow
The House makes available on the web results of recorded votes:
> hr3997 = "http://clerk.house.gov/evs/2008/roll674.xml"
> hr1424 = "http://clerk.house.gov/evs/2008/roll681.xml"
Despite the way they look in your browser, the resources linked above are XML document instances — verify for yourself with View Source — that we can use for a little accountability. The agenda for our program is straightforward: pull the results of the votes, extract the votes from each, and output the flip-floppers. As a bit of lagniappe, we group the principled stalwarts into classes according to how they changed their votes.
> main :: IO ()
> main = do
>   a <- runX $ readDoc hr3997 >>> votes
>   b <- runX $ readDoc hr1424 >>> votes
>   let turncoats = flipFlops a b
>   forM_ (groupBy same (sort turncoats)) $
>     \ xs -> do
>       let (v,v',_) = head xs
>           n = show $ length xs
>       putStrLn $ v ++ " -> " ++ v' ++ ": (" ++ n ++ ")  "
>       putStrLn $ intercalate ", " (map name xs)
>       putStrLn ""
>   where
>     a `same` b = before a == before b && after a == after b
>     before (v,_,_) = v
>     after  (_,v,_) = v
>     name   (_,_,n) = n
>     readDoc = readDocument [(a_tagsoup, "1")]
We'll represent each vote by pairing a representative's name with his yea-or-nay:
> type Name = String
> type Vote = (Name, String)
For a baseline, we use HR 3997 to build a hash table whose keys are representative names and whose values are the corresponding votes. Then for each vote from HR 1424, we compare the latter vote against the former, making note of those members who changed their votes. As the type of flipFlops indicates, the result is a list of tuples of the form (former-vote, latter-vote, rep-name).
> flipFlops :: [Vote] -> [Vote] -> [(String, String, Name)]
> flipFlops before after =
>   let prev = M.fromList before
>   in after >>= ff prev
>   where
In cases where a member did not vote on the earlier issue, lookup produces an error value, which is Nothing inside the Maybe monad. In Haskell, we don't get NullPointerExceptions. The astute reader will note that flipFlops is not fully general: it doesn't report cases where representatives voted on the former question but not the latter.
>     ff prev (name, latter) =
>       case M.lookup name prev of
>         Just former -> if former == latter
>                          then []
>                          else [(former,   latter, name)]
>         _           ->        [("<none>", latter, name)]
These are the bits that worry about slogging through the XML, but XPath makes it straightforward: the expression below says we want all recorded-vote elements, and those are children of the vote-data element, which are children of the rollcall-vote element at the document root.
> votes :: ArrowXml a => a XmlTree Vote
> votes = getXPathTrees "/rollcall-vote/vote-data/recorded-vote" >>>
>   proc rv -> do
>     name <- getName -< rv
>     vote <- getVote -< rv
>     returnA -< (name, normalize vote)
Consider the structure of a recorded-vote element:
<recorded-vote>
    <legislator>Cramer</legislator>
    <vote>Aye</vote>
</recorded-vote>
So for each recorded-vote, we extract the inner-text of the legislator and vote child elements.
>   where
>     getName = getChildren >>>
>               isElem >>> hasName "legislator" >>>
>               xshow getChildren
>     getVote = getChildren >>>
>               isElem >>> hasName "vote" >>>
>               xshow getChildren
Due to supremely lovely irony, yea is not yea nor nay nay in the recorded votes, so we have to normalize.
>     normalize "Yea" = "Y"
>     normalize "Yes" = "Y"
>     normalize "Aye" = "Y"
>     normalize "Nay" = "N"
>     normalize "No"  = "N"
>     normalize v     = v

Finally the output:

N → Y: (58)
Abercrombie, Alexander, Baca, Barrett (SC), Berkley, Biggert, Boustany, Braley (IA), Buchanan, Carson, Cleaver, Coble, Conaway, Cuellar, Cummings, Dent, Edwards (MD), Fallin, Frelinghuysen, Gerlach, Giffords, Green, Al, Hirono, Hoekstra, Jackson (IL), Jackson-Lee (TX), Kilpatrick, Knollenberg, Kuhl (NY), Lee, Lewis (GA), Mitchell, Myrick, Ortiz, Pascrell, Pastor, Ramstad, Ros-Lehtinen, Rush, Schiff, Schmidt, Scott (GA), Shadegg, Shuster, Solis, Sullivan, Sutton, Terry, Thompson (CA), Thornberry, Tiberi, Tierney, Wamp, Watson, Welch (VT), Woolsey, Wu, Yarmuth

Not Voting → Y: (1)
Weller

Y → N: (1)
McDermott

Tuesday, October 07, 2008

Friday, July 04, 2008

What could have been

As Doug Newman put it, "I write this on July 4, when we celebrate the ouster of a 'tyrant' who taxed his subjects at the rate of about three percent."

Today, Gary North wrote, "When Jefferson wrote [the declaration of independence], the British were extracting approximately 1% of national income from the American colonies. For the southern colonies, it may have been 2.5%. If we could somehow get back to the tyranny of Great Britain in 1776, I would be willing to celebrate the Fourth of July with greater enthusiasm. But that would take a revolution."

Tuesday, June 24, 2008

Dear Coach Saban

After the latest disaster, please consider radical action: tear up the scholarships of all players who signed with your incompetent predecessor. He didn't look for character and heart in his recruits, and it shows on and off the field. Before more of his deadwood falls and does further damage, get out in front of the problem.

Yes, that will make for a rough couple of years, but after the torture we've taken since Coach Stallings left, we can tough it out a little while longer.

Sunday, November 25, 2007

How to lose six in a row to a cow college

Play with all the fire, intensity, and desire of a house fern.

Monday, September 17, 2007

Dear Coach Saban

Just beat Auburn.

Saturday, August 18, 2007

Word ladder in Haskell

Another followup to my earlier post about searching for word ladders, this time using Haskell!

This blog post is a Haskell program, written using the "literate comment" convention.

First a bit of front matter. This implementation of the word-ladder search will use the State and list monads.


> module Main where
> import Control.Monad.State
> import Data.Char
> import Data.List (find)
> import Data.Set (Set, member, difference)
> import qualified Data.Set as Set
> import System.Environment (getArgs)
> import System.Exit

The idea is simple: read the dictionary, search for the desired ladder, and show it to the user:


> main :: IO ()
> main = do
>   (start, goal, dict) <- getArgs >>= parse
>   fullDictionary <- readDictionary dict
>   print $ search start goal (trim fullDictionary start)

Remember that getArgs is an action that returns the list of command-line arguments. We bind this action to the following:


>   where parse [start,goal,dict] = return (start,goal,dict)
>         parse [start,goal]      = return (start,goal,"/usr/dict/words")
>         parse _ =
>           putStrLn "Usage: ladder start goal [ dictionary ]" >>
>           exitWith (ExitFailure 1)

Haskell's pattern matching shows that the program takes two or three arguments. The first two are the start and goal words. The optional third argument is the path to a dictionary (one word per line) to use.

We condition the dictionary by eliminating words whose lengths differ from the length of the start word and also converting everything to lowercase.


>         trim :: [String] -> String -> [String]
>         trim words start = filter (sameLength start) (lc words)
>
>         sameLength start = (== length start) . length
>
>         lc = map (map toLower)

The search can fail, so result is of type Maybe [String]. Handling both cases is straightforward:


>         print Nothing = putStrLn "No ladder found."
>         print (Just a) = mapM_ putStrLn a

The dictionary's format is simple, so reading it is a matter of extracting the lines from the file:


> readDictionary :: FilePath -> IO [String]
> readDictionary path = liftM lines $ readFile path

Now for the fun bits. Imagine a graph where nodes are words from the dictionary and where edges are between words that are "one hop' from each other, i.e., words that could be on consecutive "rungs" of a ladder.

Beginning with the start word, the program performs a breadth-first search of this graph. We call the set of words reached in the most recent iteration the "fringe." When the fringe contains the goal word, we're done.

The state monad simulates destructive update in imperative programming languages. (Haskell is purely functional.) Without it, we'd have to explicitly thread the state value through the call chain, but with it, we retrieve and update the state value with get and put as below:


> search start goal words =
>   evalState (loop [[start]]) (Set.fromList $ filter (/=start) words)
>   where
>     loop :: [[String]] -> State (Set String) (Maybe [String])
>     loop [] = return Nothing
>     loop paths = do
>       next <- step paths
>       let newFringe = fringe next
>       words <- get
>       put $ words `difference` newFringe
>       if goal `member` newFringe
>         then return $ Just (winner next)
>         else loop next

The list monad is handy for representing nondeterministic computations. In concept at least, the search carries around a list of lists that has all of the partial results computed so far.

For example, if the start word is dog, the state value on the second iteration might be [["dog", "dig"], ["dog", "fog"], ["dog", "bog"]]. This approach might seems to be a memory pig, but it remains surprisingly frugal.

To proceed to the next iteration of the search, for each partial result (one ladder beginning with the start word) we find the as-yet unseen neighbors of its last element (a member of the current fringe) and replace the current partial result with new ones for each of the neighbors. Again, consider the partial results at the second iteration in the previous paragraph.


>     step :: [[String]] -> State (Set String) [[String]]
>     step paths = do
>       words <- get
>       return $ paths >>= augment words
>
>     augment :: Set String -> [String] -> [[String]]
>     augment words path = [ path ++ [n] | n <- ns ]
>       where ns = Set.elems $ neighbors (last path) words
>     
>     neighbors :: String -> Set String -> Set String
>     neighbors word words = Set.filter (oneHop word) words
>       where oneHop [] [] = False
>             oneHop (x:xs) (y:ys) | x /= y = xs == ys
>                                  | otherwise = oneHop xs ys

As described above, the fringe is the set of words at the ends of the partial ladders computed so far:

>     fringe :: [[String]] -> Set String
>     fringe paths = Set.fromList (map last paths)

Once we've seen the goal in the fringe, we return the ladder that ends with the goal word:

>     winner :: [[String]] -> [String]
>     winner paths =
>       case (find ((== goal) . last) paths) of
>         Nothing -> undefined
>         Just a -> a

Saturday, August 04, 2007

Word ladder in Python

In an earlier post, I described an implementation in Common Lisp of a breadth-first search to find word ladders.

This time I practiced the kata using Python. Python's list comprehensions help to make the solution concise, but apparently the lunch isn't free. For example, I could have written one_hop as

    def one_hop(a, b):
      return len([aa for aa, bb in zip(a, b) if aa != bb]) == 1

but that resulted in about a twenty percent slowdown.

The code falls out pretty easily:

#! /usr/bin/env python

"""Usage: %(prog)s start-word goal-word [ dictionary-path ]
"""

import sys

prog = sys.argv[0]

def read_words(path):
  words = []

  try:
    f = open(path, "r")
  except IOError, (errno, error):
    sys.stderr.write("%s: open %s: %s\n" % (prog, path, error))
    sys.exit(1)

  for word in f:
    words.append(word[:-1].lower())

  return words

def unpack_args(args):
  dict = "/usr/dict/words"

  if len(args) < 2 or len(args) > 3:
    sys.stderr.write(__doc__ % globals())
    sys.exit(1)

  start, goal = args[0:2]
  if len(args) == 3:
    dict = args[2]

  return (start, goal, dict)

def one_hop(a, b):
#  return len([aa for aa,bb in zip(a, b) if aa != bb]) == 1
  hops = 0
  for aa, bb in zip(a, b):
    if aa != bb:
      hops += 1

  return hops == 1

def rungs(start, goal, begat):
  path = [goal]
  while path[-1] != start:
    path.append(begat[path[-1]])
  path.reverse()

  return path

def ladder(start, goal, dict):
  if len(start) != len(goal):
    return None

  words = read_words(dict)
  candidates = set([w for w in words if len(w) == len(start)])

  start = start.lower()
  goal  = goal.lower()

  begat = {}

  last = [start]
  while len(last) > 0:
    fringe = []

    for w in last:
      neighbors = [n for n in candidates if one_hop(n, w)]

      for n in neighbors:
        begat[n] = w
        candidates.remove(n)

      if goal in neighbors:
        return rungs(start, goal, begat)
      else:
        fringe.extend(neighbors)

    last = fringe
  else:
    return None

def main(args):
  start, goal, dict = unpack_args(args)

  path = ladder(start, goal, dict)
  if path is None:
    print "%s: no path from '%s' to '%s'" % (prog, start, goal)
  else:
    for w, i in zip(path, range(1, len(path) + 1)):
      print "%3d. %s" % (i, w)

  return 0

if __name__ == "__main__":
    sys.exit(main(sys.argv[1:]))

Friday, June 15, 2007

Word ladder

You form a word ladder by changing exactly one letter in the current "rung" to form the next. For example, the following is a ladder from 'paste' to 'carry':

  1. paste
  2. pasty
  3. party
  4. parry
  5. carry

Given starting and goal words, the Lisp code below performs a breadth-first search in the supplied dictionary. Using BFS has the interesting property of guaranteeing that the path found is the shortest between the two words.

I'm not really pleased with the result: there's not enough abstraction. I guess with Lisp, it's hard to be satisfied unless you write a couple of fly-daddy macros that reduce the meat of the code to about three lines.

(defparameter *default-dictionary*
  #P"/usr/dict/words"
)


(defvar *dictionary* (make-hash-table :test #'equal))

(defun ladder (start goal)
  (if (/= (length start) (length goal))
      (error "'~S' and '~S' have different lengths" start goal)
      (let* ((dict (read-dictionary))
             (candidates (ladder-candidates dict start))
             (seen (make-hash-table :test #'equal))
             (begat (make-hash-table :test #'equal))
             (todo (list start))
)

        (loop while todo do
              (let ((next '()))
                (loop for word in todo do
                      (let ((neighbors (neighbors word candidates seen)))
                        (loop for w in neighbors do
                              (setf (gethash w seen) 1
                                    (gethash w begat) word
)
)

                        (if (find goal neighbors :test #'equal)
                            (return-from ladder (rungs start goal begat))
                            (setf next (nconc next neighbors))
)
)
)

                (setf todo next)
)
)

        (error "No path from '~A' to '~A'" start goal)
)
)
)


(defun read-dictionary (&optional (path *default-dictionary*))
  (let ((cached (gethash path *dictionary*)))
    (if cached
        cached
        (let ((dict '()))
          (with-open-file (s path)
            (loop for word = (read-line s nil)
                  while word do
                  (push word dict)
)
)

          (setf (gethash path *dictionary*) dict)
)
)
)
)


(defun ladder-candidates (dict start)
  (let ((candidates '())
        (len (length start))
)

    (loop for w in dict
          when (and (= len (length w)) (string-not-equal w start)) do
          (push (string-downcase w) candidates)
)

    candidates
)
)


(defun one-hop-p (from to)
  (let ((hops 0))
    (loop for ff across from
          for tt across to
          when (char-not-equal ff tt) do
          (incf hops)
)

    (= hops 1)
)
)


(defun rungs (start goal begat)
  (let ((path (list goal)))
    (loop for word = (first path)
          for parent = (gethash word begat)
          while (string-not-equal word start) do
          (push parent path)
)

    path
)
)


(defun neighbors (word pool &optional (seen (make-hash-table)))
  (loop for w in pool
        when (and (one-hop-p word w)
                  (not (gethash w seen))
)

        collect w
)
)


(defun one-hop-neighbors (word)
  (neighbors word (ladder-candidates (read-dictionary) word))
)

Friday, May 18, 2007

I *seen* it!

I've been meaning to put this baby up forever, and I finally got around to scanning it (albeit two years later as you can see from the date).

This was the game where where Jamie Christiansen won the game with that ugly kick and of course Roman Harper's famous forced fumble, memorialized by Daniel Moore in "Rocky Stop." I'd still like to add a copy next to Tyrone Prothro's amazing catch and put the stub inside the frame.

Before the game, I got to meet my aunt, uncle, and a couple of cousins for some mean Mexican. That was after the Florida game where we humbled the cocky Urban Meyer. I heard the ground was literally rumbling from all the cheering. Wish I coulda been there too!

We had great seats -- at the 40 yard line -- and could see everything. I remember being sick of hearing it from my Tennessee-fan friends (if there can be such a thing). I even told my aunt that I'd rather beat UT than Auburn if we could only have one.

(If you remember, that was how it ended up. My brother-in-law who scored those tickets also had a hookup for Iron Bowl tickets. After Prothro took that horrific injury on a stupid, needless, low-class, NFL-style showoff long pass when the Gators were already starting to load the buses -- Shula, you dog! -- we just didn't have it. They were mine for the taking, and I easily said, "No thanks.")

But now the bad times are behind us: it's morning in Alabama!

Monday, April 16, 2007

Tuesday, March 20, 2007

It's official!

Not long ago, I was on the same flight to DC with Bud Cramer. When we reached the terminal at Reagan, I said to him, "Congressman, give my best to Ron Paul!" An honest man and perhaps the humble American republic's last hope, Dr. Paul is officially a candidate for president!

Notable quotes:

  • "I'm very confident about the message of liberty and the constitution. I'm very confident that the American people are sick and tired of what they're getting. And I'm also very confident that the Republican party has gone in the wrong direction. We used to be the party of small government, but now we're the party of Big Government."
  • "My main thrust would be I would emphasize my oath of office. As a congressman, I emphasize that. As president, I would emphasize that. And that is, to obey the constitution, which strictly limits the power of government. It strictly limits the power of the executive branch. It strictly limits the power of the congress -- and even the courts. That would be my goal: to shrink the size and scope of government, believing very sincerely that the benefits to people are far better off in a free society than in an authoritarian society. When government is involved in central planning, and running the world, running the economy, and running our personal lives, we're not better off: we're worse off."
  • "If we don't get a handle on the entitlements, if we don't get a handle on all this foreign adventurism, this country is going broke. Actually, I think the country is insolvent. It's just the fact that the world still accepts our dollars that we can still get away with this. Yes, we can have full accountability, but the ultimate accountability has to be to make sure that we hold government under control -- that we not allow it to continue to grow or try to do everything conceivable at the central level."
  • "Very simply, governments always like inflation, that is, the creation of money out of thin air to debase the value of your currency. This is the reason that we don't have a gold standard: because big-government conservatives and big-government liberals like to spend money. But they really don't like the taxes, and there's a limit to how much they can borrow... and every time they create new money, they devalue the money we have in our pockets. So it's a tax on us; it's a sinister, immoral tax..."
  • "[Inflation is] so destructive because it's the most regressive of all taxes. Poor people and the middle class eventually get wiped out by rising prices. Now government tells us there's only a 2% inflation rate, but that's not true: the inflation rate for poor people and the middle class might be 6 or 8 or 10 percent. Who benefits the most? It's the wealthy class: the bankers, the domestic industries, the military-industrial complex."
  • "The answer to this is gold and silver, and that's still the law of the land. Under the constitution, only gold and silver can be legal tender, yet it's been a good many years since we've completely forgotten about it. We've had no connection -- our dollar's had no connection to gold since 1971. If you look at the problems we've had since that time, they're definitely related."
  • "I would come home [from Iraq] as soon as possible."
  • "Liberty will provide the answers that we need."

Dr. Paul is for peace and friendships among nations. When he gives his solemn word to uphold and defend the constitution, he'll really do it: he won't merely be reading a script. A politician is actually making an issue of sound money!

Ron Paul is a true American. See the video below for more details.

Sunday, March 11, 2007

Wal-Mart, health care, and irresistable market forces

Bo's post today about Wal-Mart made me think of an excellent definition, thanks to Byrne's Eye View:

capitalism
Economic system under which any legitimate complaint can be rephrased as a decent business plan…

Bo's complaint is about customer service: it can take a long time to get in and out of the place. In a free market, goods are allocated by price and by time. When we think of Tiffany & Co., for example, a price tag with many digits comes to mind, but if a customer walks in weary from hauling around so much cash, they'll graciously relieve him of that burden.

Wal-Mart chooses the opposite corner: low prices but slow service. Target's business model attracts customers with more money to spend, and they do it with features such as cleaner stores and better customer service, which their customers value more highly than the few extra dollars that they trade in return.

Even deeper in the corner of low price and long lines are the popular proposals for "free" health care. (As P.J. O'Rourke quipped, "If you think health care is expensive now, wait till it's free.") The "free" health care in Canada and the UK are characterized by long waiting lists -- which exist for exactly the same reasons as the bread lines in the Soviet Union.

Economist Ludwig von Mises wrote, "Even the most mighty government, operating with the utmost severity, cannot succeed in endeavors that are contrary to what has been called 'economic law.'" The mighty United States government has sort of a pilot program for "free," "single-payer" health care: the VA's frightening maze, and, boy, is it a success!

I'm confident that the calls for "free" health care are well-meaning, but their inevitable result would cruelly force everyone into the same trap -- while politicians insult everyone with unending proclamations of success. (Don't be surprised if members of the congress also give themselves a "special" health care system just as they did with Social Security.)

The lesson is simple: there ain't no such thing as a free lunch.

Saturday, March 10, 2007

"How's that working out for you -- being clever?"

Timeless political commentary

Insincerity. Gratuitous appeals to emotion. Tired clichés. Focus-groupped pablum. Wanton demagoguery.

Refuse to allow your mind to be filled with this trash! Instead, enrich your mind with reasoned, intellectual analysis:

What is the attitude of the democrat when political rights are under discussion? How does he regard the people when a legislator is to be chosen? Ah, then it is claimed that the people have an instinctive wisdom; they are gifted with the finest perception; their will is always right; the general will cannot err; voting cannot be too universal . . .
But when the legislator is finally elected — ah! then indeed does the tone of his speech undergo a radical change. The people are returned to passiveness, inertness, and unconsciousness; the legislator enters into omnipotence. Now it is for him to initiate, to direct, to propel, and to organize. Mankind has only to submit; the hour of despotism has struck.

The passage above comes from The Law by Frédéric Bastiat, available as a two-part audio book from FreeAudio.org.

Remember this one?

Thursday, March 08, 2007

Mr. Dylan can moo! Can you?

Yes, it's as cool as you imagine!

Waterfalls are bad, mmmkay?

Adobe's Photoshop team reports success and joy from abandoning waterfall! For details, read an interview with co-architect Russell Williams in which he talks about the benefits of such practices as nightly builds; running, tested features; and continuous integration.

42 Presidents in 10 Minutes

42 presidents remain

Named so far:
None

Saturday, March 03, 2007

Ron Paul on CNN

In this appearance from February 26, Dr. Ron Paul talks about economics, foreign policy, immigration reform, and upholding the constitution.

Saturday, February 24, 2007

My first monadic program!

Problem 32 from Project Euler reads

The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

Not one of my brighter moments, the first approach I considered was applying goon-force to permute a list of eleven characters ('1' .. '9', 'x', and '=') -- a search space of almost 40 million -- looking for well-formed and valid statements.

Initially, I looked at using Text.Regex. As I was fishing for examples to crib from, I saw a suggestion that people may as well use Parsec, the monadic parser combinator library. So let's knock out the preliminaries:

> module Main where
>
> import Data.List hiding (map)
> import Text.ParserCombinators.Parsec

A parser for the simple expressions reads easily:

> num :: Parser Int
> num = do ns <- many1 digit
>          return $ read ns
>
> expression :: Parser (Int,Int,Int)
> expression = do multiplier <- num
>                 times <- char 'x'
>                 multiplicand <- num
>                 equals <- char '='
>                 product <- num
>                 return (multiplier, multiplicand, product)

Generating permutations is no problem in Haskell:

> permutations :: [a] -> [[a]]
> permutations [x] = [[x]]
> permutations xs =
>   [ y : zs
>   | (y,ys) <- selections xs
>   , zs     <- permutations ys
>   ]
>
> selections []     = []
> selections (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- selections xs]

I'd been wanting to solve as a learning example one of the Project Euler problems using monads. As I tried to shoehorn the problem into a monadic solution, I remembered the characterization of the Maybe monad as being useful for computations that can fail, and I saw two possibilities for failure: garbage input (e.g., "x=123456789") and false statements (e.g., "1x2=3456789").

Having a particular permutation, check tests whether it's well-formed and valid:

check :: String -> Maybe Int
check s = do
  result <- parseExpr s
  p <- validProduct result
  return p

parseExpr :: String -> Maybe (Int,Int,Int)
parseExpr s =
  case parse expression "expression" s of
    Left err -> Nothing
    Right tuple@(mr,md,pr) -> return tuple

validProduct (mr, md, pr)
  | mr * md == pr = Just pr
  | otherwise = Nothing

The test goes just as you would describe it to someone else: parse the input to extract the components of the mulitiplication and then check whether the multiplication holds. Simple.

You wonder, 'But what about when the parse fails or when the statement is bogus?' Those checks are still happening, but the Maybe monad and the do-notation syntactic sugar are performing those checks implicitly! "Control" (to borrow an imperative concept) reaches the return p line only if both the parse and validProduct succeed. Otherwise, check bails and returns Nothing.

All that's left to do is feed it input and sum the result. Note: it's very s-l-o-w.

p32 = sum $ elems $ fromList $ catMaybes $ map check (permutations cs)
  where cs = ['1','2','3','4','5','6','7','8','9','x','=']

An obvious improvement is to use nub instead of (elems . fromList). Even better, lists are also monads, so Maybe distractions disappear with only a few very minor changes:

> p32 = sum (nub $ concatMap check (permutations cs))
>   where cs = ['1','2','3','4','5','6','7','8','9','x','=']
>
> main = print p32
>
> check :: (Monad m) => String -> m Int
> check s = do
>   result <- parseExpr s
>   p <- validProduct result
>   return p
>
> parseExpr :: (Monad m) => String -> m (Int,Int,Int)
> parseExpr s =
>     case parse expression "expression" s of
>       Left err -> fail (show err)
>       Right tuple@(mr,md,pr) -> return tuple
>
> validProduct :: (Monad m) => (Int,Int,Int) -> m Int
> validProduct (mr, md, pr)
>   | mr * md == pr = return pr
>   | otherwise = fail "invalid product"

This works because failure in the list monad is the empty list, and concatMap gets rid of all the empties.

Saturday, February 17, 2007

Very touching short animation

I saw this video when my wife was in St. Louis at a baby shower for one of the girls she played volleyball with in college and my kids were at my mother-in-law's. So moving.

Thursday, January 11, 2007

A candidate worth supporting

Ron Paul filed papers to form an exploratory committee!

In an interview, Dr. Tom DiLorenzo said, "No one is proposing anything near constitutional government. I consider the act of voting to be treasonous to the Constitution." Unlike so many of his colleagues, Paul has read but also works diligently to apply the constitution properly.

Peace. Freedom. Property. Vote for Dr. Ron Paul.

Wednesday, January 03, 2007

Bo stole my line!

Bo stole my line! (Not really -- he gave an attribution and everything -- but "Bo follows MLA style" is a pretty lame headline.)

A relative of my wife's -- one of those baby-mama-sista-cousin kind of deals -- knows someone connected to the Bama athletic department and had been saying since around Thanksgiving that Nick Saban was a done deal.

Given Saban's strong denials, it didn't seem likely at all. Bill, I'm glad I was wrong!

Shula was a clown. He's gone, so it's morning in Alabama.