Most elegant solution for creating a star

Well, forget the comment about copying the star to Notepad - it looks like EE strips out too many leading spaces...

For some reason, I couldn't create this question with 400 pts...

for (int i = 1; i <= (width * 2 - 1); i++) {
               for (int j = 0; j <  (width - (Math.abs(i - width))); j++)
                    System.out.print("*");
               System.out.println();
          }

m_onkey_boy -

Your code only prints 1/2 of a star - it looks like a pyramid standing on one end....

The star needs to be completely symmetrical.  Try again :)

If you specify the width as 3, how are you going to align the row with one and two stars? Wouldn't it end up as a pyramid standing on one end?

If the width is three, the "star" should look like this (I'll use an underscore '_' to show where spaces should be):

_*_
***
_*_

If the width is five, it would look like this:

_ _ * _ _
_ * * * _
* * * * *
_ * * * _
_ _ * _ _


You know, EE really needs a way to specify a fixed font in messages;  it would make code listings and stuff like this a lot easier...

Oh.  I misread the original.  I'll repost in the morning.

btw.. in the original question, the consecutive rows have a difference of one star.. but in the later comments, the difference is 2 i.e. "1 3 1" or "1 3 5 3 1".

if you want to get such formation, the number must be odd. because if it is even, an addition of 2 very time (starting from 1) wont total to any even number.

it would be helpful if you would give examples of both even and odd numbers. and preferably one greater than the base cases.

That's all I could do.... At least it's working...

int spaces = (width / 2);
        for (int i=1; i<=width+1; i+=2)
        {
                  for (int k=0; k<spaces; k++)
                       System.out.print(" ");
                  for (int j=1; j<=i; j++)
                  {
                       System.out.print("*");
                  }
                  spaces = spaces-1;
                  System.out.println();
        }
       
        for (int l=width-2; l>=0; l-=2)
        {
                  for (int k=0; k<spaces+2; k++)
                       System.out.print(" ");
                  for (int j=l; j>=0; j--)
                  {
                       System.out.print("*");
                  }
                  System.out.println();
                  spaces++;
        }

  Took me about 10'

 Sorry... I was trying it with even numbers. The following is working with odd numbers. The first for loop is as above. The second becomes:

for (int l=width-2; l>=0; l-=2)
 {
                  for (int k=0; k<spaces+2; k++)
                       System.out.print(" ");
                  for (int j=l-1; j>=0; j--)
                  {
                       System.out.print("*");
                  }
                  System.out.println();
                  spaces++;
   }

  Not a very optimized solution though... I am curious to see what people can come up with.

and similar solution that uses recursion

  public Star(final int width)
  {
    char[] symbols = new char[width];
    for (int i = 0; i < width; i++) symbols[i] = ' ';
 
    line(symbols, (width + 1) / 2 - 1, width);
  }

 
  private void line(char[] symbols, int i, int width)
  {
    symbols[i] = symbols[width - i - 1] = '*';
    System.out.println(symbols);
    if (i >0) line(symbols, i - 1, width);
    symbols[i] = symbols[width - i - 1] = ' ';
    System.out.println(symbols);
  }

Here is my solution. I don't know if you can call that eleguant, but it sure is short. And I would say quite crytpic;)
If you have managed to do it in 3 lines with a code less cryptic I sure would like to see it.

public Star(final int width)
{
    for(int row = 1;row <= width;row++)
      for(int col=1,pos=Math.abs((width+1)/2-row); col<=width; col++)
        System.out.print((col>pos && col<=(width-pos)?'*':' ') + ((col == width)?"\n":""));
}

Llaurick

Here is my version:
    public Star(final int width){
        for(int row=1; row<=width; ++row){
            int offset = (width+1)/2;
            for( int col=1; col<=width; ++col ){
                System.out.print(Math.abs(row-offset)+Math.abs(col-offset)<offset?"*":" ");
            }
            System.out.println();
        }
    }

Oops. Unnecessary variable moved out of the loop:

public Star(final int width){
       final int offset = (width+1)/2;
       for(int row=1; row<=width; ++row){
           for( int col=1; col<=width; ++col ){
               System.out.print(Math.abs(row-offset)+Math.abs(col-offset)<offset?"*":" ");
           }
           System.out.println();
       }
   }

In order to be symmetrical and work for both odd and even numbers, I added spaces in between the asterisks. Is that cheating?

for(int j=1;j<=(2*width-1);j++){
      for(int k=1;k<=Math.abs(width-j);k++)System.out.print(" ");
      System.out.print("*");
      for(int k=1;k<=(width-1-Math.abs(width-j));k++)System.out.print(" *");
      System.out.println();
}

Bazarny: You gave me the Math.abs relation I was looking for. Now I can do it in 2 lines with only one loop:

public Star(final int width){
  for(int pos = 0,offset=(width-1)/2;pos<width*width;pos++)
    System.out.print((Math.abs(pos/width-offset)+Math.abs(pos%width-offset)<=offset?"*":" ") + (pos%width==width-1?"\n":""));
}

Not that I would write something that cryptic in a real code...

Llaurick

hellonloose -

Yes, my original "star" didn't look right;  the difference between rows is always 2, not 1.  Thanks for pointing that out.

girionis -

Your code works, but can you make a single method handle both the even and odd numbers?  Although technically not a requirement, forcing the code to handle both will lead you to a more optimized algorithm...

heyhey -

Your second one doesn't count :), since I wanted everything to be in the constructor.  The first one works, but there's an extra line feed at the end (you have two blank lines at the end, whereas the others (mine included) only have one)...

Hey, this is getting kind of fun.  Sometimes the most enjoyable part of programming is when you're solving a random puzzle, just for the thrill of solving it...

llaurick -

(1st post)
That's pretty close to my own solution.  However, the last part of your println:

 ((col == width)?"\n":""));

