Question

I need help writing this C code. Here is the description:

Let's say we have a program called smart typing which does two things:

1. The first letter of a word is always input manually by a keystroke.
2. When a sequence of n letters has been typed: c₁c₂...c_n and the set of words in the dictionary that start with that sequence also have c₁c₂...c_nc then the smart typing displays c automatically.

we would like to know,  for each word in the dictionary, which letters have to be input by a keystroke and to know the average of keystrokes needed to type a word in a dictionary.

The program gets from the command line the name of an input file containing the dictionary an the name of an output file which will contain the solution.

The first line of the input file contains an integer N that is the number of words of the dictionary (1<=N<=20). Each of the next N lines contains a word of the dictionary. The length of each word is at most 50 lowercase letters from the English alphabet ={a,b,...,z}. Assume all words are different.

The program creates a file which will contains N+2 lines with the solution. The first line contains an integer N that is the number of words. Each of the next N lines contains a word of the dictionary indicating with an asterisk the position of the letter that is displayed automatically by the smart typing. The last line shows the average number of keystrokes needed to type a word in the given dictionary. The average must be displayed with 2 digits after the decimal point.

Example of input file:

4
hello
hell
heaven
goodbye

Example of Output:

4

h*l*o
h*l*
h*a***
g******
2.00

Further Explanation:

To type the word hello, we need to type always the first letter for any word, in this case is h, every word which starts with h has as next letter e, then "e" is displayed automatically and we get the sequence "he". The 3rd letter is "l" and not every word which starts with "he" has "l" as 3rd letter (e.g. heaven) so we need to press "l". After press "l" we have the sequence "hel". Every word that starts with "hel" has "l" as 4th letter (hello, hell), then "l" in the 4th position is displayed automatically and we get "hell". Finally, smart typing doesn't know if we want to type the word "hell" or "hello" that's why "o" is not displayed automatically and we need to press "o" to complete the word "hello". In this way we can determine which letters of "hello" are displayed automatically. The same logic is applied for each word.

The average number of keystrokes needed to type a word is the sum of keystrokes needed to type each word (no asterisks in the output for each word) over the total of words in the dictionary. For this example is:

(3+2+2+1)/4 = 2.00

Testing the program:

Here is an example of what is expected in the functionality of the program

Example
Program_x Input1.txt 
Error! You must specify a filename for input and output

Program_x Input.txt Output1.txt
Error! Input.txt cannot be opened

Program_x Input1.txt Output1.txt
Output1.txt was created successfully!

Answer 1

In this ques ...Trie data structure can be used to solve the problem ..Here two functions are there

insert_in_trie(trie *root ,char word[ ]) ==>this function inserts the word in trie;

write_word(FILE *fptr,trie *root,char word[ ])==>this function writes the words as required in ques.

.....basically the letter will be typed when more words can be made by the present prefix or prefix is equal to some word in dictionary ==>this can be easily handled by trie  

So at particular node in trie...the possible options are seen ..if unique option is there then letter would be typed automatically else the letter must be typed .

Code snippet and screenshots has been attached

#include <stdio.h>
#include <stdlib.h>
struct Trie{
 struct Trie *child[26];//member containing info which different letter nodes it connects from this node
 int isleaf;//tells whether the node here signifies the end of the word or not

};
typedef struct Trie trie; //giving alias name as trie
void initialize(trie *node)
{
    node->isleaf=0; //initially leaf will be marked 0 since it is not leaf
    for(int i=0;i<26;i++)
    {
        node->child[i]=NULL; //node is not having any child ...so make it null
    }

}
int count_typed=0;//counts the total letters to be typed

void insert_in_trie(trie *root,char x[]) //function to insert the given word in trie
{


    for(int i=0;x[i]!='\0';i++) //iterate until null character arrives
    {
        int req=x[i]-'a'; //get index representing character
      if(root->child[req]==NULL)   //this checks whether this particular letter is there or not (if not then create the node)
        {
            root->child[req]=(trie *)malloc(sizeof(trie));
          initialize(root->child[req]);//initialize the node with initial state
        }
        root=root->child[req];

               //move the required node
    }
    root->isleaf=1;   // after traversing the whole word we will get the last node which will represent end of the word //and we will mark iseleaf as true

}
void write_word(FILE *fptr,trie *root,char word[])
{
    int prev_finished=0;//holds the info whether any word was finished at pervious node or not
    int curr_finshed=0;//holds the info whether any word was finished at current node or not
    for(int i=0;word[i]!='\0';i++)
    {
        int options=0; //holds info of possible options from this node
       for(int j=0;j<26;j++)
        {
            if(root->child[j]!=NULL) //checks whether the child[j] is present or not
            {
                if(root->child[j]->isleaf==1) //checks whether the child[j] represents the end of word
                    curr_finshed=1; //if condition above is true mark the current_finished as 1
                options++; //increment the option
            }

        }
        if(options>1||prev_finished==1) //if options is greater than 1 or any word was finished at previous node then character must be typed
        {
            fprintf(fptr,"%c",word[i]);
            int index=word[i]-'a';//get index representing the child
          root=root->child[index]; //move to the child
            count_typed++; //increment the variable


        }
        else  //this means only one option is there to traverse
        {
            fprintf(fptr,"%c",'*'); //so print *
          //get the only child having not null value
          for(int j=0;j<26;j++)
          {
              if(root->child[j]!=NULL)
              {
                  root=root->child[j];
                  break;
              }
          }

        }
   prev_finished=curr_finshed; //make curr_finished  as prev_finished
    }
    fprintf(fptr,"%s","\n");


}

