• Advertisement
Sign in to follow this  

Gray code

This topic is 3311 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi. I know about the FAQ and this is indeed partially homework related. I'm not asking someone for a solution but rather a direction. I need to write a recursive function that gets two strings and checks whether they differ by only one bit. The thing is the skeleton of the function is already given (you can assume that the stings only contain 0's and 1's and are of the same length):
boolean IsGray(String s1,String s2)
{
   if ((s1.length()==0) || (s2.length()==0))
      return false;
   if (s1.charAt(0)!=s2.charAt(0))
   {
      // Do stuff
   }
   else
   {
      // Do stuff
   }
}
I only got here:
boolean IsGray(String s1,String s2)
{
   if ((s1.length()==0) || (s2.length()==0))
      return false;
   if (s1.charAt(0)!=s2.charAt(0))
   {
      boolean res=IsGray(s1.substring(1),s2.substring(1));
      if (res)
         return false;
      else
         return true;
   }
   else
   {
      return IsGray(s1.substring(1),s2.substring(1));
   }
}
As expected this code only checks if they differ by an odd number of bits. Any suggestions, tips and such would be greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Quick question: you say you are checking if they differ by only a bit; does this mean that in the case where one bit or less are different, to return true? Or only return true if the strings are identical?

Can you please be very specific as to the 'true' conditions?

Share this post


Link to post
Share on other sites
The function should return true only if the two strings differ by exactly one bit.
For instance:
s1=0001
s2=0000
returns true
but
s1=0001
s2=1000
returns false.

Share this post


Link to post
Share on other sites
Quote:
Original post by CableGuy
The function should return true only if the two strings differ by exactly one bit.
It is often helpful to think of boolean problems in terms of their inverse - in this case, you can return false as soon as you encounter second bit that is different, or at the end of the strings if all bits are the matching.

Share this post


Link to post
Share on other sites
But I can't count how many bits differ. My first thought was when I encounter two bits that are different check if there are more and return false, as written in my first post. But since it is recursive, it checks if the number of bits are odd.

Share this post


Link to post
Share on other sites
Consider these hints:

- For your function, the only data that you can pass recursively are the two strings themselves. This means you need to think about string usage and manipulation.

- Each recursive call always checks the first index of each string to compare. If the function always checks the first index of the string for each recursive call, what would that indirectly imply about the parameter strings that are passed each recursive chain (would they be the same string always or not)?

- Are the parameters passed by reference or by value? If they are passed by value, it means you can modify them in place. If they are passed by reference, then you will be passing a new object. The answer to this does not matter in particular, but it is related to the previous hint.

I think that's about as much can be said without giving it away, good luck [smile]

Share this post


Link to post
Share on other sites
As I see it, the function should "choose" different code paths depending on what was found previously but I can't know that.
Quote:

- Each recursive call always checks the first index of each string to compare. If the function always checks the first index of the string for each recursive call, what would that indirectly imply about the parameter strings that are passed each recursive chain (would they be the same string always or not)?

Sorry didn't quite get you. Did you mean I have to trim the strings I pass? If so did you look at the code at bottom of my first post?

Share this post


Link to post
Share on other sites
Is there any reason why this needs to be recursive in the first place.

With a simple loop over two equal-length strings it shouldn't be hard to inspect each pair of characters and keep a counter how many are different. You can stop earlier as already suggested, or continue till the end of the strings if you for some reason really want to find out the total count of different bits.

Of course, it wouldn't be hard to turn that into recursion either...

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
Is there any reason why this needs to be recursive in the first place.

With a simple loop over two equal-length strings it shouldn't be hard to inspect each pair of characters and keep a counter how many are different. You can stop earlier as already suggested, or continue till the end of the strings if you for some reason really want to find out the total count of different bits.

Of course, it wouldn't be hard to turn that into recursion either...


It needs to be recursive because that's the requirement.

Share this post


Link to post
Share on other sites
Don't know if I'm giving the answer away, but I'll try to just give you a hint (according to how I solved it). Return in this form: return a + b;. What a and b are, and what operator to use instead of + is up to you ;)

Share this post


