Back to General and Gameplay Programming

Gray code

Idan Bachar · 2009-01-27T20:00:20

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.

General and Gameplay Programming Programming

Started by CableGuy January 26, 2009 07:26 AM

69 comments, last by CProgrammer 15 years, 2 months ago

swiftcoder

18,997

January 26, 2009 07:24 PM

Quote:Original post by DevFred
Looking forward to reading the solution :)

Nope, you are right. My solution breaks down for strings with 3 non-consecutive differences. As with your tests, I only tried with 4 character strings, which don't cause it to break.

Unfortunately, it seems that ToohrVyk's solution also requires 2 characters of lookahead, and is complicated in Java, due to strings being constant.

As it stands, the most elegant way to solve this is by delegating the functionality to an inner function/closure, although there is potentially a deliciously evil way using an exception to signal the third case.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

Mantear

251

January 26, 2009 08:53 PM

Are you or are you not restricted to the exact skeleton code you posted earlier? If you are, are you also restricted from doing a look-ahead at the next character, charAt(1)? If you are, then there is no solution.

Quote:Original post by ToohrVyk
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

How do you propose this solution could work if the strings are being passed by value? Again, I'm under the assumption that you can't look ahead to charAt(1).

Once you hit the condition where there were 2 bits different, there is no way to pass back up the recursive call chain whether you found 2 (or any number of even differences) or none. Therefore, it makes it impossible to determine if you found 1, 3, 5, 7, etc, differences, where 1 difference == Gray and all the others == !Gray. Again, all under the assumption that you can't look at charAt(1) and that all the strings are being passed by value.

mostly_human

122

January 26, 2009 10:12 PM

You guys are making things way to complicated. OP's solution is almost correct, in fact he just needs to modify one line.
Hint: Add another base case.

Hope this helps.

[Edit]
Never mind, I was over thinking the problem.

[Edited by - mostly_human on January 26, 2009 10:12:27 PM]

GoDoG23

139

January 26, 2009 10:14 PM

I think I got a fully recursive solution (multiple recursion).

The problem is that the function have 3 different states:
0 differences,
1 difference (its a grey code),
>=2 differences,

but the skeleton returns a boolean value. So we could memorize, lookahead or come with a fancy recursive formula.

When subproblem E0 = isGrey(s0.sub(1), s1.sub(1)) is false we could be at 0 differences or >=2 differences.

But if we look at subproblem E1 = isGrey(s0.sub(0, s0.lenght()-1), s1.sub(0, s1.lenght()-1) we could deduce the real state.

swiftcoder

18,997

January 26, 2009 10:50 PM

Quote:Original post by GoDoG23
I think I got a fully recursive solution (multiple recursion).
...
But if we look at subproblem E1 = isGrey(s0.sub(0, s0.lenght()-1), s1.sub(0, s1.lenght()-1) we could deduce the real state.

That is the solution I thought I had, but I wasn't able to get it to work for multiple discontinuous differences.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

iMalc

2,466

January 27, 2009 01:34 AM

One solution that immediately comes to mind is: Divide and Conquer.
Chop both strings in half, recurse on both halves until they consist of only 1 characters, for which the answer is trivial. Then for the returned-from recursive calls, the answer is true only if the first halves are identical and the second halves recursive call returned true, or vice-versa.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

CableGuy

1,335

Author

January 27, 2009 02:22 AM

@iMalc: That might work but as I already stated you must use the supplied skeleton.

I'm quite certain it is not possible without memorization/lookahead/helper function. If anyone got it please say so.

ToohrVyk

1,596

January 27, 2009 02:38 AM

Quote:Original post by Mantear
How do you propose this solution could work if the strings are being passed by value? Again, I'm under the assumption that you can't look ahead to charAt(1).

You can get the equivalent of charAt(1) by using substring(1) and charAt(0), both of which are allowed [smile]

Blog — Facebook

EmrldDrgn

198

January 27, 2009 03:00 AM

Would you be able to look at other indexes (indicies?) inside that function skeleton? Specifically the end of the string? If so I might see a possibility...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~I program in C++, on MSVC++ '05 Express, and on Windows. Most of my programs are also for windows.

DevFred

840

January 27, 2009 05:16 AM

Quote:Original post by Mantear
How do you propose this solution could work if the strings are being passed by value?

In Java, everything is passed by value. By "everything", I mean primitive types and reference types. No other types exist. Especially no object types. You can't pass objects in Java.

So what happens here is that references to immutable String objects are passed by value.

But why does that matter?

Gray code

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Gray code

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines