Marathon Match 110

Problem Statement

Like in the classic game, you will need to rotate, move horizontally and then drop pieces made of connected blocks. This time instead of clearing rows, the goal is to fill a playing area, which will contain a given image.
The blocks in each piece will have different colors and you will get more points if the block is placed in a part of the image with pixel colors as similar as possible to the block's color. In other words, you need to place pieces in a way that the final configuration resembles the given image.
To make things easier (?!), you can discard some of the pieces.
This is the visualization of seed 1 in the middle of a game, with a few pieces already placed.

Implementation

Your code should implement two methods: init and placePiece.

The first one (init) will be called once, in the beginning of the game:

	String init(int imageHeight, int blockSize, int maxDiscard, int[] image)

• imageHeight is the height of the image, in pixels. You can get the width of the image as (image.length / imageHeight).
• blockSize is the length in pixels of each block.
• maxDiscard is the maximum number of pieces you can discard.
• image contains the pixels of image: image[R * imageWidth + C] describes the color of the pixel in row R and column C, encoded as an integer with 8 bits per color component in RGB order.
  You can decode color components as follows:
  int red = (image >> 16) & 0xFF, green = (image >> 8) & 0xFF, blue = pixel & 0xFF

The return of init is ignored, you can return an empty string.

The second method (placePiece) is called for each piece:

	String placePiece(int pieceHeight, int[] piece, int timeLeft)

• pieceHeight is the height of the piece, in number of blocks. You can get the width of the piece as piece.length / pieceHeight.
• piece gives you the color of each block in the piece: piece[R * pieceWidth + C] describes the color of block in the row R and column C, encoded in the same way as image pixels, with the exception of the value, -1, which indicates an empty position in the piece. For example, the piece depicted below would be encoded as {-1, 0xFF, 0xFF00, 0xFF0000, 0, -1}, i.e. first row is "empty, blue, green" and second row is "red, black, empty".
  
  Pieces are made of 2, 3 or 4-connected blocks (squares), so there are 10 possible shapes (1 with 2 blocks, 2 with 3 blocks and 7 with 4):
  

• timeLeft is the remaining time available in milliseconds, provided to help time control. After many calls to placePiece, small differences between server time and time measured by the solution may accumulate.
• You should return from placePiece:
  • A string containing the rotation and the number of horizontal moves from the left side of the playing area right, separated by a single space, if you want to place the piece.
    Rotation value can be 0, 1, 2 or 3, for no rotation, 90, 180 or 270 degrees clockwise, respectively.
    The piece will be rotated, then moved and finally dropped, going down until it reaches the bottom of playing area or a block from another already placed piece.
    For example, "1 5" will rotate the piece 90 degrees and move it 5 cells to the right before dropping it.
    Important: If the piece can't be placed in the chosen position, because it is out of bounds or the piece won't fit the playing area, the game will end. So this would still be a valid move but will finish the game.
  • Or "D" (a string with a single character D) if you want to discard that piece.

Scoring

• For each test case we will calculate your raw score. If your solution produced an invalid return (invalid rotation value, any malformed return or use more discards than allowed), the raw score for this test case will be -1.
• Otherwise, for each block of each placed pieced, an error will be calculated as the sum of the absolute differences, for each channel, between the color of pixels in the image that were covered by the placed block and the color of the block itself.
• This error, ERR, will be normalized, dividing by the number of pixels * number of channels * color range, i.e. (blockSize^2 * 3 * 255).
• Finally you will get (1 - ERR)^2 points for that block.
• This match uses relative scoring: if your raw score for a test case is negative, then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is YOUR/MAX, where YOUR is your raw score and MAX is the largest raw score currently obtained on this test case (considering only the last submission from each competitor).
• Finally, the sum of all your test scores is multiplied by 1,000,000 and divided by the number of test case

Submission Format

Your submission must be a single ZIP file not larger than 500 MB, with the following content:

Java (Sample Zip File)

• solution.sh

Last Line of the `solution.sh` file should be `echo '<command>' > /workdir/command.txt`
e.g. echo 'java -cp /workdir ImageFromBlocks' > /workdir/command.txt
/workdir would be the base folder for the solution

Example: 
#!/bin/sh
javac /workdir/ImageFromBlocks.java
echo 'java -cp /workdir ImageFromBlocks' > /workdir/command.txt

