Thread: The Xmas Tree competition results

  1. #1
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660

    The Xmas Tree competition results

    Well there were a total of 8 entries into the xmas tree competion.

    A number of different solutions were tried, though I was somewhat surprised
    to see that there were no recursive entries.

    The competition at the top was pretty strong, with 3 entries in particular
    standing out from the rest. These were from DaveSinkula, DavT and glUser3f.

    As they say, there can be only one winner, and that is
    <drum roll....>
    DavT
    Congratulations!!

    DaveSinkula and glUser3f claim a well-deserved joint second place.

    And so, here are all the entries for you to peruse, along with my comments
    on various aspects of the coding and comments - vague as it is.

    There is a zip file at the end to download all the entries if you want.


    Entry from CornedBee
    Code:
    ///////////////////////////////////////////////////////////////////////////
    // XMAS Competition #1
    // See http://cboard.cprogramming.com/showt...threadid=47777
    // for details.
    
    // Indentation: 4 tab
    
    // This entry by Sebastian "CornedBee" Redl
    
    #include <iostream>
    #include <sstream>
    #include <string>
    #include <stdexcept>
    
    typedef unsigned int uint;
    
    // Functions called from main
    uint get_level(int argc, char **argv);
    void tree(uint level);
    
    /**
     * Entry point for the application.
     * Calls functions to get the argument and to draw the tree.
     */
    int main(int argc, char **argv)
    {
    	using std::cerr;
    
    	uint level;
    	try {
    		level = get_level(argc, argv);
    	} catch(const std::invalid_argument &e) {
    		cerr << e.what() << '\n';
    		return 1;
    	}
    	tree(level);
    }
    
    /**
     * Gets the command line argument.
     * Throws an exception if not enough arguments or wrong format.
     */
    uint get_level(int argc, char **argv)
    {
    	using std::istringstream;
    	using std::invalid_argument;
    	if(argc < 2) {
    		throw invalid_argument("Not enough arguments.");
    	}
    	// Since I can't use lexical cast...
    	istringstream conv(argv[1]);
    	uint level;
    	conv >> level;
    	if(!conv) {
    		throw invalid_argument("Argument must be a positive number or 0.");
    	}
    	return level;
    }
    
    // Functions used by tree
    inline uint sum0tox(uint x);
    void one_level(uint level, uint offset);
    
    /** Draws the tree by calling one_level for each level. */
    void tree(uint level)
    {
    	uint offset = sum0tox(level);
    	for(uint i = 0; i <= level; ++i) {
    		one_level(i, offset);
    		offset -= i;
    	}
    }
    
    /**
     * Draws one level of the tree.
     * The topmost stage is indented by offset space characters.
     * Subsequent levels are drawn less indented.
     * Level 0 is handled specially, as are the first stages of
     * the other levels.
     */
    void one_level(uint level, uint offset)
    {
    	using std::cout;
    	using std::string;
    
    	string soff(offset, ' ');
    	if(level == 0) {
    		cout << soff << "/\\\n";
    		return;
    	}
    
    	string sspace(sum0tox(level-1)*2, ' ');
    
    	// The first stage.
    	cout << string(offset-1, ' ') << "*/" << sspace << "\\*\n";
    
    	// All other stages
    	for(; level > 0; --level) {
    		soff.erase(soff.end()-1);
    		sspace.append("  ");
    		cout << soff << '/' << sspace << "\\\n";
    	}
    	cout << std::flush;
    }
    
    /** Calculates the sum of the sequence 0...x */
    inline uint sum0tox(uint x)
    {
    	return (x&1) ? (((x>>1)+1)*x) : ((x>>1)*(x+1));
    }
    Formatting
    Overall the formatting of the code itself was good. The use of
    space, indentation and positioning of braces was consistent
    throughout.

    Comments
    The comments were fairly light given the nature of the exercise.
    Some you could easily determine from the code, eg
    ("Functions called from main"), some were plain confusing
    ("Since I can't use lexical cast", Ok, why not?) and some were
    simply not explaining the significance of the code which
    followed ("Calculates the sum of the sequence 0...x")

    Functions
    There was a nice decomposition of the problem into functions. The
    only downside was the complete lack of explanation of the sum0tox()
    function. In particular, why inline and what is that complex
    expression actually doing?

    Tests
    A number of tests were performed, and the correct output was seen
    in all of them.

    Overall Score
    4/10


    Entry from curlious
    Code:
    //ASCII christmas tree by Curlious
    //Date 2/12/03
    //source tree.cc
    //compile: g++ tree.cc -o tree.cc
    
    #include <iostream>
    using std::cout;
    using std::endl;
    
    //function to display i spaces
    void space(int i){for (int index=0;index<i;++index) cout<<" ";}
    
    //calculates position of tip of christmas tree where you would put the star
    int star(int bell)
    {
       int sum=0;
       for (int i=0;i<=bell;++i)
         sum=sum+i;
       return sum;
       
    }
    //end function declartions
    
    int main(int argc, char *argv[])
    {
      
      int order=atoi(argv[1]);// convert the argument to a numerical order
      int center=star(order);
      int offset=0;           // offset from center of tree to the right 
      int levelbranch=0;      // ascending index of current level where bells are hung
      cout <<endl<<endl<<endl;// provide a little ceiling room
      //display tip of tree
      space(center);
      cout <<"/\\"<<endl;
      
      for (int level=order;level>=1;--level)
        {
          
          //hang and display bells
          
          space(center-offset-1);  
          cout << "*/";
          space(offset*2);
          cout <<"\\*"<<endl;
          
          //wind your way down a branch
          for (int bellbranch=0;bellbranch<=levelbranch;++bellbranch)
    	{
    	  ++offset;
    	  space(center-offset);
    	  cout << "/";
    	  space(offset*2);
    	  cout << "\\"<<endl;
    	 }
          ++levelbranch;
          
        }
      //plant base and wrapp with ribbons
      space(center-2);
      cout << "@[]&"<<endl;
      cout << "Merry Christmas from Curlious!@"<<endl;
      cout << endl;
    
    }
    Formatting
    The formatting was fairly inconsistent through the code. One function
    was wrapped onto a single line, and indentation varied elsewhere between
    2 and 3 spaces. The sudden change to tabs in main() caused even more
    visual disturbance. The use of blank lines within main() could have been
    better also, for example separating declarations from the first cout
    statement.

    Comments
    The comments were terse, and focussed on explaining what was going on rather
    than why.

    Functions
    The functions were fine in themselves, performing clear well defined
    tasks. Though for me, main() seems a little busy in comparison.

    Tests
    The only failed test was supplying no command line parameter.
    This was indirectly diagnosed by a compiler warning about argc being unused.

    Overall Score
    4/10


    Entry from DaveSinkula
    Code:
    /*
     * Competition 1
     * -------------
     * Draw a xmas tree using ASCII art, as demonstrated below.
     * The input to the program will be a single command line argument indicating
     * the order
     * Eg. xmastree 7
     *
     * The judging will be based on the most elegant solution (whatever that means)
     * But presentation, comments, layout, etc will score big
     *
     * Send your submissions to [email protected]
     */
    #if 0
    Order 0
    /\                                i = 0, j = 0, c = ' ', lead =  0, middle =  0
                                                                                 
    Order 1                                                                      
     /\                               i = 0, j = 0, c = ' ', lead =  1, middle =  0
    */\*                              i = 1, j = 0, c = '*', lead =  0, middle =  0
    /  \                              i = 1, j = 1, c = ' ', lead =  0, middle =  2
    
    Order 2                                                                      
       /\                             i = 0, j = 0, c = ' ', lead =  3, middle =  0
      */\*                            i = 1, j = 0, c = '*', lead =  2, middle =  0
      /  \                            i = 1, j = 1, c = ' ', lead =  2, middle =  2
     */  \*                           i = 2, j = 0, c = '*', lead =  1, middle =  2
     /    \                           i = 2, j = 1, c = ' ', lead =  1, middle =  4
    /      \                          i = 2, j = 2, c = ' ', lead =  0, middle =  6
    #endif
    /*
     * I had a hard time with the spacing variables, so the extrapolation below
     * was most helpful. I was able to clearly see the pattern once I got Order 5.
     */
    #if 0
    Order 3                                                                      
          /\                          i = 0, j = 0, c = ' ', lead =  6, middle =  0
         */\*                         i = 1, j = 0, c = '*', lead =  5, middle =  0
         /  \                         i = 1, j = 1, c = ' ', lead =  5, middle =  2
        */  \*                        i = 2, j = 0, c = '*', lead =  4, middle =  2
        /    \                        i = 2, j = 1, c = ' ', lead =  4, middle =  4
       /      \                       i = 2, j = 2, c = ' ', lead =  3, middle =  6
      */      \*                      i = 3, j = 0, c = '*', lead =  2, middle =  6
      /        \                      i = 3, j = 1, c = ' ', lead =  2, middle =  8
     /          \                     i = 3, j = 2, c = ' ', lead =  1, middle = 10
    /            \                    i = 3, j = 3, c = ' ', lead =  0, middle = 12
    Order 4                           
              /\                      i = 0, j = 0, c = ' ', lead = 10, middle =  0
             */\*                     i = 1, j = 0, c = '*', lead =  9, middle =  0
             /  \                     i = 1, j = 1, c = ' ', lead =  9, middle =  2
            */  \*                    i = 2, j = 0, c = '*', lead =  8, middle =  2
            /    \                    i = 2, j = 1, c = ' ', lead =  8, middle =  4
           /      \                   i = 2, j = 2, c = ' ', lead =  7, middle =  6
          */      \*                  i = 3, j = 0, c = '*', lead =  6, middle =  6
          /        \                  i = 3, j = 1, c = ' ', lead =  6, middle =  8
         /          \                 i = 3, j = 2, c = ' ', lead =  5, middle = 10
        /            \                i = 3, j = 3, c = ' ', lead =  4, middle = 12
       */            \*               i = 4, j = 0, c = '*', lead =  3, middle = 12 
       /              \               i = 4, j = 1, c = ' ', lead =  3, middle = 14 
      /                \              i = 4, j = 2, c = ' ', lead =  2, middle = 16
     /                  \             i = 4, j = 3, c = ' ', lead =  1, middle = 18
    /                    \            i = 4, j = 3, c = ' ', lead =  0, middle = 20
    Order 5                           
                   /\                 i = 0, j = 0, c = ' ', lead = 15, middle =  0
                  */\*                i = 1, j = 0, c = '*', lead = 14, middle =  0
                  /  \                i = 1, j = 1, c = ' ', lead = 14, middle =  2
                 */  \*               i = 2, j = 0, c = '*', lead = 13, middle =  2
                 /    \               i = 2, j = 1, c = ' ', lead = 13, middle =  4
                /      \              i = 2, j = 2, c = ' ', lead = 12, middle =  6
               */      \*             i = 3, j = 0, c = '*', lead = 11, middle =  6
               /        \             i = 3, j = 1, c = ' ', lead = 11, middle =  8
              /          \            i = 3, j = 2, c = ' ', lead = 10, middle = 10
             /            \           i = 3, j = 3, c = ' ', lead =  9, middle = 12
            */            \*          i = 4, j = 0, c = '*', lead =  8, middle = 12 
            /              \          i = 4, j = 1, c = ' ', lead =  8, middle = 14 
           /                \         i = 4, j = 2, c = ' ', lead =  7, middle = 16
          /                  \        i = 4, j = 3, c = ' ', lead =  6, middle = 18
         /                    \       i = 4, j = 4, c = ' ', lead =  5, middle = 20
        */                    \*      i = 5, j = 0, c = '*', lead =  4, middle = 20
        /                      \      i = 5, j = 1, c = ' ', lead =  4, middle = 22 
       /                        \     i = 5, j = 2, c = ' ', lead =  3, middle = 24 
      /                          \    i = 5, j = 3, c = ' ', lead =  2, middle = 26 
     /                            \   i = 5, j = 4, c = ' ', lead =  1, middle = 28 
    /                              \  i = 5, j = 5, c = ' ', lead =  0, middle = 30 
    #endif
    /*
     * My submission...
     */
    #include <stdio.h>
    #include <stdlib.h>
    /*
     * Some might argue that once a program is debugged, the debug code should be
     * deleted. I prefer to use conditional compilation to more easily add it back
     * in, should the need arise or modifications be made.
     */
    #define NDEBUG /* no debug; i.e., "release" version */
    /*
     * This function is the workhorse.
     * Given an order, make a tree as described above.
     */
    void xmastree(int order)
    {
       int height, width;   /* loop indices */
       int top = order + 1; /* we use 'order + 1' in a couple places */
       /*
        * The leading spaces is half of what the total middle spaces will be. And
        * once the pattern is recognized, you can see that it begins at:
        *
        *   order * (order + 1) / 2
        */
       int leading_spaces = order * top / 2;
       /*
        * The number of middle spaces begins at zero and is increased by 2 every
        * 'width' that we don't have an ornament to hang.
        */
       int middle_spaces = 0;
    
    #ifndef NDEBUG
       printf("Order %d\n", order);
    #endif
    
       /*
        * Tree height.
        * Loop from 0 to order + 1. This ensures we have a tree for order 0.
        */
       for ( height = 0; height < top; ++height )
       {
          /*
           * Tree width.
           * The width may be different for each 'sub-height'.
           */
          for ( width = 0; width <= height; ++width )
          {
             /*
              * Place an ornament at the start of every new 'height' except for
              * the first.
              */
             int ornament = height && !width;
    
    #ifndef NDEBUG
             printf("i = %d, j = %d, lead = %2d, middle = %2d:", 
                    height, width, leading_spaces, middle_spaces);
    #endif
    
             /*
              * Increment by two the number of middle spaces if we don't have an
              * ornament to hang.
              */
             if ( width )
             {
                middle_spaces += 2;
             }
             /*
              * Add in the leading spaces. (My attempt at 'elegance'.)
              */
             printf("%*s", leading_spaces, "");
             /*
              * Add the ornament if it is time.
              * Otherwise, it is time to decrement the number of leading spaces.
              */
             if ( ornament )
             {
                putchar('*');
             }
             else
             {
                --leading_spaces;
             }
             /*
              * Add the tree outline. (Another attempt at 'elegance'.)
              */
             printf("/%*s\\", middle_spaces, "");
             /*
              * Again, add the ornament if it is time.
              */
             if ( ornament )
             {
                putchar('*');
             }
             /*
              * We're done with the current 'width'.
              */
             putchar('\n');
          }
       }
    }
    /*
     * The C entry point. The program accepts a command-line argument indicating
     * the "order" of the tree. This value will be the first argument.
     */
    int main(int argc, char *const *argv)
    {
       /*
        * First make sure that the user actually provided the argument.
        * Otherwise, let's try to help them out.
        */
       if ( argc > 1 )
       {
          /*
           * Using atoi is not the most bulletproof number conversion method.
           * But we aren't striving for a robust program, merely one that produces
           * the required output for the *intended* usage.
           */
          xmastree(atoi(argv[1]));
       }
       else
       {
          puts("usage: exename order");
       }
       return 0;
    }
    
    #if 0 /* sample output */
    C:\test>test 0
    /\
    
    C:\test>test 1
     /\
    */\*
    /  \
    
    C:\test>test 2
       /\
      */\*
      /  \
     */  \*
     /    \
    /      \
    
    C:\test>test 3
          /\
         */\*
         /  \
        */  \*
        /    \
       /      \
      */      \*
      /        \
     /          \
    /            \
    
    C:\test>
    #endif
    Formatting
    The formatting was nice and consistent throughout the code. Although
    not a formatting issue, the debug flag
    #define NDEBUG
    should not be in the code, but should be driven from the command line.

    Comments
    There are plenty of comments explaining what is going on, and why.
    In particular, an explanation of how critical formulas were derived.
    One very curious comment was "if we don't have an ornament to hang."
    being followed by
    if ( width )

    Functions
    Although the code only contains a single function to do all the work,
    it is no less clear for being so.

    Tests
    A number of tests were performed, and the correct output was seen
    in all of them.

    Overall Score
    8/10


    Entry from DavT
    Code:
    /*-----------------------------------------------------------------------*/
    /* xmastree.c - entry by DavT into Salem's Christmas coding contest #1   */
    /*-----------------------------------------------------------------------*/
    
    #include <stdlib.h>
    #include <stdio.h>
    #include <ctype.h>
    
    /* symbols used to draw the tree */
    static const char LBRANCH[]     = "/";
    static const char LBRANCHSTAR[] = "*/";
    static const char RBRANCH[]     = "\\";
    static const char RBRANCHSTAR[] = "\\*";
    
    /*------------------------------------------------------------------------*/
    /* function:    drawTree()                                                */
    /* input:       order - order of tree to draw                             */
    /* return:      void                                                      */
    /* decription:  draws the xmas tree order by order. the algorithm uses a  */
    /*              number of features of the required output.                */
    /*                - each order is made up of order+1 lines                */
    /*                - the first line of each order has '*' - except order 0 */
    /*                - the no. spaces sperating '/' and '\' increases by one */
    /*                  for each line except when starting a new order.       */
    /*                - the number of spaces seperating '/' and '\' at the    */
    /*                  bottom of the tree can be calculated as 2*rMax        */
    /*                  where rMax = (0+1+2+...+order)+1. this is             */
    /*                  calculated using the formula for a geometric          */
    /*                  progression                                           */
    /*------------------------------------------------------------------------*/
    static void drawTree (unsigned int order)
    {
      unsigned int r = 0;     /* radius of current layer of the tree measured */
                              /* from the center to the inside of the branch  */
    
      unsigned int rMax = ((order+1)*(order))/2 + 1;    /* max radius         */
      unsigned int o, h;
    
      /* order 0 is a special case ... */
      printf("%*s%*s\n",rMax+1,LBRANCH,1,RBRANCH);
    
      /* all other orders follow a common algorithm */
      for (o = 1; o <= order; o++) {
        printf("%*s%*s\n",rMax-r+1,LBRANCHSTAR,2*r+2,RBRANCHSTAR);
        for (h = 1; h <= o; h++) {
          r++;
          printf("%*s%*s\n",rMax-r+1,LBRANCH,2*r+1,RBRANCH);
        }
      }
    }
    
    /*------------------------------------------------------------------------*/
    /* function:    main()                                                    */
    /* input:       argc - must be 2                                          */
    /*              argv - argv[2] = order. must be unsigned int.             */
    /* return:      int  - always returns 0                                   */
    /*------------------------------------------------------------------------*/
    int main (int argc, char * argv[])
    {
      if ((argc == 2) && (isdigit(argv[1][0]))) {
        drawTree(atoi(argv[1]));
      }
      else {
        fprintf(stderr, "usage: %s <order>\n", argv[0]);
        fprintf(stderr, "  order = positive integer\n");
      }
    
      return 0;
    }
    Formatting
    The formatting was nice and consistent throughout the code.
    One small point on scope would suggest that the const strings
    would be inside the function. The upper-case names suggest that
    these were macros at some point.

    Comments
    The function comments pretty much explained all that is going on inside
    the function. They were both concise and informative.
    The spelling of "sperating" is but a minor nit.

    Functions
    Again, this example contains only one function to do all the work,
    but it is clearly explained, and performs the task it is supposed to do.

    Tests
    A number of tests were performed, and the correct output was seen
    in all of them.

    Overall Score
    9/10


    Entry from glUser3f
    Code:
    /**
     *  CProgramming.com Xmas Competition #1
     *  Programmer: glUser3f
     *  E-Mail: [email protected]
     *
     *  This program draws an Xmas tree using ASCII art
     *  Program command-line input: accepts 1 integer as order
     */
    
    #include <cstdlib>  // for int atoi(const char*)
    #include <iostream> // for cout, endl
    using std::cout;
    using std::endl;
    
    /**
     *  function: ParseCmdLine
     *   parses command-line input and returns Xmas tree order
     *   param argc: command-line arguments count, passed in by OS
     *   param argv: command-line arguments array, passed in by OS
     *   return: Xmas tree order, or -1 on invalid input
     */
    int ParseCmdLine(int argc, char* argv[]);
    
    /**
     *  function: DrawXmasTree
     *   draws the Xmas tree
     *   param order: Xmas tree order
     */
    void DrawXmasTree(int order);
    
    /**
     * function: SkipSpaces
     *  skips cells on the same line by outputting white spaces
     *  param count: number of cells to skip
     */
    void SkipSpaces(int count);
    
    /**
     *  function: main
     *   program main entry
     */
    int main(int argc, char* argv[]) {
    	int order = ParseCmdLine(argc, argv);
    	if (order == -1) {
    		cout << "Usage: xmastree [order]" << endl;
    		return 0;
    	}
    	DrawXmasTree(order);
    	return 0;
    }
    
    /*
    ** Description of how DrawXmasTree works:
    ** The function draws the tree by looping 0 to order+1, drawing a "layer" each time.
    ** A layer is drawn by looping 0 to layer+1, drawing a line, or "level," each time.
    ** There are 2 tricks one should solve to get DrawXmasTree to work:
    ** 1. calculating how many white-spaces should be skipped before drawing the first
    **    part of the tree ( / or * / )
    ** 2. calculating how many white-spaces should be skipped before drawing the second
    **    part of the tree ( \ or \* )
    ** To solve the problems, let's see how these 2 variables (1.skip and 2.width)
    ** change when moving from one line to the next, to simplify things, I'll assume that
    ** asterisks aren't required right now, I'll add them later.
    **
    ** #1# skip:
    ** First, we can notice that skip is always either getting decremented or keeping its
    ** current value, therefore, when the function starts, skip should be given a value 
    ** large enough to prevent it from reaching a negative value later (I'll explain how
    ** to calculate this value later)
    **
    ** skip
    ** | |
    **    /\    skip = 3 (layer 0)
    **    /\    skip = 3 (layer 1)
    **   /  \   skip = 2 (layer 1)
    **   /  \   skip = 2 (layer 2)
    **  /    \  skip = 1 (layer 2)
    ** /      \ skip = 0 (layer 2)
    **
    ** So, skip keeps its current value when moving to the next layer, and is decremented 
    ** when we are in the same layer.
    **
    ** #2# width
    ** Apparently, width starts with a value of 0.
    **
    **    /\    width = 0 (layer = 0)
    **    /\    width = 0 (layer = 1)
    **   /  \   width = 2 (layer = 1)
    **   /  \   width = 2 (layer = 2)
    **  /    \  width = 4 (layer = 2)
    ** /      \ width = 6 (layer = 2)
    **
    **  |____|
    **  width
    **
    ** First of all, width should always be an even number, otherwise the tree won't
    ** look OK.
    ** Once again, we can notice that width either gets incremented by 2 (when we are in the 
    ** same layer), or keeps its current value (when moving to the next layer).
    **
    ** We still have 2 problems to solve, the first problem is adding asterisks to the output,
    ** which can be solved easily by checking if we have started a new layer, and then skipping
    ** skip-1 (because an additional asterisk is printed), we also print * / and  \* instead of just
    ** / and \ as the left part of the tree.
    ** The final problem is calculating the initial value of skip, which involves some basic
    ** math, if we examine the previous ASCII art, we can notice that:
    ** Initial value of skip = Final value of width / 2
    ** final value of width = (Count of levels - Count of layers) * 2
    ** Because for each level, we increase width by 2, except when moving to a new layer.
    **                   order+1
    ** Count of levels = Sigma(i) = (order+1)*(order+2)/2
    **                     0
    ** Count of layers = order+1
    ** => Initial value of skip = (order+1)*(order+2)/2 - (order+1)
    **
    ** Initial value of skip = (order*order + order) / 2
    **
    ** Phew, now that was long! Let's "dive" into DrawXmasTree code ;)
    **
    */
    
    /*
     * ================
     *  DrawXmasTree
     * ================
    */
    void DrawXmasTree(int order) {
    	int skip = (order * order + order) / 2; // Initial value of skip
    	int width = 0; // Initial value of width
    
    	// Loop 0 to order+1, drawing a layer each time
    	for (int layer = 0; layer < order + 1; layer++) {
    		// Loop 0 to layer+1, drawing a level(line) each time
    		for (int level = 0; level < layer + 1; level++) {
    			
    			if (layer > 0 && level == 0) { // if this is the first level,
    						       // but not the first layer
    				SkipSpaces(--skip); // skip should be less by 1 for the extra asterisk
    				cout << "*/"; // print the left part of the tree with an asterisk
    			} else { // no asterisks here
    				SkipSpaces(skip--); // skip normally
    				cout << '/'; // print the left part of the tree w/o an asterisk
    			}
    			// notice that either way, skip is decreased by 1
    
    			// now before drawing the right part of the tree, we skip spaces for width
    			SkipSpaces(width);
    			width += 2; // width is increased by 2
    			if (layer > 0 && level == 0) { // same asterisk stuff
    				cout << "\\*";
    			} else {
    				cout << '\\';
    			}
    			cout << endl;
    		}
    		// a new layer will start next iteration:
    		// we decrease width by 2 (because it was increased by 2 in the inner loop)
    		width -= 2;
    		// and increase skip by 1 (because it was decreased by 1 in the inner loop)
    		skip++;
    	}
    }
    
    /*
     * ================
     *   SkipSpaces
     * ================
    */
    void SkipSpaces(int count) {
    	// no fancy stuff here...
    	for (int i = 0; i < count; i++) {
    		cout << ' ';
    	}
    }
    
    /*
     * ================
     *  ParseCmdLine
     * ================
    */
    int ParseCmdLine(int argc, char* argv[]) {
    	if (argc != 2) {
    		return -1;
    	}
    	// atoi is used to convert command-line input to order
    	int r = atoi(argv[1]);
    	if (r < 0) {
    		return -1;
    	}
    	return r;
    }
    Formatting
    The formatting was nice and consistent throughout the code.
    There was just one line which mixed spaces and tabs, and this looked
    odd in my editor set to different tab stops to the author.

    Comments
    The overall comment of how the code works was very good. Some of the
    inline comments ("no fancy stuff here...") did seem kind of pointless
    by comparison.

    Functions
    The code showed a good decomposition of the problem into functions.

    Tests
    A number of tests were performed, and the correct output was seen
    in all of them.

    Overall Score
    8/10


    Entry from Magos
    Code:
    //+-----------------------------------------------------------------------------
    //| Included files
    //+-----------------------------------------------------------------------------
    #include <iostream>
    using namespace std;
    
    
    //+-----------------------------------------------------------------------------
    //| Calculates the sum:   n
    //|                      E(i)
    //|                       i=0
    //+-----------------------------------------------------------------------------
    int Sum(int n)
    {
    	//Data
    	int TotalSum = 0;
    
    	//Calculate the sum
    	while(n > 0)
    	{
    		TotalSum += n;
    		n--;
    	}
    
    	//Return the sum
    	return TotalSum;
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Prints a certain amount of blankspaces
    //+-----------------------------------------------------------------------------
    void PrintSpace(int Amount)
    {
    	for(int i = 0; i < Amount; i++)
    	{
    		cout << " ";
    	}
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Draws a single branch section with level 0 being the top one
    //+-----------------------------------------------------------------------------
    void DrawBranch(int CurrentLevel, int TotalLevel)
    {
    	//Data
    	int Loop;
    
    	//Draw the top part. There is a special case for CurrentLevel = 0
    	//since it doesn't have any * around it.
    	if(CurrentLevel == 0)
    	{
    		PrintSpace(Sum(TotalLevel));
    		cout << "/\\" << endl;
    	}
    	else
    	{
    		PrintSpace(Sum(TotalLevel) - Sum(CurrentLevel) + CurrentLevel - 1);
    		cout << "*/";
    		PrintSpace(2 * (Sum(CurrentLevel) - CurrentLevel));
    		cout << "\\*" << endl;
    	}
    
    	//Draw the bottom parts
    	Loop = CurrentLevel;
    	while(Loop > 0)
    	{
    		PrintSpace(Sum(TotalLevel) - Sum(CurrentLevel) + Loop - 1);
    		cout << "/";
    		PrintSpace(2 * (Sum(CurrentLevel) - Loop + 1));
    		cout << "\\" << endl;
    		Loop--;
    	}
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Draws an entire christmas tree
    //+-----------------------------------------------------------------------------
    void DrawChristmasTree(int Size)
    {
    	//Abort if a negative size is entered
    	if(Size < 0)
    	{
    		cout << "Invalid size!" << endl;
    	}
    	else
    	{
    		//Draws every branch of the tree
    		for(int i = 0; i <= Size; i++)
    		{
    			DrawBranch(i, Size);
    		}
    	}
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Main function (assumes the argument is correct)
    //+-----------------------------------------------------------------------------
    int main(int NrOfArgs, char* Arg[])
    {
    	//Only calculate if an argument was passed
    	if(NrOfArgs < 2)
    	{
    		cout << "You didn't pass an argument!" << endl;
    	}
    	else if(NrOfArgs == 2)
    	{
    		DrawChristmasTree(atoi(Arg[1]));
    	}
    	else
    	{
    		cout << "You passed too many arguments!" << endl;
    	}
    
    	//Exit
    	return 0;
    }
    Formatting
    The formatting was nice and consistent throughout the code.

    Comments
    The comments stick to describing pretty much what is going on,
    with very little in the way of why and how.
    The complex expressions passed to PrintSpace() get no mention.

    Functions
    The functional decomposition of the code is clear and easy to
    read.

    Tests
    A number of tests were performed, and the correct output was seen
    in all of them.

    Overall Score
    5/10


    Entry from Prelude
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <errno.h>
    
    /*
     * Copied from covering email
    I went with a more table and mathematically driven solution than krufty looping. 
    The idea is simple, set up a single function that can print branches of 
    ornamented and nonornamented types of any size, another function that prints an 
    ornamented branch followed by N nonornamented branches, and use a single loop 
    around the second function to print the tree and manage correct arguments to it.
    
    I found a nice numeric progression for both the external spacing (to the left of 
    the branches, giving a tree-like structure) and internal spacing (making a nice 
    tree-like structure for the right as well). The external spacing follows the 
    progression (for a tree of order 7):
    
    [0] - 1 + [1] == 30
    [1] - n + [2] == 29
    [2] - n + [3] == 28
    [3] - n + [4] == 26
    [4] - n + [5] == 23
    [5] - n + [6] == 19
    [6] - n + [7] == 14
    [7] - n +  1  == 8
    
    Of course, indices [n] and [0] are problematic as they don't quite fit into the 
    overall scheme, but it was close enough for a simple loop.
    
    The internal spaces were far more simple. Each new level has n * ( n - 1 )
    internal spaces. Nice and neat. :-)
     */
    
    /*
     * Print a single tree branch with optional ornamentation
     */
    static void print_branch ( int left, int center, int ornament )
    {
      while ( left-- > 0 )
        printf ( " " );
      printf ( "%s/", ( ornament != 0 ) ? "*" : "" );
      while ( center-- > 0 )
        printf ( " " );
      printf ( "\\%s\n", ( ornament != 0 ) ? "*" : "" );
    }
    
    /*
     * Print an ornamented branch followed by 'order'
     * regular branches
     */
    static void print_order ( int left, int center, int order )
    {
      print_branch ( left, center, (int)( order != 0 ) );
      while ( order-- > 0 )
        print_branch ( left--, center += 2, 0 );
    }
    
    /*
     * Print an X-mas tree
     */
    static int merry_xmas ( int order )
    {
      int *left_vals;
      int i = order++;
    
      left_vals = malloc ( order * sizeof *left_vals );
      if ( left_vals == NULL )
        return 0;
      /*
       * Calculate external spacing
       */
      left_vals[i] = i + 1;
      while ( --i >= 0 )
        left_vals[i] = i + left_vals[i + 1];
      left_vals[0]++;
      /*
       * Print the tree, how festive!
       */
      for ( i = 0; i < order; i++ )
        print_order ( left_vals[i], i * ( i - 1 ), i );
      free ( left_vals );
    
      return 1;
    }
    
    int main ( int argc, char *argv[] )
    {
      char *endp;
      int  order;
    
      if ( argc < 2 ) {
        fprintf ( stderr, "usage: $ %s <order>\n", argv[0] );
        return EXIT_FAILURE;
      }
      errno = 0;
      order = (int)strtol ( argv[1], &endp, 0 );
      if ( errno == ERANGE || order < 0 || endp == argv[1] ) {
        fprintf ( stderr, "Invalid order\n" );
        return EXIT_FAILURE;
      }
      if ( merry_xmas ( order ) == 0 ) {
        fprintf ( stderr, "Unrecoverable error\n" );
        return EXIT_FAILURE;
      }
    
      return EXIT_SUCCESS;
    }
    Formatting
    The formatting was nice and consistent throughout the code.

    Comments
    I was a little disappointed that the main block comment was in the
    email and not in the code. The use of an allocated array to contain
    a prepared set of indentations could have been explained better.

    Functions
    The code showed a good decomposition of the problem into functions.

    Tests
    A number of tests were performed, and the correct output was seen
    in all of them.

    Overall Score
    7/10


    Entry from TheDog
    Code:
    /*
     *	Written for Salem's X-Mas Tree contest
     *  
     *	Filename : TheDog_xmastree.c
     *	Author   : The Dog
     *
     *	This program draws an ascii christmas tree.
     */
    
    //Headers
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    // Prototypes
    int printUsage( void );
    int printTree( int order, FILE* stream );
    int getNumRows( int order );
    int getNumCols( int order );
    
    /*
     *	main() 
     */
    int main( int argc, char* argv[] )
    {
    	int tree_order;
    
    	// Check arguments
    	if( argc == 1 )
    	{
    		printTree( 0, stdout );
    	}
    	else if( argc == 2 )
    	{
    		// Get tree-order
    		tree_order = atoi( argv[1] );
    
    		// Check if tree-order is valid
    		if( tree_order > 8 || tree_order <= 0 )
    		{
    			return printUsage();
    		}
    
    		// Print the tree
    		printTree( tree_order, stdout );
    	}
    	else
    	{
    		printUsage();
    	}
    
    	return 0;
    }
    
    /*
     *	Prints the usage of this program.
     */
    int printUsage()
    {
    	return printf(	"Usage: xmastree <order>\n\n"
    					"<order>    - integer from 1 - 8\n\n"
    					"No arguments prints a 0-order tree to stdout.\n" );
    }
    
    /*
     *	Prints a xmas-tree according to the order passed to the specified stream.
     */
    int printTree( int order, FILE* stream )
    {
    	int i, j, x, ly, ry;
    	int rows, cols;
    	char *tree_array;
    
    	//Get the dimensions for the array
    	rows = getNumRows( order );
    	cols = getNumCols( order );
    
    	//Allocate memory
    	tree_array = malloc( rows * cols * sizeof( x ) );
    
    	//Check if pointer is valid
    	if( !tree_array )
    		return -1;
    
    	//Fill array with spaces
    	memset( tree_array, ' ', rows * cols * sizeof( x ) );
    
    	//Special case
    	if( order == 0 )
    	{
    		free( tree_array );
    		fprintf( stream, "/\\" ); // :)
    		return 0;
    	}
    
    	//Note:
    	//x is used as row.
        //ly is used as the column for the left part of the tree.
    	//ry is used as the column for the right part of the tree.
    
    	//Handle order-0
    	ly = cols / 2 - 1;
    	ry = ly + 1;
    	x = 0;
    	tree_array[ (x * cols) + ly ] = '/';
    	tree_array[ (x * cols) + ry ] = '\\';
    	x++;
    
    	//Populate the array
    	for( i = 1; i <= order; i++ )
    	{
    		//Draw the first line of the order-i
    		tree_array[ (x * cols) + ly - 1 ] = '*';
    		tree_array[ (x * cols) + ly ] = '/';
    		tree_array[ (x * cols) + ry ] = '\\';
    		tree_array[ (x * cols) + ry + 1 ] = '*';
    
    		//Draw the diagonals
    		x++;
    		for( j = 0; j < i; j++, x++ )
    		{
    			ly--;
    			tree_array[ (x * cols) + ly ] = '/';
    
    			ry++;
    			tree_array[ (x * cols) + ry ] = '\\';
    		}
    	}
    
    	//Print the tree
    	for( i = 0; i < rows; i++ )
    	{
    		for( j = 0; j < cols; j++ )
    		{
    			fputc( tree_array[ (i * cols) + j ], stream );
    		}
    		fputc( '\n', stream );
    	}
    
    	//Free the allocated memory
    	free( tree_array );
    
    	return 0;
    }
    
    /*
     *	Returns the number of rows for the tree
     */
    int getNumRows( int order )
    {
    	int i;
    	int rows = 0;
    
    	for( i = order + 1; i > 0; i-- )
    	{
    		rows += i;
    	}
    
    	return rows;
    }
    
    /*
     *	Returns the number of columns for the tree
     */
    int getNumCols( int order )
    {
    	int i;
    	int cols = 2;
    
    	for( i = order; i >= 0; i-- )
    	{
    		cols += ( i * 2 );
    	}
    
    	return cols;
    }
    Formatting
    The formatting was nice and consistent throughout the code.

    Comments
    The comments were fairly terse, and focussed on what was immediately
    happening in the code, rather than why it was necessary.
    The use of a 2D array to 'draw' the whole tree in memory is an interesting
    idea, but it is in no way explained in any detail how this is accomplished.

    Functions
    The printTree() function dominates the code. It could easily have been
    split into two functions to calculate and print the tree.

    Tests
    An order-0 tree could not be printed for some reason. This is
    probably due to the rows * cols calculation returning zero also.
    and the 0-bytes request returning NULL on my machine.
    The sizeof( x ) is wrong, and should have been sizeof( char )
    The inclusion of C++ comments in C code was a small point

    Overall Score
    3/10
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Congratulations, DavT!
    I also expected recursive entries, but perhaps it'd have been too complex (level 1 needs to be centered etc.)
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949
    Congratulations all!

    Looks like no one found my algorithm for making the tree.....too bad it was due December 7th, not December 14th like the second one was .
    Do not make direct eye contact with me.

  4. #4
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    Congradulation DavT. I like this contest and and happy there is some feed back for the the entrys that lost. As always a learning experience.

  5. #5
    Registered User glUser3f's Avatar
    Join Date
    Aug 2003
    Posts
    345
    congrats DavT
    hoorey, I managed to get the second place (along with DaveSinkula), not bad I guess, hopefully I'll manage to get a good place in #2 too.

    now commenting on Salem's comments:
    >There was just one line which mixed spaces and tabs, and this looked odd in my editor set to different tab stops to the author.

    I wonder whom to blame, me or vi


    >Some of the inline comments ("no fancy stuff here...") did seem kind of pointless
    by comparison.

    it was a humor attempt, looks like it failed.

  6. #6
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    I would just like to point out that the summation from 1 to n = n(n+1)/2. No loop needed to find that.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    "Since I can't use lexical cast", Ok, why not?
    Because you explicitly forbade me using the Boost libraries...
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Code:
    /** Calculates the sum of the sequence 0...x */
    inline uint sum0tox(uint x)
    {
    	return (x&1) ? (((x>>1)+1)*x) : ((x>>1)*(x+1));
    }
    I don't know about the lack of comments. The comment makes it clear WHAT the function does (I couldn't find a function name that is even remotly self-explanatory), and who cares HOW it does it?

    It is inline simply because I think such a tiny function should be directly embedded and I wanted to give the compiler the option to do so.

    Anyway, here are my thoughts behind it.

    Everyone knows that for caculating the sum of the sequence 0...x (or 1...x) the iterative approach is not the best. If you calculate the sum from 1 to 100, you won't do
    sum = 1 + 2 + 3 + 4 + 5 + ...
    You will do
    1 + 100 = 101
    2 + 99 = 101
    ...
    50 + 51 = 101
    sum(1...100) = 50*101 = 5050
    In general:
    sum(1...x) = (x/2)*(x+1)

    This is slightly different for uneven numbers because of C's integer division:
    1 + 101 = 102
    2 + 100 = 102
    ...
    50 + 52 = 102
    ?
    thus
    sum(1...100) = 50*102 + 51 = 5151
    But it's easier to write
    0 + 101 = 101
    1 + 100 = 101
    ...
    50 + 51 = 101
    sum(1...101) = 51*101 = 5151
    In general:
    sum(1...x) = ((x/2)+1)*x
    This assumes C integer division.

    My function packs all this in a single line.
    First the check for an uneven number
    (x&1)

    Second, the part that calculates uneven numbers.
    (((x>>1)+1)*x)
    x>>1 is of course the same as x/2, and the rest is as above.

    Third, the part for even numbers.
    ((x>>1)*(x+1))
    Again the shift, and else like the theory.

    Maybe I should have left the shifts and the and to the compiler, but these tiny things I can be sure of and it's a habit to automatically write them as bit operations.

    P.S: I think I could have written it even better in assembly by using the carry bit. Maybe.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    And joshdick is absolutly right, my solution is overly complicated
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Originally posted by CornedBee
    And joshdick is absolutly right, my solution is overly complicated
    Yeah, I still can't believe you were doing bitwise operations for that. Math is cool, and knowledge is power.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I must've been tired.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. The xmas Song competition results
    By Salem in forum Contests Board
    Replies: 3
    Last Post: 12-30-2003, 04:43 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM