need 4 small programs debugged in c99. no variable-length arrays and no memory leaks. send a message for the source code. 1.3-1.5 from pdf
Treat the arguments (excluding argv[0]) as given: make no attempt to process or otherwise normalize the strings before sorting. Note that your shell will perform some manipulation on your input before passing the strings to your program, and most punctuation marks have special meanings: use escape sequences and/or quotation marks to avoid this. Usage $ ./sorta foo bar baz quuz bar baz foo quux $ ./sorta aaa aAa AaA AAA AAA AaA aAa aaa $ ./sorta 3 20 100 100 20 3 $ ./sorta " z" a z a 1.3 sudoku: Checking Sudoku solutions Write a program sudoku that (part 1) checks whether a proposed Sudoku solution is correct and (part 2) checks whether a partially-solved Sudoku puzzle with one unknown square can be solved. sudoku takes a single argument, which is the path to a file containing a completed or almost-completed Sudoku puzzle. A completed Sudoku puzzle is a 9× 9 matrix containing the digits 1–9, inclusive. The matrix is divided into nine 3× 3 submatrixes, themselves arranged in a 3× 3 square. A completed Sudoku puzzle is a correct solution if and only if it has the following properties: • Each digit occurs exactly once in each row (that is, no row contains any digit more than once. • Each digit occurs exactly once in each column. • Each digit occurs exactly once in each submatrix. 3 For example, this completed puzzle is a correct solution: 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 An almost-completed Sudoku puzzle is similar, except that one or two elements are unspecified. This portion of the assignment has two parts. For full credit, your program must correctly handle both parts. You will receive half credit if your program handles one part but not both. Part 1 sudoku will be given a completed Sudoku puzzle, determine whether the solution is correct, and print either correct or incorrect. Part 2 sudoku will be given an almost-complete Sudoku puzzle, determine whether the partial solution can be solved, and print either solvable or unsolvable. 1.3.1 Correctness checking The input file contains a completed Sudoku puzzle. The puzzle is given on nine lines, each of which contains nine digits without any separation. Note that the digit 0 will not occur. The input file file1.txt corresponding to the puzzle above would contain: 534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179 When given such a file, sudoku must determine whether the completed puzzle is a correct solution (meaning it satisfies the three properties). If so, it prints correct. Otherwise, it prints incorrect. If the input file does not exist, is not readable, or does not follow the format specified here, sudoku may print error. Usage $ ./sudoku file1.txt correct 4 1.3.2 Solvability checking The input file contains an almost-completed Sudoku puzzle. The format is the same as above—nine lines with nine characters each—except that up to two of the characters may be spaces instead of digits. The spaces indicate that the digit for that element is unspecified. The input file file2.txt contains an almost-completed puzzle with two unknown entries: 435269781 682571493 1978345 2 826195347 374682915 951743628 519 26874 248957136 763418259 If the input file contains an almost-completed puzzle, sudoku must determine whether the puzzle can be solved. If the puzzle has unspecified entries, can they be replaced by a digits such that the completed puzzle is a correct solution? If so, sudoku prints solvable. Otherwise, it prints unsolvable. If the puzzle contains no unspecified entries (that is, it is a completed puzzle), sudoku will print correct or incorrect as before. If the input file does not exist, is not readable, does not follow the format specified above, or contains more than two unspecified elements, sudoku may print error. Usage $ ./sudoku file2.txt solvable 1.4 list: Linked lists Write a program list that maintains and manipulates a sorted linked list according to instructions received from standard input. The linked list is maintained in order, meaning that the items in the list are stored in increasing numeric order after every operation. Note that list will need to allocate space for new nodes as they are created, using malloc; any allocated space should be deallocated using free as soon as it is no longer needed. Note also that the list will not contain duplicate values. list supports two operations: insert n Adds an integer n to the list. If n is already present in the list, it does nothing. The instruction format is an i followed by a space and an integer n. delete n Removes an integer n from the list. If n is not present in the list, it does nothing. The instruction format is a d followed by a space and an integer n. After each command, list will print the length of the list followed by the contents of the list, in order from first (least) to last (greatest). list must halt once it reaches the end of standard input. 5 Input format Each line of the input contains an instruction. Each line begins with a letter (either “i” or “d”), followed by a space, and then an integer. A line beginning with “i” indicates that the integer should be inserted into the list. A line beginning with “d” indicates that the integer should be deleted from the list. Your program will not be tested with invalid input. You may choose to have list terminate in response to invalid input. Output format After performing each instruction, list will print a single line of text containing the length of the list, a colon, and the elements of the list in order, all separated by spaces. Usage Because list reads from standard input, you may test it by entering inputs line by line from the terminal. $ ./list i 5 1 : 5 d 3 1 : 5 i 3 2 : 3 5 i 500 3 : 3 5 500 d 5 2 : 3 500 ^D To terminate your session, type Control-D at the beginning of the line. (This is indicated here by the sequence ^D.) This closes the input stream to list, as though it had reached the end of a file. Alternatively, you may use input redirection to send the contents of a file to list. For example, assume list_commands.txt contains this text: i 10 i 11 i 9 d 11 Then we may send this file to list as its input like so: $ ./list < list_commands.txt 1 : 10 2 : 10 11 3 : 9 10 11 2 : 9 10 6 1.5 mexp: matrix manipulation write a program mexp that multiplies a square matrix by itself a specified number of times. mexp takes a single argument, which is the path to a file containing a square (k × k) matrix m and a non-negative exponent n. it computes mn and prints the result. note that the size of the matrix is not known statically. you must use malloc to allocate space for the matrix once you obtain its size from the input file. to compute mn, it is sufficient to multiply m by itself n− 1 times. that is, m3 = m ×m ×m . naturally, a different strategy is needed for m0. input format the first line of the input file contains an integer k. this indicates the size of the matrix m , which has k rows and k columns. the next k lines in the input file contain k integers. these indicate the content of m . each line corresponds to a row, beginning with the first (top) row. the final line contains an integer n. this indicates the number of times m will be multiplied by itself. n is guaranteed to be non-negative, but it may be 0. for example, an input file file.txt containing 3 1 2 3 4 5 6 7 8 9 2 indicates that mexp must compute 1 2 34 5 6 7 8 9 2 . output format the output of mexp is the computed matrix mn. each row of mn is printed on a separate line, beginning with the first (top) row. the items within a row are separated by spaces. using file.txt from above, $ ./mexp file1.txt 30 36 42 66 81 96 102 126 150 1.6 bst: binary search trees write a program bst that manipulates binary search trees. it will receive commands from standard input, and print resposes to those commands to standard output. a binary search tree is a binary tree that stores integer values in its interior nodes. the value for a particular node is greater than every value stored its left sub-tree and less than every value stored in its right sub-tree. the tree will not contain any value more than once. bst will need to allocate space for new nodes as they are created using malloc; any allocated space should be deallocated using free before bst terminates. this portion of the assignment has two parts. 7 part 1 in this part, you will implement bst with three commands: insert n adds a value to the tree, if not already present. the new node will always be added as the child of an existing node, or as the root. no existing node will change or move as as result of inserting an item. if n was not present, and hence has been inserted, bst will print inserted. otherwise, it will print not inserted. the instruction format is an i followed by a decimal integer n. search n searches the tree for a value n. if n is present, bst will print present. otherwise, it will print absent. the instruction format is an s followed by a space and an integer n. print prints the current tree structure, using the format in section 1.6.1. part 2 in this part, you will implement bst with an additional fourth command: delete n removes a value from the tree. see section 1.6.2 for further discussion of deleting nodes. if n is not present, print absent. otherwise, print deleted. the instruction format is a d followed by a space and an integer n. input format the input will be a series of lines, each beginning with a command character (i, s, p, or d), possibly followed by a decimal integer. when the input ends, the program should terminate. your program list_commands.txt="" 1="" :="" 10="" 2="" :="" 10="" 11="" 3="" :="" 9="" 10="" 11="" 2="" :="" 9="" 10="" 6="" 1.5="" mexp:="" matrix="" manipulation="" write="" a="" program="" mexp="" that="" multiplies="" a="" square="" matrix="" by="" itself="" a="" specified="" number="" of="" times.="" mexp="" takes="" a="" single="" argument,="" which="" is="" the="" path="" to="" a="" file="" containing="" a="" square="" (k="" ×="" k)="" matrix="" m="" and="" a="" non-negative="" exponent="" n.="" it="" computes="" mn="" and="" prints="" the="" result.="" note="" that="" the="" size="" of="" the="" matrix="" is="" not="" known="" statically.="" you="" must="" use="" malloc="" to="" allocate="" space="" for="" the="" matrix="" once="" you="" obtain="" its="" size="" from="" the="" input="" file.="" to="" compute="" mn,="" it="" is="" sufficient="" to="" multiply="" m="" by="" itself="" n−="" 1="" times.="" that="" is,="" m3="M" ×m="" ×m="" .="" naturally,="" a="" different="" strategy="" is="" needed="" for="" m0.="" input="" format="" the="" first="" line="" of="" the="" input="" file="" contains="" an="" integer="" k.="" this="" indicates="" the="" size="" of="" the="" matrix="" m="" ,="" which="" has="" k="" rows="" and="" k="" columns.="" the="" next="" k="" lines="" in="" the="" input="" file="" contain="" k="" integers.="" these="" indicate="" the="" content="" of="" m="" .="" each="" line="" corresponds="" to="" a="" row,="" beginning="" with="" the="" first="" (top)="" row.="" the="" final="" line="" contains="" an="" integer="" n.="" this="" indicates="" the="" number="" of="" times="" m="" will="" be="" multiplied="" by="" itself.="" n="" is="" guaranteed="" to="" be="" non-negative,="" but="" it="" may="" be="" 0.="" for="" example,="" an="" input="" file="" file.txt="" containing="" 3="" 1="" 2="" 3="" 4="" 5="" 6="" 7="" 8="" 9="" 2="" indicates="" that="" mexp="" must="" compute="" ="" 1="" 2="" 34="" 5="" 6="" 7="" 8="" 9="" 2="" .="" output="" format="" the="" output="" of="" mexp="" is="" the="" computed="" matrix="" mn.="" each="" row="" of="" mn="" is="" printed="" on="" a="" separate="" line,="" beginning="" with="" the="" first="" (top)="" row.="" the="" items="" within="" a="" row="" are="" separated="" by="" spaces.="" using="" file.txt="" from="" above,="" $="" ./mexp="" file1.txt="" 30="" 36="" 42="" 66="" 81="" 96="" 102="" 126="" 150="" 1.6="" bst:="" binary="" search="" trees="" write="" a="" program="" bst="" that="" manipulates="" binary="" search="" trees.="" it="" will="" receive="" commands="" from="" standard="" input,="" and="" print="" resposes="" to="" those="" commands="" to="" standard="" output.="" a="" binary="" search="" tree="" is="" a="" binary="" tree="" that="" stores="" integer="" values="" in="" its="" interior="" nodes.="" the="" value="" for="" a="" particular="" node="" is="" greater="" than="" every="" value="" stored="" its="" left="" sub-tree="" and="" less="" than="" every="" value="" stored="" in="" its="" right="" sub-tree.="" the="" tree="" will="" not="" contain="" any="" value="" more="" than="" once.="" bst="" will="" need="" to="" allocate="" space="" for="" new="" nodes="" as="" they="" are="" created="" using="" malloc;="" any="" allocated="" space="" should="" be="" deallocated="" using="" free="" before="" bst="" terminates.="" this="" portion="" of="" the="" assignment="" has="" two="" parts.="" 7="" part="" 1="" in="" this="" part,="" you="" will="" implement="" bst="" with="" three="" commands:="" insert="" n="" adds="" a="" value="" to="" the="" tree,="" if="" not="" already="" present.="" the="" new="" node="" will="" always="" be="" added="" as="" the="" child="" of="" an="" existing="" node,="" or="" as="" the="" root.="" no="" existing="" node="" will="" change="" or="" move="" as="" as="" result="" of="" inserting="" an="" item.="" if="" n="" was="" not="" present,="" and="" hence="" has="" been="" inserted,="" bst="" will="" print="" inserted.="" otherwise,="" it="" will="" print="" not="" inserted.="" the="" instruction="" format="" is="" an="" i="" followed="" by="" a="" decimal="" integer="" n.="" search="" n="" searches="" the="" tree="" for="" a="" value="" n.="" if="" n="" is="" present,="" bst="" will="" print="" present.="" otherwise,="" it="" will="" print="" absent.="" the="" instruction="" format="" is="" an="" s="" followed="" by="" a="" space="" and="" an="" integer="" n.="" print="" prints="" the="" current="" tree="" structure,="" using="" the="" format="" in="" section="" 1.6.1.="" part="" 2="" in="" this="" part,="" you="" will="" implement="" bst="" with="" an="" additional="" fourth="" command:="" delete="" n="" removes="" a="" value="" from="" the="" tree.="" see="" section="" 1.6.2="" for="" further="" discussion="" of="" deleting="" nodes.="" if="" n="" is="" not="" present,="" print="" absent.="" otherwise,="" print="" deleted.="" the="" instruction="" format="" is="" a="" d="" followed="" by="" a="" space="" and="" an="" integer="" n.="" input="" format="" the="" input="" will="" be="" a="" series="" of="" lines,="" each="" beginning="" with="" a="" command="" character="" (i,="" s,="" p,="" or="" d),="" possibly="" followed="" by="" a="" decimal="" integer.="" when="" the="" input="" ends,="" the="" program="" should="" terminate.="" your="">