TopCoder problem "Scale" used in TCCC '04 Qual. 3 (Division I Level Two)



Problem Statement

    *** You may only submit a given problem once - no resubmissions will be accepted. ***



A common image editing task is to scale an image. For example, given an image 1024 pixels wide, and 768 pixels high, you might want to reduce it to 400x300 so it takes up less disk space. In this problem, you will be given an image as a String[], where each element represents a row of pixels, and each character represents a single pixel (the colors are simply ASCII values between 32 and 126, inclusive). Your task is to scale the image so that it is x pixels wide, and y pixels high. To determine the colors of the new pixels, you should draw a grid over the image such that there are x columns and y rows. Each region of the grid will then represent a single pixel, whose color is the weighted average of all the colors within it (0.5 rounds up). The weight of each color is equal to the area it covers in the region. For example, consider the input {"AB","BC"}, with x = y = 3. Here is a zoomed in view of the scaled image (with grid): 
   AA | AB | BB
   AA | AB | BB
  ----+----+----
   AA | AB | BB
   BB | BC | CC
  ----+----+----
   BB | BC | CC
   BB | BC | CC
Now, taking the average value of each pixel in the scaled image, we end up with: 
   ABB
   BBC
   BCC
 

Definition

    
Class:Scale
Method:scale
Parameters:int, int, String[]
Returns:String[]
Method signature:String[] scale(int x, int y, String[] image)
(be sure your method is public)
    
 

Notes

-Each character represents a color, as given by its ASCII value. The average of colors is just the average of the ASCII values.
-Note that grid lines may go through the pixels in the original image.
 

Constraints

-x and y will be between 1 and 100, inclusive.
-x * y will be less than or equal to 8000.
-image will contain between 1 and 50 elements, inclusive.
-Each element of image will contain between 1 and 50 characters, inclusive.
-Each element of image will contain the same number of characters.
-Each character in image will have ASCII value between 32 and 126, inclusive.
 

Examples

0)
    
3
3
{"AB","BC"}
Returns: { "ABB",  "BBC",  "BCC" }
The example from the problem statement.
1)
    
2
4
{"AB","BC"}
Returns: { "AB",  "AB",  "BC",  "BC" }
2)
    
51
43
{"......",
 ".X....",
 ".X....",
 ".X....",
 ".X....",
 ".XXXX.",
 "......"}
Returns: 
{ "...................................................",
 "...................................................",
 "...................................................",
 "...................................................",
 "...................................................",
 "...................................................",
 "........@RRRRRRRR..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX..................................",
 "........CXXXXXXXX:::::::::::::::::::::::::4........",
 "........CXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXC........",
 "........CXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXC........",
 "........CXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXC........",
 "........CXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXC........",
 "........CXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXC........",
 "........@RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR@........",
 "...................................................",
 "...................................................",
 "...................................................",
 "...................................................",
 "...................................................",
 "..................................................." }
3)
    
4
4
{"...AAA...",
 "...AAA..."}
Returns: { ".;;.",  ".;;.",  ".;;.",  ".;;." }
4)
    
4
4
{"......",
 ".X....",
 ".X....",
 ".X....",
 ".X....",
 ".XXXX.",
 "......"}
Returns: { "44..",  "<<..",  "<@40",  "4@@4" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2294

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5002&pm=2294

Writer:

lars2520

Testers:

schveiguy , vorthys

Problem categories:

Math, String Manipulation