[Kc] Solutions and Discussion for Perl Quiz of the Week #12 (Histogram s)

[Garrett Goebel]

Sample solutions and discussion
Perl Quiz of The Week #12 (20030212)

[ This is a writeup of a very old quiz for which I never posted a
  report.  I hope to be able to fill in the other missing reports in
  the coming months.  Thanks to John J. Trammell for doing it.  -MJD ]

NAME
    qotw-r12-summary.pod - summary of "regular" Perl Quiz of the
    Week #12

SYNOPSIS

    The following programmers participated in Quiz 12:

      James Edward Gray II
      Kurt Hutchinson
      David Kershaw
      Brian King
      Not a Number
      Riccardo Perotti
      Marcelo Ramos
      John Trammell (late)

    Their code is available from

        http://perl.plover.com/qotw/misc/r012/


THE QUIZ
    The quiz text reads:

      You'll write functions for displaying histograms (bar charts).
      We'll use these to display the output from next week's quiz.

      You're build one function, 'histogram()', whose arguments will
      be a list of numbers.  The function should construct a bar chart
      and then return a list of strings which, if printed, would
      display the numbers suitably.

      For example, 

          histogram(1, 4, 2, 8, 5, 7)

      might return the following list of strings:

          "   *\n", 
          "   * *\n", 
          "   * *\n", 
          "   ***\n", 
          " * ***\n", 
          " * ***\n", 
          " *****\n", 
          "******\n"

      when printed, these strings look like this:

              *
              * *
              * *
              ***
            * ***
            * ***
            *****
           ******

      The behavior of 'histogram' will be controlled by several global
      variables.  $HISTOGRAM_WIDTH and $HISTOGRAM_HEIGHT will specify
      the width and height of the result.  The output should be scaled
      to fit in a rectangle with $HISTOGRAM_HEIGHT rows and
      $HISTOGRAM_WIDTH rows.

      The bars themselves will be made up of the character
      $HISTOGRAM_CHAR, which must be a string of length 1.

      If any of the $HISTOGRAM_ variables are undefined, the function
      should use reasonable defaults.


ISSUES

  Output Scaling and/or Truncation

    The main issue with this Quiz was discussed in a thread started by
    Andy Bach, archived at:

      http://perl.plover.com/~alias/list.cgi?1:mss:1292

    The crux of the issue is this text from the Quiz:

      $HISTOGRAM_WIDTH and $HISTOGRAM_HEIGHT will specify the width
      and height of the result.  The output should be scaled to fit in
      a rectangle with $HISTOGRAM_HEIGHT rows and $HISTOGRAM_WIDTH
      rows.

    Although all were in agreement that output should not exceed the
    dimensions specified by $HISTOGRAM_WIDTH and $HISTOGRAM_HEIGHT
    (see below however), there was some disagreement about whether
    $HISTOGRAM_WIDTH and $HISTOGRAM_HEIGHT were to be the *exact*
    width and height, or the *maximum* width and height.

    Also at issue was the correct behavior in the case where the
    number of arguments in the histogram() function call was greater
    than $HISTOGRAM_WIDTH. Arguments were made for and against
    truncating the histogram rather than making the output width
    greater than $HISTOGRAM_WIDTH.

  Miscellaneous Issues

    The following issues were also mentioned but not discussed at
    length:

      * how and whether to represent negative values
      * what to do with fractional inputs
      * horizontal vs. vertical histogram orientation
      * other alternate formatting suggestions (truncation, etc.)

    Little discussion regarding these issues ensued, although the
    solution offered by Kurt Hutchinson did handle representation of
    negative numbers.

    [This puzzles me, since the histograms I was taught in school
    always represented the "count" of something in a "bin".  Certainly
    there can be bar graphs with negative values on the vertical axis,
    but I wouldn't call that a histogram. - JJT

      "Histogram" is from Greek "histos", meaning a beam or a mast.  A
      histogram is therefore a drawing of beams or masts, and is
      nothing more or less than a bar chart. - MJD 
    ]

EXAMPLE

  An example solution is listed below (with slight modifications),
  courtesy of Brian King.

  sub histogram {
    my @list = @_;
    my @response  = ();
    my $x_scale   = 1;   # horizontal scaling factor
    my $y_scale   = 1;   # vertical scaling factor
    my $max_value = 0;   # greatest value (tallest bar) in @list

    $HISTOGRAM_WIDTH  ||= 0;
    $HISTOGRAM_HEIGHT ||= 0;
    $HISTOGRAM_CHAR   ||= 'H';
    $HISTOGRAM_CHAR   = unpack('a1',$HISTOGRAM_CHAR); # must be 1 char long.

  # determine y scaling factor. Increase $HISTOGRAM_HEIGHT
  # if what we got is too big to fit.

    foreach( @list ){
      if( $_ > $max_value ){
        $max_value = $_;
      }
    }
    if($max_value > $HISTOGRAM_HEIGHT){
      $HISTOGRAM_HEIGHT = $max_value;
    }
    $y_scale = int($HISTOGRAM_HEIGHT / $max_value);

  # determine x scaling factor. Increase $HISTOGRAM_WIDTH
  # if we got too many values to fit. Can't just omit some...

    if( $HISTOGRAM_WIDTH < $#list ){
      $HISTOGRAM_WIDTH = $#list;
    }
    $x_scale = int($HISTOGRAM_WIDTH / $#list);

  # build @response, based on @list and scaling factors.
  # iterate over @list $HISTOGRAM_HEIGHT times.
  # for each element in @list, if ($_ * scaling factor) is >
  # current position in the histogram (one less than the y-value of the
graph),
  # then append $x_scale number of $HISTOGRAM_CHAR to the current element
  # of @response. Otherwise, append $x_scale number of spaces.

    for( my $i=0; $i<$HISTOGRAM_HEIGHT; $i++ ){
      foreach(@list){
        if( $_ * $y_scale > $i ){
          $response[$i] .= $HISTOGRAM_CHAR x $x_scale;
        }
        else{
          $response[$i] .= ' ' x $x_scale;
        }
      }
      $response[$i] .= "\n";
    }
    return reverse @response;
  }


  Comments on this solution:

 * $HISTOGRAM_HEIGHT is increased, rather than truncating data

 * $HISTOGRAM_WIDTH is increased, rather than truncating data

 * vertical scaling only occurs if $HISTOGRAM_HEIGHT is at least twice
   as large as the largest input value

 * horizontal scaling only occurs if $HISTOGRAM_WIDTH is at least
   twice the number of input values

 * the histogram is constructed by looping over horizontal histogram
   slices from bottom to top.  Vertical scaling is accomplished by
   comparing the vertical histogram position $i to a rescaled input
   value ($_ * $y_scale), and setting the output "pixel" accordingly.
   Horizontal scaling is accomplished by scaling this pixel by the
   calculated value $x_scale.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/archives/kc/attachments/20040928/f4801a12/attachment.htm