6 Solving the ladder game

 

This chapter covers

  • Writing complex algorithms with multiple helper functions
  • The intricacies of type variables and their scoping
  • Profiling the performance of our application and adding external dependencies to the project

In the last chapter, we covered the ladder game and discussed how to implement a data structure that can represent graph structures. Furthermore, we can construct a graph that represents all possible outcomes of our game.

Now, we want to turn our attention to solving the problem of computing a solution within this graph. We can achieve this goal using a search algorithm that will guarantee we always find the shortest possible solution to our game.

This chapter begins by discussing how to implement a breadth-first search algorithm for our ladder game AI. Then, type variables are discussed, and language extensions are introduced. The chapter closes with a discussion on profiling of our project and how to improve its performance.

6.1 Constructing a breadth-first search

Knowing we can construct a ladder graph from a given dictionary, the only computational complex task we need to perform is to search in it. An additional requirement for our algorithm is that it needs to find the shortest path to produce an optimal word ladder. Our graph is special, in that it has uniform edge cost, since none of them are weighed. In this case, we are guaranteed to find the shortest path with a breadth-first search!

6.1.1 Overview of the algorithm

6.1.2 Keeping track of search state

6.1.3 Finding the solution by backtracking

6.2 Type variable scoping

6.2.1 Universal quantification

6.2.2 Language extensions

6.2.3 Using lexically scoped type variables

6.3 Improving performance with hashmaps

6.3.1 Analyzing performance with profiling

6.3.2 Adding project dependencies

6.3.3 Lazy evaluation

Summary