Thread: Algorithm not working in C

  1. #1
    Registered User
    Join Date
    May 2022
    Posts
    18

    Algorithm not working in C

    I have an algorithm which transposes columns based on a key and its alphabetical order. This is an example. However, when I input a key of more than 5 characters long the program is messed up. Some letters don't even go into the matrix.



    https://media.geeksforgeeks.org/wp-c...on-cipher1.png
    insert
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    
    // use bubble sort to sort letters in a key
    void sort_letters(char *phrase) {
        int i,j;
        int n = strlen(phrase);
        //printf("The string to sort is: %s\n", phrase);
        for ( i = 0; i < n-1; i++) {
            for ( j = i+1; j < n; j++) {
                if (phrase[i] > phrase[j]) {
                        char temp = phrase[i];
                        phrase[i] = phrase[j];
                        phrase[j] = temp;
                }
            }
        }
        //printf("The sorted string is:  %s\n", phrase);
    }
    
    
    // allocate a matrix for string and fill it
    char** gridStr(char *line, char *key)
    {
        int n = strlen(line);    
        int columns = strlen(key);
        int rows = (n + columns - 1) / columns;
        int j;
        char **matrix = malloc(rows * sizeof(char *));
        for ( j = 0; j < rows; j++) {
            matrix[j] = malloc(columns * sizeof(char));
        }
    
    
        int i = 0;
        int k,l;
        for ( k = 0; k < rows; k++) {
            for ( l = 0; l < columns; l++) {
                if (i<n) {
                    matrix[k][l] = line[i++];
                } else {
                    matrix[k][l] = '-'; // fill letter
                }
                //putchar(matrix[k][l]);
            }
            //putchar('\n');
        }
        
        
        return matrix;
    }
    
    
    // swap columns i and j of the given matrix, zero-based indices
    void swap_matrix_columns(char **matrix, int rows, int columns, int i, int j) {
        int k;
        for ( k = 0; k < rows; k++) {
            char tmp = matrix[k][i];
            matrix[k][i] = matrix[k][j];
            matrix[k][j] = tmp;
        }    
    
    
    }
    
    
    // print matrix to stdout
    void print_matrix(char **matrix, int rows, int columns) {
        int i,j;
        for (i = 0; i < rows; i++) {
            printf("Row %2d: ", i);
                for (j = 0; j < columns; j++) {
                    if (matrix[i][j] == ' ') {
                        putchar('-');
                    } else {
                        putchar(matrix[i][j]);
                    }
                }
                putchar('\n');
        }
        
    }
    
    
    
    
    // sort key and transpose matrox columns according new order
    void encrypt(char **matrix, int rows, int columns, char *key) {
        char sorted_key[strlen(key)];
        strcpy(sorted_key, key);
        sort_letters(sorted_key);
        printf("Sorted key: %s  (length: %2zu)\n", sorted_key, strlen(sorted_key));
    
    
        bool is_used[columns];
        int i;
        for ( i = 0; i < columns; i++) is_used[i]= false;
    
    
        for ( i = 0; i < columns; i++) {
            if (!is_used[i]) {
                // find new position, must exist
                int j;
                for (j = 0; j < columns; j++) {
                    if (key[i] == sorted_key[j] && !is_used[j]) {
                        break;
                    }
                }
                swap_matrix_columns(matrix, rows, columns, i, j);
                is_used[i] = true;
                is_used[j] = true;
            }
        }
    }
    
    
    int main(){
        char key[50];
        char line[256];
        
        printf("Enter your string: ");
        if (fgets(line, sizeof line, stdin) == NULL) {
            fprintf(stderr, "No line read\n");
            exit(EXIT_FAILURE);
        }
        
        printf("Enter your key: ");
        if (fgets(key, sizeof key, stdin) == NULL) {
            fprintf(stderr, "No line read\n");
            exit(EXIT_FAILURE);
        }
        
        int len = strlen(line);
        if (len && line[len - 1] == '\n') {
            line[--len] = '\0';
        }
            
        int len1 = strlen(key);
        if (len1 && key[len1 - 1] == '\n') {
            key[--len1]= '\0';
        }
    
    
        //printf("string: |%s|  (length: %2zu)\n", line, strlen(line));
        //printf("key:    |%s|  (length: %2zu)\n", key, strlen(key));
            
        char **matrix = gridStr(line, key);
    
    
        int columns = len1;
        // Use simple trick (+ len1 - 1) to determine number of rows with one integer divison
        int rows = (len + columns - 1) / columns;
    
    
        print_matrix(matrix, rows, columns);
        encrypt(matrix, rows, columns, key);
        print_matrix(matrix, rows, columns);
        int i,j;
           for(i=0; i<columns; i++) {
            for(j=0;j<rows;j++) {
                    printf("%s", matrix[i][j]);
        int row;
        for ( row = 0; row < rows; row++) {
            free(matrix[row]);
        }
        free(matrix);
    
    
        
    }
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,126
    > char sorted_key[strlen(key)];
    This should be
    char sorted_key[strlen(key)+1];

    You need the +1 for the \0 at the end of the string.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2022
    Posts
    18

    Still not working

    As you can see below some elements are not in the matrix and there is a big gap.

    adwa — ImgBB

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,376
    What do you get for phrase "one two three four five" and key "king"?
    A long time ago being crazy meant something. - Charles Manson

  5. #5
    Registered User
    Join Date
    May 2022
    Posts
    18

    What do you get for phrase "one two three four five" and key "king"?

    I get eorf enwh rvotteui which is correct. However if I add an "s" to that key I will get "e erenoeuvowroi thff-" instead of " t noeuvowroie erethff"

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,376
    If you consider it "correct" to get an 18 character output from a 23 character input then I can't help you.
    Maybe post your real code since the garbage you posted above doesn't even compile.

    At any rate, your basic algorithm of swapping individual columns is flawed. If it was correct then shouldn't this modified code yield the sorted key string? The only change is that it "sorts" a copy of the key string by making the same swaps as your column swaps.
    Code:
    void encrypt(char **matrix, int rows, int columns, char *key) {
        char sorted_key[strlen(key) + 1];
        strcpy(sorted_key, key);
        sort_letters(sorted_key);
        printf("Sorted key: %s  (length: %2zu)\n", sorted_key, strlen(sorted_key));
     
        bool is_used[columns];
        int i;
        for ( i = 0; i < columns; i++) is_used[i]= false;
     
        char x[columns + 1];
        strcpy(x, key);
     
        for ( i = 0; i < columns; i++) {
            if (!is_used[i]) {
                // find new position, must exist
                int j;
                for (j = 0; j < columns; j++) {
                    if (key[i] == sorted_key[j] && !is_used[j]) {
                        break;
                    }
                }
                swap_matrix_columns(matrix, rows, columns, i, j);
                is_used[i] = true;
                is_used[j] = true;
     
                char t = x[i]; x[i] = x[j]; x[j] = t;
            }
        }
     
        printf("Sorted key??? <%s>\n", x);
    }
    Last edited by john.c; 2 Weeks Ago at 11:17 AM.
    A long time ago being crazy meant something. - Charles Manson

  7. #7
    Registered User
    Join Date
    May 2022
    Posts
    18

    I see you are indeed correct.

    I realise the mistake you are speaking about. The code doen't swap the outer column. With the string "one two three four five" and key king the output should be " eofnwh rvotteuieorf e" not what I said earlier. Here is an image of what happens.

    code — ImgBB

    I fixed the code so it will compile better now.

    insert
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    
    
    
    // use bubble sort to sort letters in a key
    void sort_letters(char *phrase) {
        int i,j;
        int n = strlen(phrase);
        //printf("The string to sort is: %s\n", phrase);
        for ( i = 0; i < n-1; i++) {
            for ( j = i+1; j < n; j++) {
                if (phrase[i] > phrase[j]) {
                        char temp = phrase[i];
                        phrase[i] = phrase[j];
                        phrase[j] = temp;
                }
            }
        }
        //printf("The sorted string is:  %s\n", phrase);
    }
    
    
    
    
    // allocate a matrix for string and fill it
    char** gridStr(char *line, char *key)
    {
        int n = strlen(line);    
        int columns = strlen(key);
        int rows = (n + columns - 1) / columns;
        int j;
        char **matrix = malloc(rows * sizeof(char *));
        for ( j = 0; j < rows; j++) {
            matrix[j] = malloc(columns * sizeof(char));
        }
    
    
    
    
        int i = 0;
        int k,l;
        for ( k = 0; k < rows; k++) {
            for ( l = 0; l < columns; l++) {
                if (i<n) {
                    matrix[k][l] = line[i++];
                } else {
                    matrix[k][l] = '-'; // fill letter
                }
                //putchar(matrix[k][l]);
            }
            //putchar('\n');
        }
        
        
        return matrix;
    }
    
    
    
    
    // swap columns i and j of the given matrix, zero-based indices
    void swap_matrix_columns(char **matrix, int rows, int columns, int i, int j) {
        int k;
        for ( k = 0; k < rows; k++) {
            char tmp = matrix[k][i];
            matrix[k][i] = matrix[k][j];
            matrix[k][j] = tmp;
        }    
    
    
    
    
    }
    
    
    
    
    // print matrix to stdout
    void print_matrix(char **matrix, int rows, int columns) {
        int i,j;
        for (i = 0; i < rows; i++) {
            printf("Row %2d: ", i);
                for (j = 0; j < columns; j++) {
                    if (matrix[i][j] == ' ') {
                        putchar('-');
                    } else {
                        putchar(matrix[i][j]);
                    }
                }
                putchar('\n');
        }
        
    }
    
    
    
    
    
    
    
    
    // sort key and transpose matrox columns according new order
    void encrypt(char **matrix, int rows, int columns, char *key) {
        char sorted_key[strlen(key)];
        strcpy(sorted_key, key);
        sort_letters(sorted_key);
        printf("Sorted key: %s  (length: %2zu)\n", sorted_key, strlen(sorted_key));
    
    
    
    
        bool is_used[columns];
        int i;
        for ( i = 0; i < columns; i++) is_used[i]= false;
    
    
    
    
        for ( i = 0; i < columns; i++) {
            if (!is_used[i]) {
                // find new position, must exist
                int j;
                for (j = 0; j < columns; j++) {
                    if (key[i] == sorted_key[j] && !is_used[j]) {
                        break;
                    }
                }
                swap_matrix_columns(matrix, rows, columns, i, j);
                is_used[i] = true;
                is_used[j] = true;
            }
        }
    }
    
    
    
    
    int main(){
        char key[50];
        char line[256];
        
        printf("Enter your string: ");
        if (fgets(line, sizeof line, stdin) == NULL) {
            fprintf(stderr, "No line read\n");
            exit(EXIT_FAILURE);
        }
        
        printf("Enter your key: ");
        if (fgets(key, sizeof key, stdin) == NULL) {
            fprintf(stderr, "No line read\n");
            exit(EXIT_FAILURE);
        }
        
        int len = strlen(line);
        if (len && line[len - 1] == '\n') {
            line[--len] = '\0';
        }
            
        int len1 = strlen(key);
        if (len1 && key[len1 - 1] == '\n') {
            key[--len1]= '\0';
        }
    
    
    
    
        //printf("string: |%s|  (length: %2zu)\n", line, strlen(line));
        //printf("key:    |%s|  (length: %2zu)\n", key, strlen(key));
            
        char **matrix = gridStr(line, key);
    
    
    
    
        int columns = len1;
        // Use simple trick (+ len1 - 1) to determine number of rows with one integer divison
        int rows = (len + columns - 1) / columns;
    
    
    
    
        print_matrix(matrix, rows, columns);
        encrypt(matrix, rows, columns, key);
        print_matrix(matrix, rows, columns);
        int i,j;
      
        int row;
        for ( row = 0; row < rows; row++) {
            free(matrix[row]);
        }
        free(matrix);
    
    
    
    
        
    }

  8. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    1,376
    It looks like all you might need to do is remove the line:
    Code:
    is_used[i] = true;
    Also, when printing the string, remember that the row index comes first:
    Code:
    for (int c = 0; c < columns; ++c)
        for (int r = 0; r < rows; ++r)
            putchar(matrix[r][c]); // row must be the first index
    putchar('\n');
    A long time ago being crazy meant something. - Charles Manson

  9. #9
    Registered User
    Join Date
    May 2022
    Posts
    18

    So I'm trying to do the opposite of what I did earlier

    Here's my code. It basically reverses everything by using the key and jumbled text. Again it won't put a whole column into the matrix. I also took out this part is_used[j] = true;

    insert
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    
    // use bubble sort to sort letters in a key
    void sort_letters(char *phrase) {
    	int i,j;
        int n = strlen(phrase);
        //printf("The string to sort is: %s\n", phrase);
        for ( i = 0; i < n-1; i++) {
            for ( j = i+1; j < n; j++) {
                if (phrase[i] > phrase[j]) {
                        char temp = phrase[i];
                        phrase[i] = phrase[j];
                        phrase[j] = temp;
                }
            }
        }
        //printf("The sorted string is:  %s\n", phrase);
    }
    
    
    // allocate a matrix for string and fill it
    char** gridStr(char *line, char *key)
    {
        int n = strlen(line);    
        int columns = strlen(key);
        int rows = (n + columns - 1) / columns;
    	int j;
        char **matrix = malloc(rows * sizeof(char *));
        for ( j = 0; j < rows; j++) {
            matrix[j] = malloc(columns * sizeof(char));
        }
    
    
        int i = 0;
        int k,l;
        for ( l = 0; l < columns; l++) {
        	for ( k = 0; k < rows; k++) {
                if (i<n) {
                    matrix[k][l] = line[i++];
                } else {
                    matrix[k][l] = '-'; // fill letter
                }
                //putchar(matrix[k][l]);
            }
            //putchar('\n');
        }
        
        
        return matrix;
    }
    
    
    // swap columns i and j of the given matrix, zero-based indices
    void swap_matrix_columns(char **matrix, int rows, int columns, int i, int j) {
    	int k;
        for ( k = 0; k < rows; k++) {
            char tmp = matrix[k][i];
            matrix[k][i] = matrix[k][j];
            matrix[k][j] = tmp;
        }    
    
    
    }
    
    
    // print matrix to stdout
    void print_matrix1(char **matrix, int rows, int columns) {
    	int i,j;
        for (i = 0; i < rows; i++) {
        	printf("Row %2d: ", i);
    	        for (j = 0; j < columns; j++) {
    	            if (matrix[i][j] == ' ') {
    	                putchar('_');
    	            } else {
    	                putchar(matrix[i][j]);
    	            }
    	        }
    	        putchar('\n');
    	}
        for(i=0; i<rows; i++) {
        	 for(j=0;j<columns;j++) {
                    printf("%c", matrix[i][j]);
    }
    }
    }
    
    
    // sort key and transpose matrox columns according new order
    void decrypt(char **matrix, int rows, int columns, char *key) {
        char sorted_key[strlen(key)+1];
        strcpy(sorted_key, key);
        sort_letters(sorted_key);
        printf("Sorted key: %s  (length: %2zu)\n", sorted_key, strlen(sorted_key));
    
    
        bool is_used[columns];
        int i;
        for ( i = 0; i < columns; i++) is_used[i]= false;
    
    
        for ( i = 0; i < columns; i++) {
            if (!is_used[i]) {
                // find new position, must exist
                int j;
                for (j = 0; j < columns; j++) {
                    if (key[i] == sorted_key[j] && !is_used[j]) {
                        break;
                    }
                }
                swap_matrix_columns(matrix, rows, columns, i, j);
                is_used[i] = true;
                //is_used[j] = true;
            }
        }
    }
    
    
    int main(void) {
        char key[50];
        char line[256];
        
        printf("Enter your string: ");
        if (fgets(line, sizeof line, stdin) == NULL) {
            fprintf(stderr, "No line read\n");
            exit(EXIT_FAILURE);
        }
        
        printf("Enter your key: ");
        if (fgets(key, sizeof key, stdin) == NULL) {
            fprintf(stderr, "No line read\n");
            exit(EXIT_FAILURE);
        }
        
        int len = strlen(line);
        if (len && line[len - 1] == '\n') {
            line[--len] = '\0';
        }
            
        int len1 = strlen(key);
        if (len1 && key[len1 - 1] == '\n') {
            key[--len1]= '\0';
        }
    
    
        //printf("string: |%s|  (length: %2zu)\n", line, strlen(line));
        //printf("key:    |%s|  (length: %2zu)\n", key, strlen(key));
            
        char **matrix = gridStr(line, key);
    
    
        int columns = len1;
        // Use simple trick (+ len1 - 1) to determine number of rows with one integer divison
        int rows = (len + columns - 1) / columns;
    
    
        //print_matrix1(matrix, rows, columns);
        decrypt(matrix, rows, columns, key);
        print_matrix1(matrix, rows, columns);
    	int i;
    	
    	int row;
        for ( row = 0; row < rows; row++) {
            free(matrix[row]);
        }
        free(matrix);
    
    
        return EXIT_SUCCESS;
    }

  10. #10
    Registered User
    Join Date
    Dec 2017
    Posts
    1,376
    It turns out that encrypt doesn't work properly anyway.
    It's up to you to test it with many inputs, not just a couple.
    The input "ebfacd" doesn't work.
    Sorted it's "abcdef", but the result here is "abdcef".
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdbool.h>
     
    #define MAX_KEY 50
     
    void sort(char *s) {
        int n = strlen(s);
        for (int i = 0; i < n - 1; ++i)
            for (int j = i + 1; j < n; ++j)
                if (s[i] > s[j]) {
                    char t = s[i]; s[i] = s[j]; s[j] = t;
                }
    }
     
    void encrypt(const char *key, int columns) {
        char sorted_key[MAX_KEY];
        strcpy(sorted_key, key);
        sort(sorted_key);
     
        printf("Key   : <%s>\n", key);
        printf("Sorted: <%s>\n", sorted_key);
     
        bool is_used[MAX_KEY] = {false};
     
        char x[MAX_KEY];
        strcpy(x, key);
     
        for (int i = 0; i < columns; i++) {
            if (!is_used[i]) {
                int j = 0;
                for ( ; j < columns; j++)
                    if (key[i] == sorted_key[j] && !is_used[j])
                        break;
                is_used[j] = true;
                char t = x[i]; x[i] = x[j]; x[j] = t;
            }
        }
     
        printf("Result: <%s>\n", x);
    }
     
    int main() {
        char key[MAX_KEY] = "ebfacd";
        encrypt(key, strlen(key));
        return 0;
    }
    A long time ago being crazy meant something. - Charles Manson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 04-28-2017, 01:21 PM
  2. Replies: 4
    Last Post: 02-25-2016, 08:49 AM
  3. Working with LZW data compression algorithm
    By husslela2 in forum C Programming
    Replies: 3
    Last Post: 07-01-2010, 09:23 AM
  4. Replies: 9
    Last Post: 03-30-2009, 04:09 AM
  5. algorithm not working like i want it to
    By Panopticon in forum C++ Programming
    Replies: 3
    Last Post: 01-01-2003, 04:57 PM

Tags for this Thread