Kenny Dewhirst

I recently got a chance to work with Ruby for the first time. I’m pretty pleased with the result, and I thought it would make a pretty good post here.

What follows is what’s called a code kata, and comes from this website. Code katas are a kind of practice problem, and the word comes from a Japanese word for a kind of ‘practicing the motions’ martial art exercise. The problems are much simpler than most business problems, but are complicated enough to be interesting. There’s a full description of the idea here.

What this kata asks is to make a program that transforms one word into another by changing one letter at a time, without making any invalid words. This kind of problem was invented by Lewis Carrol, who called them ‘word ladders‘. This kind of logic problem is a good fit for katas because it gives us a chance to be clever; I have written this so that it always finds the shortest path between two words.

The code uses a word list of ‘real’ or ‘valid’ words named words.txt which must be in the same folder as the Ruby script for it to run.

# Checks to see if you can move from the first string to the second in a single
# move
def connected?(first, second)
  if first.length != second.length
    return false
  end

# Count how many letters in the first string are different from in the second
# string
  count = 0
  for index in 0..first.length
    if first[index] != second[index]
      count = count + 1
    end
  end
  count == 1
end

# Gets the set of words in a list that are connected to a given word by a
# single move
def get_connected_words(word, list)
  connected_words = []
  list.each{|word_to_check|
    if connected?(word, word_to_check)
      connected_words << word_to_check
    end
  }

  return connected_words
end

# Does the work of finding the chain by doing a breadth-first search of the
# dictionary
def find_chain(first, target)
  if first.length != target.length
    puts "There is no chain between '" + first + "' and '" + target + " because they are different lengths."
    return
  end

  # Build an array of unvisited words of the right length from our dictionary
  unvisited_words = []
  File.open('words.txt').each_line{ |line|
    if line.strip.length == first.length
      unvisited_words << line.strip
    end
  }

  # Now that we have a list of words of the right length in memory, we might as
  # well check our arguments for validity
  if !unvisited_words.include?(first)
    puts "There is no chain between '" + first + "' and '" + target + "' because '" + first + "' is not in my dictionary."
    return
  elsif !unvisited_words.include?(target)
    puts "There is no chain between '" + first + "' and '" + target + "' because '" + target + "' is not in my dictionary."
    return
  end

  puts "Please wait..."

  # Build a queue to hold the chains that we're going to try
  queue_of_chains = []

  # Add our degenerate chain (the start link) to the queue
  start_chain = Array.new()
  start_chain << first # Array with the single word in it
  queue_of_chains << start_chain

  # Remove our starting point from our list of nodes; we know it's a dead end
  unvisited_words.delete(first)

  success = false
  # Visit each chain in the queue, checking if the last link in the chain is
  # our target. Work finishes when we find a chain ending in our target
  # (success!) or we run out of queue (failure!)
  while !queue_of_chains.empty?
    chain_to_visit = queue_of_chains.shift()

    if chain_to_visit.last == target
      puts "Chain found!"
      success = true
      puts chain_to_visit
      break
    else
      # The chain we're looking at isn't a match, so try to add more things to
	  # our queue. We're adding copies of our chain, plus an unvisited word
	  # that will connect to the last link
      words_to_visit = get_connected_words(chain_to_visit.last, unvisited_words)
      words_to_visit.each{ |word|
        links_of_new_chain = Array.new(chain_to_visit)
        links_of_new_chain << word
        queue_of_chains << links_of_new_chain
      }

      # Don't let the words we just enqueued be added a second time
      unvisited_words = unvisited_words - words_to_visit
    end
  end

  if !success
    puts "Sorry, there is no chain connecting '" + first + "' and '" + target + "'."
  end
end

puts "This program tries to find a word chain between two words. Please enter a first word."
# All of the words in our dictionary are lowercase, so let's transform input
# rather than comparing case-insensitive everywhere else.
first = gets.chomp.downcase

puts "Okay; and your second word?"
target = gets.chomp.downcase

find_chain(first, target)

A little while back, I challenged myself to write a Scheme implementation of quicksort. After all, it’s a recursive algorithm, and Scheme is nothing if not recursive, and it seemed like a fun change of pace from writing algorithms in a procedural language.

