Playing chess with Maddy

My four-year-old daughter wanted to play against the computer in Chess Titans. Observations:

• She plays an unorthodox opener: p-h4 and then continuing right-to-left, she advanced pawns one or two spaces (apparently at random).
• No concept of position.
• Her understanding of material advantage is better suited for checkers: a few times, she asked, "Do I have more of their people?"
• Her strategy is better suited for a first-person shooter. A couple of times, I tried to explain that she was making bad trades, but the appeal of capturing was irresistible.
• Knights on d2 and e2 were highly comforting.

Still, it's a start!

Kids say the darndest things

This morning on the way to school, my 8-year-old son and I were talking about his spelling words. One was investor, and I asked whether he knew what it meant.

"Is it someone who invents something?"

"No, that's an inventor. Hmm, let's see. Do you know what profit is?"

"Like the guy in Halo?"

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."

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%

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.

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!

SEC coaches spoof

Elvis + bacon =

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.

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.

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.

"Vincent" by Tim Burton

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

Toy Story got a lot cooler!

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."

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.

How to lose six in a row to a cow college

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

Dear Coach Saban

Just beat Auburn.

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

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:]))