

Students:

Section 14.5 is a part of 1 assignment:

Programming Project 05 - Link Lint List - Find Shortest Word Ladder

Includes:zyLab

Due: 11/07/2024, 11:59 PM CST

14.5 P05 - Link Lint List - Find Shortest Word Ladder

Word Ladder Solver

______________________________________________________________________________

_________

Introduction to Word Ladders (reproduced from Project03)

A word ladder is a bridge between one word and another, formed by changing one letter at a time, with the constraint that

at each step the sequence of letters still forms a valid word. For example, here is a word ladder starting from the

word "data" and climbing up the ladder to the word "code". Each changed letter is bolded as an illustration:

| code |

| ^ |

| cove |

| ^ |

| cave |

| ^ |

| gave |

| ^ |

| gate |

| ^ |

| date |

| ^ |

| data |

This word ladder has height 7. There are many other word ladders that connect these two words. For example, here is

another ladder of height 5 that uses some more obscure words:

| code |

| ^ |

| cade |

| ^ |

| cate |

| ^ |

| date |

| ^ |

| data |

In fact, this ladder has the shortest height that connects data to code. Note that there might be other ladders of the same

height, but none with fewer rungs than this one. Notice that the shortest a word ladder can be is 2, e.g. cove -> code.

There are also pairs of words for which a word ladder cannot be formed, e.g. there is no word ladder to connect stack ->

queue.

In this project, you will write functions to support a program that prompts the user for two words and nds a minimum-

height ladder linking the words, which uses linked lists of words to store ladders, linked lists of partially completed

ladders to organize all possible solutions, and a prescribed algorithm to nd the shortest word ladder.

Dictionary File, Word Array, Word Struct, and a Linked List for the Word Ladder

The provided le dictionary.txt contains the full contents of the "Ocial Scrabble Player's Dictionary, Second Edition." This

word list has over 120,000 words, which should be more than enough for the purposes of making word ladders for small

to moderate sized words. Smaller dictionaries are also provided for testing purposes: simple3.txt contains a limited

number of 3-letter words, simple4.txt contains a limited number of 4-letter words, and simple5.txt contains a limited

number of 5-letter words.

The complete primary application is provided in main() of the starter code; however, it involves many calls to functions

that still need to be written. Here are the main steps of the program:

Instructor created



The user interactively sets the length of the starting and nal words for the word ladder. This, in turn, also sets the

wordSize for the full set of words to be read in from the dictionary le.

The user also interactively inputs the dictionary le name to be used for reading words into the full array of possible

words that could later make up the ladder.

The dictionary le is opened for the rst time and is scanned to count the number of words it contains that has the

desired wordSize; this count is stored as numWords.

We now know the user-specied word length (wordSize) AND the number of words in the dictionary that have the

correct length (numWords). Thus, we can now allocate array space for all of the words, open the le again, and read

the words in from the le to ll the newly-allocated array. The full set of words is stored using a heap-allocated array

of pointers to C-strings. That is, words is an array of pointers with size numWords, where each pointer points to a

heap-allocated C-string of size wordSize+1 (to allow space for a word and the null character). See the gure below

for a diagram of the words array.

The user interactively inputs both the starting word (startWord) and the nal word (nalW ord). If either entered

word has an incorrect size (i.e. not equal to wordSize) or the word is not found in the words array, then the user is

requested to enter another word.

With the words array lled from the dictionary and the two ends of the word ladder set, an algorithm is run to

produce the minimum-height word ladder. This entails building a linked list of WordNode structs, which contain

pointers to C-strings in the words array and a pointer to the next element in the linked list. Full details on the

minimum-height word ladder algorithm are in the next section.

If a word ladder connecting the two words is possible, the minimum-height ladder is displayed (with the starting

word on the bottom and the nal word at the top of the ladder), along with the ladder height.

Example:

The diagram below uses a sample dictionary of only 15 words, where the word length varies from 3 to 8. If wordSize is

selected to be 3, then numWords would be set to 7, since there are seven 3-letter words in the dictionary le: bug, ear, y ,

tap, tar, toe, top.  Note that the seven words are heap-allocated C-strings with an extra character for '\0'. Then, startWord

is chosen to be "toe" and nalWord is chosen to be "ear". The algorithm produces a linked list where the head

node's myWord pointer points to the nalW ord C-string in the words array, i.e. "ear". It is important to notice that the

linked list node does NOT store characters for the word, nor is an additional copy of the word made; instead the linked list

node simply points to an element of the words array. So...

the head node points to "ear" in the words array, then following to next,

the next node points to "tar" in the words array, then following to next,

the next node points to "tap" in the words array, then following to next,

the next node points to "top" in the words array, then following to next,

the next node points to "toe" in the words array, then following to next,

the next node points to NULL

