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.