|
Size: 3611
Comment:
|
Size: 3685
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 24: | Line 24: |
| Generate a graph that represents all the words in the input that ''differ by one''. Each word is represented by a vertex in the graph, and vertices are adjacent if the corresponding words ''differ by one''. The words can be found on ''stdin'', and are in dictionary order, and will have white space between them (which means they may be all on one line, or spread out over many lines). You may assume that they consist of just lower-case letters (''a-z'') in this assignment (so no punctuation, hyphens, capital letters ...). As you will be building graphs, you must use the graph ADT provided in lectures (use the ''Adjacency Matrix'' version). For example, if a dictionary consists of the 7 words {{{an ban bean ben hen mean men}}} then the graph that represents all ''ordered word ladders'' would be drawn as: |
Generate a graph that represents all the words in the input that ''differ by one''. Each word is represented by a vertex in the graph, and vertices are adjacent if the corresponding words ''differ by one''. For example, if a dictionary consists of the 7 words {{{an ban bean ben hen mean men}}} then the graph that represents all ''ordered word ladders'' would be drawn as: |
| Line 33: | Line 31: |
| | / \ 5 6 -- 4 |
| / \ 5 6---4 |
| Line 36: | Line 34: |
| where the vertices 0..6 represent the 7 words in the given order. There are lots of ordered word ladders in this graph: for example, 0→1→2→5 representing ''an→ban→bean→mean'. Notice that the edges are undirected, but you can select only vertices in ascending order (hence the term 'ordered' in 'owl'). There is only one longest 'owl' 0→1→2→3→4→6. | where the vertices 0..6 represent the 7 words in the given order. There are lots of ordered word ladders in this graph: for example, 0→1→2→5 representing ''an→ban→bean→mean''. Any path between any two vertices in the graph is an ''owl'', but notice that, although the edges are undirected, you can select vertices only in ascending order (hence the term 'ordered' in 'owl'). There is only one ladder of length 6 for this dictionary, and that is 0→1→2→3→4→6. |
| Line 38: | Line 36: |
''Owl'' graphs are not typically trees, and typically have a single maximal ladder length. One reason for this is that (English) dictionaries often contain subsets of 3 or 4 letter words that are closely related. Take the dictionary {{{pan pen pin}}} which generates the complete graph on 3 vertices: {{{ 0 / \ 1---2 }}} This clearly has one maximal path of length 3. More basically, a single-letter dictionary {{{a b c d}}} generates a tetrahedron and has maximal ''owl'' length 4. If your dictionary has the full alphabet of 26 single-letter words {{{a b c d e f g h ... z}}} then the maximal ''owl'' length is 26. |
In this phase you are asked to create a graph for a dictionary, and print the graph. * '''Input''' The words in the dictionary should be read from ''stdin''. There will be ''whitespace'' between them (i.e. spaces, tabs, newlines). You may assume that the words are in lower-case letters (so there are no capital letters, punctuation, hyphens ...) You may assume also the words are sorted in dictionary order. For example, an input file could consist of: {{{ an ban bean ben hen mean men }}} * '''Output''' Print the dictionary and the resulting graph. You should use ''Graph ADT'' from lectures to build and display your graph (I recommend you use the ''adjacency matrix'' version, but it should not make any difference). For the example above, the output of your program should look like: {{{ Dictionary 0: an 1: ban 2: bean 3: ben 4: hen 5: mean 6: men Ordered Word Ladder Graph V=7, E=9 <0 1> <1 0> <1 2> <1 3> <2 1> <2 3> <2 5> <3 1> <3 2> <3 4> <3 6> <4 3> <4 6> <5 2> <5 6> <6 3> <6 4> <6 5> }}} |
Assignment 2: Ordered Word Ladders
An ordered word ladder ('owl') is an alphabetically-ordered sequence of words where each word in the sequence differs from its predecessor by one action:
changing one letter, e.g. barn→born
adding or removing one letter, e.g. band→brand and bran→ran
The following are examples of word ladders of different length:
ban→bar→boar→boat→goat, length 5
an→can→cane→dane→date→mate→mite→site→size, length 9
Phase 1
At the heart of the assignment is a function that compares 2 arbitrary null-terminated strings and returns true if the strings satisfy one of the 2 conditions above, and false otherwise. This function has signature:
1 bool differByOne(char *, char *)
Write such a function and of course test it.
Phase 2
Generate a graph that represents all the words in the input that differ by one. Each word is represented by a vertex in the graph, and vertices are adjacent if the corresponding words differ by one. For example, if a dictionary consists of the 7 words an ban bean ben hen mean men then the graph that represents all ordered word ladders would be drawn as:
0
|
1
/ \
2 --- 3
| / \
5 6---4where the vertices 0..6 represent the 7 words in the given order. There are lots of ordered word ladders in this graph: for example, 0→1→2→5 representing an→ban→bean→mean. Any path between any two vertices in the graph is an owl, but notice that, although the edges are undirected, you can select vertices only in ascending order (hence the term 'ordered' in 'owl'). There is only one ladder of length 6 for this dictionary, and that is 0→1→2→3→4→6.
In this phase you are asked to create a graph for a dictionary, and print the graph.
Input The words in the dictionary should be read from stdin. There will be whitespace between them (i.e. spaces, tabs, newlines). You may assume that the words are in lower-case letters (so there are no capital letters, punctuation, hyphens ...) You may assume also the words are sorted in dictionary order. For example, an input file could consist of:
an ban bean ben hen mean men
Output Print the dictionary and the resulting graph. You should use Graph ADT from lectures to build and display your graph (I recommend you use the adjacency matrix version, but it should not make any difference). For the example above, the output of your program should look like:
Dictionary 0: an 1: ban 2: bean 3: ben 4: hen 5: mean 6: men Ordered Word Ladder Graph V=7, E=9 <0 1> <1 0> <1 2> <1 3> <2 1> <2 3> <2 5> <3 1> <3 2> <3 4> <3 6> <4 3> <4 6> <5 2> <5 6> <6 3> <6 4> <6 5>
Phase 3
Now a more 'formal' specification:
input Your program should read the format described in lectures: a #integer followed by an arbitrary number of pair of edges
For example, if a dictionary consists of the 12 words case cast cat cats cave cost cove love post sale save suave then the graph that represents all ordered word ladders would be drawn as:
0 9
/ \ |
1 4 10
/ \ / \
2 5 6 10
| | | |
3 8 7 11where the vertices 0..11 represent the 12 words in the given order.