Thus, the linked list is the word ladder, with the nalW ord pointed to by the head node and the startWord pointed to by

the last node.

Figure 14.5.1: Diagram of a sample word ladder - words array & ladder linked list

The Minimum-Height Word Ladder Finding Algorithm

Finding a word ladder is a specic instance of what is known as a shortest-path problem: a problem in which we try to

nd the shortest possible route from a given start to a given end point. Shortest-path problems come up in routing

Internet packets, comparing gene mutations, Google Maps, and many other domains. The strategy we will use for nding

the shortest path between our start and end words is called breadth-rst search ("BFS"). This is a search process that

gradually expands the set of paths among which we search outwards: BFS rst considers all possible paths that are one

step away from the starting point, then all possible paths two steps away, and so on, until a path is found connecting the

start and end point. A step can be understood as one unit of measurement; depending on the problem, this could be a

millisecond, a minute, a mile, a subway stop, and so on. By exploring all possible paths of a given length before

incrementing to the next length, BFS guarantees that the rst solution you nd will be as short as possible.

For word ladders, start by examining ladders that contain only words that are one “step” away from the original word; i.e.,

words in which only one letter has been changed. If you nd your target word among these one-step-away ladders,

congratulations, you’re done! If not, look for your target word in all ladders containing words that are two steps away; i.e.,

ladders in which two letters have been changed. Then check three letters, four, etc., until your target word is located. 

We implement the breadth-rst algorithm using a linked list of partially complete ladders, each of which represents a

possibility to explore (i.e., each item in the list of partial ladders is examined in turn, checking to see if it contains a path to

our target word). Each partial ladder is represented as a linked list of words, which means that your overall collection will

be a linked list of partially complete ladders, which are themselves linked lists of words.

A word ladder is a linked list of WordNode structs, which is dened as follows:

typedef struct WordNode_struct {

    char* myWord;

    struct WordNode_struct* next;

} WordNode;

Here myWord is a pointer to a C-string element of the words array and next is a pointer to the next element in the list of

words. 

The algorithm centers on storing partially completed word ladders in a linked list of LadderNode structs, which is dened

as follows:

typedef struct LadderNode_struct {

    WordNode* topWord;

    struct LadderNode_struct* next;

} LadderNode;

Here topWord is a pointer to the head node of a partially completed word ladder and next is a pointer to the next element

in the list of ladders. 

Below is a partial pseudo-code description of the algorithm to solve the word-ladder problem (Note: some students may

complain at this point that we are giving too much information and that they want to gur e the problem out on their own. In

that case, great! Don’t look at the pseudocode below if you want to try it on your own!)

To find the shortest word ladder between words w1 and w2:

Create myList, an empty list of LadderNode structs

Create myLadder, an empty list of WordNode structs

Prepend w1 to the front of myLadder

  Append myLadder to the back of myList

While myList is not empty:

Pop the head LadderNode off the front of myList, call it myLadder

For each word in the words array that is a neighbor of the head myWord of

myLadder:

If the neighbor word has not already been used in a ladder to this point:

If the neighbor word is w2:

Prepend w2 to the front of myLadder

Hooray! We found the shortest word ladder, so return myLadder

  Otherwise:

Copy myLadder to anotherLadder

               Prepend neighbor word to the front of anotherLadder

               Append anotherLadder to the back of myList 

   If no ladder was returned, then no ladder is possible

Some of the pseudo-code corresponds almost one-to-one with actual C code. Other parts are more abstract, such as the

instruction to "pop" a LadderNode from the front of MyList. Popping a node from the front of a list means that the the

head node is removed from the list, such that the node that was one away from the head node is the new head node. In

this case, we are interested in keeping the popped ladder for further analysis, but it is no longer connected to the linked

list.

Another instruction that needs more explanation is to examine each "neighbor" of a given word. A neighbor of a given

word w is a word of the same length as w that differs by exactly 1 letter from w. For example, “date” and “data” are

neighbors; “dog” and “bog” are neighbors; “debug” and “shrug” are NOT neighbors.

Your solution is not allowed to look for neighbors by looping over the full dictionary, nor looping over the entire words

array, every time; this is much too inecient. To nd all neighbors of a given word, use two nested loops: one that goes

through each character index in the word, and one that loops through the letters of the alphabet from a-z, replacing the

character in that index position with each of the 26 letters in turn. For example, when examining neighbors of “date”, you'd

try:

aate, bate, cate, ..., zate ← all possible neighbors where only the 1st letter is changed.

date, dbte, dcte, ..., dzte ← all possible neighbors where only the 2nd letter is changed.

...

data, datb, datc, ..., datz ← all possible neighbors where only the 4th letter is changed.

Note that many of the possible letter combinations along the way (aate, dbte, datz, etc.) are not valid English words. Your

algorithm has access to the words array, which is built from an English dictionary, and each time you generate a word

