B
Big Tony
Hi
I decided this afternoon that it was time I learned a bit of C and to
set me going had a stab at the 'bitflip' sample problem from the
topCoder website. This requires the program to calculate the minimum
number of flips of sections of a binary string necessary to convert
the string to all zeros.
My code for this problem is posted below - but it doesn't quite work!
It appears that if more than 4 flips are required, the strncpy
function (called in the function flip and used to copy the leading
zeros) copies the whole string rather than just the leading portion of
p1-1 characters. So it succeeds for an input string eg 01010, but
fails for eg 01010101010. Can anyone shed some light onto why this
might be? It seems to work fine for the first couple of calls to flip.
I'm not used to pointers, so is it a problem with the way I'm
referencing the memory?
Also feel free to point out any further inadequacies in my program,
including more efficient ways of doing this (I don't have a C book
(yet) and am just querying google for the functions I need to get the
job done).
Thanks in advance
BT
-----------------> My Code
/* TopCoder sample problem.
for info see bitflip.info */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main() {
char string[100]; /* A string of 1s and 0s */
int getone(char *str, int fl); /* function */
int flip(char *str, int p1, int p2, int len); /* prototypes */
int p1,p2,len,flips; /* p1 position of first 1 in string */
/* p2 position of last 1 in string */
/* len length of string */
/* flips no. of bit flips performed */
printf("Enter your bit string:");
scanf("%s", string);
len=strlen(string);
flips=0;
while(p1!=p2){ /* more than one 1 in string */
p1=getone(string, 1);
p2=getone(string, -1);
flips=flips+p2-p1+1;
if (p1!=p2) {flip(string, p1, p2, len);} /* flip bits between
p1&p2 */
if (p1==0) {flips=flips-1;} /* We've already flipped
everything */
if (p1==p2 && p1!=0) { /* Only one 1 left to
flip */
printf("Finally flipping bit %d\n",p1);}
if (flips >100) {/* Don't go too far */
printf("Too many flips!\n"); exit(1);}
}
printf("Total flips=%d\n", flips);
return 0;
}
int getone(char *str, int fl){ /* Function to find the first 1 */
/* in a string if fl=1 or the */
/* last 1 in a string if fl=-1 */
char bitc[1]; /* a character in the string */
int pos, bit, j, len; /* pos position of 1 in string */
/* bit bit in string */
/* loop counter */
/* len length of the string */
j=1;
len=strlen(str);
if (fl==-1) {j=len;}
bit=0;
pos=0;
while (bit==0 && j<=len+1 && j>=0){/* search thro string for a 1
*/
memcpy(bitc,str+j-1,1);
bit=atoi(bitc);
j=j+fl;
}
pos=j-fl;
if (pos>len) {pos=0;} /* If we get to the end of the string
without */
return pos; /* finding a 1 then return 0 */
}
int flip(char *str, int p1, int p2, int len){
char bitc[2], bitc1[2]; /* characters to store the bits and */
char *str2; /* the new string */
int i, bit, retVal;
int static k=0; /* number of times function is called
*/
k++; /* (for debugging purposes) */
printf("flipping bits %d to %d",p1,p2);
str2=(char*)malloc(len); /* Allocate memory to new string */
strncpy(str2,str,p1-1); /* copy leading zeros to new string */
printf("\n%s %d\n", str2,p1-1); /* debugging */
for (i=p1;i<=p2;i++){ /* flip the bits of the original string */
/* between p1 & p2 and add these to */
/* the new string */
memcpy(bitc1, str+i-1,1); /* copy character in str to bitc1
*/
bit=1-atoi(bitc1); /* flip it */
retVal=snprintf(bitc,2,"%d",bit); /* write flipped bit to
bitc */
strncat(str2,bitc,1); /* add bitc to end of new string */
printf("%s\n", str2); /* debugging */
}
for (i=p2+1;i<=len;i++){/* add trailing zeros to new string */
strncat(str2,"0",1);
}
memcpy(str,str2,len); /* copy new string to original string */
free(str2); /* free memory */
printf(".....new string=%s\n",str);
if (k>3){exit(1);} /* debugging */
return 0;
}
/* Compiled with: gcc -Wall bitflip.c -o bitflip */
I decided this afternoon that it was time I learned a bit of C and to
set me going had a stab at the 'bitflip' sample problem from the
topCoder website. This requires the program to calculate the minimum
number of flips of sections of a binary string necessary to convert
the string to all zeros.
My code for this problem is posted below - but it doesn't quite work!
It appears that if more than 4 flips are required, the strncpy
function (called in the function flip and used to copy the leading
zeros) copies the whole string rather than just the leading portion of
p1-1 characters. So it succeeds for an input string eg 01010, but
fails for eg 01010101010. Can anyone shed some light onto why this
might be? It seems to work fine for the first couple of calls to flip.
I'm not used to pointers, so is it a problem with the way I'm
referencing the memory?
Also feel free to point out any further inadequacies in my program,
including more efficient ways of doing this (I don't have a C book
(yet) and am just querying google for the functions I need to get the
job done).
Thanks in advance
BT
-----------------> My Code
/* TopCoder sample problem.
for info see bitflip.info */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main() {
char string[100]; /* A string of 1s and 0s */
int getone(char *str, int fl); /* function */
int flip(char *str, int p1, int p2, int len); /* prototypes */
int p1,p2,len,flips; /* p1 position of first 1 in string */
/* p2 position of last 1 in string */
/* len length of string */
/* flips no. of bit flips performed */
printf("Enter your bit string:");
scanf("%s", string);
len=strlen(string);
flips=0;
while(p1!=p2){ /* more than one 1 in string */
p1=getone(string, 1);
p2=getone(string, -1);
flips=flips+p2-p1+1;
if (p1!=p2) {flip(string, p1, p2, len);} /* flip bits between
p1&p2 */
if (p1==0) {flips=flips-1;} /* We've already flipped
everything */
if (p1==p2 && p1!=0) { /* Only one 1 left to
flip */
printf("Finally flipping bit %d\n",p1);}
if (flips >100) {/* Don't go too far */
printf("Too many flips!\n"); exit(1);}
}
printf("Total flips=%d\n", flips);
return 0;
}
int getone(char *str, int fl){ /* Function to find the first 1 */
/* in a string if fl=1 or the */
/* last 1 in a string if fl=-1 */
char bitc[1]; /* a character in the string */
int pos, bit, j, len; /* pos position of 1 in string */
/* bit bit in string */
/* loop counter */
/* len length of the string */
j=1;
len=strlen(str);
if (fl==-1) {j=len;}
bit=0;
pos=0;
while (bit==0 && j<=len+1 && j>=0){/* search thro string for a 1
*/
memcpy(bitc,str+j-1,1);
bit=atoi(bitc);
j=j+fl;
}
pos=j-fl;
if (pos>len) {pos=0;} /* If we get to the end of the string
without */
return pos; /* finding a 1 then return 0 */
}
int flip(char *str, int p1, int p2, int len){
char bitc[2], bitc1[2]; /* characters to store the bits and */
char *str2; /* the new string */
int i, bit, retVal;
int static k=0; /* number of times function is called
*/
k++; /* (for debugging purposes) */
printf("flipping bits %d to %d",p1,p2);
str2=(char*)malloc(len); /* Allocate memory to new string */
strncpy(str2,str,p1-1); /* copy leading zeros to new string */
printf("\n%s %d\n", str2,p1-1); /* debugging */
for (i=p1;i<=p2;i++){ /* flip the bits of the original string */
/* between p1 & p2 and add these to */
/* the new string */
memcpy(bitc1, str+i-1,1); /* copy character in str to bitc1
*/
bit=1-atoi(bitc1); /* flip it */
retVal=snprintf(bitc,2,"%d",bit); /* write flipped bit to
bitc */
strncat(str2,bitc,1); /* add bitc to end of new string */
printf("%s\n", str2); /* debugging */
}
for (i=p2+1;i<=len;i++){/* add trailing zeros to new string */
strncat(str2,"0",1);
}
memcpy(str,str2,len); /* copy new string to original string */
free(str2); /* free memory */
printf(".....new string=%s\n",str);
if (k>3){exit(1);} /* debugging */
return 0;
}
/* Compiled with: gcc -Wall bitflip.c -o bitflip */