Saturday, May 23, 2009

Hollow Rhombus, a change in perspective

What is Hollow Rhombus?

For all those of you who do not know what exactly is Hollow Rhombus, here is a little intro for that. Hollow Rhombus is a homework problem given to students learning programming in procedural languages like BASIC, C, C++, Java etc. The problem goes like:

Write a program to input a word and print it out in the following format (for input word “HAPPY”):

HAPPY#HAPPY
HAPPY HAPPY
HAPP   APPY
HAP     PPY
HA       PY
H         Y
HA       PY
HAP     PPY
HAPP   APPY
HAPPY HAPPY
HAPPY#HAPPY
The whole point is to make students get acquainted with the various ways to use the looping statements like for, while, do-while. The problem is not a very easy one to solve for somebody who has just started with the looping constructs. It seemed to be quite an hurdle when I faced it back in std IX.

Usual Approach

The usual approaches towards solving the problem is to break up the figure into 6 parts:
First Line:
HAPPY#HAPPY

Left-Top:
HAPPY
HAPP
HAP
HA
H

Right-Top:
HAPPY
 APPY
  PPY
   PY
    Y

Left-Bottom:
HA
HAP
HAPP
HAPPY

Right-Bottom:
   PY
  PPY
 APPY
HAPPY

Last Line:
HAPPY#HAPPY

Then to code each part individually. The first and last lines are printed as it is. The top left and right parts are combined within a loop. Similarly the bottom parts are also combined within a loop (usually a for loop).

Sample Java Code for the usual approach

import java.io.* ;
public class gap
{
public static void main(String args[])throws IOException
{
 BufferedReader input = new BufferedReader( new InputStreamReader( System.in )) ;
 int j, k=0, x, y, z, Wl=0, sp=-1, st=0 ;
 String W="" ;

 System.out.print("\nENTER A WORD (MAX:19) : ") ;
 W = input.readLine() ;
 Wl = W.length() ;

 W = W+"#"+W ; // changing the string including a hash
 System.out.print("\n"+W ) ; // printing first-line

 for( j=0 ; j<Wl ; ++j )
 { // loop to generate top half
  System.out.println() ;
  sp += 2 ;// increasing space by 2
 
  for( x=0 ; x<(Wl-j) ; ++x )
   System.out.print( W.charAt(x) ) ;
  for( y=1 ; y<=sp ; ++y )
   System.out.print(" ") ;
  for( z=st ; z<Wl ; ++z )
   System.out.print( W.charAt(z) ) ;
 
  ++st ;
 }

 st -= 2 ;
 for( k=Wl-1-1 ; k>=0 ; --k )
 { // loop to generate bottom half
  System.out.println() ;
 
  sp -= 2 ;
  for( x=0 ; x<(Wl-k) ; ++x )
   System.out.print( W.charAt(x) ) ;
  for( y=sp ; y>0 ; --y )
   System.out.print(" ") ;
  for( z=st ; z<Wl ; ++z )
   System.out.print( W.charAt(z) ) ;
  --st ;
 }

 System.out.println("\n"+W+"\n") ; // printing last-line
}
}

Change in Perspective

The method that I have demonstrated so far to solve this looping problem is usual run-of-the-mill type. The coding is lengthy and the start and end loop values have to be carefully thought out. My brother, Bikkhan, who is in Std XII now had got this as a part of his programming assignments. When he came to me with this problem, I was quick to show him the common way of doing it by breaking it into 6 parts as demonstrated. It took him quite sometime, about 6 hours to come up with the Java code that you saw above.

I have been doing a lot of Prolog recently and I guess this is what led me to think recursively. Prolog does not have any traditional iterative statements, instead all sort of looping is achieved using recursion. To my surprise, thinking recursively had great effects on this program, and I solved it in almost no time in C++. The code length is very small compared to the former approach and I guess the logic is simpler too. So I guess its all about perspective. Here is a copy of my code in C++.

#include<iostream>
#include<string>

using namespace std;

int len;   // length of the input string

void hollow_rhombus ( string str, int n )
// str : is the string to be printed
// n   : is the step count
{
   cout<<str<<endl;

   if ( n < len )  // n==len indicates the middle line
   {
       string newstr=str;
       newstr[len-n] = newstr[len+n] = ' ';   // adding 2 new blanks
       hollow_rhombus ( newstr, n+1 );
       cout<<str<<endl;
    }
}

int main()
{
    string str;
    cin>>str;      // the word is taken as input

    len = str.length();
    str = str + "#" + str;     // first line is generated
    hollow_rhombus(str,0);     // calling the recursive function
}

Why talk about a silly looping exercise?

When I started writing this piece for my blog, my brother was the first one to ask about why did I like to share something trivial as this? After all this is another exercise in looping given to novice programmers. But what I felt was that this is a great example of how the right sort of problem analysis can lead to a simpler code, which is easier to write and read.

4 comments:

  1. Good to see the old C++ juggling again! Yeah I agree that the more you refine the solution the easier to do it may become. In this respect I would like to say that the initial 6-parts logic was good for my school days but when I went on to teach school level students they were always apprehensive of lengthy code.

    Hence I decided to simplify the code a bit. I took each character of the word and formed the sequence similar to your str=str+#+str and then did it through double nested for loop uder the logic of either printing the character or a blank based on iteration count. Ha ha ....

    ReplyDelete
  2. Thanks for your comments Prasenjit. I am sure that I was not the first one to improvise a solution using recursion. But what I wanted to share was how easy it had become to code it, in terms of the terminal value of loop computation, along with the fact that what a little change in perspective can bring about.

    ReplyDelete
  3. Nice one...impressive logic. But don't say that its a very simple code to understand... Took me some time... I guess its all about Perspective :-)

    ReplyDelete
  4. @Silent Assasin, yeah I guess its all about perspective after all. Maybe I should have explained the recursive version a bit. Actually to the programmer, the logic always seems crystal clear.

    ReplyDelete

I'd love to hear from you !