int main()
{
 FILE *fptr; //initialise the file pointer
 int f=0;// checks whether file is opened successfully or not
     int size=0;//represents the number of words

 while(f==0)
 {
     char filename_input[100];//input filename
     char filename_output[100];//output filename
     scanf("%s",filename_input);//taking input
     scanf("%s",filename_output);//taking input

     if ((fptr = fopen(filename_input, "r")) == NULL) {
        printf("Error! opening file");
        continue;
        // Program exits if file pointer returns NULL.
     }


    trie *root=(trie *)malloc(sizeof(trie));//creating trie node
    initialize(root);//initialize root
        fscanf(fptr,"%d",&size);//read the file to get size

        char words[20][50];//to store words
        for(int i=0;i<size;i++)
        {
              fscanf(fptr,"%s",words[i]);//read word from file
            insert_in_trie(root,words[i]);//insert the word in trie
        }
        fclose(fptr);//close the file pointer
    if ((fptr = fopen(filename_output, "w")) == NULL) {
        printf("Error! opening file");
        continue;
        // Program exits if file pointer returns NULL.

    }

        f=1;//both files have been opened successfully
        fprintf(fptr,"%d\n",size);//write size to file

        for(int i=0;i<size;i++)
        {
         write_word(fptr,root,words[i]);//write the word to file

        }
        float Size=size;
        fprintf(fptr,"%.2f",count_typed/Size);//write the required value

    fclose(fptr);
    }





 }

Screenshots

egy.com/experqud Debug X main(): int C:\Users\vijay OneDrive\Desktop\coding\HomeworkLib\dict\bin\Debug\dict.exe Input1.txt output.txt DOQQSC main.c Process returned 0 (0x0) Press any key to continue. execution time : 6.474 s Х 88 89 90 FILE *fptr; //wwwwwww the file pointer int f=0; // checks whether file is opened successfully int size=0; //represents the number of words 91 92 93 94 while (f==0) { char filename e_input[100];//input filename char filename_output[100]; //output filename scanf("%s", filename_i input); //taking input scanf("%s", filename_output);//taking input if ((fptr = fopen(filename_input, "")) == NULL) printf("Error! opening file"); continue; // Program exits if file pointer returns NULL. 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 lll 112 113 114 115 trie *root= (trie *) malloc(sizeof(trie));//creating initialize (root);//initialize root fscanf(fptr,"%d", &size);//read the file to get char words [20] [50]; //to store words for (int i=0;i<size; i++) fscanf(fptr,"%s", words[i]);//read word f insert_in_trie (root, words[i]);//insert the > not displayed automatically and we need to press "o" to complete the word "hel determine which letters of "hello" are displayed automatically. The same logic is The average number of keystrokes needed to type a word is the sum of keystro each word (no asterisks in the output for each word) over the total of words in ti example is: (3+2+2+1)/4 = 2.00 Testing the program: Here is an example of what is expected in the functionality of the program Example Program_x Input1.txt Error! You must specify a filename for input and output Logs & others > Search results Сccc Х Build log x Build messages X CppCheck/ Compiler) Checking for existence: C:\Users\vijay OneDrive Desktop\coding\HomeworkLib\dict \bin\Debug\dict.exe Executing: "C:\Program Files (x86)\CodeBlocks/cb_console_runner.exe" "C: \Users\vijay OneDrive Desktop\coding\HomeworkLib\dict\bin Debug\dict.exe" (in DuSamvinnut tut Outsut1 tuet

dict ping > HomeworkLib main.c (dict] - Code::Blocks 17.12 X File Input 1.txt - Notepad File Edit Format View Help 4 hello * Qui hell File Edit View Search Project Build Debug Fortran modified wx Smith Tools Tools+ Plugins DoxyBlocks Settings Help x Debug 49 6:66: Il > D-2020 14:40 Dheaven <global main(): int Id goodbye 4 KK @QSCI X ED main.c X 5-2020 14:40 5-2020 14:37 5-2020 15:17 5-2020 15:49 D-2020 15:49 Files Pi di) Management Projects Symbols Workspace dict Sources Lmain.c 88 89 90 91 FILE *fptr; //wwwwwwwww the file pointer int f=0; // checks whether file is opened successfully or not int size=0;//represents the number of words lp . те 92 while (f==0) te * Dro char filename_input[100];//input filename char filename_output[100]; //output filename scanf("%s", filename_input);//taking input scanf("%s", filename_output);//taking input One Ln 1, Col 1 100% Windows (CRLF) UTF-8 This output.txt - Notepad 3D File Edit Format View Help D&4 h*1*0 DO h*1* Doh*a*** 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 lll if ((fptr = fopen(filename_input, "I")) == NULL) { printf("Error! opening file"); continue; // Program exits if file pointer returns NULL. } 1 Mig****** 2.00 Pic trie *root=(trie *) malloc(sizeof(trie));//creating two node initialize (root);//initialize root fscanf(fptr, "%d", &size); //read the file to get size Vid Wi char words [20] [50]://to store words for (int i=0;i< size;i++) RE LO Logs & others Net Build log X Build messages X CppCheck/Vera++ X CppCheck/Vera++ messages Checking for existence: C:\Users\vijay OneDrive\Desktop\coding\HomeworkLib\dict\bin\Debug \dict.exe Executing: "C:\Program Files (x86)\CodeBlocks/cb_console_runner.exe" "C:\Users\vijay OneDrive Desktop coding HomeworkLib\dict\bin\Debug\dict.exe" (in C:\Users\vijay OneDrive \Desktop\coding\HomeworkLib\dictl.) Process terminated with status -1073741510 (0 minute(s) 33 second(s)) Ln 1, Col 1 100% Windows (CRLF) UTF-8 C/C++ Windows (CR+LF) WINDOWS-1252 Line 108, Col 6, Pos 3727 Insert Read/Write de