# SSWE Programming Contest

The contest is over, here are the winners:

• Dijkstras on Bikestras, 13 points
• The Snakes, 8 Points
• Team Hodor, 3 Points

Congratulations!

Each program was run on four instances for three different timeframes: 10s, 30s and 50s, each for five times. For each instance and timeframe one point was given to the team with the best solution found (i.e. with the highest number of expanded substrings) and one point was given to the team with the highest average solution.

You can download the scores. This file contains three columns (Team 1, Team 2 and Team3) containing the individual scores. Every five consecutive lines belong to one instance and one timeframe, e.g. the first five lines are the five runs for instance 1 and the 10s timeframe. The next five lines represent the five runs for instance 1 and the 30s timeframe, and so on.

A better representation is given by the following figure.

The following bash script was used to count the number of expanded substrings:

``````#!/bin/bash

clausefile=\$1
solfile=\$2

sol=\$(tac \$solfile | sed '/^---/q' | tac | tail -n+1)

clauses=\$(head -n \$((\${n}+2)) \$1 | tail -n \$((\${n}-2)))
string=\$(head -n2 \$1 | tail -n 1)

rep=(\${l//:/ })
clauses=\${clauses//\${rep[0]}/\${rep[1]}}
done <<< "\$sol"

if [[ "\$string" =~ "\$l" ]]; then
echo \$l
fi
done <<< "\$clauses"``````

Using this script the contest was executed in this fashion:

``````t=60s
instance=contest01.SWE
for i in {1..5}
do
timeout \$t \$invoke1 "\$instance" > sol1
timeout \$t \$invoke2 "\$instance" > sol2
timeout \$t \$invoke3 "\$instance" > sol3
./solchecker \$instance sol1 |wc -l >> score_1
./solchecker \$instance sol2 |wc -l >> score_2
./solchecker \$instance sol3 |wc -l >> score_3
done
paste score_1 score_2 score3 >> score``````

(This is the old website for future reference)

In addition to the project assignment of the course Computationally Hard Problems (02249), Fall 2016, we offer a programming contest for finding SSWE (SuperStringWithExpansion) approximations.

Participation in the contest is not mandatory.

## Description

You are given a string s over an alphabet Σ and k strings t1, …, tk over an alphabet Γ.

• Problem: SuperStringWithExpansion
• Input:
• two disjoint alphabets Σ and Γ = {γ1, …, γm},
• a string s ∈ Σ*
• k strings t1, …, tk ∈ (Σ ∪ Γ)*,
• m subsets R1, …, Rm ⊆ Σ*.
• Output: YES if there is a sequence of words r1 ∈ R1, r2 ∈ R2.…, rm ∈ Rm such that for all 1 ≤ i ≤ k the expansion e(ti) is a substring of s; the expansion e(γj) of the j-th letter γj ∈ Γ, 1 ≤ j ≤ m, is defined by e(γj):=rj, and the expansion e(t) of a whole string t ∈ (Σ ∪ Γ)* is obtained by replacing all letters from Γ appearing within t by their expansions. Otherwise output NO.

Instead of solving the search version of the above stated decision problem, we are interested in the optimization version, i.e. we are trying to find an expansion that turns as many strings ti into substrings of s as possible. Obviously, this number is between 0 and k.

## 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:

``````4
abdde
ABD
DDE
AAB
ABd
A:a,b,c,d,e,f,dd
B:a,b,c,d,e,f,dd
C:a,b,c,d,e,f,dd
D:a,b,c,d,e,f,dd
E:aa,bd,c,d,e``````

The alphabets will be fixed just as in the project assignment, so Σ = {a, b, …, z} and Γ = {A, B, …, Z}.

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

The output format is the same as described in the project assignment, so every solution is a list of lines in the format γi:ri, where γi is an upper-case letter and ri the chosen element of Ri, for example:

``````A:ah
B:c
C:d``````

The program should then output solutions to standard output (`stdout`) and not to a file. If your program outputs more than one solution, the solutions are to be separated by a line consisting of three dashes `---`, for example

``````A:f
B:c
C:dd
---
A:a
B:gy
C:c``````

In this case, the last solution 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 possibly needed build instructions: If your program is written in C, provide a Makefile. If your program is written in Java, provide an Ant build file or something similar
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 13.11.2016, submissions are to be sent to cgie@dtu.dk.

## Scoring

Your programs will have a wall-clock time limit and will be stopped after that time (hence the possibility to output more than one solution). The score will be based on the time and the number of strings that are expanded to substrings.

Details will follow

## 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 used for in the contest 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.