SSWE Programming Contest

The contest is over, here are the winners:

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.

Score Results

Score Results

You can download the instances here:

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)

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

while read l; do
  rep=(${l//:/ })
  clauses=${clauses//${rep[0]}/${rep[1]}}
done <<< "$sol"

while read l; do
  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 Γ.

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