Simple Asterisk Pattern with Recursion

October 18, 2010 at 14:23 (code golf, java)

Background: I introduced code golf in a previous post.

I recently came across an easy but fun problem posted on Yahoo! Answers. It could make for a good code golf exercise. I will write the problem statement in a purposely vague manner, but clear enough to make the goal obvious; specifics can be added according to any particular contest or testing environment.

Using only recursion and no loops, print a triangular pattern of asterisks according to the following example:

Input:

1
3

Output:

*
*
**
***
**
*

Input/output wasn’t part of the original problem statement, so the code below is for hard-coded n-values. Also, the original problem statement required the solution to be in Java.

Initially I found it most convenient to separate the pattern into two parts, as follows:

class AsterisksPattern {
    public static void main(String[] args) {
        printPattern(5);
    }
    
    static void printPattern(int n) {
        printPatternAsc(1, n);
        printPatternDesc(n);
    }
    
    static void printPatternAsc(int ind, int stop) {
        if (ind == stop) return;
        printLine(ind);
        printPatternAsc(ind + 1, stop);
    }
    
    static void printPatternDesc(int ind) {
        if (ind == 0) return;
        printLine(ind);
        printPatternDesc(ind - 1);
    }
    
    static void printLine(int ind) {
        if (ind == 0) {
            System.out.println();
            return;
        }
        System.out.print("*");
        printLine(ind - 1);
    }
}

That code felt long, so I reduced it to this:

class AsterisksPattern {
    public static void main(String[] args) {
        int n = 5;
        printPattern(1, n, 1);
    }
    
    static void printPattern(int ind, int stop, int inc) {
        if (ind == stop) {
            if (stop == 0) return;
            printLine(ind);
            printPattern(ind - 1, 0, -1);
            return;
        }
        printLine(ind);
        printPattern(ind + inc, stop, inc);
    }
    
    static void printLine(int ind) {
        if (ind == 0) {
            System.out.println();
            return;
        }
        System.out.print("*");
        printLine(ind - 1);
    }
}

But this seems like just the sort of problem that could be solved with a few brilliantly cryptic and diabolical squiggles in Perl. I’m thinking of suggesting it for the SHORTEN contest at SPOJ. However, I’m guessing it would require a special judge, and I have no idea how that works.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: