19 March 2014
19 March 2014

Code kata 4: Word ladder

Naming things can be very hard, yet a well-chosen name can really help a reader understand how your code works. This code kata is an old favorite, one that we’ve done before, but this time we’ve added an emphasis on naming things well.

The kata

A word ladder is a sequence of words (each of which forms a rung on the ladder) where each word is formed from its predecessor in the sequence by a simple transformation. The possible transformations are substitution (changing a single letter for any other in the alphabet), rearrangement (swapping places of two adjacent letters in the word, inserting a letter, and deleting a letter.

Thus, if we take move and pave as our start and end words, then the following are two valid word ladders formed by substitution only:

  1. move
  2. more
  3. core
  4. care
  5. cave
  6. pave

and

  1. move
  2. cove
  3. cave
  4. pave

The task

Write a program that, given a start word and an end word, will compute a corresponding word ladder. Your program should prefer shorter ladders over longer ones.

Start off by using only substitution to form the ladder. If you have time at the end, add the ability to include rearrangements as well.

You can use any suitable word list, by the way, as your source of valid words.

Constraints

We’re going to do this kata by TDD, but with an added step to focus the task on clear naming. So, split out the TDD steps to look like this:

  1. Red: Write a failing test.
  2. Green: Implement the minimal, sensible functionality to pass the test.
  3. Refactor until you’re proud of your code.
  4. Rename any classes, members or variables that don’t explicitly state their purpose.

 

Share this post.

Share on FacebookShare on Google+Share on LinkedInTweet about this on Twitter

Related posts

Also in Blog

Learning from the Accelerate “Four Key Metrics”

There's been a lot of excitement about the book Accelerate, which summarizes research from the past several years of the State of DevOps Report from DORA (which Redgate sponsors).

Perhaps the most po...

Also in Software development

How to unlock the budget for your next IT initiative – free Redgate webinar

When you’ve got a great idea for transforming software development or IT processes in your organization, it can be frustrating. You might have a clear picture of what you can achieve, but often you...

Also about Code Katas

Code kata 7: Producer-consumer problem

First, apologies for nodding off and not posting for the last few weeks. I have the usual set of excuses, which you can guess easily enough without the need to read them here.

So, on to the kata: som...