C代写:CS228 Finding Laddergrams


General Information

In this project you need to form a team within your class, and the team size can be 1-5 student(s). Each team needs to come up solutions to the tasks described below, submits a written report, and uploads the source code through SOUL by the deadline. And the deadline is the last teaching day of the semester.

Marking Criteria

This project carries 30 marks, and normally the same marks will be assigned to each team member. The marks will be based on the solutions designed and implemented, the analysis of the solutions, and the quality of the written report. The programming part can receive at most 20 marks, and the report can receive at most 10 marks. Specifically, for the programming part, solution to each task can get at most 10 marks. For the written report, the description of the problem and identification of issues can get at most 4 marks, 2 for each task; the explanation and analysis of the solutions can get at most 6 marks, 3 for each task.

The Tasks

Your team needs to design a C program to find laddergrams of two words based on a given dictionary file (wordlist.txt on SOUL). There are two tasks.

In the first task, for each word in the dictionary file, find the word’s “1-morphs set”, and print all the words and their “1-morphs sets” in a text file. A word’s “1-morphs set” contains all the words which only have one letter different from the given word.

For example, the “1-morphs” set of “times” are {timer, timed, tires, tiles, tides, tames, limes, dimes}. In the output file, each word and its “1-morphs set” are printed in the same line in the following format

times: timer, timed, tires, tiles, tides, tames, limes, dimes

The order of words in the “1-morphs” set does not matter.

In the second task, receive two words from user input and find laddergrams of the two words. A laddergram of two words is a serious of words (including the two given words at both ends) such that each word in the serious has only one letter different from its predecessor and its successor. Through the laddergram, we can convert the first given
word to the second given word by changing one letter only in each step. For example, if the two given words are “love” and “hate”, then the laddergram can be:

love => hate: love, lone, lane, late, hate

If the two given words are “white” and “black”, then the laddergram can be:

white => black: white, whine, shine, spine, spice, slice, slick, slack, black

Your program can complete this task at three different level:

  • “pass” level: able to find any laddergram for two given words or confirm no laddergram exists for the two given words.
  • “good” level: able to find a shortest laddergram for two given words.
  • “excellent” level: able to find all the shortest laddergram for two given words.

A shortest laddergram contains the minimum number of words of two given words. Shortest laddergram in general is not unique.