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.
