Re: [algogeeks] Re: Run Length Decoding... inplace
Hope this works
http://ideone.com/MCLqO
On Sun, Mar 25, 2012 at 4:37 PM, atul anand atul.87fri...@gmail.com wrote:
@ Kalyanasundaram : no need to check you algo , bcozz i can clearly see
you are not saving output to the bufffer , you are just printing it to
stdout .
please read prev comment for better understanding the problem,
On Sun, Mar 25, 2012 at 11:54 AM, Kalyanasundaram
nks.22.1...@gmail.comwrote:
scanf(%s,a);
l=strlen(a);
for(i=l-1;i=0;i-=2)
{
while((a[i]--)-'0')
printf(%c,a[i-1]);
}
This works fine when the count of characters is a 10 .Also no extra
space used.If you find any mistake, please do correct me!
On Sun, Mar 25, 2012 at 10:18 AM, SAMM somnath.nit...@gmail.com wrote:
In this question is it mandatory to use array here .Because the output
and the space were the string is stored is required ..
I was thinking of using LL approach ..
Need four pointers to keep track of the positions .
begin - store the beginning of the LL initially containing the pointer
to he 1st node a1b2c3d4.
end - store the end node of the input string .
outputbegin - store the position where the output index begin .. It
will be appended to the next node of the input string .
outputend -store the end node of the LL.
begin -- a 1 b 2 c 3 d 4(-end) (outputbegin-) NULL -(outputend)
Delete d4 we hav now:-
begin -- a 1 b 2 c 3 (-end) (outputbegin-) d d d d -(outputend)
Take the character and corresponding value from the end index, change
the end pointer to '3' on the left of d4 , delete both nodes of d4 and
append it characters at the end .. All u have to do is remove and append ,
no extra memory greater than length(output) is used here ..
As Nothing has been mentioned abt printing the output in the question ,
we will keep printing the character on the console while appendiing the
character in the LL ).
--
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.
--
*Kalyan
Dont take life seriously as it isnt Permanent!
*
--
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.
--
Regards
Anurag Atri
III year
Computer Engineering
Delhi College Of Engineering
--
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.
Re: [algogeeks] Re: Run Length Decoding... inplace
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 a1b2c1d4e Step 2: expand 'd' 4 times.before that shift 5e's by 4 right side. a1b2c1ee step 3: here since 1 is a special case shift 'ee' left side by 1 From: atul anand atul.87fri...@gmail.com To: algogeeks@googlegroups.com 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 peacelover1987...@yahoo.co.in 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 a1b2c3 now in next loop a1b2ccc- here we have to do a)reallocation and b)copy the last 3 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 a01 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 aa . 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 aascii 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 cc 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
Re: [algogeeks] Re: Run Length Decoding... inplace
scanf(%s,a);
l=strlen(a);
for(i=l-1;i=0;i-=2)
{
while((a[i]--)-'0')
printf(%c,a[i-1]);
}
This works fine when the count of characters is a 10 .Also no extra space
used.If you find any mistake, please do correct me!
On Sun, Mar 25, 2012 at 10:18 AM, SAMM somnath.nit...@gmail.com wrote:
In this question is it mandatory to use array here .Because the output and
the space were the string is stored is required ..
I was thinking of using LL approach ..
Need four pointers to keep track of the positions .
begin - store the beginning of the LL initially containing the pointer to
he 1st node a1b2c3d4.
end - store the end node of the input string .
outputbegin - store the position where the output index begin .. It will
be appended to the next node of the input string .
outputend -store the end node of the LL.
begin -- a 1 b 2 c 3 d 4(-end) (outputbegin-) NULL -(outputend)
Delete d4 we hav now:-
begin -- a 1 b 2 c 3 (-end) (outputbegin-) d d d d -(outputend)
Take the character and corresponding value from the end index, change the
end pointer to '3' on the left of d4 , delete both nodes of d4 and
append it characters at the end .. All u have to do is remove and append ,
no extra memory greater than length(output) is used here ..
As Nothing has been mentioned abt printing the output in the question , we
will keep printing the character on the console while appendiing the
character in the LL ).
--
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.
--
*Kalyan
Dont take life seriously as it isnt Permanent!
*
--
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.
Re: [algogeeks] Re: Run Length Decoding... inplace
@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 peacelover1987...@yahoo.co.inwrote: 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 a1b2c1d4e Step 2: expand 'd' 4 times.before that shift 5e's by 4 right side. a1b2c1ee step 3: here since 1 is a special case shift 'ee' left side by 1 -- *From:* atul anand atul.87fri...@gmail.com *To:* algogeeks@googlegroups.com *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 peacelover1987...@yahoo.co.in 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 a1b2c3 now in next loop a1b2ccc- here we have to do a)reallocation and b)copy the last 3 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 a01 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.comwrote: @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.comwrote: @Ashish : a10 will be represented as aa . 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 aascii 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.comwrote: 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.comwrote: @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 cc and stopped
Re: [algogeeks] Re: Run Length Decoding... inplace
@ Kalyanasundaram : no need to check you algo , bcozz i can clearly see you
are not saving output to the bufffer , you are just printing it to stdout .
please read prev comment for better understanding the problem,
On Sun, Mar 25, 2012 at 11:54 AM, Kalyanasundaram nks.22.1...@gmail.comwrote:
scanf(%s,a);
l=strlen(a);
for(i=l-1;i=0;i-=2)
{
while((a[i]--)-'0')
printf(%c,a[i-1]);
}
This works fine when the count of characters is a 10 .Also no extra space
used.If you find any mistake, please do correct me!
On Sun, Mar 25, 2012 at 10:18 AM, SAMM somnath.nit...@gmail.com wrote:
In this question is it mandatory to use array here .Because the output
and the space were the string is stored is required ..
I was thinking of using LL approach ..
Need four pointers to keep track of the positions .
begin - store the beginning of the LL initially containing the pointer
to he 1st node a1b2c3d4.
end - store the end node of the input string .
outputbegin - store the position where the output index begin .. It will
be appended to the next node of the input string .
outputend -store the end node of the LL.
begin -- a 1 b 2 c 3 d 4(-end) (outputbegin-) NULL -(outputend)
Delete d4 we hav now:-
begin -- a 1 b 2 c 3 (-end) (outputbegin-) d d d d -(outputend)
Take the character and corresponding value from the end index, change the
end pointer to '3' on the left of d4 , delete both nodes of d4 and
append it characters at the end .. All u have to do is remove and append ,
no extra memory greater than length(output) is used here ..
As Nothing has been mentioned abt printing the output in the question ,
we will keep printing the character on the console while appendiing the
character in the LL ).
--
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.
--
*Kalyan
Dont take life seriously as it isnt Permanent!
*
--
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.
Re: [algogeeks] Re: Run Length Decoding... inplace
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
a1b2c3
now in next loop
a1b2ccc- here we have to do a)reallocation and b)copy the last 3
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 a01 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 aa . 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 aascii 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
cc
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 :-
#includestdio.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
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 peacelover1987...@yahoo.co.in 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
a1b2c3
now in next loop
a1b2ccc- here we have to do a)reallocation and b)copy the last 3
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 a01 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.comwrote:
@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.comwrote:
@Ashish : a10 will be represented as aa . 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 aascii 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.comwrote:
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.comwrote:
@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
cc
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 :-
#includestdio.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
Re: [algogeeks] Re: Run Length Decoding... inplace
@ashish:
i guess you are thinking too much , question say you have character 'a' to
'z' and some value after which will tell ,how many times you shuld print it.
if we take 15 as 1 then this would require other means of encoding
to interpret it correctly.
On Sat, Mar 24, 2012 at 1:19 AM, Ashish Goel ashg...@gmail.com wrote:
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 a01 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.comwrote:
@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.comwrote:
@Ashish : a10 will be represented as aa . 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 aascii 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.comwrote:
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.comwrote:
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
cc
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 :-
#includestdio.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;jloop;j++)
{
str[res_len]=c;
res_len++;
}
}
}
Re: [algogeeks] Re: Run Length Decoding... inplace
In this question is it mandatory to use array here .Because the output and the space were the string is stored is required .. I was thinking of using LL approach .. Need four pointers to keep track of the positions . begin - store the beginning of the LL initially containing the pointer to he 1st node a1b2c3d4. end - store the end node of the input string . outputbegin - store the position where the output index begin .. It will be appended to the next node of the input string . outputend -store the end node of the LL. begin -- a 1 b 2 c 3 d 4(-end) (outputbegin-) NULL -(outputend) Delete d4 we hav now:- begin -- a 1 b 2 c 3 (-end) (outputbegin-) d d d d -(outputend) Take the character and corresponding value from the end index, change the end pointer to '3' on the left of d4 , delete both nodes of d4 and append it characters at the end .. All u have to do is remove and append , no extra memory greater than length(output) is used here .. As Nothing has been mentioned abt printing the output in the question , we will keep printing the character on the console while appendiing the character in the LL ). -- 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.
Re: [algogeeks] Re: Run Length Decoding... inplace
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 aa . 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 aascii 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.comwrote:
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.comwrote:
@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
cc
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 :-
#includestdio.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;jloop;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
Re: [algogeeks] Re: Run Length Decoding... inplace
what if we simply use the same char instead of '\0' that would reduce one
traversal?
(@utkarsh We discussed that earlier in lab.Did u found out the bug in this
approach?)
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Mar 23, 2012 at 6:38 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.comwrote:
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.comwrote:
@Ashish : a10 will be represented as aa . 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 aascii 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.comwrote:
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.comwrote:
@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
cc
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 :-
#includestdio.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;jloop;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
Re: [algogeeks] Re: Run Length Decoding... inplace
yes if we use char instead of that place then again we will loss the data
on the input a1b1c4
On Fri, Mar 23, 2012 at 7:42 PM, saurabh singh saurab...@gmail.com wrote:
what if we simply use the same char instead of '\0' that would reduce one
traversal?
(@utkarsh We discussed that earlier in lab.Did u found out the bug in this
approach?)
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Mar 23, 2012 at 6:38 PM, 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.comwrote:
@Ashish : a10 will be represented as aa . 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 aascii 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.comwrote:
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.comwrote:
@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
cc
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 :-
#includestdio.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;jloop;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
Re: [algogeeks] Re: Run Length Decoding... inplace
Yes u are correct...My bad...That obviously didn't made any sense Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Fri, Mar 23, 2012 at 7:49 PM, UTKARSH SRIVASTAV usrivastav...@gmail.comwrote: yes if we use char instead of that place then again we will loss the data on the input a1b1c4 -- 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.
Re: [algogeeks] Re: Run Length Decoding... inplace
@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.comwrote:
@Ashish : a10 will be represented as aa . 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 aascii 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.comwrote:
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.comwrote:
@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
cc
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 :-
#includestdio.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;jloop;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
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 a01 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.comwrote:
@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.comwrote:
@Ashish : a10 will be represented as aa . 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 aascii 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.comwrote:
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.comwrote:
@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
cc
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 :-
#includestdio.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;jloop;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
Re: [algogeeks] Re: Run Length Decoding... inplace
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.comwrote:
@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
cc
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 :-
#includestdio.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;jloop;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.
Re: [algogeeks] Re: Run Length Decoding... inplace
Gene, Atul
How would a string of say 257 or say 10 times a would be represented, will
it be a10 or aascii 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.comwrote:
@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
cc
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 :-
#includestdio.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;jloop;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.
Re: [algogeeks] Re: Run Length Decoding... inplace
this will work even if run length is 1.
#includestdio.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;
/*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')
{
/*converting to number*/
loop=(str[i]-'0')*k+loop;
k=k*10;
}
else
{
for(j=0;jloop;j++)
{
str[res_len]=str[i];
res_len++;
}
loop=0;
k=1;
}
}
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.
Re: [algogeeks] Re: Run Length Decoding... inplace
using Gene logic , but we need to take care of number with more than 1
digits , so updated gene's code is as follows :-
#includestdio.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;jloop;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.
Re: [algogeeks] Re: Run Length Decoding... inplace
@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
cc
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 :-
#includestdio.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;jloop;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.