• Your Java Source Code : ImageFromBlocks.java

C++ (Sample Zip File)

• solution.sh

Last Line of the `solution.sh` file should be `echo '<command>' > /workdir/command.txt`
e.g. echo '/workdir/ImageFromBlocks' > /workdir/command.txt
/workdir would be the base folder for the solution

Example: 
���#!/bin/sh
g++ -std=gnu++11 -O3 /workdir/ImageFromBlocks.cpp -o /workdir/ImageFromBlocks
echo '/workdir/ImageFromBlocks' > /workdir/command.txt

• Your C++ Source Code : ImageFromBlocks.cpp

 

Python (Sample Zip File)

• solution.sh

Last Line of the `solution.sh` file should be `echo '<command>' > /workdir/command.txt`
e.g. echo 'python3.6 /workdir/ImageFromBlocks.py' > /workdir/command.txt
/workdir would be the base folder for the solution

Example: 
#!/bin/sh
echo 'python3.6 /workdir/ImageFromBlocks.py' > /workdir/command.txt

• Your Python Source Code : ImageFromBlocks.py

  General marathon match rules apply

Notes

• blockSize is chosen randomly between 8 and 20, inclusive.
• maxDiscard is chosen randomly between (numCells / 40) and (numCells / 4), where numCells is the number of cells in the playing area, which is equal to the number of pixels in the image divided by (blockSize ^ 2).
• Images used in tests were photographic images from a set of about 400 pictures of landmarks, beaches, objects, food and animals.
• Each dimension of these images is between 300 and 800 pixels, inclusive.
• Both dimensions will always be a multiple of blockSize (original images will be cropped, discarding pixels in the bottom/right, if necessary).
• A random split of the image set was made and 100 of them are available for local tests: testing-images.zip. The first 10 images are used as example tests.
• The full set of images will be released when the contest is over, so competitors can reproduce results locally for any seed.
• Piece shapes will be chosen uniformly at random, i.e. each of the 10 possible shapes has the same chance to be selected.
• For choosing the color of each block of the piece, first a random "base" position (x, y) in the image will be chosen and stay fixed for that piece. Then, for each block, it will pick the color of a pixel at a random position chosen "near" the "base" position, with coordinates x in [x - blockSize, x + blockSize] and y in [y - blockSize, y + blockSize], avoiding out of image bounds positions.
• The time limit is 10 seconds per test case (this includes only the time spent in your code).
• The memory limit is 1024 megabytes.
• There are 10 example test cases and 100 full submission (provisional) test cases. There will be 1000 test cases in the final testing.
• The match is rated.

Tools

An offline tester is available:

• JAR: tester.jar
• Source code: ImageFromBlocksVis.java

You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation.
To run the tester with your solution, you should run:

	java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation. If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\solution.exe" or "~/topcoder/solution". In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder Solution".

The visualizer has a manual mode, enabled when the exec parameter is omitted.

Additionally, you can use the following options:

• -novis: Turn off visualization;
• -noborder: Block's borders are not drawn;
• -delay: Delay in milliseconds between each placed piece in the "exec" mode. 0 to disable;
• -anim: Duration in milliseconds of an animation of the pieces "falling" (and moving in "exec" mode). 0 to disable. 300 is the default value;
• -colored: Image is not displayed in the playing area and pieces are drawn with fixed colors;
• -time: use a different time limit, in seconds. Default is 10;
• -images: path to a different folder for testing images. Default is "images";
• -paused: starts the visualizer paused, when in the "exec" mode;
• -max: starts with visualizer window maximized;
• -debug: Print debug information.

In the visualizer, the following keys are available:

• Left/Right to move the piece horizontally (manual mode);
• Up to rotate the piece (manual mode);
• Down to drop the piece (manual mode);
• D to discard the piece (manual mode);
• B to toggle draw piece border option (both modes);
• C to toggle "colored" option (both modes);
• N to place a single piece and go the next one, when paused (exec mode);
• SPACE to pause/continue (exec mode).

Here are example solutions for different languages, which include the code to communicate with the visualizer (you may modify and submit these example solutions):

• ImageFromBlocks.java
• ImageFromBlocks.cpp
• ImageFromBlocks.py