@raghavan : please read previous post...given m/m is fixed which is sufficient enough to accommodate input. so if input string is a1b1c4 then max buffer available to us is 1+1+4=7 , 7+1=8(+1 is for '\0' at the end) but 8 is also length of the input.
so to make your algo work first you need to further squeeze the input before starting expanding. On Sun, Mar 25, 2012 at 1:02 PM, raghavan M <[email protected]>wrote: > Atul > '1' is a special case for this RLE.Instead of copying back you have to > copy front > > a1b2c1d4e5 > Step 1: expand e 5 times a1b2c1d4eeeee > Step 2: expand 'd' 4 times.before that shift 5e's by 4 right side. > a1b2c1ddddeeeeee > step 3: here since 1 is a special case shift 'ddddeeeeee' left side by 1 > .... > > > > > ------------------------------ > *From:* atul anand <[email protected]> > *To:* [email protected] > *Sent:* Saturday, 24 March 2012 4:32 PM > > *Subject:* Re: [algogeeks] Re: Run Length Decoding... inplace > > @raghavan: wont work...take input as a1b1c4...it willl fail. > read prev comment ... > On 24 Mar 2012 14:23, "raghavan M" <[email protected]> wrote: > > For sake of in-place > > Instead of doing it from the "Start" we can do it from the "end" in which > case, the data precision wont be lost. > > Eg: > a1b2c3d4 > start with d4 > a1b2c3dddd > now in next loop > a1b2cccdddd- here we have to do a)reallocation and b)copy the last 3 dddd > from next one it is more swaps :D i hope it can be optimised by some > way. > > not sure though. > > > ------------------------------ > *From:* Ashish Goel <[email protected]> > *To:* [email protected] > *Sent:* Saturday, 24 March 2012 1:19 AM > *Subject:* Re: [algogeeks] Re: Run Length Decoding... inplace > > Atul > > > > a10 looks good however, when there are multiple such cases within the same > string, it is is a problem because i would not know if the char is the real > character of the string or part ofthe length > > eg > > a10115 > is a valid string and can be interpreted as a011111 or a 10115 times. > RLE is the first case not the second case which is pretty easy to take > care. > > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Fri, Mar 23, 2012 at 11:39 PM, atul anand <[email protected]>wrote: > > @utkarsh: +1 > On 23 Mar 2012 18:38, "UTKARSH SRIVASTAV" <[email protected]> wrote: > > I am considering that I am having total size of buffer that is maximum of > output or input buffer and input is given in the buffer. > > My first approach of the solution was that > 1. first traverse whole array and then count total number of characters > that will be present in whole array. O(n) > 2. fill the output array from rightmost side and start filling it until > you reach 0th index. O(n) > > But it failed on this test case a1b1c4 here I could lost data b1 once I > start filling character from right side.It faile because of characters > whose count is 1. > > So I think just a change in algo will give me correct answer. > 1. first traverse whole array and then count total number of characters > that will be present in whole array and in case if the character count is 1 > place '\0' in place of 1. O(n) > 2. imagining \0 as space .convert this problem to removing white space > from strings and compress it . Again can be done in O(n). > 3. fill the output array from rightmost side and start filling it until > you reach 0th index. O(n) > > Please correct me if I am wrong. > > > > On Thu, Mar 22, 2012 at 9:13 AM, atul anand <[email protected]>wrote: > > @Ashish : a10 will be represented as aaaaaaaaaa . Here '1' and '0' are > character type in the given input , so you need to convert it into numeric > 10. > > > On Thu, Mar 22, 2012 at 1:09 AM, Ashish Goel <[email protected]> wrote: > > Gene, Atul > > How would a string of say 257 or say 10 times a would be represented, will > it be a10 or a<ascii of 10> > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Wed, Mar 21, 2012 at 2:04 PM, atul anand <[email protected]>wrote: > > wasnt able to come up with an algo which would satisfy all the cases input > like a1b1c4 here output length is equal to input length . till now i dont > knw how to handle these type of input. :( :( > > On Wed, Mar 21, 2012 at 10:02 AM, atul anand <[email protected]>wrote: > > @Gene : yes you are right , i misunderstood the problem . so m/m available > is just enough to hold the output. > thanks for correcting ... that would make this ques little interesting :) > :)...i guess my first posted code can be modified to meet the requirement. > i will post the updated code. > > On Tue, Mar 20, 2012 at 5:45 PM, Gene <[email protected]> wrote: > > I don't think you're seeing the requirement completely. The problem > promises only that the output buffer will be big enough to hold the > output. You have made it huge. I tried your code on an input of > > a1b1c6 > > with the required output space of 8 characters (plus 1 for the C null > character), and it printed > > cccccc > > and stopped. > > Last night I realized there is another approach that will work in all > cases, so I deleted my post. I guess it wasn't deleted on the server > in your part of the world. > > You all can certainly work it out. You can't just copy the input to a > predetermined place in the buffer before processing it. It needs to be > placed carefully, and it needs to be processed from both ends to a > certain point in the middle. > > On Mar 20, 7:32 am, atul anand <[email protected]> wrote: > > using Gene logic , but we need to take care of number with more than 1 > > digits , so updated gene's code is as follows :- > > > > #include<stdio.h> > > #define MAX 1000 > > > > int copy(char *str,int len) > > { > > int max_len=MAX-1,i; > > for(i=len-1;i>=0;i--) > > { > > str[max_len]=str[i]; > > max_len--; > > } > > return max_len+1; > > > > } > > > > void runLength(char *str) > > { > > unsigned int j,k=1,loop=0,res_len=0; > > int i,n_start; > > char c; > > /*copying input to the end of the buffer*/ > > n_start=copy(str,strlen(str)); > > > > for(i=MAX-1;i>=n_start;i--) > > { > > if(str[i]>='0' && str[i]<='9') > > { > > continue; > > } > > else > > { > > sscanf(&str[i],"%c%d",&c,&loop); > > for(j=0;j<loop;j++) > > { > > str[res_len]=c; > > res_len++; > > } > > } > > } > > str[res_len]='\0'; > > printf("\nDecoded Msg = %s\n",str); > > > > } > > > > int main() > > { > > char str[MAX]; > > memset(&str,0,MAX); > > printf("\nEnter String = "); > > scanf("%s",str); > > runLength(str); > > > > return 1; > > > > > > > > > > > > > > > > } > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > *UTKARSH SRIVASTAV > CSE-3 > B-Tech 3rd Year > @MNNIT ALLAHABAD* > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