using this looping process, you should look it up in the words array to make sure that it is actually a legal English word.

Only valid English words should be included in your group of neighbors. Since we will be searching the words array many

times, we will take advantage of the dictionary le being in alphabetical order, which produces a words array that is also

in alphabetical order, which allows an ecient process for nding words using a binary search.

Another way of visualizing the search for neighboring words is to think of each letter index in the word as being a

"spinner" that you can spin up and down to try all values A-Z for that letter. The diagram below tries to depict this:

Figure 14.5.2: Ecient search for neighbor words

Another subtle issue is that you should not reuse words that have been included in a previous, shorter ladder. For

example, suppose that you have the partial ladder cat → cot → cog in your list. Later on, if your code is processing the

ladder cat → cot → con, one neighbor of con is cog, so you might want to examine cat → cot → con → cog. But doing

so is unnecessary. If there is a word ladder that begins with these four words, then there must be a shorter one that, in

effect, cuts out the middleman by eliminating the unnecessary word con. As soon as you've entered a ladder in your list

ending with a specic word, you've found a minimum-length path from the starting word to that end word in that ladder,

so you never have to enter that end word again in any later ladder.

To implement this strategy, we keep track of the set of words that have already been used in any ladder, and ignore those

words if they come up again. Keeping track of which words you've used also eliminates the possibility of getting trapped

in an innite loop by building a circular ladder, such as cat → cot → cog → bog → bag → bat → cat. 

The set of previously-used words is recorded in the Boolean array usedWord, which has size numWords to align with the

words array by index. The elements of usedWord are all initialized to false, representing no words have been added to

any ladders yet. Thus, if the algorithm seeks to add words[i] to a ladder, rst check usedWord[i]; if it is false, then proceed

to add words[i] to the ladder and set usedWord[i] to true; otherwise, ignore words[i] and move on. This should feel

familiar, as it is a form of memoization.

Lastly, whereas the pseudo-code does a nice job laying out the important structural elements of the algorithm and the

underlying linked list structures, it makes no effort at complete memory management. The algorithm requires a great

deal of heap-memory allocations, i.e. for each WordNode and LadderNode. The vast majority of these allocations (but

not all) go out of scope once the algorithm has nished. Thus, whenever you are done investigating an incomplete partial

ladder, make sure to free up all heap-memory that was allocated for it before moving on with the algorithm. Furthermore,

when you have found a complete ladder, make sure to free up all remaining heap-memory that was allocated for the

algorithm before returning the ladder (do NOT free the memory for the complete ladder as you need to return the ladder

to be displayed to screen, etc.). Lastly, in the case where no ladder is possible, the list of LadderNode structs should be

empty and all heap-memory should be free'd naturally within the algorithm.

A nal tip on the algorithm: it may be helpful to test your program on smaller dictionary les rst to nd bugs or issues

related to your dictionary or to word searching. Thus, the simple#.txt les t this bill nicely.

______________________________________________________________________________

_________

Programming Tasks

First, read through the code in main() to get an understanding for the primary components of the program. Keep in mind

that it includes MANY calls to functions that you need to write. As you peruse main() and run across function calls, you

may want to nd each of the function headers above to get acquainted with them. 

Then, nd the following twelve function headers:

Functions related to the words array:

countWordsOfLength()

buildWordArray()

findWord()

freeWords()

Functions related to linked lists of WordNode structs, i.e. a word ladder:

insertWordAtFront()

getLadderHeight()

copyLadder()

freeLadder()

Functions related to linked lists of LadderNode structs, i.e. a list of ladders:

insertLadderAtBack()

popLadderFromFront()

freeLadderList()

A function to perform the minimum-height word ladder finding algorithm:

findShortestWordLadder()

The comments in each function body of the starter code provide an explanation of what each function should

accomplish, implicitly dening each parameter and returned quantity. Your task in this project is to complete the program

by writing the twelve functions listed above, without modifying the struct denitions or the code in main().

Whereas, there is no structured student testing requirement for this project, you are expected to test the functions on

your own before relying on the autograder. This should be done by writing your own test case functions and/or using the

main() application outputs to compare expected vs. actual results. The executable demo.exe is a fully functioning

program that is provided with the starter code to help with student testing (prior to submission to autograder). As always,

you need to change the permissions to allow execution as follows:

>> chmod a+x demo.exe

>> ./demo.exe

There are many of good options for developing and using your own test cases; here are two:

Write individual test cases in main.c, right below each function that you want to test. For example, right underneath

countWordsOfLength(), write a Boolean test case function called test_countWordsOfLength(), to fully test the

functionality of countWordsOfLength(). Then, write one additional master testing function that calls all of the test_*

() functions and has nicely formatted print statements to communicate if test cases are passed or not. Finally, call

