Thursday, August 31, 2017

interesting programs


1. C code to generate you tube like random string
Example:
 https://www.youtube.com/watch?v=AB2rwvDXc-Y
https://www.youtube.com/watch?v=YW57xBVEIP8

#include<stdio.h>
#include<string.h>

static const char alphanum[] =
"0123456789"
"!@#$%^&*"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
int stringLength = sizeof(alphanum) - 1;

char genRandom()  // Random string generator function.
{

    return alphanum[rand() % stringLength];
}

int main()
{
    char String[128]={0};
    int z;
    srand(time(0));
    for(z=0; z < 21; z++)
    {
        String[z] = genRandom();

    }
    printf("random string is : %s\n",String);
    return 0;

}
[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ ./a.out
random string is : auoaP!MsZTEp9rsndUoEC

Ref:
http://www.cplusplus.com/forum/windows/88843/

Source code highligher:
http://hilite.me/

Sunday, August 20, 2017

graph theory

What is topological sort:


Reference:
https://www.youtube.com/watch?v=ddTC4Zovtbc
http://www.geeksforgeeks.org/topological-sorting/


Khan's algorithm for topological sorting:

http://connalle.blogspot.in/2013/10/topological-sortingkahn-algorithm.html

Topological sorting



Introduction:

topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex vu comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Directed acyclic graph.png
The graph shown to the left has many valid topological sorts, including:
  • 7, 5, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
  • 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
  • 3, 7, 8, 5, 11, 10, 2, 9 (because we can)
  • 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
  • 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
  • 7, 5, 11, 2, 3, 8, 9, 10


Algorithms:

Kahn Algorithm:

        Initialize sorted list to be empty, and a counter to 0
        Compute the indegrees of all nodes
        Store all nodes with indegree 0 in a queue
        While the queue is not empty
                get a node U and put it in the sorted list. Increment the counter.
                For all edges (U,V) decrement the indegree of V, and put V in the queue if the updated indegree is 0.
        If counter is not equal to the number of nodes, there is a cycle.


Recursive DFS Algorithm:

For this algorithm, edges point in the opposite direction as the previous algorithm (and the opposite direction to that shown in the diagram in the Examples section above).


        L ← Empty list that will contain the sorted nodes

        while there are unmarked nodes do

            select an unmarked node n

            visit(n) 

        function visit(node n)

            if n has a temporary mark then stop (not a DAG)

            if n is not marked (i.e. has not been visited yet) then

                mark n temporarily

                for each node m with an edge from n to m do

                    visit(m)
                mark n permanently
                add n to head of L



Complexity:
    The number of operations is O(|E| + |V|), |V| - number of vertices, |E| - number of edges.
    How many operations are needed to compute the indegrees?
    Depends on the representation:
    Adjacency lists: O(|E|)
    Matrix: O(|V|2)

Code Implementation:

Kahn Algorithm
//Input : adj_list ->Adjacency list; indegree : indegrees of all nodes .....
void top_sort(vector<list<int> > & adj_list, vector<int> &indegree) {
      queue<int> tsort_queue;
      vector<int> sorted;
     
      //If a node is not present in the graph , its indegree is -1.....
      for(int i = 0; i < (signed)indegree.size(); i++) {
            if(indegree[i] == -1)
                  continue;
            if(indegree[i] == 0)
            tsort_queue.push(i);
      }
     
      while(!tsort_queue.empty()) {
            int front = tsort_queue.front();
            tsort_queue.pop();
            sorted.push_back(front);
            list<int>::iterator it;
            for(it = adj_list[front].begin();
                        it != adj_list[front].end(); it++) {
                  indegree[*it] -= 1;
                  if(indegree[*it] == 0)
                        tsort_queue.push(*it);
            }
      }
      cout<<"Top Sorted Order : ";
      for(int i = 0; i < (signed)sorted.size(); i++)
            cout<<sorted[i]<<" ";
      cout<<endl;
}



DFS Algorithm:


//Top Sort using DFS .....
void top_sort_DFS_loop(vector<list<int> > adj_list,
            stack<int>& sorted, vector<bool>& visited, int node) {
      list<int>::iterator it;
      for(it = adj_list[node].begin(); it != adj_list[node].end(); it++) {
            if(visited[*it])
                  continue;
            visited[*it] = true;
            top_sort_DFS_loop(adj_list, sorted, visited, *it);
      }
      sorted.push(node);
}

void top_sort_DFS(vector<list<int> > adj_list) {
      stack<int> sorted;
      vector<bool> visited(adj_list.size(), false);

      for(int i = 0; i < (signed)adj_list.size(); i++) {
            if(visited[i])
                  continue;
            visited[i] = true;
            top_sort_DFS_loop(adj_list, sorted, visited, i);
      }
      cout<<"Top Sort Using DFS : ";
      while(!sorted.empty()) {
            cout<<sorted.top()<<" ";
            sorted.pop();
      }
      cout<<endl;

}

Note : The above codes only accepts DAG.


Applications : 


Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers.


Dijkstra's algorithm

Friday, August 18, 2017

how to embed PDF in the blogger

http://www.mybloggerlab.com/2013/03/how-to-embed-pdf-and-other-documents-in-blogger-posts.html

C++ STL LIBRARY

:) happy that learning c++ data structures.