is adding a null string each time (unless you're at the end of the row).  That's a little inefficient;  you can easily move that \n somewhere else, and simplify your logic.

(2nd post)
That's impressive to see it squeezed into two lines, but calling Math.abs() twice is inefficent.

So far, you're in first place here!  Good work!

bazarny -

That looks good, although you could collapse it a little by rearranging your variables.  Also, can you find a way to remove the multiple calls to Math.abs() ??

rrz -

Your code works, but my specification didn't allow for spaces :)  Can you get it to work without them?

To nebeker,
I am confused as to what you wanted as the output to your program.
you posted
>I'm sure lots of people have been required to write the "star" program (i.e. you give it a number, and
>it creates a star whose width is <number>  
you also posted  
>The star needs to be completely symmetrical  
You seemed to accept llaurick's 2nd post, it works for odd numbers but not for even numbers.
It just gives the width displayed as (width-1) when an even number is given.
llaurick's 1st post (as many others) works for odd numbers but not for even numbers.
When an even number is given, the first and last lines of the output contains 2 asterisks.
Is that what you want?

Right - How do you expect even numbers to be handled?

rrz -

llaurick's 2nd post indeed doesn't work for even numbers, so it is disqualified.  His first post, however, works for both even and odd, so it is still in the running.

When an even number is given, yes, the first and last lines will show two stars;  the only way for those lines to have 1 star is when the width is odd...

A star in my mind has points. That is why I added spaces.

In that line of my post:

System.out.print((Math.abs(pos/width-offset)+Math.abs(pos%width-offset)<=offset?"*":" ") + (pos%width==width-1?"\n":""));

How can you do it without calling abs twice? You need to call Math.abs twice or else you could add a positive with a negative before the abs and that would not get the same result.

I know he last part for the \n is not performant;)
It was just a trick to squeeze it on a line.

Llaurick

You can do it without abs at all. I still have a bug with even numbers, but I;ll post it soon.

rrz -

llaurick's 2nd post indeed doesn't work for even numbers, so it is disqualified.  His first post, however, works for both even and odd, so it is still in the running.

When an even number is given, yes, the first and last lines will show two stars;  the only way for those lines to have 1 star is when the width is odd...

Oops - sorry about the double post...

rrz -

Your solution is symmetrical for both even and odd numbers.  The more I look at it, the more I like it.  I'll think about changing my requirements in the future.

llaurick -

In my solution, I call Math.abs() exactly once;  since you're calling it twice per character, there is room for improvement...

Not using abs.  this could be crammed into fewer lines, but that just seems silly:

public Star(final int width) {
     int nOffset = (width % 2 == 0) ? 1 : 0;
     int n = (width + 1)/2 + nOffset;
     for (int x = 0; x <= width; x++) {
          for (int y = 0; y <= width; y++) {
               if (y > (-x + n - nOffset) && y < (-x + 3 * n - (nOffset * 2)) && y > (x - n + nOffset) && y < (x + n))
                    System.out.print("*");
               else
                    System.out.print(" ");
          }
          System.out.println();
     }
}

Not using abs.  this could be crammed into fewer lines, but that just seems silly:

public Star(final int width) {
     int nOffset = (width % 2 == 0) ? 1 : 0;
     int n = (width + 1)/2 + nOffset;
     for (int x = 0; x <= width; x++) {
          for (int y = 0; y <= width; y++) {
               if (y > (-x + n - nOffset) && y < (-x + 3 * n - (nOffset * 2)) && y > (x - n + nOffset) && y < (x + n))
                    System.out.print("*");
               else
                    System.out.print(" ");
          }
          System.out.println();
     }
}

As you all know, there's always more than one way to do things in programming, and it is always possible to have multiple "correct" answers.  What I look for, when asking this question, is how someone solves a particular problem.

I would prefer an answer that is short, yet still readable (i.e. not have 25 things on one line).  The logic should be evident, and should represent the process that was used to solve the question.  I also like to see efficiency (i.e. there's no need to constantly recalculate a variable that doesn't change).  So, let me run down some of the noteworthy solutions so far:

1.  heyhey  - He's the only one that avoids Java's inefficient console printing routines by printing a line at a time.  All of the other solutions (mine included), print out one character at a time.

2.  llaurick - Short and to the point;  pretty straightforward.

3.  rrz - The only code to maintain symmetry for both even and odd widths.  This shows the ability to go beyond the stated requirements, and produce a proper solution, even with flawed specifications :)

4.  bazarny  - Also short and to the point.  Could be simplified (i.e. remove the Math.abs calls) by keeping an extra state variable around).

I have one more observation.
If the <number> is 1 then the output is just *  
Then that looks like a star.  
If the <number> is 2 then the output of most of these solutions is **  which has the wrong form.
If <number> is large then the the form is more of a star.

rrz -

Yes, you are correct.  Usually the Star program only needs to work with odd numbers greater than 3.  I didn't specify that in the beginning, but if I had, I doubt you would have posted your excellent version that works equally well with any number.

I don't know how the rest of you solved this problem, but here's how I did it.  First of all, the star is symmetrical - i.e. the top half is a mirror of the bottom half, and the left side is a mirror of the right side.  This means that I only have to draw 1/4th of the star, and the rest is just a mirrored copy.  

First, I set up a grid that was width x width spaces, since a star that is 5 wide will be 5 tall.  That's pretty basic.  Now I am able to reference the cells of this grid with the basic row/column terminology.

Next, I saw two fixed lines (i.e. all '*' characters):  one at the very middle of the star where the row = (width/2) + 1, and one at the center line, where column = (width/2) + 1.  Since this middle point is the same for both rows and columns, I calculated it once up front and saved it:

int mid = (width/2) + 1;

The next thing I did was set up my for() loop to print out each row:

for( int row = 1; row <= width; row++ )
{
    /* print out the current row */
    System.out.println();
}

Now, since I was going for compactness, I decided to roll the println() into the for loop:

int mid = (width/2) + 1;

for( int row = 1; row <= width; row++, System.out.println() )
{
    /* print out the current row */
}

To further compact the code, I decided to also roll in the definition of the mid-point into the for loop:

for( int row = 1, mid = (width/2)+1; row <= width; row++, System.out.println() )
{
    /* print out the current row */
}