this master testing function as the rst line of main(), but ONLY if testing mode is ON, where testing mode can be

turned ON by a command-line argument (defaulted to OFF). Note that the autograder does not use command-line

arguments, so it will not run your test cases if you use this option.

Copy/paste your main.c functions (in full) that you want to test into a test case le inside a subdirectory where all

testing is compiled and run; that is, the main.c functions are copied into tests/test.c, which also have a test case

function (e.g. test_countWordsOfLength()) for each function (e.g. countWordsOfLength()) copied in, and also has

its own main() that calls all of the test_*() functions. This subdirectory (tests/) also may have its own makele and

is where the test.c is compiled and the testing suite is executed. This option is nice since it keeps the primary

main.c application clean, putting all testing in a separate location. The major downside to this option is having

multiple copies of the same code, which needs to be managed carefully.

You will submit an explanation of how you tested your code. Include samples of running the program and/or test case

code that you developed for testing purposes. In order to earn all of the points for testing, you do need to write and run

test cases of your own. Script your explanation of testing in a word-processor and save it as a .pdf. Submit

this testing.pdf with your Gradescope submission.

Lastly, you should develop a makele with many useful targets. Here are some example targets:

a target to compile the code

a target to run the program interactively

a target to run the program interactively under valgrind

a target to run the program using the redirection operator to supply input values non-interactively (you will need to

make a .txt le that contains preset user-inputs)

additional targets you nd useful for developing, testing, and running your program

The makele will not be tested as part of the autograded test cases. Instead, you will submit the makele with your code

submission to Gradescope.

Run the Application

With all functions written, tested, and passing the autograded test cases, run the program with various inputs using the

full dictionary.txt to investigate the following questions:

1. Finding very short word ladders is easy, e.g. connecting debug and debut is trivial. However, your program is so

good at nding short word ladders that it takes some effort to nd word pairs where the shortest word ladder is

actually long. What is the longest optimal word ladder you can nd between 3-letter words? 4-letter words? 5-letter

words? After some systematic attempts, your instructors were able to nd (can you nd word-pairs where the

shortest word ladder is longer than these???)...

a 3-letter-word-pair with shortest word ladder of height 7, 

a 4-letter-word-pair with shortest word ladder of height 9, and 

a 5-letter-word-pair with shortest word ladder of height 14. 

2. Describe your method for nding word pairs where the shortest word ladder is relatively long. Note: in the

setWords() function of the provided starter code, after 5 invalid words are inputted, the program chooses a word at

random so it can proceed. Can you use this feature to your advantage?

3. Based on your experience developing and running the program, briey explain why word ladders tend to be shorter

between smaller words (e.g. 3-letter word pairs) than longer words (e.g. 5-letter word pairs).

4. How does the word length affect the ease of being able to connect words with a word ladder? You may nd that

almost any 3-letter-word-pairs can be connected. Conversely, you may nd it dicult to connect any 9-letter-word-

pairs. At what word size do you begin to nd it dicult to connect randomly chosen words (you may be surprised at

how small this number is)? Explain this phenomenon based on your experience running the program.

Note: even if you are not able to get a fully-functioning program, you can use demo.exe to answer these reection prompts.

Script your reection in a word-processor and save it as a .pdf. Submit this reection.pdf with your Gradescope

submission.

Optional Extension (Extra Credit)

After you have completed all required tasks and have built a fully functioning program, consider a modication to the

problem: can you nd the longest word ladder than connects the two input words?

Modify the algorithm to nd the longest word ladder that connects the two words, while still avoiding duplicate words.

Here, the avoidance of duplicate words prevents innite loops only. In order to nd the longest word ladder, it no longer

works to prevent words from being entered into multiple ladders. Develop your modied algorithm in a new function

called ndLongestWordLadder(). There are no autograded test cases for this function. Instead, display the long word

ladder at the end of main, similarly to how the shortest word ladder is displayed.

This component is optional and only for extra credit. To receive the extra credit you MUST include a le

titled extension.pdf with your submission, which fully explains how you modied the algorithm to nd the longest word

ladder and with instructions on how to run your extended program. The le must also include sample program outputs

displaying some examples for longest possible word ladders.

______________________________________________________________________________

_________

Requirements

Use the starter code as provided, adding code to complete functions, without making any structural changes.

Violations of this requirement will receive manually graded deduction(s). 

Do NOT modify the WordNode and LadderNode struct denitions (no name change, do not add subitems, do

not remove subitems, do not modify subitem denitions, etc.); one exception is that minor changes to the

struct denitions are allowed if you prefer to alias the node pointer, e.g. typedef struct struct_WordNode*

WordNodePtr. 

Do NOT change the function headers (no name changes, do not add parameters, do not remove parameters,

do not modify parameter types, etc.). 

Whereas minor changes to main() may be helpful when developing, testing, and debugging, the primary