Reference: http://www.cs.cornell.edu/~wdtseng/icpc/notes/stl_part1.pdf http://www.cs.cornell.edu/~wdtseng/icpc/notes/stl_part2.pdf

http://www.geeksforgeeks.org/vector-in-cpp-stl/
http://www.geeksforgeeks.org/list-cpp-stl/

http://www.geeksforgeeks.org/sorting-vector-of-pairs-in-c-set-1-sort-by-first-and-second/


Tuesday, August 8, 2017

file operations

1. getchar() - by default read char from the stdin. return EOF if it reaches end of file
2. gets(char *buff)- by default read from stdin until new line. it will read the newline as well. return NULL if it reaches end of file
3. fgetc(FILE *fp) - read char by char from file and return EOF if it reaches end of file
4. fgets(char *buff,size_of_buffer,FILE *fp) - reads string from the file pointer until reaches new line or size_of_buffer reaches. return NULL once it reaches end of file. it will read newline as well.
5. fscanf(FILE *fp,"%d....",char *buff) - return EOF if it reaches end of the file


File handlers functions Return type Example
getc * The difference between getc() and getchar() is getc() can read from any input stream, but getchar() reads from standard input.                                                                    * It reads a single character from a given input stream and returns the corresponding integer value (typically ASCII value of read character) on success.
* even it reads the new line till EOF . 
Ex: if we give new line that also stored and printed
int getc(FILE *stream);  #include <stdio.h>
int main()
{
   printf("%c", getc(stdin));
   return(0);
}

int in;  
while ((in = getchar()) != EOF) 
{
   putchar(in);
} 
getchar getchar() reads from standard input. So getchar() is equivalent to getc(stdin).  int getchar(void);  #include <stdio.h>
int main()
{
   printf("%c", getchar());
   return 0;
} 
getch getch() is a nonstandard function and is present in conio.h header file which is mostly used by MS-DOS compilers like Turbo C. int getch();  
getche Like getch(), this is also a non-standard function present in conio.h. It reads a single character from the keyboard and displays immediately on output screen without waiting for enter key. int getche(void);   
gets * For reading a string value with spaces, we can use either gets() or fgets() in C
* Reads characters from the standard input (stdin) and stores them as a C string into str until a newline character or the end-of-file is reached.
char * gets ( char * str );  
fgets It reads a line from the specified stream and stores it into the string pointed to by str. It stops when either (n-1) characters are read, the newline character is read, or the end-of-file is reached, whichever comes first. char *fgets(char *str, int n, FILE *stream)
str :Pointer to a block of memory (array of char)
where the string read is copied as a C string.
returns : the function returns str
 



Ref: https://www.geeksforgeeks.org/difference-getchar-getch-getc-getche/
https://www.geeksforgeeks.org/fgets-gets-c-language/

1. program to print the each words from the file using the fscanf 

