Back to General and Gameplay Programming

Gray code

General and Gameplay Programming Programming

Started by CableGuy January 26, 2009 07:26 AM

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

139

January 27, 2009 11:10 AM

Quote:Original post by Mantear
Quote:Original post by GoDoG23
You don't need Dn_m; it's just the reasoning behing the formula. When you are in s[0] != s1[0] you know that there are 0 or >=2 differences.

If E0_n-1 is true then the differences are 0 and if E0_n-1 is false the differences are >=2.

I disagree. Having only a boolean return value from the recursive call, it's ambiguous as to whether you have 0, or 2, or 4, or any x*2 number of differences. Show a method in which it is not ambiguous.

What do you want the code?

I give you a formal method to the answer. You are thinking with one subproblem but you could use as many as you want.

isGrey(s0.sub(0, s0.length()-1), ...) is not an ambiguous call. You know that you have at least 1 difference (you are in s0[0] != s1[0]). With that result you could know the real state of isGrey(s0.sub(1, ...).

CProgrammer

303

January 27, 2009 11:48 AM

if you are going to use multiple isGray calls then u can just use isGray(s1.sub(1, 1), ...) to get the second index through a little hack. I think using the second index is what the homework intended.

Antheus

2,410

January 27, 2009 12:06 PM

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 [wink]

bool isGray(const char *s1, const char *s2);

No malloc/new, casts, array declarations, etc...

How do you solve it? It allows exactly and precisely same set of operations as presented in the skeleton.

If concatenation between a char and string is somehow implicitly allowed since it happens to exist for Java strings, then why not equals()? Or lastIndexOf()?

I once had to deal with same kind of ill-defined problem dealing with sorting. We were given a set of allowed functions to use. Of course, a crucial one was missing. I finally ended up coming with solution that defined the missing function using the allowed ones, and it only took several hundred lines of code, using methods akin to pre-processor programming.

When presented, I got a funny look back, asking why I didn't simply use a C library function - with task stating that "you're only allowed to use ...".

Thinking outside of box is dangerous for this type of exercises.

After all, can I just submit: C-x M-c M-isGray?

Mantear

251

January 27, 2009 12:21 PM

Quote:Original post by GoDoG23
isGrey(s0.sub(0, s0.length()-1), ...) is not an ambiguous call. You know that you have at least 1 difference (you are in s0[0] != s1[0]). With that result you could know the real state of isGrey(s0.sub(1, ...).

Are you proposing that there be a for-loop that loops through all sub-string lengths whenever you hit the s1[0]!=s2[0] condition, starting with the shortest strings to find detect multiple bit differences? That solution works, but if you use a for-loop like that, you might as well not bother with recursion to begin with.

SPOILER ALERT! Below is code that works, but I think it's garbage as it destroys the whole purpose of recursion. Sorry, it's been mangled into C++.

bool IsGray(std::string str1, std::string str2){    if ((str1.size() == 0) || (str2.size() == 0))        return false;    if (str1[0] != str2[0])    {        bool one_difference = true;        for (size_t i = 1; i < str1.size(); i++)        {            if (IsGray(str1.substr(1, i), str2.substr(1, i)))            {                one_difference = false;                break;            }        }        return one_difference;    }    else    {        return IsGray(str1.substr(1), str2.substr(1));    }}

GoDoG23

139

January 27, 2009 04:52 PM

Quote:Original post by Mantear
Quote:Original post by GoDoG23
...

Are you proposing that there be a for-loop that loops through all sub-string lengths whenever you hit the s1[0]!=s2[0] condition, starting with the shortest strings to find detect multiple bit differences? That solution works, but if you use a for-loop like that, you might as well not bother with recursion to begin with.
...

No. I'm not proposing a for loop, just a multiple recursion solution.

I have send you two fully recursive solutions.

EmrldDrgn

198

January 27, 2009 04:59 PM

Quote:Original post by Mantear
Again, how do you distinguish between the case where there are 0 differences or 2 (or any number of even) differences? The recursive call only returns a boolean, there's no way to represent the three states required. There is no Dn_m function that returns something more informative than a boolean.

Why does it matter? It was my impression that all even differences should return false, regardless, meaning that the number of differences doesn't matter, as long as it's not 1...

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

CableGuy

1,335

Author

January 27, 2009 05:31 PM

@Nyarlath: The original function was called grayPair or something. either way, it's meant to check what previously stated.
@Mantear you might as well use string equality test because the recursive nature of the solution is quite pointless.

CProgrammer

303

January 27, 2009 07:28 PM

Ok heres a recursive function following all the guidelines. I left it incomplete so that its just a hint but using this approach you can make a very easy fully recursive solution. The rest is just appropriate isGray calls. There are no iterative loops or the like.
EDIT: added dots infornt of the if for the termination code

boolean IsGray(String s1,String s2){   if ((s1.length()==0) || (s2.length()==0))      return false;   if (s1.charAt(0)!=s2.charAt(0))   {      ...      if(isGray(s1.substring(1, 2), s2.substring(1, 2))      ...      else      ...   }   else   {      ...   }}

[Edited by - CProgrammer on January 27, 2009 8:28:02 PM]

GoDoG23

139

January 27, 2009 07:43 PM

Quote:Original post by CProgrammer
...

boolean IsGray(String s1,String s2){   if ((s1.length()==0) || (s2.length()==0))      return false;   if (s1.charAt(0)!=s2.charAt(0))   {      if(isGray(s1.substring(1, 2), s2.substring(1, 2))      ...      else      ...   }   else   {      ...   }}

Is not that the skeleton of the solution based on string mutation?

Zahlman

1,682

January 27, 2009 07:50 PM

Quote:Original post by DevFred
Why do teachers choose such poor examples for recursion?

They are poor in the sense of practicality, but good in the sense that the recursive solution can (hopefully!) be easily understood and verified by hand. Examples where recursion is really necessary to solve the problem (or where other solutions are either unwieldy or tend to amount to emulating recursion manually) are often too complex for a classroom environment. Unless you have some good examples handy? :)

Although, I'm not entirely convinced that recursion needs to be taught at all; only shown as a technique - after all, it's only a special case of calling one function from another.

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