application in main() should not be modied in your nal submission, except for student-written testing (such

as command-line argument for TESTING MODE to call a master test case function, or similar) and additional

code related to the optional extra credit extensions. 

Additional helper functions are allowed/encouraged when appropriate for proper functional decomposition. 

Solve each task and the program at large as intended. Violations of this requirement will receive manually graded

deduction(s).

For example, when creating a word ladder linked list, each WordNode should simply point to a C-string

element of the words array that is already allocated on the heap; i.e. do not allocate additional space for a

copy of the word to point to. 

Also, the search for neighbor words must NOT involve looping through the entire words array; instead, use a

nested loop over the character index and the 26 letters of the alphabet and check if each possible neighbor

word is a valid entry in the dictionary using a binary search. 

Student testing of the required functions and the program at large is required; however, there is no structural

requirements for how the testing is done and it is not checked by the autograder. Instead, you will submit an

explanation on how you continually tested your code as you developed functions. Include a separate test case le if

you developed one for testing your program.

The development of a useful makele with meaningful targets is required; however, it is not checked by the

autograder. Use past programming assignments that involved a makele as a template. Your makele should AT

LEAST include targets for the following:

a target to compile the code

a target to run the program interactively

a target to run the program interactively under valgrind

a target to run the program using the redirection operator to supply input values non-interactively (you will

need to make a .txt le that contains preset user-inputs)

additional targets you nd useful for developing, testing, and running your program

All dynamic heap-allocated memory must be freed to prevent possible memory leaks. This issue is checked by the

autograder but may also receive a manually graded deduction.

Coding style issues are manually graded using deductions, worth up to 25% of the total project score. Style points

are graded for following the course standards and best practices laid out in the syllabus, including a header

comments, meaningful identier names, effective comments, code layout, functional decomposition, and

appropriate data and control structures.

Programming projects must be completed and submitted individually. Sharing of code between students in any

fashion is not allowed. Use of any support outside of course-approved resources is not allowed, and is considered

academic misconduct. Examples of what is allowed: referencing the zyBook, getting support from a TA, general

discussions about concepts on piazza, asking questions during lecture, etc. Examples of what is NOT allowed:

asking a friend or family member for help, using a "tutor" or posting/checking "tutoring" websites (e.g. Chegg),

copy/pasting portions of the project description to an AI chatbot, etc. Check the syllabus for Academic Integrity

policies. Violations of this requirement will receive a manually graded deduction, and may be reported to the Dean

of Students oce.

______________________________________________________________________________

_________

Tips for Success on this Programming Project

Trickiest task/function is implementing a prescribed algorithm - the project focuses on implementing a

prescribed algorithm to extend an earlier project (that let the user build word ladders) to nd the shortest possible

word ladder using linked lists in a C program. The resulting program centers on an algorithm that nds the

shortest word ladder that connects two English words. The algorithm involves organizing a linked list of partially

complete word ladders, which are themselves linked lists of words. A full pseudo-code for the algorithm is provided

in the description above. The trickiest part of this project is converting the pseudo-code to actual C-code, within the

context of the primary application, main(), as written. Thus, it is important that you understand all of the steps of

the primary application, the struct denitions and how they are used to construct various linked lists, AND all steps

of the algorithm's pseudo-code prior to actually beginning to code.

NOT all tasks/functions are created equal - the Programming Tasks for this project are primarily to develop many

functions to support the primary application, most of which is provided for you in the starter code. The level of

scaffolding is designed to lead you through the program development that leaves room for creatively applying

course concepts and tools. A natural consequence is that..

some Tasks are straightforward and some Tasks are challenging; 

some Tasks ask you to do one thing specically and some Tasks are purposefully open-end with multiple

components;

some Tasks test your ability to follow instructions verbatim and some Tasks require you to practice problem-

solving and critical-thinking skills;

some Tasks may only take you a few minutes and some Tasks may require an initial attempt followed by a

break to do something else only to come back multiple times to tackle the challenge;

Continual Testing - you should continue building the best practice habit of continual testing functionality as you

develop code. There is no formal required structure to the testing you do, but you must explain and demonstrate

your testing process when you submit your project. Continual testing in small chunks of code is essential for

ecient code development.

No print statements - the functions you write should have no print statements. All of the console output is handled

in the primary application and/or provided helper functions. Of course, as you develop, test, and debug your code,

you may introduce some print statements to achieve those purposes. These print statements must be removed

and/or commented out before you submit to the autograder. 

______________________________________________________________________________

_________

Submission & Grading

Develop your code in the IDE below. The provided starter code is substantial. Thus, make sure to read all instructions

carefully and only make changes to the specic les referenced in the project description. Use the terminal to test your

code interactively as you develop your program. Part of your tasks is to write a helpful and meaningful makele for