After this, I thought I had enough stuff in the first for loop :-).  Now, I had to figure out how to print the individual columns.  Looking at a 5x5 star, we see the following pattern:

Row 1:  one *    (drawn only on the center line mid-point)
Row 2:  three *  (one * on each side of the center line)
Row 3:  five *   (two * on each side of the center line)
Row 4:  three *  (one * on each side of the center line)
Row 5:  one *    (drawn only on the center line mid-point)

Rows 1 and 5 are the same, rows 2 and 4 are the same, row 3 is the mid point.

Here, I decided to use a pivot point - i.e. any cell that was greater than or equal to this pivot point away from the center line would be drawn as a space.  If it was closer, it would be a *.  Also, the pivot needs to be recalculated for each row, since each row has a different number of stars.

Therefore, by taking the mid point and subtracting the current row, we find the pivot point for that particular row.  In a 5x5 star, in the first row we would have:

Mid point = 3
Row = 1 (on the first row)
Pivot = 3 - 1 = 2

So, in the first line, cells that are in columns 1 and 2 would contain spaces, since:

 column 1:  1 <= 2  == true, print a space
 column 2:  2 <= 2  == true, print a space
 column 3:  3 <= 2  == false, print a star

Now, this doesn't work once you pass the pivot point, so we'll also need to check the column to see if it exceeds the pivot on the right hand side of the center line.  This can be done by subtracting the pivot from the width of the star.  Therefore:

 column 3:  3 > (5-2) == false, print a star
 column 4:  4 > (5-2) == true, print a space
 column 5:  5 > (5-2) == true, print a space

So far, this works for the upper half of the star.  It quits working as soon as we go to the bottom half of the star, since now the row numbers are greater than the mid point.  Here, we have to use the Math.abs() to keep us on track.  We can now define the pivot point for each row as:

int pivot = Math.abs( mid - row );


Using the logic from above, we can complete the program as follows:

for( int row = 1, mid = (width/2)+1; row <= width; row++, System.out.println() )
{
    int pivot = Math.abs( mid - row );
 
    for( int col = 1; col <= width; col++ )    // loop once for each column
    {
        if( col <= pivot  ||  col > (width - pivot) )
        {
            System.out.print( " " );
        }
        else
        {
            System.out.print( "*" );
        }

    }
}


From here, it is a simple matter of collapsing the statements to make them more efficient.  First of all, we can get rid of the if/else block and condense the two System.out.print() calls by using the ? : operator:

     System.out.print( (col <= pivot || col > (width-pivot)) ? " " : "*" );

then we can roll in the pivot calculation into the for loop:

   for( int col=1, pivot=Math.abs(mid-row); col <= width; col++ )


Which leaves us with the final program, consisting of just three statements:  two for loops and a print:

for( int row = 1, mid = (width/2)+1; row <= width; row++, System.out.println() )
{
    for( int col=1, pivot=Math.abs(mid-row); col <= width; col++ )
    {
        System.out.print( (col <= pivot || col > (width-pivot)) ? " " : "*" );
    }
}


since there's only 1 statement after each for loop, the braces are unnecesary, so the program can be reduced to just three lines:

for( int row = 1, mid = (width/2)+1; row <= width; row++, System.out.println() )
    for( int col = 1, pivot = Math.abs(mid-row); col <= width; col++ )
        System.out.print( (col <= pivot || col > (width-pivot)) ? " " : "*" );

-----------------------------------------------------------------------------------------

Anyway, that's the way I did it.  Questions, comments or ridicule????

nebeker thanks for  challenge it was fun.
Question:
Why is more efficient to stuff your "for" statements ?
Comment:
Most elegant solution for creating a star!
heyhey's first post

rrz -

When I first came across this puzzle, there were two pieces:  first, get the code to work properly, and second, to condense it into as few lines as possible, without losing readability....

From a compiled code standpoint, it doesn't make any difference at all if the midpoint and pivot values are before or inside the for() loop...

I like heyhey's code -- especially the simple reuse of the character array.  It's not compact by any means, but it is elegant :-)...   Of course, I never did specify compactness in my requirements.