Link to post
Share on other sites
Given that exact "skeleton" and assuming you can't write a second function that does the recursive stuff, and you can't use a global (since there's no place to give it an initial value), and you can't inspect other pairs of characters in "do stuff", since then it's recursiveness would be dubious, I'd say it is an impossible task.

Now, if you were allowed a third parameter to represent differing characters so far, that would be another story...

Share this post


Link to post
Share on other sites
That's what I thought. Of course I can replace the first "do stuff" with an iteration over the remaining strings and check if I found other bits which are different, but don't it wouldn't be really recursive. Has anyone got a truely recursive solution without using for/while in without any strings hackery?

Share this post


Link to post
Share on other sites
Quote:
I'd say it is an impossible task.


Of course it isn't. I have a solution, and I'd post it if it wasn't a homework question.

Share this post


Link to post
Share on other sites
LISP programmers have called it car and cdr, ML programmers have called it head and tails. In general, a recursive algorithm needs to work on a recursive data type.

So, if you managed to express your strings as recursive data types (for instance, by considering, as you already did, s.substring(1) as being the tail, and s[0] as being the head), you could solve the problem recursively.

A recursive solution solves the problem by assuming that smaller-sized problems have already been solved. So, assuming that you can determine whether IsGray(s1.substring(1),s2.substring(1)), how would you determine whether IsGray(s1,s2) ?

Share this post


Link to post
Share on other sites
Why do teachers choose such poor examples for recursion? Here is a completely recursion-free approach:

public static boolean isGray(String s1, String s2)
{
long x = Long.parseLong(s1, 2);
long y = Long.parseLong(s2, 2);
long a = x ^ y;
long b = a & (a - 1);
return a != 0 && b == 0;
}

Does IsGray have to call itself? Or can it call another function which calls itself recursively?

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
So, assuming that you can determine whether IsGray(s1.substring(1),s2.substring(1)), how would you determine whether IsGray(s1,s2) ?

It's impossible to determine, because if IsGray(s1.substring(1),s2.substring(1)) returns false, you cannot know if the substrings were a) equal or b) too different. Both would return false.

CableGuy: Are you allowed to compare strings for equality? In that case, the solution is trivial.

Share this post


Link to post
Share on other sites
I concur with DevFred.

As you work backwards out of your recursive calls, the return value of IsGray() can only indicate: 1) 'false' if the strings are identical (See the case where the strings' lengths hit 0) and 2) 'true' if the latest character is different (and all following characters were the same, see case 1).

However, if the next character is again different, you would have to change the return value from 'true' to 'false'. Now, the parent call doesn't know if the return value is 'false' because the strings were identical OR there are two differences. Thus you can only get the right answer if there are an odd number of different bits/characters. If you have an even number of different bits, it's impossible to tell, given the restrictions of the 'skeleton' code.

Share this post


Link to post
Share on other sites
@DevFred: There are no "don't do" but I guess you are not supposed to use string equality as this is the same as doing an iteration over the string.

@ToohrVyk: As I said before it is if the function should return different values depending on past differences. When the function first encounter a difference it needs to check whether there are no other differences.

@All other: I usually nail down recursion, it might take me sometime but eventually I get it. This one really baffles me. So If any of you who have claimed to solve the problem can post a little more specific guidance I will be grateful.

Share this post


Link to post
Share on other sites
Quote:
Original post by CableGuy
I guess you are not supposed to use string equality

Right. This is how my solution would have looked:

public static boolean IsGray(String s1, String s2)
{
if (s1.isEmpty() || s2.isEmpty()) return false;
String t1 = s1.substring(1);
String t2 = s2.substring(1);
return s1.charAt(0) != s2.charAt(0) ? t1.equals(t2) : IsGray(t1, t2);
}

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
It's impossible to determine, because if IsGray(s1.substring(1),s2.substring(1)) returns false, you cannot know if the substrings were a) equal or b) too different. Both would return false.
It's possible. Think outside the box, and notice that you can modify the strings to "remember" that you already encountered an identical pair [wink]

Share this post


Link to post
Share on other sites
First I wanna thank everyone for their responses.

As I said there is not a strict definition how the recursion should look like and what is allowed and what is not, but I guess DevFred's suggestion is more "correct" than using the strings to store some counter (or something similar).

Thanks again.

Share this post


Link to post
Share on other sites
Quote:
Original post by CableGuy
more "correct" than using the strings to store some counter (or something similar).


Not really storing a counter. The basic idea is that, if the first characters are different and the second characters are also different, then you have two differences and can thus return false. Otherwise, if the first characters are different but the second characters are not, swap the first and second characters in each string to move the diferring characters forward, and repeat the process on the substrings.

Share this post


Link to post
Share on other sites
OK, I think I finally got it:

isGray :: String -> String -> Bool

isGray [ ] _ = False
isGray _ [ ] = False

isGray [x] [y] = x /= y

isGray (x:a:xs) (y:b:ys)
| x == y = isGray (a:xs) (b:ys)
| a == b = isGray (x:xs) (y:ys)
| otherwise= False

As one might guess, the Java code to this recursive problem isn't nearly as beautiful.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
OK, I think I finally got it:

isGray :: String -> String -> Bool

isGray [ ] _ = False
isGray _ [ ] = False

isGray [x] [y] = x /= y

isGray (x:a:xs) (y:b:ys)
| x == y = isGray (a:xs) (b:ys)
| a == b = isGray (x:xs) (y:ys)
| otherwise= False

As one might guess, the Java code to this recursive problem isn't nearly as beautiful.


Say what?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement