Thread: Algorithms - Draw a Box

  1. #1
    Registered User
    Join Date
    Jan 2014
    Posts
    17

    Algorithms - Draw a Box

    So I recently attempted the following exercise:

    Write a program that reads in the size of the side of a square and then prints a hollow squareof that size out of asterisks and blanks. Your program should work for squares of all side sizes be-tween 1 and 20 .
    My solution?
    Code:
    #include <iostream>
    
    
    int main()
    {
        int size;
        int row = 1;
        int col = 1;
        
        std::cout << "Enter size of square: ";
        std::cin >> size;
        
        while ( row <= size)
        {
            while (col <= size)
            {
                if (row == 1)
                    std::cout << "*";
                else if (row != size)
                {
                    if (col == 1)
                        std::cout << "*";
                    else if (col!= size)
                        std::cout << " ";
                    else if (col == size)
                        std::cout << "*";
                }
                else if (row == size)
                    std::cout << "*";
                col++;
            }
            std::cout << "\n";
            col = 1;
            row++;
        }
    }
    I'm not too happy with it, it feels like a kludged solution. In the real world how important is it to make an elegant and concise algorithms vs one that simply works?

    Working out the algorithm was the hardest part for me that involved a lot of trial and error. How would you organize your thinking to solve a problem like this?

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by jaxdid View Post
    So I recently attempted the following exercise:



    My solution?
    Code:
    #include <iostream>
    
    
    int main()
    {
        int size;
        int row = 1;
        int col = 1;
        
        std::cout << "Enter size of square: ";
        std::cin >> size;
        
        while ( row <= size)
        {
            while (col <= size)
            {
                if (row == 1)
                    std::cout << "*";
                else if (row != size)
                {
                    if (col == 1)
                        std::cout << "*";
                    else if (col!= size)
                        std::cout << " ";
                    else if (col == size)
                        std::cout << "*";
                }
                else if (row == size)
                    std::cout << "*";
                col++;
            }
            std::cout << "\n";
            col = 1;
            row++;
        }
    }
    I'm not too happy with it, it feels like a kludged solution. In the real world how important is it to make an elegant and concise algorithms vs one that simply works?

    Working out the algorithm was the hardest part for me that involved a lot of trial and error. How would you organize your thinking to solve a problem like this?
    I wouldn't worry about it too much. Refinement comes naturally with experience, and you can always spend time on such things when you have nothing better to do. In the meantime, just concentrate on creating programs that work correctly.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    Quote Originally Posted by jaxdid View Post
    So I recently attempted the following exercise:



    My solution?
    Code:
    #include <iostream>
    
    
    int main()
    {
        int size;
        int row = 1;
        int col = 1;
        
        std::cout << "Enter size of square: ";
        std::cin >> size;
        
        while ( row <= size)
        {
            while (col <= size)
            {
                if (row == 1)
                    std::cout << "*";
                else if (row != size)
                {
                    if (col == 1)
                        std::cout << "*";
                    else if (col!= size)
                        std::cout << " ";
                    else if (col == size)
                        std::cout << "*";
                }
                else if (row == size)
                    std::cout << "*";
                col++;
            }
            std::cout << "\n";
            col = 1;
            row++;
        }
    }
    I'm not too happy with it, it feels like a kludged solution. In the real world how important is it to make an elegant and concise algorithms vs one that simply works?

    Working out the algorithm was the hardest part for me that involved a lot of trial and error. How would you organize your thinking to solve a problem like this?
    I can only give how I've worked out similar things. The first part is figuring out exactly what the program needs to do (draw a square). Then figure out the basic information the system will need in order to do this (moveable x,y coordinates, some sort of printing/rendering function).

    So your solution seems adequate for the problem (which is what really matters). As for improvements, I would probably build your system into a class. That way you could build methods such as SetHeight(), SetWidth(), Draw(), ect. The best thing about doing it this way is that you can reuse, and build on your own code.

  4. #4
    Registered User
    Join Date
    Jan 2014
    Posts
    17
    I ended up looking the official answer book and they actually used a similar method. They managed to do it in one while loop by properly working down the exceptions.

  5. #5
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    Quote Originally Posted by jaxdid View Post
    I ended up looking the official answer book and they actually used a similar method. They managed to do it in one while loop by properly working down the exceptions.
    If you think about it, the string you need to create the sides of a rectangle is always TopWidth - 2 in width(you subtract 2 because it is "up to but not including" the character representing the sides). You can use this to create rectangles of arbitrary dimensions pretty easily (especially if you use a string object to add the spaces in).

    Normally in graphical programming, you need at least 4 values to describe a rectangle - x , y , width , height. Some other ways would be - top , right , bottom , left ; or 2 points - (x, y) , (x, y). All these contain the same information as the first, it's just separate ways you can look at it.

    If your looking for a challenge (?), a good one would be to work out a way to represent the x and y components of your rectangle. In other words, how would you make the rectangle print anywhere on the console? Just a thought .

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Cool

    Quote Originally Posted by Alpo View Post
    Normally in graphical programming, you need at least 4 values to describe a rectangle - x , y , width , height. Some other ways would be - top , right , bottom , left ; or 2 points - (x, y) , (x, y). All these contain the same information as the first, it's just separate ways you can look at it..
    Here's a fun exercise/puzzle: How to represent a rectangle on a plane with just 3 values?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  7. #7
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    Quote Originally Posted by Sebastiani View Post
    Here's a fun exercise/puzzle: How to represent a rectangle on a plane with just 3 values?
    Do you mean simple/ primitive values? I mean technically you could do it with one large value if you just stuffed everything into a 64 bit integer type or something lol, but I'm guessing this doesn't use a trick like that?

    Hrm.. Off the top of my head I was thinking you could maybe use something like the hypotenuse formula, but I don't think that's it as you still need 2 values for the coordinates I believe.

    I'm stumped, I'll have to think a while on it.

  8. #8
    Registered User
    Join Date
    May 2009
    Posts
    3,783
    Quote Originally Posted by Sebastiani View Post
    Here's a fun exercise/puzzle: How to represent a rectangle on a plane with just 3 values?
    For this problem; would 2 points - (x1, y1) , (x2, y2) count as two values?

    If yes, I know how to solve your puzzle.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Sebastiani View Post
    Here's a fun exercise/puzzle: How to represent a rectangle on a plane with just 3 values?
    (x2-x1)/x1, (y2-y1)/y1, (x2-x1)^2+(y2-y1)^2


    Does that work? The ratio of each side to its position, and the length of the diagonal (squared). I can't quite work out how you'd get the position from that, but it seems like enough information. You might need an extra bit to differentiate rectangles in quadrant 1 from quadrant 3 and the like, but you can use the sign bit of the last value.
    Last edited by King Mir; 09-02-2014 at 08:45 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by stahta01 View Post
    For this problem; would 2 points - (x1, y1) , (x2, y2) count as two values?
    Nope, that's four.

    Quote Originally Posted by King Mir View Post
    (x2-x1)/x1, (y2-y1)/y1, (x2-x1)^2+(y2-y1)^2
    Does that work? The ratio of each side to its position, and the length of the diagonal (squared). I can't quite work out how you'd get the position from that, but it seems like enough information. You might need an extra bit to differentiate rectangles in quadrant 1 from quadrant 3 and the like, but you can use the sign bit of the last value.
    I don't think that gives you what you need to reconstruct it...I tried, but couldn't seem to work out the unknowns.

    So there were two methods I was thinking of, specifically. I'll reveal the hardest first. Imagine two circles centered at the origin and of arbitrary radii. Each circle defines a corner of the rectangle. Now rotate a ray (also centered at the origin) some angle and project it past both circles, right through one of the corners. Substending lines in both directions yields the original rectangle. It's convoluted, and the math is expensive, but it does indeed use just three values: r1, r2, t1.

    The key thing to realize here is that rectangles have certain properties that might be considered "implicit" information. Like we can assume that the sides will be at right angles, and moreover that the shape won't be rotated from the x and y planes.

    As a matter of fact, we can do even better: turns out, it can be done with just two values! Anyone?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  11. #11
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Sebastiani View Post
    Nope, that's four.



    I don't think that gives you what you need to reconstruct it...I tried, but couldn't seem to work out the unknowns.

    So there were two methods I was thinking of, specifically. I'll reveal the hardest first. Imagine two circles centered at the origin and of arbitrary radii. Each circle defines a corner of the rectangle. Now rotate a ray (also centered at the origin) some angle and project it past both circles, right through one of the corners. Substending lines in both directions yields the original rectangle. It's convoluted, and the math is expensive, but it does indeed use just three values: r1, r2, t1.
    That can't work. You're just giving one of the points in polar notation, and the magnitude of the other. But there's still a large number of ways to make a rectangle that has an endpoint on that second circle. Unless I'm misunderstanding you.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithms with C
    By talin in forum C Programming
    Replies: 6
    Last Post: 05-08-2013, 02:52 PM
  2. algorithms
    By Animesh Gaitond in forum Tech Board
    Replies: 2
    Last Post: 10-20-2011, 12:09 PM
  3. algorithms
    By ElastoManiac in forum C++ Programming
    Replies: 7
    Last Post: 04-28-2006, 04:45 AM
  4. Algorithms
    By valar_king in forum C++ Programming
    Replies: 5
    Last Post: 11-17-2002, 04:24 PM
  5. C Algorithms
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 09-28-2001, 02:59 AM