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 <ashg...@gmail.com>
To: algogeeks@googlegroups.com
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 <atul.87fri...@gmail.com> wrote:
@utkarsh: +1
>On 23 Mar 2012 18:38, "UTKARSH SRIVASTAV" <usrivastav...@gmail.com> 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 <atul.87fri...@gmail.com> 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 <ashg...@gmail.com> 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 <atul.87fri...@gmail.com> 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 <atul.87fri...@gmail.com>
>>>>>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 <gene.ress...@gmail.com> 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 <atul.87fri...@gmail.com> 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 algogeeks@googlegroups.com.
>>>>>>>To unsubscribe from this group, send email to
>>>>>>>algogeeks+unsubscr...@googlegroups.com.
>>>>>>>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 algogeeks@googlegroups.com.
>>>>>To unsubscribe from this group, send email to
>>>>>algogeeks+unsubscr...@googlegroups.com.
>>>>>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 algogeeks@googlegroups.com.
>>>>To unsubscribe from this group, send email to
>>>>algogeeks+unsubscr...@googlegroups.com.
>>>>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 algogeeks@googlegroups.com.
>>>To unsubscribe from this group, send email to
>>>algogeeks+unsubscr...@googlegroups.com.
>>>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 algogeeks@googlegroups.com.
>>To unsubscribe from this group, send email to
>>algogeeks+unsubscr...@googlegroups.com.
>>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 algogeeks@googlegroups.com.
>To unsubscribe from this group, send email to
>algogeeks+unsubscr...@googlegroups.com.
>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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