compiling and running your program. Once you have fully tested your code for a given task, use the "Submit for grading"

button to test your code against the suite of autograded test cases. 

When you are ready to formally submit, download the following les from the zyLab IDE le trees, and be prepared to

upload the les to the Project 05 Gradescope submission form; look for Project 05:

main.c

makele (not included in the starter code, but you are required to create one). 

Additionally, be prepared to describe your method of continually testing functionality as you developed your code,

with supporting documentation where appropriate, and make sure your testing.pdf is ready to upload with the other

les. 

Also, prepare your reection responses to the four prompts listed in the Run the Application section above, and

make sure your reection.pdf is ready to upload with the other les. 

Lastly, if you extended the program to nd the longest possible word ladders for extra credit, then you will also

upload extension.pdf, which should thoroughly describe your extension.

Formally, you must submit your nal program les to Gradescope, where your code will be manually inspected for style

(details in the syllabus) and project requirements (details listed above). The ocial code submission is the version you

submit to Gradescope (look for Project05). If you fail to submit to Gradescope, you have not formally submitted anything,

and the resulting score is a zero for the project. 

The standard deadline for the project is Thursday, November, 7th. As detailed in the syllabus, early submissions receive

+1 extra credit point/day early, up to a maximum of +3 points. Also, students are allocated a certain number of late days

throughout the term, where no late penalty is applied. Students can use their late days whenever they choose, simply by

submitting their work to Gradescope after the deadline. However, no more than two late days are allowed for each

project.

The grading breakdown is as follows:

90 points for functionality - autograder points with manual deductions for any style issues (check syllabus for how

style is graded) and program requirements not adhered to. Style is checked for the functions you write in main.c.

6 points - countWordsOfLength()

6 points - buildWordArray()

9 points - ndW ord()

9 points - insertWordAtFront()

3 points - getLadderHeight()

9 points - copyLadder()

9 points - insertLadderAtBack()

9 points - popLadderFromFront()

9 points - ndShortestWordLadder()

13 points - program output checks on the shortest word ladder heigh for various word lengths and start/nal

word pairs

8 points - valgrind memory leak and error checks, which implicitly checks freeWords(), freeLadder(), and

freeLadderList()

3 points for makele - a meaningful makele with useful targets

3 points for student testing - a full explanation/demonstration of how you tested functionality as you developed

code, submitted as a pdf (see above for details)

4 points for free-response prompts - from the Run the Application section, submitted as a pdf (see above for

details)

extension extra credit - up to +5 extra credit points for an innovative idea to nd the longest word ladder to connect

the word pairs. To receive any extra credit, up to a maximum of +5 extra credit points, the extension must be fully

implemented and working correctly. Additionally, you MUST include a le titled extension.pdf with your submission,

which presents your program extension to the grader with a full explanation of how the program works, how to run

your extension, AND sample program outputs displaying some examples for longest possible word ladders.

early submission extra credit - +1 point/day early with a maximum of +3 extra credit points.

______________________________________________________________________________

_________

Citation/Inspiration

The idea for this programming project is greatly inspired by Chris Gregg at Stanford University, with much of the

introduction and algorithm description directly borrowed.

Copyright Statement

This assignment description is protected by U.S. copyright law. Reproduction and distribution of this work, including

posting or sharing through any medium, such as to websites like chegg.com or AI chat bots, is explicitly prohibited by law

and also violates UIC's Student Disciplinary Policy (A2-c. Unauthorized Collaboration; and A2-e3. Participation in

Academically Dishonest Activities: Material Distribution).

Material posted on any third party sites in violation of this copyright and the website terms will be removed. Your user

information will be released to the author.

LAB

ACTIVITY

14.5.1: Find the Shortest Word Ladder

77 / 90





Coding trail of your work

11/7Rmin:12

Latest submission - 9:54 PM CST on 11/07/24Total score: 77 / 90

Only show failing tests

1: unit test for countWordsOfLength() - small & invalid les



3 / 3

2: unit test for countWordsOfLength() - large le



3 / 3





7



RunHistory



Tutorial



main.c

496

497

498

499

500

501

502

503

504

505

506

507

    }

    printf("Word Ladder height = %d\n",getLadderHeight(myLadder));

    // free the heap-allocated memory for the shortest ladder

    freeLadder(myLadder);

    // free the heap-allocated memory for the words array

    freeWords(words,numWords);

    free(usedWord);

    return 0;

}

DESKTOPCONSOLE



➜

Submit for grading

What is this?

77,62,62,62,77

Open submission's code

3: unit test for buildWordArray() - small le - valid & invalid inputs



3 / 3

4: unit test for buildWordArray() - large le



3 / 3

5: unit test for ndWord() - numWords = 26, wordSize = 3



3 / 3

6: unit test for ndWord() - numWords = 30, wordSize = 4



