4
\$\begingroup\$

This is exercise 2.3.24. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

Modify Beckett to print the Gray code.

Beckett refers to the following program within the text:

public class Beckett
{
    public static void moves(int n, boolean enter)
    {
        if (n == 0) return;
        moves(n-1, true);
        if (enter) System.out.println("enter " + n);
        else       System.out.println("exit " + n);
        moves(n-1, false);
    }
    public static void main(String[] args)
    {
        int n = Integer.parseInt(args[0]);
        moves(n, true);
    }
}

As stated in the text:

The playwright Samuel Beckett wrote a play called Quad that had the following property: starting with an empty stage, characters enter and exit one at a time so that each subset of characters on the stage appears exactly once.

The above program tries to simulate the above-explained stage instructions. Here is my attempt at turning Beckett into a program that produces Gray code:

public class exercise2_3_24 
{
    public static String swap(String s, String t, int n)
    {
        n = n-1;
        return s.substring(0,n) + t + s.substring(n+1);
    }
    public static void beckett(String s, int n)
    {
        if (n == 0) return;
        beckett(s, n-1);
        System.out.println(swap(s, "1", n));
        s = swap(s, "1", n);
        beckett(s, n-1);
    }
    public static void graycodes(int n)
    {
        String s = "";
        for (int i = 0; i < n; i++)
            s += "0";
        System.out.println(s);
        beckett(s, n);
    }
    public static void main(String[] args)
    {
        int n = Integer.parseInt(args[0]);
        graycodes(n);
    }
}

Is there any way that I can improve my program?

Thanks for your attention.

\$\endgroup\$
7
  • \$\begingroup\$ This does not produce Gray codes. It produces something completely different. \$\endgroup\$ – vnp Aug 30 '20 at 21:15
  • \$\begingroup\$ @vnp On page 273 of the aforementioned book, the author considers sequences like 00 01 10 11 (for n=2 for instance) Gray code and has a picture of these saying Gray code representations. I actually like to learn more about Gray code and its applications. I appreciate your guidance. Thank you. :) \$\endgroup\$ – Khashayar Baghizadeh Aug 30 '20 at 21:55
  • \$\begingroup\$ By definition of Gray code, successive numbers differ in exactly one bit. When I run your program (with n = 4), I see that the generated sequence starts with 0000, 1000, 0100. The second and third numbers differ in two positions. And there are more violations. \$\endgroup\$ – vnp Aug 30 '20 at 22:00
  • \$\begingroup\$ Thank you very much. I see now. These are not in accordance with the stage instructions. My code only produces all possible combinations but with the wrong order. I try to fix my code and edit my post. :) \$\endgroup\$ – Khashayar Baghizadeh Aug 30 '20 at 22:39
  • 2
    \$\begingroup\$ Please do not update the code in your question after receiving answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Having multiple versions of the same program in the same question is very confusing and the original code can't be removed or it would possibly invalidate the answers. Please, check your code is correct next time before posting. \$\endgroup\$ – Mast Aug 31 '20 at 9:02
3
\$\begingroup\$

I have some suggestions for your code.

Always add curly braces to loop & if

In my opinion, it's a bad practice to have a block of code not surrounded by curly braces; I saw so many bugs in my career related to that, if you forget to add the braces when adding code, you break the logic / semantic of the code.

Use java.lang.StringBuilder to concatenate String in a loop.

It's generally more efficient to use the builder in a loop, since the compiler is unable to make it efficient in a loop; since it creates a new String each iteration. There are lots of good explanations with more details on the subject.

before

String s = "";
for (int i = 0; i < n; i++) {
   s += "0";
}

after

StringBuilder s = new StringBuilder();
for (int i = 0; i < n; i++) {
   s.append("0");
}

Don’t use a loop when you want to repeat a string of x elements

The API that java give you offer a method to repeat the character x times; you can use java.lang.String#repeat (Java 11+)

before

StringBuilder s = new StringBuilder();
for (int i = 0; i < n; i++) {
   s.append("0");
}

after

String s = "0".repeat(n);

Extract the expression to variables when used multiple times.

In your code, you can extract the similar expressions into variables; this will make the code shorter and easier to read.

before

beckett(s, n - 1);
System.out.println(swap(s, "1", n));
s = swap(s, "1", n);
beckett(s, n - 1);

after

int previousNumber = n - 1;
beckett(s, previousNumber);
System.out.println(swap(s, "1", n));
s = swap(s, "1", n);
beckett(s, previousNumber);

Uses the increment and decrement operators when possible

Try to use the x++ / ++x, x-- or --x instead of x = x + 1 since they are more widely used and make the code easier to read.

before

n = n - 1;

after

n--;
\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much for your time. :) \$\endgroup\$ – Khashayar Baghizadeh Aug 30 '20 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.