HTW Berlin Fachbereich 4 Internationaler Bachelor Studiengang Internationale Medieninformatik (Bachelor) Info 2: Informatik II Summer Term 2018

Donald Knuth from Stanford University started writing the series "The Art of Computer Programming" back in the 60s. He kept getting sidetracked and invented extremely useful things such as TeX and MetaFont along the way. One other thing is The Stanford Graphbase, a number of programs and very large datasets for generating and manipulating graphs and networks.

Knuth put together a list of 5757 five-letter English words. According to his book, The Stanford GraphBase: A Platform for Combinatorial Computing, ACM Press and Addison-Wesley Publishing Company, 1993, this collection started life as a dictionary for playing a game called Jotto that Michael Beeler put together. Beeler hat 6627 five-letter words from Webster's 7th New Collegiate Dictionary, and Knuth removed a good many of these words he had never heard of before.

In this exercise we are going to teach the computer to play Ladders, a game invented by the Oxford mathematician Charles Dodgson, better known as Lewis Carroll. The idea is to choose two words from random from the list, and then find words that "step" between the two words, changing only one letter per word. For example:

COLD → CORD → CARD → WARD → WARM

Your job, young Padawans, is to use a graph to find ladders for five-letter words.

Lab exercises:

1. Given two words, how can you tell if they differ by only one letter? Write a method to determine this.
2. You already have a graph data structure from exercise 10, getting from A to B. If you did a good job on that, you are all set here. If not, ask a fellow student for their implementation and make sure you give them credit in your report. Your graph is to take a five-letter word as the data in the node and to connect any two words with an edge if they differ by only one letter. Did you have to change anything in your Graph? Document this in your report!
3. First target: Construct the graph! For all words in the file, add them to the graph! You do this by going through all the vertices and checking to see if they are one letter different from the new word and if so, adding an edge.
4. (For the bored) Were there and words that didn't fit into the graph? How can you list them? How many were there?
5. How can you pick two words at random from the file of five-letter words? From a graph? Write a method to do so.
   
6. Second target: Choose two words at random from the graph. Construct the shortest ladder between them and output it. Hint: Dijkstra had an algorithm for this.
7. (For the bored) How many steps do you need to go from "chaos" to "order"? From "right" to "wrong"? from "graph" to "nodes"?
8. (For the bored) Can you make double ladders choosing 3 words and laddering from A to B and from B to C? Can you ladder from A to C as well?
   

This exercise is for extra credit! Your report is due by 10.00 pm on February 3, 2015.