3 / 3

7: unit test for ndWord() - numWords = 10, wordSize = 5



3 / 3

8: unit test for insertWordAtFront() - numWords = 26, wordSize = 3



3 / 3

9: unit test for insertWordAtFront() - numWords = 30, wordSize = 4



3 / 3

10: unit test for insertWordAtFront() - numWords = 10, wordSize = 5



3 / 3

11: unit test for getLadderHeight()



3 / 3

12: unit test for copyLadder() - numWords = 26, wordSize = 3



3 / 3

13: unit test for copyLadder() - numWords = 30, wordSize = 4



3 / 3

14: unit test for copyLadder() - numWords = 10, wordSize = 5



3 / 3

15: unit test for insertLadderAtBack() - numWords = 26, wordSize = 3



3 / 3

16: unit test for insertLadderAtBack() - numWords = 30, wordSize = 4



3 / 3

17: unit test for insertLadderAtBack() - numWords = 10, wordSize = 5



3 / 3

18: unit test for popLadderFromFront() - numWords = 26, wordSize = 3



3 / 3

19: unit test for popLadderFromFront() - numWords = 30, wordSize = 4



3 / 3

20: unit test for popLadderFromFront() - numWords = 10, wordSize = 5



3 / 3

21: unit test for ndShortestWordLadder() - numWords = 26, wordSize = 3



3 / 3

22: unit test for ndShortestWordLadder() - numWords = 30, wordSize = 4



3 / 3

23: unit test for ndShortestWordLadder() - numWords = 10, wordSize = 5



3 / 3

24: Output test - 3-letter words - case 1



1 / 1

Input

3

dictionary.txt

bit

fun

Your OutputExpected output contains this at least once

1.⏎

2.Welcome to the CS 211 Word Ladde

3.⏎

4.Enter the word size for the ladd

5.This program will make the short

6.word ladder between two 3-letter

7.⏎

8.Enter filename for dictionary:

9.Building array of 3-letter words

10.Setting the start 3-letter word.

11. Enter a 3-letter word:

25: Output test - 3-letter words - case 2



0 / 1

Input

3

dictionary.txt

sky

elk

Your OutputExpected output contains this at least once

1.⏎1.Word Ladder height = 7

Output is nearly correct, but whitespace differs. See highlights above.Special character legend

26: Output test - 3-letter words - case 3



1 / 1

Input

3

dictionary.txt

gnu

new

Your OutputExpected output contains this at least once

1.⏎

2.Welcome to the CS 211 Word Ladde

3.⏎

4.Enter the word size for the ladd

5.This program will make the short

6.word ladder between two 3-letter

7.⏎

8.Enter filename for dictionary:

9.Building array of 3-letter words

10.Setting the start 3-letter word.

11. Enter a 3-letter word:

27: Output test - 4-letter words - case 1



1 / 1

Input

4

dictionary.txt

code

data

Your OutputExpected output contains this at least once

10.Setting the start 4-letter word.

11. Enter a 4-letter word:

12.Setting the final 4-letter word.

13. Enter a 4-letter word:

14.Shortest Word Ladder found!

15.⇥⇥⇥data

16.⇥⇥⇥date

17.⇥⇥⇥cate

18.⇥⇥⇥cade

19.⇥⇥⇥code

20.

Word Ladder height = 5

28: Output test - 4-letter words - case 2



1 / 1

Input

4

dictionary.txt

zoom

chat

Your OutputExpected output contains this at least once

1.⏎

2.Welcome to the CS 211 Word Ladde

3.⏎

4.Enter the word size for the ladd

5.This program will make the short

6.word ladder between two 4-letter

7.⏎

8.Enter filename for dictionary:

9.Building array of 4-letter words

10.Setting the start 4-letter word.

11. Enter a 4-letter word:

29: Output test - 4-letter words - case 3



1 / 1

Input

4

dictionary.txt

tiki

slab

Your OutputExpected output contains this at least once

1.⏎

2.Welcome to the CS 211 Word Ladde

3.⏎

4.Enter the word size for the ladd

5.This program will make the short

6.word ladder between two 4-letter

7.⏎

8.Enter filename for dictionary:

9.Building array of 4-letter words

10.Setting the start 4-letter word.

11. Enter a 4-letter word:

30: Output test - 5-letter words - case 1



1 / 1

Input

5

dictionary.txt

point

debug

Your OutputExpected output contains this at least once

1.⏎

2.Welcome to the CS 211 Word Ladde

3.⏎

4.Enter the word size for the ladd

5.This program will make the short

6.word ladder between two 5-letter

7.⏎

8.Enter filename for dictionary:

9.Building array of 5-letter words

10.Setting the start 5-letter word.

11. Enter a 5-letter word:

31: Output test - 5-letter words - case 2



0 / 1

Input

5

