4 Searching for the Ladder

 

This chapter covers

  • Modeling a graph structure as a map
  • Applying type constraints to ensure properties about types
  • Properly encapsulating data types and functions in a module
  • Using list comprehensions to more easily transform lists
  • Designing an algorithm with a complex state being handled
  • Profiling and improving program performance

Our last project was a minimal clone of a popular UNIX tool. Serious business! But life is more than just writing industry grade utilities for all of our terminal line numbering needs. Let’s have some fun! And how do people usually have fun? By playing games of course!

A fun little game to play is the word ladder game, which makes the players build chains of words that can be found by transforming single letters within them. The game has many variants and we will focus on a pretty complex one! But, why play games, when we could be a bit lazy about it? The computer can play for us!

Writing an artificial intelligence, even for a children’s game, isn’t always a cakewalk. This project will make us think about clever usage of data structures in order to implement the solution for a search problem. While it might seem simple on the surface, we will see that there can be pitfalls, even in child’s play!

4.1 A nest of ladders

 
 
 

4.1.1 Graphing it out

 
 
 
 

4.1.2 Staying modular

 
 

4.2 In front off the class

 
 
 

4.2.1 Flipping out

 
 
 

4.3 To redraw the map

 
 
 

4.3.1 Adding, removing, altering

 
 
 

4.3.2 Into another module it goes

 
 
 
 

4.4 Adjacency map redux

 
 
 

4.4.1 Permuting words for profit

 
 
 
 

4.4.2 One step after the other

 
 
 

4.5 A search going wide

 

4.5.1 Type trouble tinkering

 

4.6 To play the ladder game

 

4.6.1 What’s the hold up?

 
 
 
sitemap

Unable to load book!

The book could not be loaded.

(try again in a couple of minutes)

manning.com homepage
test yourself with a liveTest