designing algorithms

this code below has been copied and annotated from the C++ section,

Code:

using System;


class Test
{
	 
	
	
	static void Main(string[] args)
	{
		int t, space, star; 
			int outer=5;//set final value of control variable 

			//top of diamond - outer loop
			for (t = 1; t <= outer; t++)//control variable t active while  
			{							//less than or equal to outer
				for (space = outer; space >= t; space--)//set control variable 
					Console.Write(' ');//space to outer value
				//while space is greater/or equal to t print space
				for (star = 1; star <= (t * 2 - 1); star++)
					Console.Write('*');
					Console.WriteLine();
			}
			
		
			//bottom of diamond
			for (t = 1; t <= outer - 1; t++)
			{
				for (space = 1; space <= t + 1; space++)//while control variable 
					Console.Write(' ');//space is less than or equal to outer 
									   //control var t + 1 print space
				for (star = 1; star <= outer * 2 - (t * 2 + 1); star++)//7, 5, 3, 1
					Console.Write('*');
				Console.WriteLine();
			}
			
	}
	
}

this program prints a diamond shape, my question is how does one work out the these 2 loops

Code:

for (star = 1; star <= (t * 2 - 1); star++)
	Console.Write('*');
	Console.WriteLine();


for (star = 1; star <= outer * 2 - (t * 2 + 1); star++)//7, 5, 3, 1
	Console.Write('*');
	Console.WriteLine();

previous to seeing this code i had written down a simple flowchart depicting all different stages for each line, as well writing out the sequence of numbers for stars and spaces. is it purely a maths calculation to work out the line...

Code:

for (star = 1; star <= outer * 2 - (t * 2 + 1); star++)//7, 5, 3, 1

or is there a method to this ?

i would have taken forever to get to this without seeing this code, i guess some people are quick problem solvers or they have solved many similar problems

what are your thoughts?

There's many ways to print a diamond. Consider a diamond with a "radius" of 2:

Code:

  *      radius of 2
 *** 
*****
 *** 
  *

The next step I took to create an algorithm was to note the coordinates of each spot where a * was printed:

Code:

        0,2        radius of 2
    1,1 1,2 1,3
2,0 2,1 2,2 2,3 2,4
    3,1 3,2 3,3
        4,2

I really don't know how to describe the next step. It seemed to me that taking the absolute value of the difference of both the row and the radius and the column and the radius might help. So, I wrote those down:

Code:

        2,0
    1,1 1,0 1,1
0,2 0,1 0,0 0,1 0,2
    1,1 1,0 1,1
        2,0

I then noticed a pattern. The sum of those differences were never greater than the radius. I checked the points outside my diamond to make sure I was on the right track:

Code:

4 3 2 3 4
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4

Then I coded it up and tested it for a few other cases. Looks like it works to me.

Code:

static void PrintDiamond(int radius)
{
	Debug.Assert(radius >= 0);

	int diameter = radius * 2 + 1;
	for (int line = 0; line < diameter; line++)
	{
		for (int col = 0; col < diameter; col++)
		{
			if (Math.Abs(col - radius) + Math.Abs(line - radius) <= radius)
				Console.Write("*");
			else
				Console.Write(" ");
		}
		Console.WriteLine();
	}
}

I can't really explain how to come up with an algorithm like that. It's just about finding the patterns.

EXCELLENT POST (excuse my shouting, i thought in this case it was appropriate)

thanks pianorain

Originally Posted by pianorain

I can't really explain how to come up with an algorithm like that. It's just about finding the patterns.

I agree with this statement. Designing algorithms is a very personal thing that comes from your experience.

I would suggest that if you struggle with coming up with ways to solve problems, just practice practice practice!

Originally Posted by CompiledMonkey

I agree with this statement. Designing algorithms is a very personal thing that comes from your experience.

I would suggest that if you struggle with coming up with ways to solve problems, just practice practice practice!

Aye, and most of that practice should be away from the compiler. Implementing an algorithm is trivial compared to designing an algorithm. In the above example, I spent around 20 minutes playing with the numbers, looking for patterns. It took less than 2 minutes to code.

In my opinion, that's where most programmers fail. They code before they design. If you plan it all out in detail, then coding becomes far easier. I prefer using some sort of spreadsheet (like Excel) and a notepad. No, not Notepad, but a real paper-and-pen notepad with several colors of pens. You can't beat paper for the ease of associating ideas, and Excel is nice for mass number-crunching. Assigning each idea or concept a color of ink keeps all the numbers straight, making it easier to absorb.

Originally Posted by pianorain

Aye, and most of that practice should be away from the compiler. Implementing an algorithm is trivial compared to designing an algorithm.

Correct again. So many people hear a problem and jump to the IDE. Sit down, bust out a pencil and some paper, and think through it visually. It's funny, but every interview I've had with Google and Microsoft has been away from a computer, and hopefully everyone can now see why.