dictionary.txt

manic

amigo

Your OutputExpected output contains this at least once

1.⏎1.Word Ladder height = 14

Output is nearly correct, but whitespace differs. See highlights above.Special character legend

32: Output test - 5-letter words - case 3



0 / 1

Input

5

dictionary.txt

quart

meter

Your OutputExpected output contains this at least once

1.⏎1.Word Ladder height = 12

Output is nearly correct, but whitespace differs. See highlights above.Special character legend

33: Output test - 5-letter words - case 4



0 / 1

Input

5

dictionary.txt

think

smart

Your OutputExpected output contains this at least once

1.⏎1.Word Ladder height = 7

Output is nearly correct, but whitespace differs. See highlights above.Special character legend

34: Output test - 5-letter words - case 4



1 / 1

Input

5

dictionary.txt

melon

lemon

Your OutputExpected output contains this at least once

1.⏎

2.Welcome to the CS 211 Word Ladde

3.⏎

4.Enter the word size for the ladd

5.This program will make the short

6.word ladder between two 5-letter

7.⏎

8.Enter filename for dictionary:

9.Building array of 5-letter words

10.Setting the start 5-letter word.

11. Enter a 5-letter word:

35: Output test - 6-letter words - case 1



1 / 1

Input

6

dictionary.txt

memory

dynamo

Your OutputExpected output contains this at least once

1.⏎

2.Welcome to the CS 211 Word Ladde

3.⏎

4.Enter the word size for the ladd

5.This program will make the short

6.word ladder between two 6-letter

7.⏎

8.Enter filename for dictionary:

9.Building array of 6-letter words

10.Setting the start 6-letter word.

11.Entera 6-letterword:

36: Output test - 6-letter words - case 2



0 / 1

Input

6

dictionary.txt

canyon

wicked

Your OutputExpected output contains this at least once

1.⏎1.Word Ladder height = 9

Output is nearly correct, but whitespace differs. See highlights above.Special character legend

37: Valgrind memory leak check - successful ladder



0 / 2

38: Valgrind memory leak check - unsuccessful ladder



0 / 2

39: Valgrind error check - successful ladder



0 / 2

40: Valgrind error check - unsuccessful ladder



0 / 2

==150== definitely lost: 35,728 bytes in 2,233 blocks

==150== indirectly lost: 24,544 bytes in 1,534 blocks

==150== possibly lost: 0 bytes in 0 blocks

==150== still reachable: 0 bytes in 0 blocks

==150== suppressed: 0 bytes in 0 blocks

==150==

==150== Use --track-origins=yes to see where uninitialised values

==150== For lists of detected and suppressed errors, rerun with: -

==150== ERROR SUMMARY: 6 errors from 4 contexts (suppressed: 0 fro

VALGRIND: Memory Leak. Memory is NOT freed for ALL malloc calls.

==150== LEAK SUMMARY:

==150== definitely lost: 16 bytes in 1 blocks

==150== indirectly lost: 0 bytes in 0 blocks

==150== possibly lost: 0 bytes in 0 blocks

==150== still reachable: 0 bytes in 0 blocks

==150== suppressed: 0 bytes in 0 blocks

==150==

==150== For lists of detected and suppressed errors, rerun with: -

==150== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 fro

VALGRIND: Memory Leak. Memory is NOT freed for ALL malloc calls.

==150== definitely lost: 35,728 bytes in 2,233 blocks

==150== indirectly lost: 24,544 bytes in 1,534 blocks

==150== possibly lost: 0 bytes in 0 blocks

==150== still reachable: 0 bytes in 0 blocks

==150== suppressed: 0 bytes in 0 blocks

==150==

==150== Use --track-origins=yes to see where uninitialised values

==150== For lists of detected and suppressed errors, rerun with: -

==150== ERROR SUMMARY: 6 errors from 4 contexts (suppressed: 0 fro

VALGRIND: Error(s) reported.

==150== LEAK SUMMARY:

==150== definitely lost: 16 bytes in 1 blocks

==150== indirectly lost: 0 bytes in 0 blocks

Activity summary for assignment: Programming Project 05 - Link Lint List - Find

Shortest Word Ladder

77 / 90

points

Previous submissions

9:23 PM on 11/7/2477 / 90

9:51 PM on 11/7/2462 / 90

9:52 PM on 11/7/2462 / 90

9:54 PM on 11/7/2462 / 90

==150== possibly lost: 0 bytes in 0 blocks

==150== still reachable: 0 bytes in 0 blocks

==150== suppressed: 0 bytes in 0 blocks

==150==

==150== For lists of detected and suppressed errors, rerun with: -

==150== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 fro

VALGRIND: Error(s) reported.

View



View



View



View



Trouble with lab?

Feedback?

Due: 11/07/2024, 11:59 PM CST

Completion details

