In addition to the project assignment of the course Computationally Hard Problems (02249), Fall 2015, we offer a programming contest for finding Madragon solutions.

Participation in the contest is not mandatory.

## Description

You are given an $$m\times n$$-board, consisting of $$m$$ rows and $$n$$ columns, where each tile on the board is colored either black or white. Each transformation of the board that shifts a row or a column by a number of positions $$s\in\mathbb{N}$$ in one of the two possible directions such that tiles that are moved off the board are reinserted on the other side is called an operation, e.g., shifting the first column three positions down is an operation. Consider the following decision problem:

• Input: Two $$m\times n$$-boards $$A$$ and $$B$$ and a number $$k\in \mathbb{N}$$.
• Output: YES if there is a sequence of at most $$k$$ operations (each of which may shift by an arbitrary number of positions) that transforms A into B and NO otherwise

Instead of solving the optimization version of the above stated decision problem, we are interested in finding solutions fast. However, the solutions do not need to be of minimum length as opposed to the project assignment.

## Programming Languages

The programs should be implemented in C, C++, Java or Python. Other languages are possible, but should be discussed with me beforehand. You are allowed to make use of (free) software libraries if that helps you (GSL, Boost etc).

## Format

The instances are given in the same format that was presented in the project assignment, e.g. an instance file can look like:

5
5
100
bbwbb
wwbwb
wbwbb
wwbwb
bbbbb
wwwbb
wbbwb
wbbwb
bwbwb
bbbbb

The third line has no particular meaning for the problem itself. It will, however, be important for the score.

The built program should take an instance file as input from the command line, i.e. if testfile.mad is an instance file and the executable is called myprogram, your program should be invoked as ./myprogram testfile.mad.

Solutions are encoded as a comma separated list of operations in the following way:

• Row operations are encoded as the row number (starting from 1), followed by an uppercase R, followed by the number of right shifts. Shifting the fourth row for three times to the right would be encoded as 4R3.
• Column operations are encoded as the column number (starting from 1), followed by an uppercase C, followed by the number of down shifts. Shifting the second column for one time down would be encoded as 2C1. A complete solution could therefore look like

4R3,2C1,3R4,2C2

The program should then output solutions to standard output (stdout). If your program outputs more than one solution, the last one before termination counts.

## Submission

Every student of the course can participate in the contest. You are allowed to work in groups of up to three people, but every participant may only be part of one group.

Every entry to the contest should include the following:

1. your team name (be creative)
2. a list of group members, including email addresses
3. the source code
4. any build instructions: If your program is written in C, provide a Makefile. If your program is written in Java, provide an Ant build file.
5. a list of library dependencies (if any), including version numbers

The entries should be packaged in a gzipped tar archive or zip file. Please don’t create tarbombs.

The submission deadline is 19.11.2015, submissions are to be sent to .

## Scoring

The programs will be tested for ten times on five problem instances. There will be a wall-clock time limit $$t_{0,i}$$ per instance $$i$$ depending on the perturbation for each of the instances. The algorithms will be stopped after that time if they have not finished beforehand. As described above, the last solution that appeared on the standard output will be taken in this case. The time taken by the algorithm on instance $$i$$ in the $$j$$th run $$t_{i,j}$$ is measured in wall-clock time, i.e. $$t_{i,j}\leq t_{0,i}$$. Provided the solution is correct, the number of moves $$n_{i,j}$$ is counted for the $$j$$th run of problem instance $$i$$. In case the program did not have any output, $$n_{i,j}:=\infty$$ then. Denoting the number on the third line of the input file of instance $$i$$ as $$n_{0,i}$$, the total score is

$\frac{1}{10}\sum_{i=1}^5\sum_{j=1}^{10}\left(2-\frac{t_{i,j}}{t_{0,i}}\right)\frac{n_{0,i}}{n_{i,j}}\enspace.$

The team with the highest score wins.

## Notes

• While the fun in participating is prize enough, there will also be a real prize for the winning team.
• Before the deadline, I will provide one of the actual problem instances for testing purposes.
• The programs will be run on a x86 GNU/Linux machine.
• Feel free to contact me for any questions.
• All judged decisions are final.