Project 5 Solution

Write a C program project5.c that operates as follows. First read the command-line arguments which consist of two strings S and T, followed by a list of m≥1 integer distances d1, d2, … dm. It is expected that the two strings S and T will be anagrams or permutations of the same characters.

The goal is to transform S into T by a sequence of character swaps. Each character swap must exchange two characters that are exactly dj positions apart, for some j such that 1 ≤ j ≤ m. Examples:

Suppose the current string is “abcde”. Then each possible next string in the sequence may be obtained as follows:




If some dj = 1 then “abcde” can be transformed into “bacde” or “acbde” or “abdce” or “abced”.

If some dj = 2 then “abcde” can be transformed into “cbade” or “adcbe” or “abedc”.

If some dj = 3 then “abcde” can be transformed into “dbcae” or “aecdb”.

If some dj = 4 then “abcde” can be transformed into “ebcda”.

Your program will search for a possible solution sequence that transforms S into T. Hint: use recursion, and maintain a linked list of all the strings that have been obtained so far. To prevent infinite looping, prune the search whenever it would lead to a string that has previously been obtained. Stop making recursive calls whenever string T is reached, or when all possible search avenues have been exhausted.

Finally your program will display the number of strings in some sequence from S to T, followed by such a sequence. However, if no sequence from S to T exists, then instead just display “No solution”.

For each sample run below, some (but not necessarily all) of the possible correct answers are shown.

The sequence must not repeat any strings, but you are not required to find a shortest-length sequence.




./a.out post opts 2 3
./a.out decal laced 2 4
./a.out abcd dcba 1
5
5
19


3
3
11


7
7
19
post
post
post


decal
decal
decal


abcd
abcd
abcd
tosp
tosp
sopt


lecad
dacel
dacel


bacd
abdc
acbd
tpso
sotp
stpo


laced
laced
cadel


bcad
adbc
cabd
spto
spto
ptso






ladec


bcda
dabc
cadb
opts
opts
otsp






dalec


cbda
dacb
acdb




stop






delac


cdba
dcab
adcb




spot






ledac


dcba
dcba
dacb




opst






lecad






dabc




tpso






celad






adbc




tosp






caled






abdc




sotp






laced






badc




pots














bdac




tops














dbac




tspo














dbca




psto














bdca




ostp














bcda




tsop














cbda




tpos














cdba




opts














dcba



./a.out sets test 1 2 3
./a.out decal laced 3
./a.out abcd dcba 2
No solution




No solution




No solution








Motivation: The problem described here is similar to several kinds of word puzzles such as ladders and anagrams, and 2-dimensional variants of this problem can be used to solve well-known problems such as 8-puzzle or 15-puzzle. Implementing the program should also provide you with excellent practice in using both recursion and linked lists.







Please carefully read the following requirements:




You must do your own work. You must not borrow any code from any other person, book, website, or any other source. You also must not share your code with any other person, or post it on any website. We run plagiarism detection software on every project. So if you violate these rules, you may receive an invitation to the dean’s office to discuss the penalties for academic misconduct.



Make sure your program runs properly on the cs-intro.ua.edu server. Your program will be graded on that system using this command: gcc project5.c –Wall –lm –std=c99. In particular, make sure your program initializes the values of all variables when they are declared or allocated. Otherwise it might behave differently on Linux than it does on a PC or Mac.



Compress your project into a zip file that contains your C program source file. Right-click (or secondary click) on your project directory, and then (depending on your operating system) select either the Compress option or Send To → Compress from the popup menu. Finally upload your .zip file that contains your .c file for this project to Blackboard.



If you violate the above requirements such that it breaks our grading script, your project will be assessed a significant point deduction, and extreme or multiple violations may cause the project to be considered ungradable.



Every semester many students lose some points because they don’t follow all the instructions. So please read and follow all the project specifications precisely to prevent losing points unnecessarily. If anything is unclear, please ask for clarification well before the project is due. Please pay particular attention to input and output formats.



Submit your project on Blackboard by the due date (11:59pm Friday). There is a grace period of 24 hours (until 11:59pm Saturday). Projects submitted on Sunday will be assessed a late penalty of 5% per hour. No projects will be accepted after Sunday. Once it is graded, your project score will be posted on Blackboard and the results of the grading script will be sent to your Crimson email account.



Double-check and triple-check your submission when you submit it. Errors discovered later cannot be fixed and resubmitted after the project is graded. Projects will not be re-graded unless an error is found in the grading script or in the input/output files that are used during grading.