His second version, though....  :(   I think it's interesting, but just doesn't strike me as elegant..

Hi,

Nice discussion, thanks. It's pity that everything happened during the night in my time zone :(.
Few things I never take into acoount in real life:

> since there's only 1 statement after each for loop, the
> braces are unnecesary, so the program can be reduced to
> just three lines:

I never omit braces around loop, if, and else body. Please don't start style wars. It's my style, you are free to keep yours.

> From a compiled code standpoint, it doesn't make any
> difference at all if the midpoint and pivot values
> are before or inside the for() loop...

I prefer more readable code. I believe that squizing mid and println into for header decrease code readability.

As for my solution, idea was pretty simple. We were supposed to draw 'circle' when distance is measured in a way I wrote:
dist((x1,y1),(x2,y2)) = abs(x1-x2)+abs(x2-y2)
filled circle with radius r and center (a,b) defined by
dist((x,y)(a,b)) <= r
For r,a,and b we have width/2 (y axis pointing down)
Plus some tweaking to get it work with integers.
Pretty simple math, directly reflected in my code. Of course it could be more compact or more efficient, but I like my version because it direcly reflects solution idea (for those who can remember a bit of math).

Regards,
Igor Bazarny,
Brainbench MVP for Java 1
www.brainbench.com

hi all :)

some comments:

1. my first solution can be easily modified to not print last LF.

2.
> since I wanted everything to be in the constructor

hey that's OO language right ? :)
my second solution is the only solution that does not use any for / while statements - it uses pure recursion do to what's needed. (well, there is one for statement that initalizes the array, but it can be removed with another recursion)

anybody remembers LOGO laguage ? :)

3. nebeker three-statement solution prints one new line in front of the star for even numbers - try it yourself.

and here is my last solution - I've removed all comments, so you'll have to try it yourself
(wel, it's a kind of rip-off of nebeker solution :)

  public Star(final int width)
  {
    for(int i = 0, mid = (width+1)/ 2, col = 0, row = 0, pivot = mid - 1; (i < width * width); i++, col = i % width, row = i / width, pivot = Math.abs(mid-row-1))
      System.out.print( ((col <= pivot - 1 || col >= (width-pivot)) ? " " : "*") + ((col == width - 1)?"\n": ""));
  }

 

my final suggestion has only two 'statements'.

nevertheless I don't think that I'll hire coder that gives me such answer for a long-term Java project :) (Long Live C !)

now let's move to phase 2 of the game - let's give all the solutions to some Java coder and ask him to guess what's the app supposed to do.
best solution will be consider the one that takes least time to understand :)

(and please, excuse my english again)

what about creating smallest .java / .class file ? :)

correction

star with size 6 will have only five rows, so you need to adjust the code. below is my final solution:

  public Star(final int width)
  {
    for(int i = 0, max = width * (width - (width + 1) % 2), mid = (width+1)/ 2, col = 0, row = 0, pivot = mid - 1; i < max; i++, col = i % width, row = i / width, pivot = Math.abs(mid-row-1))
      System.out.print( ((col <= pivot - 1 || col >= (width-pivot)) ? " " : "*") + ((col == width - 1)?"\n": ""));
  }

 That's quite impressive... Most of you have come up with some really amazing solutions. But I will have to agree with someone who said the heyhey's solution is th emost elegant.

P.S. If I did not know what this piece of code is supposed to do I do not think I could be able to understand what most of the solutions are doing. And I am an average programmer.

Nebeker:
You did say in your question:
>I'll award the points to the shortest, clearest, most elegant solution
So you DID specify shortest...
But my solution was in no way clear, I'll admit.
I like the way you put the System.out inside the for loop. I did not thaugh of that one.

I like Heyhey recursive solution. Would make a real nice question for students:
What does that code print??

And Heyhey: I do teach LOGO to my 7 years old boy;)

Llaurick

bazarny -

In production code, I do not omit the braces.  And in production code, I wouldn't have rolled the midpoint and pivot declaractions into the for() loop.  But, this wasn't production code -- it is simply a fun thing to write to stretch your mind a little.

