Recursing the Interwebs

A bit in the accumulator

Life has changed.  We’re moving to Seattle, where I got a way-super-rad-nerd-gig and my wife has family in that area.

To add rad to awesome, I sent the following email to some family members earlier this week:

As you may know, I am partly responsible for Shelly’s current
plight—that is to say it is probably my fault that she vomits thrice
daily.

Low and behold, when we went to the doctor today, we discovered that
there was a large, olive-shaped object which is chiefly responsible
for the frequent evacuations.

Since it is the size of a large olive, we’re calling it either Oliver,
or Olivia.  As it grows to be the size of other foods, I’m sure we’ll
change its name.

Little-O’s heart was beating at 167 bpm!  We saw its little feet and
hands.  Our first time seeing Little-O I noticed that it did not have
a neck, to which I quipped, “it will never be the head of a major
corporation.”  The doctor quickly proved to me that Little-O does in
fact have a neck and that all signs point to a healthy, little,
olive-shaped human-thing.

At any rate, we’re super-excited and we wanted to share our excitement with you.

The doctor mentioned that the due date will be around April 27.  I’ve
already apologized to Beef that we cannot be there for when Baby Bash
(Beef + Ash = Bash) comes along, but I think he understands.

I partly fear The Wrath Of Mom—after all, how could Shelly and I be
so insensitive as to have started Little-O at the same time as The
Bashworks were beginning?  All I can say in my defense is that Beef
and I come from fertile stock and QED.

Love you guys,
Dave, Shelly and Little-O, the Human-thing.

Surprisingly, I’m not tickled by the thought of referring to Oliver/Olivia as “Weiser Spawn” (much to my wife’s relief).  Seeing Little-O move and groove, hearing its heartbeat and then recognizing that my wife and I (but mostly my wife) are building another human from scratch has made me awestruck.  I feel a seriousness and a preciousness that I did not expect to feel.

How life changes.  I’m sure the content of this blog will change as time goes on.

How do I test solutions to search problems?

I was recently given a programming challenge where I had to solve the game Boggle.  I ended up implementing the solution by, first, using greedy search to create a board configuration and then, second,  running 100 simulations remembering the board configuration which had the highest score.  If you’re interested in what I did, take a gander at my solution.

(Beware though, the code is ugly as I only had 72 hours to implement a solution.  I’m not content with the small amount of tests I wrote, there are things I could clean up to make the code more understandable, I hit a learning curve using Maven and I only implemented one solution to the problem instead of exploring multiple solutions.  Please keep in mind that most of those 72 hours were spent either at work or I was sleeping.)

But this post really isn’t about what approach I took to solve the problem.  This post is about how I learned to trust the output of the simulation.  Or, to put it another way, “how do I test solutions to this search problem?”

Historically, for me, I always thought, “there’s no way I can test to ensure that a given board will have the maximum score out of all possible board configurations.”  Because of that, I wrote testing the code off as something that was impossible.

This time, though, I took a different approach.  I began to ask myself questions like:

What would the score be if the board was only filled with A’s and the dictionary I used had words which only consisted of A’s?  Could I find the maximum score of that board?

If I knew which words I placed on a board, when I created it, could I find those words when I go to score the board?

Isn’t it reasonable that the score of a board configuration that I plan out be higher than a randomly generated board configuration?

Suddenly, my view of what testing looked like changed.  I no longer looked at testing as a means to verify that an optimal solution was on the board, I looked at testing as a means to verify that a solution I generate is no worse than the worst solution I can think of.

What does this buy me?  

1. Data which, at least, hints that my code is working properly (instead of making hand-wavy arguments based on a single run), should someone challenge me on what I wrote.
2. Peace of mind, knowing that as long as my tests pass, I can change whatever code I want, confident that I did not reintroduce any bug.
3. Tests communicate how I intend to use my code.  New people looking at my code can get their heads wrapped around it easier since tests show example usage.

I hope that this helps you if you are writing AI code.

tumblrbot asked: WHAT IS YOUR EARLIEST HUMAN MEMORY?

My parent’s Doberman Pinscher, JoJo.  That dog was a sofa to me.

Women in Computer Science

Bar camps are awesome!  They create an atmosphere where learning and sharing ideas is really, really fun!  Two of the sessions I went to this year were about women in Computer Science (or, more accurately, lack of women in Computer Science).  One of the big questions discussed was, “why are there so few women studying Computer Science?”

One of the most popular responses to this question had to deal with how Computer Science is marketed to students.  When asking high school girls what they think Computer Science is, they tend to answer with either, ”I do not know,” or “it is something about video games.”

Both answers are understandable.  After all, it is fairly obvious what people with degrees in Education or Pharmacy or Nursing do with their degrees.  “Computer Science” as a term, however, can be rather ambigious.  Am I doing experiments on computers?  Am I going to be stuck in a lab forever, doing “science”? 

The answer involving video games is equally understandable.  How many video game lovers got into Computer Science because they wanted to create video games?  As a second grader, I certainly wanted to do programming so that I could create games.  Games are fun! 

After having gone through both an undergraduate and graduate studies in Computer Science, I’d throw in a suggestion on how to define Computer Science:

Computer Science is both the art of figuring out how to solve a problem and the skill of telling a computer what steps it needs to take to follow the solution to the problem.

This definition requires some explanation.  I’m sure you’re probably thinking, “what a wonderfully nonsensical definition, Dave.  Could you be more ambiguous?”

First off, what “problems” are being solved by Computer Science?  Any situation where you see that a computer being used is a problem that could be solved by having a degree in Computer Science.  Of course, these are not the only problems that this discipline can be useful in solving.  For instance, here is a problem:

Suppose that you are in a third-world country.  In this country, they are wanting to create their first, nation-wide telephone network.  For simplicity sake, say that there are four cities that need to be connected to this phone network.  The costs between any two cities are not be the same.  Below shows a picture of cities (the dots) and the cost to put a telephone line between two cities:

Your mission, should you choose to accept it, is to figure out how to connect all cities to the telephone network while minimizing the cost of the network.  

After you figured it out, can you cook up a set of instructions to each a 7 year old to find the answer?

If so, then congratulations, you (probably) just recreated Prim’s Algorithm, which is taught in Computer Science undergrad courses.

Now, if you enjoyed wrestling with that problem you may really enjoy Computer Science.  I promise that there are other, funner, problems to solve.:)

I am using Jetty as an HTTP server.  Part of what I want Jetty to do is serve JSP pages.

But, when getting Jetty from eclipse.org via:

JETTY_VERSION=7.0.2.v20100331
wget http://download.eclipse.org/jetty/$JETTY_VERSION/dist/jetty-distribution-$JETTY_VERSION.tar.gz
tar xfz jetty-distribution-$JETTY_VERSION.tar.gz
cd jetty-distribution-$JETTY_VERSION
java -jar start.jar

I noticed that a message would appear on the command line “No JSP support configured.”  This was really frustrating.

I later discovered that the Jetty package at eclipse.org doesn’t have the jsp libraries packaged with them, but you can find Jetty distributions with the JSP libraries here.

Hopefully this will save you a couple of hours of pain.

Tumbling with Tumblr

This is a post created from an email. Woot!