; Quicksort a proper list
(define (quicksort lst)
  (cond
    ((null? lst)
     '())
    (else (append (quicksort (find-smaller-or-equal
                              (cdr lst) (car lst)))
                  (cons (car lst)
                        (quicksort (find-larger
                                    (cdr lst) (car lst))))))))

(define (find-larger lst lower-bound)
  (cond
    ((null? lst)
     '())
    ((<= (car lst) lower-bound)
     (find-larger (cdr lst) lower-bound))
    (else
     (cons (car lst)
           (find-larger (cdr lst) lower-bound)))))

(define (find-smaller-or-equal lst upper-bound)
  (cond
    ((null? lst)
     '())
    ((> (car lst) upper-bound)
     (find-smaller-or-equal (cdr lst) upper-bound))
    (else (cons (car lst)
                (find-smaller-or-equal (cdr lst) upper-bound)))))

I had a good time writing this, and it’s one of the shortest quicksorts I’ve seen, though I make no claims as to its efficiency.

My Advanced C++ class focused heavily on memory management; we built a string class, a date class, a time class, and a custom vector. The final project in the class was to put them all together to build an appointment book. All strings had to be handled with our own string class, all sequences had to be stored in our own vector class, and the appointments were stored using our own time and date class.

It was fun to be able to build something like this almost from scratch, and the libraries that I wrote to do it came in handy later in school, especially the MyArray class, which I made good use of in my Data Structures class a couple semesters later.

Download the C++ source code here.

This was the culminating project from my Advanced C# class. It uses a DLL built as a previous assignment as the back-end.

The program was designed to be used as a front-end to an inventory database for a media store, which sells books, music, and movies. Each kind of media can be added, removed, modified or looked up for viewing.

Download the C# source code here.

For my Assembly class, the final project was to build Conway’s Game of Life in C++, with the inner loops written in MASM.

The program allows the user to enter live cells by hand, specifying X and Y coordinates, and then it allows the user to iterate the world any number of times. Below is a screenshot of a familiar pattern, the Glider. Over successive time-steps, it will ‘walk’ down and to the right across the game world.

Download the C++ and MASM source code here.

This is a proof of concept flocking model, very similar to the first flocking simulation, Boids. It’s a toroidal world with constantly moving airplanes. In it, each of the airplanes is an agent, and they all make independent decisions based on incomplete knowledge of the world around them.

Each plane has a sight radius around it that represents how far the plane can see and a wedge behind it where it can’t see. This is intended to represent how real-world birds are thought to flock. Planes try to fly towards one another, and to align themselves with the planes in their neighborhood. This leads to a distinct flocking behavior.

Download the C# code here. It was built with XNA 3.1.

My first genetic algorithm solves problems like ‘Make X cents given Y coins from the set Z of allowed coins’. The user can input those problem values, as well as control the population size, mutation rate, and elitism bias of the genetic algorithm solving it.

Genetic algorithms work by ‘breeding’ a solution from previously generated solutions, with the goal being to breed solutions closer to a target. This is wonderful for problems with huge solution spaces, where you know the form of the answer, but not what it is, because GA’s can ‘hill-climb’ across the fitness landscape to quickly approach a right answer.

Sometimes, though, GA’s can get stuck on a local maximum in the fitness landscape, where evolving towards the right answer costs on the fitness function. In these cases, GA’s can take much longer to find the answer.

Download the C# source code here.

In my Artificial Life class, one of our assignments was to build a deterministic cellular automata. These are distinguished from totalistic CA’s like Conway’s Game of Life in that the positions of their neighbors matter. Each of the squares in the grid represents a cell; the black ones are ‘alive’, and the gray ones are ‘dead’.

The CA can be set to run a single step, or to run several, refreshing the drawing between each. The seed button will randomly set each cell on the grid to alive or dead.

The program can save the current state out to a file, and then load these files back into the program.

My CA allows the user to enter a rule by in a separate tab by checking a box for each of the possible states in a von Neumann neighborhood. The number generated at the bottom of the pane is a 32-bit number, derived from the 32 states. It provides a unique identifier for the rule set.

Download the C# source code here.