Problem: Life

Want to try solving this problem? You can submit your code online if you log in or register.

Life

Download input files for [Linux] [Windows]

Today is the most important day of your career as an exobiologist. After many attempts, you finally managed to maintain a stable micro-wormhole for more than 20 nanoseconds between your lab and PHR 5426b, the most earth-like exoplanet discovered to this day, and were even able to repeat the experiment 10 times before the plasma of your hypergenerator collapsed. 20 nanoseconds is just enough time for enough photons to traverse the wormhole and be captured by the camera of your xPhone 5.

Using a $49 xPhone 5 to capture the most important images of the century may seem odd, but the xxd sensor in its camera is by far the most sensitive ever manufactured, and is much better than even the $500,000 sensors created for Hubble 5.

However, just after announcing the big discovery to the world and organising the largest press conference since the launch of the xPhone 5 itself, you realize that you have a problem: since the wormhole is really tiny, you had to take many pictures to get a whole image of each life form. Unfortunately, you were so excited about your discovery that you forgot to keep track of which picture corresponds to which part of the whole image. You absolutely need to rearrange them before the press conference starts.

Input

You are given ten input files life.k.in (1 ≤ k ≤ 10), describing the ten scrambled pictures.

The first line of each file contains four integers, W H C R, indicating that the image is composed of a grid of C x R tiles (C columns and R rows), each tile being a small image of W x H pixels (W columns and H rows).

Following this are C x R groups of H lines. Each group describes a tile with H lines of W integers between 0 and 255 inclusive, giving the brightness of the pixels that compose the tile. The tiles are numbered 1 ...(C x R) and are given in this order. Your only problem is that this order is completely unrelated to the position of each tile in the original image.

Your task is to determine in which order the C x R tiles need to be arranged to form an image as similar as possible to the original image. Since you don't have the original images, you can only rely on the fact that these are images of life forms on a distant planet.

Output

For each input file life.k.in, you must produce an output file life.k.out that contains your solution.

Each solution file should contain R lines of C distinct integers, each being the number of a tile. These numbers should be arranged in such a way that placing the corresponding tiles in this manner on an C x R grid creates an image that looks as much as possible like an alien form of life.

Sample Input

Sample Output

5 1 2
6 4 3

Input Details

The input describes 6 tiles, as illustrated below:

The original image of this very simple life form is illustrated below:

The above sample case is not representative of the test cases provided.

Output Details

The output describes an ordering of the tiles that corresponds to the following recomposed image:

Scoring

Your score for each input scenario will be determined as follows:

If your solution doesn't contain exactly R lines of C integers, all distinct and between 1 and R x C, it will obtain a score of 0%.
Otherwise, let A be the total number of adjacent pairs (sharing one side) of tiles in the image (A=C x R x 2-C-R), and let B be the number of adjacent pairs of tiles in your output that are adjacent in the same way (same sides) as in the original image. Your solution will be scored 100 x B / A and rounded down (expressing a percentage of points).

For example, in the sample case above, a perfect output file would be:

2 5 3
1 6 4

As this corresponds exactly to the original image, all 7 pairs of adjacent tiles are correct, so this output would have given a score of 100% (100 x 7 / 7).

In the sample output, however, only the pairs (5,6) and (6,4) are adjacent in the same way as in the original image. This output would thus be awarded a score of 28% (100 x 2 / 7 = 28).

Experimentation

Use the trial runs feature on the submission site in order to experiment with the input data. There you may submit a possible mapping, and view the resulting image.

Submitting for an Output Only Task

To submit your output files, you must do the following:

Create a zip file containing all of your output files. You may include as many or as few output files as you like (i.e., you do not need a solution for every input scenario). On a GNU/Linux system you can use a command like the following:

zip mysolutions.zip life.*.out

On Windows systems you can create a zip file by selecting File -> New -> Compressed (zipped) Folder from within Windows Explorer, and then you can copy your output files into this new zip file.
Submit this zip file to the FARIO website, in the same way that you would submit an ordinary solution.

The website will look inside the zip file and ensure that the output files are named correctly, although it will not check the formatting or layout of these files.

If you resubmit a different zip file, the old zip file will be deleted. For instance, suppose you submit a zip file with solutions to the first nine scenarios, and later on you find a solution to the tenth. Your new submission must contain all ten output files, since when you submit your new solutions the old ones will be thrown away.

Please contact the contact organisers at fario@fario.org if you have any questions about this procedure.