J
jay
PROBLEM: You are given a string FOOFIGHTERS. You have to come up with an algorithm that will compress this string. You also have to make sure that youare not using extra memory. For example: FOOFIGHTERS will be compressed asFO2FIGHTERS. You should not use another array or bitfield to keep a frequency count for the individual letters.
WHAT I DID: coded it in C. It is working fine.
WHAT I WANT from c.l.c: This is written purely to learn C. This is not home work and I am not getting any interview calls since an year
. I wroteit because I wanted to know C better
Is the C code written here is of good quality as per c.l.c standard ?
Can more improvements be done ?
Did I miss any C library which could solve my task in a better way ?
do you see any hidden bugs there ?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { MAXNUMSZ = 100 };
void get_string(char** pp, const char* t);
void add_num(char* s, const size_t begin, const size_t cnt, size_t* end);
void convert_num_to_str(char* p, const size_t num);
void add_count_to_str(char* s, const char* snum, size_t* begin, size_t* end);
void move_elements(char* s, size_t begin, size_t end);
void compress_string(char* str, const size_t sz);
int main(int argc, char* argv[])
{
size_t sz = 0;
char* p = NULL;
if(2 != argc)
{
printf("Please provide one argument\n");
exit(EXIT_FAILURE);
}
sz = strlen(argv[1]) + 1;
get_string(&p, argv[1]);
printf("You entered: [%s]\n", p);
compress_string(p, sz);
printf("Result = [%s]\n", p);
free(p);
return 0;
}
void get_string(char** pp, const char* t)
{
size_t len;
char* mp;
len = strlen(t) + 1;
mp = malloc(len * (sizeof *mp));
if(NULL == mp)
{
printf("IN: %s @ %d: Out of Memory\n", __FILE__, __LINE__);
*pp = NULL;
exit(EXIT_FAILURE);
}
*pp = mp;
strcpy(*pp, t);
}
void compress_string(char* str, const size_t sz)
{
size_t bidx = 0;
size_t idx = 0;
size_t cnt = 0;
char prev = '\0';
char c = '\0';
for(idx = 0; idx < sz; ++idx)
{
c = str[idx];
/* printf("c = [%c], prev = [%c]\n", c, prev); */
if(c == prev)
{
++cnt;
}
else if(cnt > 1)
{
add_num(str, bidx, cnt, &idx);
printf("Array = %s\n", str);
printf("New Index = %u\n\n", idx);
--idx; /* for loop will increment it anyhow */
cnt = 0;
}
else
{
prev = c;
cnt = 1;
bidx = idx;
}
}
}
void add_num(char* s, const size_t begin, const size_t cnt, size_t* end)
{
char strnum[MAXNUMSZ+1] = {0};
size_t bidx = begin;
size_t eidx = *end;
printf("Repitition begins at [%u] = %c, ends = %u\n", begin, s[begin],*end);
convert_num_to_str(strnum, cnt);
printf("String to add = %s\n", strnum);
add_count_to_str(s, strnum, &bidx, &eidx);
move_elements(s, bidx, *end);
*end = eidx;
}
void move_elements(char* s, size_t begin, size_t end)
{
for(; s[end]; ++end)
{
s[begin++] = s[end];
}
s[begin] = '\0';
}
void add_count_to_str(char* s, const char* snum, size_t* begin, size_t* end)
{
(*begin)++;
for(;*snum; ++snum)
{
s[(*begin)++] = *snum;
}
/* reset the index */
*end = *begin;
}
void convert_num_to_str(char* p, const size_t num)
{
int ret = 0;
ret = sprintf(p, "%u", num);
if(0 > ret)
{
printf("IN: %s @%d: SPRINTF() ERROR\n", __FILE__, __LINE__);
exit(EXIT_FAILURE);
}
}
=============== OUTPUT =============
[myhome]$ gcc -ansi -pedantic -Wall -Wextra compress.c
[myhome]$ ./a.out bbfqqqRRRRtLL
You entered: [bbfqqqRRRRtLL]
Repetition begins at [0] = b, ends = 2
String to add = 2
Array = b2fqqqRRRRtLL
New Index = 2
Repetition begins at [3] = q, ends = 6
String to add = 3
Array = b2fq3RRRRtLL
New Index = 5
Repetition begins at [5] = R, ends = 9
String to add = 4
Array = b2fq3R4tLL
New Index = 7
Repetition begins at [8] = L, ends = 10
String to add = 2
Array = b2fq3R4tL2
New Index = 10
Result = [b2fq3R4tL2]
WHAT I DID: coded it in C. It is working fine.
WHAT I WANT from c.l.c: This is written purely to learn C. This is not home work and I am not getting any interview calls since an year
. I wroteit because I wanted to know C better Is the C code written here is of good quality as per c.l.c standard ?
Can more improvements be done ?
Did I miss any C library which could solve my task in a better way ?
do you see any hidden bugs there ?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { MAXNUMSZ = 100 };
void get_string(char** pp, const char* t);
void add_num(char* s, const size_t begin, const size_t cnt, size_t* end);
void convert_num_to_str(char* p, const size_t num);
void add_count_to_str(char* s, const char* snum, size_t* begin, size_t* end);
void move_elements(char* s, size_t begin, size_t end);
void compress_string(char* str, const size_t sz);
int main(int argc, char* argv[])
{
size_t sz = 0;
char* p = NULL;
if(2 != argc)
{
printf("Please provide one argument\n");
exit(EXIT_FAILURE);
}
sz = strlen(argv[1]) + 1;
get_string(&p, argv[1]);
printf("You entered: [%s]\n", p);
compress_string(p, sz);
printf("Result = [%s]\n", p);
free(p);
return 0;
}
void get_string(char** pp, const char* t)
{
size_t len;
char* mp;
len = strlen(t) + 1;
mp = malloc(len * (sizeof *mp));
if(NULL == mp)
{
printf("IN: %s @ %d: Out of Memory\n", __FILE__, __LINE__);
*pp = NULL;
exit(EXIT_FAILURE);
}
*pp = mp;
strcpy(*pp, t);
}
void compress_string(char* str, const size_t sz)
{
size_t bidx = 0;
size_t idx = 0;
size_t cnt = 0;
char prev = '\0';
char c = '\0';
for(idx = 0; idx < sz; ++idx)
{
c = str[idx];
/* printf("c = [%c], prev = [%c]\n", c, prev); */
if(c == prev)
{
++cnt;
}
else if(cnt > 1)
{
add_num(str, bidx, cnt, &idx);
printf("Array = %s\n", str);
printf("New Index = %u\n\n", idx);
--idx; /* for loop will increment it anyhow */
cnt = 0;
}
else
{
prev = c;
cnt = 1;
bidx = idx;
}
}
}
void add_num(char* s, const size_t begin, const size_t cnt, size_t* end)
{
char strnum[MAXNUMSZ+1] = {0};
size_t bidx = begin;
size_t eidx = *end;
printf("Repitition begins at [%u] = %c, ends = %u\n", begin, s[begin],*end);
convert_num_to_str(strnum, cnt);
printf("String to add = %s\n", strnum);
add_count_to_str(s, strnum, &bidx, &eidx);
move_elements(s, bidx, *end);
*end = eidx;
}
void move_elements(char* s, size_t begin, size_t end)
{
for(; s[end]; ++end)
{
s[begin++] = s[end];
}
s[begin] = '\0';
}
void add_count_to_str(char* s, const char* snum, size_t* begin, size_t* end)
{
(*begin)++;
for(;*snum; ++snum)
{
s[(*begin)++] = *snum;
}
/* reset the index */
*end = *begin;
}
void convert_num_to_str(char* p, const size_t num)
{
int ret = 0;
ret = sprintf(p, "%u", num);
if(0 > ret)
{
printf("IN: %s @%d: SPRINTF() ERROR\n", __FILE__, __LINE__);
exit(EXIT_FAILURE);
}
}
=============== OUTPUT =============
[myhome]$ gcc -ansi -pedantic -Wall -Wextra compress.c
[myhome]$ ./a.out bbfqqqRRRRtLL
You entered: [bbfqqqRRRRtLL]
Repetition begins at [0] = b, ends = 2
String to add = 2
Array = b2fqqqRRRRtLL
New Index = 2
Repetition begins at [3] = q, ends = 6
String to add = 3
Array = b2fq3RRRRtLL
New Index = 5
Repetition begins at [5] = R, ends = 9
String to add = 4
Array = b2fq3R4tLL
New Index = 7
Repetition begins at [8] = L, ends = 10
String to add = 2
Array = b2fq3R4tL2
New Index = 10
Result = [b2fq3R4tL2]