I also prefer readable code, along with comments -- which, by the way, NO ONE bothered to include in their code :-)


heyhey -

While I applaud your use of recursion, I also have to say that it is also a lot less obvious when it comes to figuring out what the code does.  That's the primary problem with recursion:  it takes a lot more effort to understand what the code does.

Your last answer looks too much like llaurick :).  As for the second part of giving these programs to a Java programmer -- well... since these programs weren't written with readability in mind, I would sure pity that programmer....


girionis -

I fully understand your comment ("If I did not know what this piece of code is supposed to do I do not think I could be able to understand what most of the solutions are doing").

Most code (that does something non-trivial) is that way.  That's why COMMENTS are necessary.  Code should be heavily commented, because, regardless of what some people think, THERE IS NO SUCH THING AS SELF-DOCUMENTING CODE.

> While I applaud your use of recursion, I also have to say that it is also a lot less obvious when it
comes to figuring out what the code does.

you already said that this is a fun contest.

> Your last answer looks too much like llaurick :)

nope.
I started with your "3 statement" answer, aiming to make it "2 statement" answer. you do not need two for loops for such a simple task :)

anyway when contest does not have good rules, there is no winner ...

heyhey -

You don't need good rules to have a winner.  When I said that the winner would have to have "elegant" code, that should have tipped you off to the fact that the winner would be arbitrary.  While it is possible for people to agree that two solutions are elegant, getting them to agree on which one is "most" elegant just isn't going to happen -- it's just like style wars on brace placement...

I like your first post - although you seem attached to your recursion-based answer :-)

I guess my personal bias against recursion is just showing through here...  It is a powerful technique, but I don't think it should be used unless absolutely necessary.

Anyway, here are my choices:

Overall winner:  heyhey's first post

Runner up:  rrz's solution that is always symmetrical.  Your runner-up points are here:

https://www.experts-exchange.com/jsp/qManageQuestion.jsp?ta=java&qid=20263832

Thanks to everyone for participating.  I'll post a few more of my interview questions in the future -- if anything, it helps me find the flaws in the way I present these questions to people....

all my three suggestions are just experiments with different techniques.

recursive suggestion is LISP-like solution, last one is ugly C-like solution and the first one (my favourite) is human-readable solution.

btw. it was a real fun to work on this question.

whow

and thanks for the points !

 It would be interesting to see though how long took each one of you to come up with your solutions...

heyhey -

like you really need the point :-)

girionis -

When I first did this, I think I spent 15 minutes or so.

Mine took 5 minutes to code, about 20 to think through.  The bulk of my time was unnecessary because I used a mathematics-based approach, noticing that the star is bound by four lines defined by y = mx + b and it's been about 10 years since I've graphed functions (even simple lines), so I had to whip out the graph paper and count squares...

I spent 10-15 minutes deciding what's the best approach and maybe 5 more to write the code and test it.

I cannot recall why I decided against the two most obvious solutions:
- 'go over all pixels and find out which ones must have asterisk'
- 'go over all lines and calculate asterisks offest and length

It seems that I based my original solution on the second approach - I just didn't feel like printing one symbol at a time.

 It took me about 10' to think about it and about 5' more to code it. So a total of about 15'. It was the simplest and most basic anyone could write. It would actually take me hours to think of one that works in ony 2 lines. I never thought to put multiple conditions inside the for loop, and certainly never thought to use recursion.

girionis -

This is one of the reasons that programmers should always review other people's code:  it's an opportunity to discover new ways at looking at a problem that you never would have come up with on your own.

This is also one of the reasons I'm an ardent proponent of code reviews on all my projects.  Not only does it help root out bugs in the code before it gets to production, it exposes junior team members to some of the slick, advanced techniques used by more experienced programmers.

It also serves to show the more experienced programmers, who are generally set in their ways :-), that there *is* indeed more than one way to solve a problem.

As far as squeezing the program into two lines, all that really requires is a fundamental knowledge of how to abuse your favorite language....

Java, of course, isn't much fun to abuse.  There's no pre-processor...

Abusing C, on the other hand....  Now there's some fun.