[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ cat test.txt
selva kumar how are you
vithun patbitha what are you doing guys?
my name is billa 123445 selva
[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ cat word.c
#include<stdio.h>
int main()
{
    char word[50];
    FILE *fp=fopen("test.txt","r");
    while(fscanf(fp,"%s",word)!=EOF) {
    printf("%s\n",word);
    }

    printf("\n");
    return 0;
}

output:
[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ ./a.out
selva
kumar
how
are
you
vithun
patbitha
what
are
you
doing
guys?
my
name
is
billa
123445

selva
https://www.quora.com/How-do-I-search-from-a-text-file-in-c-language

2. program to get the words with space using gets and split those words using sscanf from stdin

[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ cat word2.c
#include<stdio.h>
#include<string.h>
int main()
{
    char word[50]={0},s1[20],s2[20];
// reads the strings with spca using scanf
    printf("Enter the string \n");
    gets(word);
    sscanf(word,"%s%s",s1,s2);
    //puts(word);
    puts(s1);
    puts(s2);
    // from the long given string split the words
    printf("Enter the string \n");
    fgets(word,50,stdin);
    //puts(word);
    char *ptr=word;
    while(sscanf(ptr,"%s",s1)!=EOF) {
            puts(s1);
            //printf("%d\n",strlen(s1));
            ptr=ptr+strlen(s1)+1;
    }

    printf("\n");
    return 0;

}

output:

[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ ./a.out
Enter the string
warning: this program uses gets(), which is unsafe.
selva kumar
selva
kumar
Enter the string
hi selva kumar how are you
hi
selva
kumar
how
are
you


3. program to get the string with space using the scanf statment itself:
[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ cat word3.c
#include<stdio.h>
int main()
{
    char s1[20];

    printf("Enter the string \n");
    scanf("%[^\n]s",s1);
    puts(s1);
    return 0;
}

[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ ./a.out
Enter the string
selva kumar hi
selva kumar hi

Ref:https://gpraveenkumar.wordpress.com/2009/06/10/how-to-use-scanf-to-read-string-with-space/


4. program for simple fgets and simple fputs:
  1. #include <stdio.h>

  2. int main ( void )
  3. {
  4. static const char filename[] = "file.txt";
  5. FILE *file = fopen ( filename, "r" );
  6. if ( file != NULL )
  7. {
  8. char line [ 128 ]; /* or other suitable maximum line size */

  9. while ( fgets ( line, sizeof line, file ) != NULL ) /* read a line */
  10. {
  11. fputs ( line, stdout ); /* write the line */
  12. }
  13. fclose ( file );
  14. }
  15. else
  16. {
  17. perror ( filename ); /* why didn't the file open? */
  18. }
  19. return 0;
  20. }

Ref:https://www.daniweb.com/programming/software-development/code/216411/reading-a-file-line-by-line

5. program to read from the file and converting into the integer:
#include <stdio.h>   /* required for file operations */
#include <conio.h>  /* for clrscr */
#include <dos.h>  /* for delay */

FILE *fr;            /* declare the file pointer */

main()

{
   int n;
   long elapsed_seconds;
   char line[80];
   clrscr();

   fr = fopen ("elapsed.dta", "rt");  /* open the file for reading */
   /* elapsed.dta is the name of the file */
   /* "rt" means open the file for reading text */

   while(fgets(line, 80, fr) != NULL)
   {
  /* get a line, up to 80 chars from fr.  done if NULL */
  sscanf (line, "%ld", &elapsed_seconds);
  /* convert the string to a long int */
  printf ("%ld\n", elapsed_seconds);
   }
   fclose(fr);  /* close the file prior to exiting the routine */
} /*of main*/


https://www.phanderson.com/files/file_read.html

6. program to truncate newline read from the gets/fgets:
#include <stdio.h>
#include <string.h>
#define bufSize 1024
int main(int argc, char *argv[])
{
  FILE* fp;
  char buf[bufSize];
  if (argc != 2)
  {
    fprintf(stderr,
            "Usage: %s <soure-file>\n", argv[0]);
    return 1;
  }
  if ((fp = fopen(argv[1], "r")) == NULL)
  { /* Open source file. */
    perror("fopen source-file");
    return 1;
  }
  while (fgets(buf, sizeof(buf), fp) != NULL)
  {
    buf[strlen(buf) - 1] = '\0'; // eat the newline fgets() stores
    printf("%s\n", buf);
  }
  fclose(fp);
  return 0;
}

https://gsamaras.wordpress.com/code/read-file-line-by-line-in-c-and-c/

7. string matching how can we do for the given string in the file
a. using program 1 above we can take each word and do strcmp and we
can find occurence of the string
b. using program 2 above(by doing that in the file) we can take
single word and do the strcmp
c. we can do without using any library function

[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ cat 1 #include<stdio.h> #include<conio.h> #include<stdlib.h> count_data(); void main() { // calling function count_data(); getch(); } count_data() // function for count no of words,lines & characters. { FILE *fp,*fp_rep; char ch,ch1,temp_str[50],rep_str[10],new_str[10]; int count=0; // counter clrscr(); fp=fopen("c:\\windows\\desktop\\input.txt","r"); fp_rep=fopen("c:\\windows\\desktop\\input1.txt","w"); printf("\nEnter String to find:"); scanf("%s",rep_str); printf("\nEnter String to replace:"); scanf("%s",new_str); while((ch=getc(fp))!=EOF) { if(ch==' ') { temp_str[count]='\0'; if(strcmp(temp_str,rep_str)==0) { printf("Do u want to replace(y/n):"); ch1=getche(); if(ch1=='y') { fprintf(fp_rep," %s",new_str); count=0; } else { fprintf(fp_rep," %s",temp_str);count=0;} } else { fprintf(fp_rep," %s",temp_str); count=0; } }else { temp_str[count++]=ch; } } if(strcmp(temp_str,rep_str)==0) { printf("Do u want to replace(y/n):"); ch1=getche(); if(ch1=='y') { fprintf(fp_rep,"%s ",new_str); count=0; } else { fprintf(fp_rep,"%s ",temp_str); count=0; } }else { fprintf(fp_rep,"%s ",temp_str); } fclose(fp); fclose(fp_rep); remove("c:\\windows\\desktop\\input.txt"); rename("c:\\windows\\desktop\\input1.txt","c:\\windows\\desktop\\input.txt"); fflush(stdin); [tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ [tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$


8. split strings based on any delimiter is :
 #include <string.h>
#include <stdio.h>

int main()
{
   char str[80] = "This is - www.tutorialspoint.com - website";
   const char s[2] = "-";
   char *token;
   
   /* get the first token */
   token = strtok(str, s);
   
   /* walk through other tokens */
   while( token != NULL ) 
   {
      printf( " %s\n", token );
    
      token = strtok(NULL, s);
   }
   
   return(0);
}

https://www.tutorialspoint.com/c_standard_library/c_function_strtok.htm

9. program to club two lines from two files:


  1. #include <stdio.h>

  2. int main() {
  3. char c[78]; /* declare a char array */
  4. char d[6];
  5. char e[90];
  6. FILE *file,*filep,*file2; /* declare a FILE pointer */

  7. file = fopen("data.txt", "r");
  8. file2 = fopen("data2.txt", "r");
  9. filep = fopen("dataprint.txt","w+");

  10. /* open a text file for reading */

  11. while(fgets(c, 78, file)!=NULL && fgets (d,6,file2)!=NULL) {

  12. concat (e,d,c);//fist attempt
  13. fprintf(filep,"%s",e);
  14. //fprintf(filep,"%s %s",d,c); //second attempt

  15. }

  16. printf("\n\nClosing file...\n");
  17. fclose(file);
  18. fclose(file2);
  19. fclose(filep);
  20. system("pause");
  21. return 0;

  22. }

https://www.daniweb.com/programming/software-development/threads/193980/combine-two-txt-file-line-by-line-using-fgets


REf: http://beej.us/guide/bgc/output/html/multipage/gets.html
http://people.cs.uchicago.edu/~dmfranklin/tutorials/fgets.txt


10. program for getc & getchar:

#include <stdio.h>
void read_single_char() {
   printf("%c", getc(stdin));
}
void read_single_till_eof_stdin () {
   int i=0;
   char stream[128] = {0};
   while((stream[i] = getc(stdin)) != EOF) {
         i++;
         if(i > 30) {
           break;
         }
   }
   printf("%s\n", stream);
}

int main()
{
   //read_single_char();
   read_single_till_eof_stdin();
   return(0);
}

output:

tselva@tselva-mbp:~/Documents/work/c> ./a.out
hi
selva
kumar
how
are you
this is the end of the world
hi
selva
kumar
how
are you
th

11. finding the number of occurence of the word using fscanf :

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main (int argc,char *argv[]) {
        char occur[1000][256]={0};
        int i=0,j=0;
        char matching_word[50];
        int count=0;
        if (argc != 3) {
                printf("<prog> <file_name> <matching_string>\n");
                exit(0);
        }
        FILE *fp=fopen(argv[1],"r");
        strcpy(matching_word,argv[2]);

        while((fscanf(fp,"%s",occur[i]) != EOF) && (i < 1000)) {
                //printf("%s\n",occur[i]);
                i++;
        }

        for(j=0;j<i;j++) {
            //printf("%s\n",occur[j]);
            if(strcmp(occur[j],matching_word) == 0) {
                    count++;
            }
        }
        printf("\nmatching word %s occurence - %d\n",matching_word,count);

}


output:

tselva@tselva-mbp:~/Documents/work/c> ./a.out test.txt selva

matching word selva occurence - 0
tselva@tselva-mbp:~/Documents/work/c> ./a.out test.txt you

matching word you occurence - 6
tselva@tselva-mbp:~/Documents/work/c> more test.txt
hi
how are you
how are you
this is the end of the world
you you you you