Competition

Each exercise sheet contains a magnificiently written competition exercise by the Master of Competition Senior, Herrn MC Sr. Eberl, or Master of Competition Junior, Herrn MC Jr. Kappelmann. These exercises count just like any other homework, but are also part of the official competition – overseen and marked by the MC Sr. The grading scheme for these exercises will vary: performance, minimality or beauty are just some factors the MC Sr. adores. You might use any function from the following libraries for your solution: base, array, containers, unordered-containers, attoparsec, binary, bytestring, hashable, mtl, parsec, QuickCheck, syb, text, transformers

Each week, the top 30 of the week will be crowned and the top 30 of the term updated. The best 30 solutions will receive points: 30, 29, 28, and so on. The favourite solutions of the MC Sr. will be cherished and discussed on this website. At the end of the term, the best k students will be celebrated with tasteful trophies, where k is a natural number whose value still will be determined when time has come. No bonus points can be gained, but an indefinite amount of fun, respect, and some trophies!

Important: If you do not want your name to appear on the competition, you can choose to not participate by removing the {-WETT-}...{-TTEW-} tags when submitting your homework.

Outline:

• All-time Top 30
• Results for Week 1
• Results for Week 2
• Results for Week 3
• Results for Week 4
• Results for Week 5 (updated 26.12.2019)
• Results for Week 6
• Results for Week 7
• Results for Week 8
• Results for Week 9
• Results for Week 10
• Results for Week 12
• Results for Week 13
• What is a token?

Die Ergebnisse der ersten Woche

(scoring scheme was changed from previous years because it seemed unfair in this instance)

The MC Sr bids you welcome to this year's Wettbewerb. This tradition was started by the MC emeritus Jasmin Blanchette in 2012. Much time has passed since then, and the MC emeritus is now a professor in Amsterdam, and his former MC Jr is now the MC Sr. Still, the Wettbewerb progresses more or less as always, mutatis mutandis, and the MC Sr will attempt to keep the old spirit alive. (If you are confused by the style of this blog, the fact the the MC refers to himself in the third person, or the odd mixture of German, English, and occasional other languages – that is also a legacy of the MC emeritus and changing it now would just feel wrong)

This week's problem was posed by new MC Jr Kevin Kappelmann, who seems to have an unhealthy obsession with century-old number theory. Well, the MC Sr supposes he shalt not judge (lest he be judged himself). The problem that was posed was to determine whether or not a given number is a quadratic residue for a given modulus n, i.e. if it has a square root in the residue ring ℤ/nℤ.

The MC Sr received 538 submissions. The evaluation was quite tedious for him and was made more tedious by the fact that a significant number of students chose to ignore the instructions on the exercise sheet that clearly stated that if one wishes to use auxiliary functions in one's solution for quadRes, all of them have to be within the {-WETT-} tags. Perhaps they were trying to trick the MC; perhaps they were just careless. The MC decided to be lenient this week and adjusted their solutions accordingly, but it turns out that after moving all the auxiliary functions into the tags, none of them were even remotely competetive anymore anyway.

In any case, let us talk about the solutions themselves: All of the correct ones that the MC looked at essentially followed the hint from the exercise sheet and simply tried all candidates. This is not surprising since nobody currently knows an algorithm that is substantially better than this – at least not (unless one already has a prime factorisation of the modulus), and this forms the basis for various cryptographic systems.

The longest correct solution, with 95 tokens, is this:

quadRes n a 
 | n == 1 = True
 | a > n = quadRes n (a `mod` n)
 | a `mod` n == 0 || a `mod` n == 1 = True
 | a < 0 = quadRes n (a+n)
 | otherwise = aux n 1 a where 
  aux n x a 
    | equivMod n (a `mod` n)(x^2) == True = True
    | x == n-1 = False
    | otherwise = aux n (x+1) a  

There is a lot of potential for optimisation here. The initial case distinctions are unnecessary, and the definition of the auxiliary function could easily be written in a single line with some logical connectives. Also, remember the Meta-Master Tobias Nipkow told you: never write if b == True!

A nice and much more streamlined version of the same basic approach can be found in the following 32-token solution by Jonas Jürß:

quadRes n a = find n
  where find i = i >= 0 && (i*i `mod` n == a `mod` n || find (i-1))

He does not have any unnecessary case distinctions and inlined the equivMod function. Moreover, he only used material that was covered in the first week of the lecture. The MC approves, but unfortunately this straightforward approach is not enough to land a spot among the Top 30 even in the very first week.

All the Top 30 students made use of lists one way or another. The obvious way was to use the list comprehensions introduced in the second week of the lecture. Here is one representative 24-token solution for this approach by Anton Baumann, which earned him a well-deserved 17th place:

quadRes n a = or [x^2 `mod` n == a `mod` n | x <- [0 .. n]]

Note that he cleverly checked candidates from 0 to n (as opposed to 0 to n - 1 as suggested on the exercise sheet). It doesn't hurt (because n ≡ 0 (mod n)) and it saves two tokens. With minor adjustments – such as using the elem function that returns whether a given value occurs in a list or not – one can save another token (solution by Marco Zielbauer):

quadRes n a = a `mod` n `elem` [x^2 `mod` n | x <- [0 .. n]]

A couple of students noticed that [0..n] is in fact just syntactic sugar for enumFromTo 0 n, which can, in some cases, save a few more tokens; cf. e.g. the following 22-token solution by Almo Sutedjo:

quadRes n q = or [x^2 `mod` n == mod q n| x <- enumFromTo 0 n]

Combining these two tricks, Simon Stieger found a 21-token solution, which is almost identical to the one the MC had found:

quadRes n a = a `mod` n `elem` [x*x `mod` n | x <- enumFromTo 1 n]

The nice thing about this solution is that it does not really use anything that was not covered in the lecture (other than perhaps the use of enumFromTo function).

However, one of our tutors – Herr Großer – went above and beyond and managed to beat the MC's solution with 20 tokens:

quadRes n = flip any (join timesInteger <$> enumFromTo 0 n) . on eqInteger (`mod` n)

There's a lot going on here and you are not expected or required to understand any of this. The MC will, however, do his best to explain it briefly:

• timesInteger from GHC.Num is just another name for (*) on integers (i.e. multiplication). Similarly, eqInteger is just equality on integers.
• For a two-parameter function f, join f is a somewhat cryptic way to write the function that takes an input x and returns f x x. In other words: join timesInteger is a shorter way to write (^ 2).
• The . operator is function composition (usually written as ∘ in mathematics).
• on is a nice little operator from Data.Function defined as on f g x y = f (g x) (g y). It allows you to write our equivMod function as equivMod n = (==) `on` (`mod` n) (two numbers are congruent if they are equal after reducing them modulo n).
• <$> is another way to write the map function (which we will learn about in a few weeks) as an infix operator.

If we deobfuscate Herr Großer's solution a little bit, we get something like this:

quadRes n a = any (\y -> a `mod` n == y `mod` n) [x * x | x <- [0..n]]

His tricks only make things shorter because timesInteger exists. Taking a hint from current world affairs, the MC had imposed severe restrictions on imports this year and thought this would be enough to preclude such trickery with timesInteger, eqInteger, etc. Alas, it seems that he was mistaken. Kudos to Herr Großer for finding this!

All in all, this week's solutions were perhaps not very surprising. The MC hopes that the following week's exercise will leave more room for his students' creativity to shine.

So, what are this week's lessons?

• The MC really has to streamline his competition evaluation process. Sorting through the hundreds upon hundreds of submissions with his collection of 7-year old half-rotten arcane Perl and Bash scripts did not work very well.
• Simple exercises can lead to a surprising variety of solutions, but not always.
• Things that pay off when minimising the number of tokens:
  1. inlining (eschewing auxiliary functions)
  2. a straightfoward simple solution
  3. twiddling with infix operators
  4. knowing the library functions
  5. arcane lore (cf. Herr Großer)

Die Ergebnisse der zweiten Woche

This week, the MC Sr received 156 (apparently) correct student submissions with correctly placed {-WETT-} tags. It seems that placing the tags is very difficult, and the MC grew so annoyed ploughing through submission after submission with incorrectly placed tags that he chose to do away with the MC emeritus's Perl scripts and instead automate the entire evaluation process using Haskell (whose suitability as a scripting language is greatly underappreciated, in the MC's opinion).

In any case, the variety among the solutions was still not too great this week, but already a bit greater than in the previous one. The longest submission had 254 tokens:

bernoulli :: Integer -> Rational
bernoulli x = helper 0 x (fromIntegral 1) 
    where helper k n s | n == 0 = (fromInteger 1) 
        | k == 0 = 
            if k== (n-1) then (fromIntegral (n `choose` k))  * ( s / (fromIntegral (k  - n - 1)))
            else (fromIntegral (n `choose` k))  * ( s / (fromIntegral (k  - n - 1))) + (helper (k+1) n ((fromIntegral (n `choose` k))  * ( s / (fromIntegral (k  - n - 1)))))  
        | k == (n-1) = ((fromIntegral (n `choose` k)) * ((helper 0 k 1 ) / (fromIntegral(k  - n - 1)))) 
        | k < (n-1) = ((fromIntegral (n `choose` k)) * ((helper 0 k 1 ) / (fromIntegral(k  - n - 1)))) + (helper (k+1) n ((fromIntegral (n `choose` k))  * ( s / (fromIntegral (k  - n - 1))))) 

Clearly, the author was not optimising for number of tokens. That is fine – tokens are a silly measure after all – but nevertheless, this solution is somewhat needlessly complicated. The more complicated a solution is, the more likely it is that it will contain hard-to-spot bugs. Needlessly complicated code also tends to be quite hard to maintain.

Consider, in contrast, the following 55-token solution by Herr Rinderer (which is representative of many similar solutions by other students):

n `choose` k = product [n-k+1..n] `div` product [1..k]
bernoulli 0 = 1
bernoulli n = sum [n `choose` k % (k - n - 1) * bernoulli k | k <- [0 .. n - 1]]

This is much nicer: It is short, concise, and – given the recurrence from the problem sheet – obviously correct. This is more or less exactly the solution the MC would have written if the number of tokens were of no consequence.

However, for the sake of the competition, the number of tokens is of consequence, and 55 tokens was not enough to secure a spot among the Top 30 this week. So what can be done to shrink this? Well, look at the following 43-token solution by Herr Resch:

bernoulli 0 = 1
bernoulli n = sum [ product (succ k `enumFromTo` n) `div` product [1..n-k] % (pred k - n) * bernoulli k | k <- 0 `enumFromTo` pred n]

He achieved a respectable 6^th place by employing several simple tricks to great effect:

• inlining the definition of choose
• enumFromTo instead of the [a..b] syntax
• succ k and pred k instead of k + 1 and k - 1
• infix notation like `enumFromTo` to save parentheses around function arguments

This is almost as far as one can stretch the basic approach following the recurrence from the problem sheet, but we are not quite there yet. The MC Sr managed to get down to 42 tokens using the following approach:

f = on div product
bernoulli m = 0 ^ m - sum [enumFromTo l m `f` enumFromTo 1 k % l * bernoulli k | k <- 0 `enumFromTo` pred m, let l = succ m - k] 

This eliminates the case distinction for n = 0 by using the fact that 0 ^ 0 = 1 in Haskell. Herr Eke even managed to get to 41 tokens like this:

bernoulli 0 = 1
bernoulli n = sum [genericLength (elemIndices k . map genericLength . subsequences . genericReplicate n $ 0) % succ n `subtract` k * bernoulli k| k <- enumFromTo 0 $ pred n]

The trick he uses here is that the binomial coefficient counts the number of k-element subsets of a set with n elements. He therefore uses functions from Haskell's list library to generate a list of n zeroes, then constructing the list of all 2ⁿ subsequences of that list, retrieves all those positions in that list that contain a list of length k, and counts the length of the remaining list. This is, of course, horribly inefficient, but since we are primality counting tokens this week, that is perfectly fine. This approach could easily be brought down to 40 tokens, but as far as the MC Sr knows, that is as good as it gets with this approach.

Simon Stieger found the following nice 42-token solution using the explicit formula

for the Bernoulli numbers:

bernoulli n =
  sum [product [negate k..pred j-k] `div` product [1..j] * j^n % succ k
        | k <- enumFromTo 0 n, j <- enumFromTo 0 k]

The Top 3 all used an algorithm based on the Akiyama–Tanigawa transform, cf. the following winning 37-token solution by Herr Haucke:

atCell m n = if n == 0 then recip a else a * atCell m b `subtract` atCell a b
        where a=m+1;b=n-1
bernoulli = atCell 0

Simply put, it works like this: We start with the sequence 1, 1/2, 1/3, 1/4, …. Call this sequence a₀. We then form a new sequence of numbers from this by subtracting every number from its predecessor and multiplying the result with the position of the number in the sequence, i.e. a_{i+1, j} = (j+1)(a_i,j - a_i,j+1). We iterate this process, which gives us a big infinite rectangle of numbers. The Bernoulli numbers are simply the leftmost column of that rectangle. The following is a more readable implementation of the Akiyama–Tanigawa algorithm that might make it a bit more clear how it works:

akiyamaTanigawa :: Num a => [a] -> [[a]]
akiyamaTanigawa xs = iterate step xs
  where step xs = zipWith3 (\x y i -> fromInteger i * (y - x)) xs (tail xs) [1..]

bernoullis :: [Rational]
bernoullis = [head row | row <- akiyamaTanigawa [recip n | n <- [1..]]]

bernoulli :: Integer -> Rational
bernoulli n = genericIndex bernoullis n

Lastly, the following is the MC's 26-token version of this:

bernoulli = genericIndex $ map head $ 
    iterate ((*) `zipWith` enumFrom 1 <<< zipWith subtract `ap` tail) $ recip `map` enumFrom 1

Herr Haucke, our winner this week, had complained on Piazza about the MC's choice of -½ for B₁ instead of ½. He ended up in the first place in the end anyway, but just to prove that the MC Sr can also handle this alternative definition, here is another 26-token solution that produces B₁ = ½.

bernoulli = genericIndex $ map head $ 
    iterate ((*) `zipWith` enumFrom 1 <<< zipWith subtract =<< tail) $ recip `map` enumFrom 1

You are not expected to understand what is going on here and the MC will not even attempt to explain it. For the curious: This uses the reader monad.

What have we learned this week?

• Placing {-WETT-} tags is hard.
• There are quite a few different ways to compute Bernoulli numbers, but we have yet to find one that is shorter than the Akiyama–Tanigawa transform.
• Don't look at solutions from the token-counting part of the Wettbewerb for advice on how to write readable Haskell.

Die Ergebnisse der dritten Woche

This week, the MC Sr was very disappointed. He received only eighteen submissions in total, even though the problem that was posed was the exact one as in the previous week. This means that 16 students could simply have submitted their solution from last week (or the sample solution for that matter) and have gotten into the Top 30. That's at least 105 unclaimed free Wettbewerbspunkte! Additionally, three competitors are very lucky he received points at all: one of them called his file Excercise_3.hs by mistake, so it failed to compile. Two others forgot to include the choose functions in their {-WETT-} tags. The MC, however, noticed this and graciously decided to include it in the evaluation anyway. (It is not impossible that a few more submissions fell through the cracks due to things like this – if yours is one of them, feel free to email the MC Sr and he will see what he can do)

To make up for the unfortunate lack of submissions, the MC Sr contributed four submissions of his own. These are, of course, außer Konkurrenz. To the MC Sr's delight, the 16 solutions he did receive contained a refreshing amount of variety and he will do his best to showcase all of it in this entry.

Since the efficiency of the different submissions varies greatly, the MC Sr decided to do several phases of elimination. In each phase, a particular imput n is fixed so that a clear separation between the fast and the slow submissions can be seen. The slower ones are then eliminated and we proceed to the next phase. The performance rating is comprised of two numbers a.b, where the major performance indicator a is the number of phases survived (which typically corresponds to a better asymptotic running time complexity) and b indicates the ranking within a single major class (which probably indicates a better constant factor). The final score is then computed as 6a + b.

In the first phase, we pick n = 24 to see if the solutions work at all:

We must already bid three participants farewell. All of them did a straightforward implementation of the recursive formula from the problem sheet (much like the sample solution from last week) and simply cannot compete even for relatively small inputs. The reason for this is that in order to compute B_n, the formula requires the values of all B_i for i < n and values that are computed are never stored, but recomputed every time, leading to exponential running time.

Next, we go up to n = 50:

Again, we must say good-bye to two competitors whose solution is clearly much slower than all the others. These two also implemented the straightforward exponential recurrence from the exercise sheet, but they additionally realised that B_n = 0 for any odd n greater than 1 and added a corresponding case distinction. Frau Horne additionally implemented a slightly more efficient computation of the choose function for computing binomial coefficients.

Their solutions are, of course, still exponential, but these improvements, so for slightly larger inputs, the running time still skyrockets, which is what we see in the above comparison.

For the next phase, we have to go up all the way to n=1000 to see an appreciable difference between the solutions:

Let's focus on the solutions in the lower half of the table. They now show a bit more variety:

• Herr Le Quan and Herr Ma ^* used a memoisation approach that remembers all the Bernoulli numbers computed so far to avoid unnecessary recomputations. The MC Sr also included a more streamlined version of this in the evaluation, which is referred to as MC Sr (memoised) above.
• Herr Brase implemented the Akiyama–Tanigawa algorithm (which had already served him, the MC Sr, and some of his competitors well in the previous week). Curiously, Herr Brase's implementation is considerably slower than the MC Sr's implementation of the exact same algorithm. The reason for this is that Herr Brase uses 1 % n to create the sequence 1, 1/2, 1/3, 1/4, … whereas the MC Sr uses the function recip :: Rational → Rational. The former introduces an unnecessary GCD computation (since % does not know, a priori, that numerator and denominator are on lowest terms), which apparently slows things down quite a bit.
• The Herren Wölfert, Maul, Gruhlke, and Herr Eke all used the explicit formula already mentioned in last week's post. The latter does a bit better because he optimised the computation of the binomial coefficient a little bit.
• Interestingly, Herr Sutedjo and Herr Haucke (who are still in the race at this point) implement the same formula, but optimised it a bit more cleverly: Herr Sutedjo computes the binomial coefficients using the factorial function, which he additionally caches so that computing the binomial coefficient becomes much cheaper (using an ingenious functional data structure known as finger trees from the library). Herr Haucke computes the binomial coefficients using prime numbers, which seems to help quite a bit and is likely the reason why he survived this round. He also did a lot of other optimisations, the majority of which the MC Sr unfortunately believes did not actually improve performance but only made the code less readable.
• Herr Megdiche goes a step further and uses arrays instead of sequences, which of course provide constant-time access. He uses the formula from the exercise sheet and memoises both the values of B_n computed so far and the binomial coefficients in a beautiful mutual recursion – the function b uses the values from the array bernoullis, and the array bernoullis is filled with the results of the function b. This exploits the laziness of Haskell, and the memoisation combinators from the various Hackage libraries work in much the same way.

^* The MC Sr is never quite sure which part of a Vietnamese or Chinese name to use to address someone. Feel free to correct him via email if he got it wrong! Of course, that goes for any other mistakes he makes as well, be it with names or otherwise.

All of these algorithms have polynomial complexity. However, we still see a significant change going to n = 2000:

The MC Sr's Akiyama–Tanigawa implementation (MC Sr (AT)) is finally kicked out of the race. Herr Sutedjo's and Herr Haucke's implementation of the explicit formula does not survive this round either, nor does Mr Megdiche's memoised naïve recurrence.

With that, we have arrived at the podium. For good measure, let's go over 9000 – to 10000, to be precise:

In this step, the last three remaining student submissions get kicked out. In any case, they provide results within a reasonable time for n = 5000. They work like this:

• Herr Thieme's algorithm is a bit tricky to understand. It seems to use Pascal's triangle to compute the binomial coefficients and the Bernoulli numbers at the same time, using memoisation. He does not use any fancy data structures to store the memoised values, but he does not have to – all lists are always traversed left-to-right, so there are no expensive accesses anyway.
• Herr Stieger uses Faulhaber's triangle. The i^th row of this triangle contains the coefficients of the polynomial 1ⁱ + … + nⁱ that was mentioned on the problem sheet. In particular, the first column are precisely the Bernoulli numbers! Unfortunately, Herr Stieger's code contains a lot of conspicuous similarities to the one on Rosetta code (including identical spaces and variable names). The MC Sr pondered whether to disqualify him for this or not, but ultimately decided only to deduct 4 points – in the end, Herr Stieger at least made the effort to hand in something this week and he did de-obfuscate the code he found quite a bit, which demonstrates that he understands how it works. That is definitely worth something!
• Frau Chernikova did not compute the Bernoulli numbers directly, but instead computed the Tangent numbers. These are the sequence T_n = 1, 2, 16, 272, 7936, … that appears in the Taylor series expansion

  

  It turns out that it is very easy to compute B_n given T_n, so the remaining question is how to compute T_n. Frau Chernikova does this using Seidel's triangle, which goes from one line to the next by summing the values of the line above right-to-left, then left-to-right, then right-to-left etc. This pattern is also known as the Boustrophedon transform from the Greek βοῦς (ox) and στροφή (turn), because one traverses the triangle in the same way that an ox ploughs a field.

The advantage of going through the Tangent numbers is that they are integers and can easily be computed using only integer operations, whereas the other approaches used so far all used arithmetic on rational numbers, which tends to become very expensive due to frequent GCD computations.

The MC Sr's main implementation therefore also uses the Tangent numbers, but computes them with a more efficient (but still quite simple) algorithm given in Section 6.1 of this lovely paper. The implementation MC (fast) uses the same algorithm, but tries to be a bit more efficient by only using a single array with imperative updates. As you can see, the difference is minimal – as so often in Haskell, the elegant algorithm is basically fast enough, and only very little extra performance can be gained by making it ugly.

For the sake of comparison, an artisanal hand-crafted optimised C++ program by the MC Sr that uses the same approach as MC (fast) needs about 17 seconds to compute B₁₀₀₀₀. That is only about twice as fast as the Haskell code, which seems not too bad for Haskell.

There are much crazier algorithms to compute Bernoulli numbers than this. Here are three of the MC Sr's favourite ones:

• A consequence of the Von Staudt–Clausen Theorem is that the denominator of the Bernoulli number B_2n is the product of all prime numbers that divide 2n, which is easy to compute (well, relatively speaking, compared to how huge Bernoulli numbers are). The numerator is a bit more difficult to find: It is known that

  

  where ζ is the Riemann ζ function that was mentioned on the problem sheet. Now, let a be the numerator and b the denominator (which we already know). If we rearrange, we find:

  

  This means that if we approximate the right-hand side to sufficient accuracy, we can simply round to the nearest integer and thus obtain a.
• A different approach (also described in this paper in Section 5) uses the tangent numbers again: Recall that the tangent numbers can, by definition, be read off from the Taylor series expansion of tan(x). If we are interested in the Tangent numbers T₀…T_m, we can simply define T'_n = (2m+1)! / (2n+1)! T_n, which are the coefficients of the Taylor expansion of (2m+1)tan(x) and, crucially, also integers. We can then approximate (2n+1)tan(10^-p) for some sufficiently large p and read off the T_n! For instance, for m = 3 and p = 4, we get (2n+1)tan(10^-p) = 0.5040 0000 1680 0000 0672 0000 0272, from which we can read off the values 5040, 1680, 672, 272. Converting these T'_n back to T_n, we get 1, 2, 16, 272 as expected. With some tricks, all of this can be implemented entirely with integer arithmetic (of course, using powers of two instead of powers of ten); however, it is quite difficult to implement this efficiently because the numbers involved get absolutely huge – we're talking many millions of digits. The MC included a draft of an implementation of this as MC (power series), and it did okay.
• Our tutor Herr Großer went a bit overboard and implemented Harvey's multimodular algorithm that computes B_n modulo many different prime numbers (the MC is not quite sure how) and then uses the Chinese Remainder Theorem to reconstruct the actual value of B_n. This is probably the fastest known algorithm to date for large n, so it is not too surprising that Herr Großer's solution wins over the MC Sr's for n = 10000.

What have we learned this week?

• Exponential algorithms are not good, but not handing in a solution at all is much worse.
• Memoisation is a nice and straightforward way to gain performance.
• Doing a bit of research (e.g. googling) is good and can secure you a top place – but do not simply copy-paste code or you will make the MC grumpy. You do not want the MC to be grumpy. That goes for all the MCs you will encounter, but the MC Sr is the oldest and therefore already has a high baseline value of grumpiness.
• It is not quite obvious how to optimise in Haskell. The lecture will briefly talk about this, but probably not go into too much detail. As a quick primer:
  • Haskell is lazy (if code doesn't get executed, it probably doesn't incur any cost, so eliminating it doesn't give you any benefit)
  • However, large unevaluated thunks are usually bad because they consume a lot of memory, and a lot of memory means a lot of garbage collection.
  • GHC is really good at optimising, so many ‘optimisations’ a beginner may try to do by hand will have next to no effect. In particular, operations on lists (map, filter, foldr, length, etc.) are usually fused, so attempting to pack all of that into a single tail-recursive function to avoid building the intermediate lists is commendable, but usually pointless.
• Efficient algorithms do not have to be long or ugly, especially in Haskell.
• Herr Großer has too much time on his hands.

By the way, the MC Sr is introducing a new feature next week: If you have any important comments for the MCs (e.g. an alternative solution that somehow does not make it through the test system), please include them in your submission like this to ensure they do not miss them:

{-MCCOMMENT
Hello MC! Here is my alternative solution:

bernoulli n = 4
-}

Die Ergebnisse der vierten Woche

This week, we received an encouraging 96 (correct) submissions, teaching us to always award a homework point for the Wettbewerbsaufgabe. To whittle these down to a Top 30, we spell checked 5 misspelled words of 5-10 characters against a dictionary of the 100 most common english words. Even unoptimised solutions should be able to do this in a fraction of a second. Setting the cutoff at 2 s leaves us with 30 submissions. As usual, we also have some entries hors compétition: A hyperoptimized solution by the MC Sr, an implementation based on BK-trees by co-MC Rädle (the MC Jr Sr?), and one using a simple but highly effective optimization by co-MC Stevens (the MC Jr Jr). More on these later.

Similar to last week, we will proceed in stages to distinguish submissions with different asymptotic running times. In the first phase, we simply ran the same test as before but increased the size of the dictionary to 1000 words:

Despite the generous time limit of 5 s, this already eliminates a whopping 17 contestants. All of them implemented lightly optimized versions of the recurrence on the problem sheet, which leads to a comfortably exponential running time. Here is a relatively clean example of such a solution, using only material that has been covered in the lecture:

editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = dab (length a - 1) (length b - 1) 
  where
    m = (length a) + (length b)
    dab i j = minimum [if i < 0 && j < 0 then 0 else m,
                       if i >= 0 then 1 + dab (i-1) j else m,
                       if j >= 0 then 1 + dab i (j-1) else m,
                       if i >= 0 && j >= 0 && a!!i == b!!j then dab (i-1) (j-1) else m,
                       if i >= 0 && j >= 0 && a!!i /= b!!j then 1 + dab (i-1) (j-1) else m,
                       if i >= 1 && j >= 1 && a!!i == b!!(j-1) && a!!(i-1) == b!!j then 1 + dab (i-2) (j-2) else m
                      ]

spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect d [] = []
spellCorrect d (x:xs) = spellCorrectWord d x : spellCorrect d xs

spellCorrectWord :: [String] -> String -> [String]
spellCorrectWord d s = 
  let dists = map (\ s' -> (s',editDistance s s')) d
      minDist = minimum (map snd dists)
  in map fst $ filter (\ (_,d) -> d == minDist) dists

There are two obvious approaches to improving the performance of spellCorrect: Make editDistance faster; or avoid running editDistance for every word in the dictionary. A good example of the latter approach can be found in Martin Fink's submission. While iterating through the dictionary, his correct function keeps track of the lowest edit distance found so far. If the difference in lengths between the search word and the next dictionary word is larger than this distance, then there is no need to compute the edit distance for this pair, since abs (length x - length y) is a lower bound on editDistance x y.

Co-MC Stevens takes this approach to the extreme. He passes the minimum distance found so far to his editDistance function, and simply aborts the computation of the distance if it can no longer be below this threshold. As we shall see, this is highly effective if there are words with low edit distance to the search string in the dictionary; which you would expect to be the case in a realistic spell checking scenario.

These optimizations do not improve the asymptotic worst case running time of the algorithm, however. In order to achieve a polynomial running time, all solutions that survived this round employ dynamic programming. That is, they avoid recomputing distances by storing intermediate values in lists or arrays. A somewhat readable example of this approach comes courtesy of Herr Zamel:

editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys = mem !! (length xs) !! (length ys)
    where
        mem = [[ed (i,j) | j <- [0..(length ys)]] | i <- [0..(length xs)]]
        ed (i,j) = minimum $ filter (>=0) [c1 i j, c2 i j, c3 i j, c4 i j, c5 i j]
        c1 i j = if i == 0 && j == 0 then 0 else -1
        c2 i j = if i > 0 then (mem !! (i-1) !! j) + 1 else -1
        c3 i j = if j > 0 then (mem !! i !! (j-1)) + 1 else -1
        c4 i j = if i > 0 && j > 0 then if xs !! (i-1) == ys !! (j-1) then (mem !! (i-1) !! (j-1)) else (mem !! (i-1) !! (j-1)) + 1 else -1
        c5 i j = if i > 1 && j > 1 && xs !! (i-1) == ys !! (j-2) && xs !! (i-2) == ys !! (j-1) then (mem !! (i-2) !! (j-2)) + 1 else -1

Here, the results of individual calls to ed are stored in the table mem. This requires very little extra implementation effort compared to the naive solution but brings with it a huge improvement in performance.

For the next stage we move to a different corpus, containing misspellings made by British and American students. As a first test, we picked 100 misspellings at random and ran them against the entire dictionary of 6137 correctly spelled words:

The time limit of 10 s eliminates 3 further students, leaving us with a Top 10. The eliminated students implemented dynamic programming but construct and update their tables in very inefficient ways, mainly by using excessive amounts of ++ operations, which are linear in their first argument.

In order to get some separation between the remaining submissions, we increase the number of misspellings to 3000:

Co-MC Stevens' submission is still up there, even though it uses a completely unmemoized implementation of the edit distance. This is because the words in this dictionary are quite short, and it is therefore likely that a pair with low edit distance will be found relatively quickly. Once such a pair has been found, his early exit optimization is able to discard most words after looking at a few letters.

This drastically changes, however, once we begin to look at longer words where a pair with low edit distance may not be found easily. In order to find a suitable test case that shows this, English is no longer sufficiently powerful. Only by switching to good old Deutsch can we make use of words like Straßenentwässerungsinvestitionskostenschuldendienstumlage or Rinderkennzeichnungsfleischetikettierungsüberwachungsaufgabenübertragungsgesetz.

For our last test case, we used a dictionary derived from the duden corpus, but discarded all those boring words of fewer than 15 characters. This leaves us with 94061 words, which we tested against 20 Bandwurmwörter of 32 - 81 characters. This might seem pretty brutal, but some submissions were able to handle this test quite well:

Notably, the Herren Stieger and Baumann were able to stay quite close to the MC Sr's contribution. Both implemented dynamic programming using arrays and added the previously described optimization that avoids computing the edit distance of pairs whose length differential is sufficiently large. Herr Fink also uses this optimization, but his choice of lists instead of arrays slows him down somewhat. Herr Stieger additionally implemented the early exit optimization.

To get a little bit of extra performance, the MC Sr strips common prefixes and suffixes before computing the edit distance and uses linear space in his editDistance implementation by keeping only two rows of the table. He also implemented parallelism, but our tests were run on a single thread. Otherwise, his solution is quite similar to Herr Stieger's.

Another avenue for optimization is preprocessing the dictionary, although none of the student submissions took this opportunity. Co-MC Rädle, however, stores his dictionary as a BK-tree, which is a tree where the edit distance between a node and its k-th child (if it exists) is exactly k. When running a search word against this tree representation of the dictionary, one uses the fact that the edit distance is a metric and thus fulfills the triangle inequality. We can search for words with distance of at most d from the search word as follows: If the distance between the root and the search word is n, then by the triangle equality, the distance between the k-th child and the search words is at least n-k. We therefore consider only children in the range [d-n..d+n] in our search, because children outside this range have a distance of at least n-(d+n+1) = d+1 to the search word.

This means that we do not need to compare every word in the dictionary against the search word; empirical results suggest that on an average search ~20% of the dictionary is considered. If a word is a possible candidate, however, the edit distance needs to be computed in full in order to determine which children need to be included in the search; no early exit optimization is possible. Additionally, we cannot discard words based on their length, because it is not sufficient to know that the edit distance is larger than a certain value -- we need to know the exact edit distance to proceed. This is why the BK-tree based implementation does well in the benchmarks, but is not able to compete with the very best solutions.

What have we learned this week?

• We should always award homework points for the Wettbewerbsaufgabe, lest we get fewer and fewer submissions.
• Wettbewerbspunkte need not be hard to come by; lightly optimized solutions scored 10 points this week.
• Dynamic programming can be simple to implement and highly effective.
• Computing something quickly is still slower than not computing it at all. (cf. co-MC Stevens)
• Sometimes different types of optimization can get in the way of each other, as is the case with BK-trees.
• The students are coming closer than ever to besting the venerable MC Sr.

Die Ergebnisse der fünften Woche

*cough cough, sniff, inhale* yes, this is the MC Jr speaking. Little did he know when leaving his beautiful office that he shall not return for a 3 days. The reason for his long absence are the long paths through the intriguing nature surrounding the Garchosibirsk campus that the 67 delightful submissions for week 5 were computing. The MC Jr owes you a great debt of gratitude for this splendid experience.

Moreover, he received obligatory, highly optimised, linear time submissions by the MC Sr and the tutor that has too much time on his hands: Herr Großer. As a matter of fact, the longest path problem is quite computationally expensive (NP-hard) in general, but for DAGs, like the Garchosibirsk campus, the problem is rather easy to solve (linear time). Just like his more senior fellow, the MC Jr decided to conduct several phases of elimination. So let's get down to business to defeat the Huns 🎶 to trenn die Spreu vom Weizen 🌾.

The first pre-processing step, round -1 (minus one), consists of eliminating all submissions that do not pass the tests on the server. At this phase, we already have to say goodbye to one of the top ranked participants, Herr Stieger, who did not submit a working solution. Just by chance, the MC Jr actually discovered that Herr Stieger submitted a solution using the {-MCCOMMENT...-} feature, but nevertheless, the provided solution uses the unsafe Data.Array.ST module that does not compile on the server. We are sorry Herr Stieger, but same rules for everyone:

1. The submission needs to pass the tests on the server
2. An optional, alternative solution provided in the comments needs to at least compile on the server

Herr Stieger, by the way, used the topological order of the graph – an approach that many top-ranking FPETs fancied as we will see later on. Edit 26.12.2019: After having a talk with the MC Sr, it was decided to change Herr Stieger's submission to use the safe Data.Array.ST.Safe import and make his submission part of the competition. The ranking was updated accordingly.

In round 0, the MC Jr decided to perform a very basic sanity check by running all submissions against the graph provided on the homework sheet:

Seeing all the tests pass made the MC Jr happier than a box of chocolate. But then, out of nowhere, the scary word appears: FAIL.

With great horror, he realised that one of his FPETs (Functional Programmers of Excellence in Training) failed the most simple test but still passed the tests on the submission server! He decided to have a look at the solution provided by the lucky Oleksandr Golovnya:

longestPath g t = head [snd x | x <- topsort [(v,0)| v <- fst g] (snd g), fst x == t]

topsort [] e = []
topsort (v:vs) e = [v] ++ topsort [(fst x, if elem (fst v,fst x) e && 1+snd v > snd x then 1 + snd v else snd x) | x <- vs] e

First things first: Let's clean up the code.

longestPath (vs,es) t = let ts = topsort [(v,0) | v <- vs] es in
   head [c | (t',c) <- ts, t' == t]

topsort [] es = []
topsort ((s,c):vs) es = (s,c) : topsort [(s, if elem (s,t) es then maximum (1 + c, c') else c') | (t,c') <- vs] es

That's better. Here are a few things to keep in mind:

1. Split long expressions into simpler subexpressions to increase readability (e.g. let ts denote the result of the topSort call)
2. Use pattern matching on tuples to avoid fst and snd calls
3. Do not write [x] ++ xs to concatenate a single element to a list; just use x : xs

Anyway, putting all the stylistic things aside, the topsort function sadly does not topologically order at all but merely recurses on all vertices in given order (which could be anything!) and updates the distances to all neighbours with higher index, completely neglecting the fact that there might be edges to vertices with a lower index. How this fails can easily be seen when we use Herr Golovnya's submission on our small example containing and edge from node 4 to 3:

longestPath = ([1..5] , [(1 ,2) ,(2 ,3) ,(2 ,4) ,(3 ,5) ,(1 ,4) ,(4 ,3) ,(4 ,5)]) 5 = 3

The MC Jr sadly made things too easy on the test server and only generated graphs not containing such edges. So, you got lucky this time and well-deserve your homework point Herr Golovnya, but you are sadly out of the competition. Remaining FPETs: 66 + 2

Next, the MC Jr started elimination round number 1: checking for cheeky FPETs that just assumed that the MC Jr's stroll will always start at vertex number 1. Taking the following simple graph reveals the sloppy instruction readers:

A long list of FAILs were printed on his GNU terminal of trust. 19 (that's almost a third of all submissions; #quickmaths) FPETs tried to trick the MC Jr. Relentlessly, each and every one of them will be eliminated – the MC Jr will start his walks wherevere he wishes to! Again, we have to say goodbye to some top-tier candidates at this stage, among others Frau Chernikova, Herr Soennecken, and Herr Haucke. Just like Herr Stieger, they made use of a topological ordering algorithm. The latter even hoped for some small-scale optimisations inlining his updateMap function and left the following comment:

Inlining this is akin to thinking that putting spoilers on your car adds horsepower, but now it looks a little more as if I knew what I was doing
{-# INLINE updateMap #-}
...

The MC Jr agrees and also suggests that instead of investing into small-scale optimisations, one should first prove one's implementaiton to be correct – in the best case, using Isabelle (#Dauerwerbesendung). Some other submissions got really confused with computer science and mathematical lingo, calling their topoligcal ordering a topology. The MC Jr hence kindly provides the following pictures that should clear up all confusion.

Finally, we get our hands feet dirty and start our first walk. A walk along 32 vertices. A walk so short, the MC Jr was barely able to leave the Magistrale. A small number of 5 FPETs, however, took longer than a fifth of a second (an ETERNITY!) to compute the distance. Sad! Remaining FPETs: 42 + 2

And so the same game repeats: the MC Jr increases the number of nodes to 40 (a quick stroll to the Interimsgebäude), eliminating another 27 FPETs (15 + 2 remaining), and then, he cannot quite remember the exact number, but he guarantees something between 60 and 200 (a brisk walk to the U-Bahn), to eliminate a further 10 FPETs (5 + 2 remaining) that sadly did not quite make it into the group of big girls and boys.

Before continuing with the quarter-finals, the MC Jr decided to time the submissions kicked out thus far. After all, it is almost Christmas time and he wants to hand out some gifts aka. precious ranking points. Some rounds of competition on the Interimsgebäude graph led to the following ranking – congrats to all the winners so far 🎉:

Almost all quarter-finalists made use of basically the same idea: In order to compute the longest path from the source s to some node v, it suffices to recursively calculate the longest paths to v starting from v. As, by assumption, our graph is a DAG and s is its only source node, the result of this computation will be the longest path from s to v. In other words, if l(v) denotes the longest path from s to v, then l(v) satisfies the following recurrence relation:

l(v)=max({0} ∪ {l(w) | (w,v) ∈ E}).

This backwards traversal also has the nice effect that one does not need to explicitly search for the starting node s. The MC Jr decided to show Herr Pappenheim's crisp one-line solution as a reference for this approach:

longestPath g@(vs, es) v = maximum (0:[1+(longestPath g x) | (x, a) <- es, a == v])

Note how Herr Pappenheim made use of the great as-patterns in order to inspect the components of g while still having the possibility to refer to g in its totality. If the competition would have been about style and elegance, Herr Pappenheim surely would have won! ✨

Okay, now let's get real. For the semifinals, the MC Jr drew a graph from his office to the Maschinenwesen building. It's a dense graph containing 639 vertices, including the soft-opened Galileo (according to reliable sources, the hard opening is planned at about the same time as the opening of the BER). Running the semifinalist's submissions for one second reveals the four finalists. I am afraid, but the following FPETs got eliminated due to a timeout:

An optimisation of the previously explained backwards traversal approach can be obtained by means of a tail-recursive implementation using an accumulator to store all so-far visited nodes and the so-far computed distance. This approach has been followed by Herr Nguyen, putting him on place 5 for this week. Congrats!

longestPath (node, edge) t = go [t] 0
 where go [] n = n-1
       go xs n = go (nub $ concat [ [w | (w,u)<-edge, u == x] | x<-xs]) (n+1)

Herr Ma and Herr Achenbach, however, made use of a topological order approach (that will be explained shortly), winning 28 and 27 points respectively. Congratulations! 🥳

For the finals, the MC Jr went to great pains and drew the whole Garchosibirsk campus containing a Fantastilliarde – in digits 20.000 – nodes and millions of edges using only a ruler and a compass. At first, he let the finalists compete on the whole dense graph he constructed. He then ran a second round on a very sparse graph that still contained 20.000 nodes but only 40.000 edges. The finalists' approaches can be summarised as follows:

• Herr MC Sr Manuel Eberl and Herr Ghorbel take the optimisation of the backwards traversal approach a step further. Herr Eberl uses an optimised version of nub for integers, hash maps instead of lists for quicker lookups, and a memoisation map storing the values of the so-far computed l(v) values. Herr Ghorbel decided to use Arrays and the graph library provided by Haskell instead.
  
  

  -- Faster O(n log n) nub specialised for integers.
  -- Probably doesn't make a difference but still.
  intNub :: [Int] -> [Int]
  intNub = map head . group . sort
  
  longestPath :: Graph -> Vertex -> Int
  longestPath (vs, es) v = longestPath' v
    where succMap = HS.map intNub $ HS.fromListWith (++) [(v, [u]) | (u, v) <- es]
          succs v = HS.lookupDefault [] v succMap
          m = HS.fromList [(v, longestPath'' v) | v <- vs]
          longestPath' v = fromJust (HS.lookup v m)
          longestPath'' v = maximum (0 : map ((+1) . longestPath') (succs v))
  

  Implementation by the MC Sr
  
  

  maxi::[Int]->Int
  maxi [] = -1
  maxi xs = maximum xs
  
  longestPath :: Graph-> Vertex -> Int
  longestPath (v,e) s = f s
    where cmp (a,_) (b,_) = compare a b
          min_v = minimum v
          max_v = maximum v
          graph = buildG (min_v,max_v) e
          tgraph = transposeG graph
          topo = topSort graph
          iTable = listArray (min_v,max_v) (map snd (sortBy cmp (zip topo [min_v..max_v])))
          f x = 1 + maxi [memo!(iTable!nxt)|nxt<-(tgraph ! x)]
          memo = listArray (min_v,max_v) (map f topo)
  

  Implementation by Herr Ghorbel. It is not quite clear to the MC Jr whether using the topological sorting to construct the indices (iTable) for the memoisation map memo has any benefit. A quick experiment did not show any major performance difference when replacing the last four lines by the following two:
  

          f x = 1 + maxi [memo!nxt|nxt<-(tgraph ! x)]
          memo = listArray (min_v,max_v) (map f [min_v..max_v])
  

  
  
  
• Herr Großer and Herr Sutedjo used a varient of the following topological order approach:
  1. Create a topological order of the graph. This can be done, for example, by using a depth-first-search algorithm, or by using the following, more visually appealing, strategy: select all nodes without incoming edges, remove them from the graph (including their outgoing edges), and store them at the front of the ordering. Then repeat until you are left with nothing but cold void.

     

  2. Process all vertices in topological order. For every vertex being processed, update the distances to its neighbours using the distance of the current vertex.
  The two implementations greatly vary in complexity. While Herr Großer created a "I somehow have to make this type"-battle zone 💣, Herr Sutedjo followed the "Let's optimise but not over-engineer"-principle.
  
  

It was a close race, but the final results are *can I please get some drums rolling*

Note: As you can clearly see in this beautifully formatted table, the MC Jr has a very strong web-development background.

So what have we learned this week?

• Make sure you submit something that passes the tests on the server.
• Passing the tests on the server does not guarantee correctness of the submission. Sorry Herr Golovnya and all "vertex number 1"-starters! But no need to worry. There's nothing lost and many points still to gain in upcoming competitions!
• Putting spoilers on one's car only gets you style points in Need for Speed but not the legendary FPV competition.
• A cow is a sphere. In symbols: 🐄 = 🌐
• Elegant and short implementations can get you very far
• Complicated implementations might get you even further *looking at Herr Großer*
• Using optimised libraries and cleverness gets you the furthest!
• Garchosibirsk is a mysterious, huge place.
• The MC Jr is a huge Mulan and Forrest Gump fan.
• Just to say it again: writing competition entries takes forever; it's 3am, good night! *drops mic*

Lastly, here's the combined result table for week 5. If you have any complaints, contact the MC Jr – he still is a MC in training and total correctness is hence not guaranteed.

Edit 26.12.2019: Herr Stieger's submission (modifed using safe array imports) has been added to the competition, scoring a bronze medal. Congratulations! The MC Jr decided to deduct 5 points for his unsafe imports that manually had to be changed and, as a matter of fairness, keep everyone else's points the same.

Die Ergebnisse der sechsten Woche

We at the Übungsleitung like to change things up and therefore the honourable task of writing this week's competition blog entry was bestowed upon the MC Jr Jr, Lukas Stevens. In this week we received a grand total of 109 submissions that passed the tests on the server and had Wettbewerbstags. As is tradition, some students managed to place the tags incorrectly which the MC Jr Jr generously fixed for them. Additionally, the hacky lovingly handcrafted tool to evaluate the Wettbewerbseinreichungen is not nearly as sophisticated as the submission system; due to this Umstand, the tool breaks if a student omits the type annotations. The MC Jr Jr embarked on a quest to fix these type annotations which was about as tedious as beating Pokémon without taking a single hit (this might be a slight hyperbole). Tedium aside, the MC Jr Jr was delighted to see a new strategy emerge that allows students to eliminate other competitors. This strategy, which we will discuss further down, forced one unlucky student to perform a Pofalla-Wende and thus we are left with 108 submissions.

Originally, this week's IBM Award for Software of Questionable Quality would have gone to a solution with 153 tokens; however, the MC Jr Jr noticed that the submission included the example prime program inside the tags upon closer inspection. This confirmed the suspicion that not even a very creative student could overcomplicate the task by that much. Instead, the award is granted to the solution of another student which is layed out in all its glory below.

t31 (a,b,c) = a
t32 (a,b,c) = b
t33 (a,b,c) = c

traceFractran :: [Rational] -> Integer -> [Integer]
traceFractran rs n 
    | t31 aux2 = (t32 aux2) : (traceFractran rs (numerator $ t33 aux2))
    | otherwise = [n]
        where
            aux2 = aux rs n
            aux [] n = (False, 0, 0%1)
            aux (r:rs) n = if denominator (n%1 * r) == 1 then (True, n, n%1 * r) else aux rs n

Apparently, the student in question is not afraid of loosing a billion dollars and implements a tagged tuple that looks suspiciously like a null-reference (the first component being a flag that indicates whether the tuple is null). This could be solved more elegantly using the Maybe type, but as Maybe hadn't been introduced in the lecture at that point the student may be forgiven in this instance. Nevertheless, the model solution by the semi-venerable MC Jr Sr only uses material from the lecture while achieving a reasonable degree of conciseness. With 49 tokens, this solution is only 2 tokens short of being in the top 30 and this without any serious effort to obfuscate optimise for number of tokens.

traceFractran fs n = 
  let prods = [numerator (n%1 * f) | f <- fs, denominator (n%1 * f) == 1] 
  in if null prods then [n] else n : traceFractran fs (head prods)

The following submission by Herr Tal Zwick illustrates that a few improvements to the model solution are sufficient to place in the top 30:

• Use where instead of let ... in.
• The infix notation `traceFractran` may allow you to omit parentheses.
• In Haskell, if is an expression so it can be used (almost) anywhere.

Achieving rank 16 in the Wettbewerb doesn't require arcane Haskell knowledge after all!

traceFractran fs n = n:if null nfs then nfs else fs `traceFractran` head nfs
    where   ni = fromIntegral n
            nfs = [numerator $ f*ni | f <- fs, 1 == denominator (f*ni)]

Instead of optimising for tokens, Herr Andreas Resch unintentionally employed a novel technique to eliminate other competitors: Herr Resch notified the MC Jr Jr that his solution passes the testcases on the server despite being incorrect. Consequently, the MC Jr Jr came up with additional tests to determine which students tried to gain a competitive advantage through a disgraceful disregard for the specification. If not for those additional tests, the winner of this week's competition would have been Herr Peter Wegmann. He provided the following implementation with 29 tokens that is as elegant as it is wrong.

traceFractran xs y = y : concat [traceFractran xs $ numerator $ x * fromIntegral y | x<-xs, y `mod` denominator x == 0]

Here, traceFractran is called recursively every time the we get an integer as the product of a rational in the list xs and the accumulator y. This gives erroneous results as soon we have more than one such product. As Herr Resch was aware of this issue, he cleverly provided an alternative solution, which keeps him in the competition ganz im Gegenteil zu Herr Wegmann who is promptly eliminated. The downside is that the alternative solution has 40 instead of the original 30 tokens which puts him in tenth place in the end. The submission of one other competitor, namely Herr Emil Suleymanov, had the same bug. Fortunately, his submission contained a simpler and also correcter version of traceFractran. The MC Jr Jr has doubts that Herr Suleymanov knowingly circumvented the specification but he decided to let Gnade walten and keep him in the race with the latter version. Nevertheless, this brings him from 29 up to 37 tokens thus placing him firmly on rank seven. The takeaway is that this tactic should be applied judiciously lest you eliminate yourself from the top 30.

All of the above implementations are quite basic and only use material from the lecture. Of course there are some people who just can't keep it simple like Herr Johannes Neubrand. Not only does he use the constructor (:%), which not even a Sith would tell you about, to match on Rationals, he also just learnt about all kinds of monadic operators. Such operators are used liberally throughout his implementation, sometimes even to the detriment of the token count (as seen in the implementation of integerProduct). It shows that we teach him well because he is becoming a true Haskell programmer who values beauty over everything else. The solution is actually (kind of) straightforward:

1. integerProduct only returns the result of the multiplication of its arguments if that result is an integer. Otherwise it returns Nothing.
2. concatMap (traceFractran fs) rs concatenates the lists that result from applying traceFractran fs to each element in rs.
3. Here, msum returns the first element in a list that is Just x and Nothing otherwise.
4. Finally, integerProduct n <$> fs is equivalent to map (integerProduct n) fs.

integerProduct :: Integer -> Rational -> Maybe Integer
integerProduct x f = n <$ guard (d == 1)
    where n :% d = fromIntegral x * f

-- Alternative implementation of integerProduct by the MC Jr Jr
integerProduct x f = case fromIntegral x * f of
  n :% 1 -> Just n
  _ -> Nothing

traceFractran :: [Rational] -> Integer -> [Integer]
traceFractran fs n =
    n :                                 -- we were definitely able to reach this one
        ( concatMap (traceFractran fs)  -- because: instance Foldable (Maybe a)
        $ msum                          -- first Just or Nothing
        $ integerProduct n <$> fs
        )

Further interesting optimisation were done with monadic operators, e.g. Herr Haucke used mempty instead of []. Nevertheless, to get near the top of the leaderboard, monadic operators were not necessary as the submissions of Herr Martin Fink and Herr Simon Stieger illustrate. Both of them achieved rank 2 by essentially providing a correct version of Herr Wegmanns solution with 33 tokens. The only significant adjustment is to use take 1 such that only the first product that results in an integer is considered in each step. Thus, the code loses little of its elegance and still only uses material from the lecture.

traceFractran rs n = n : concat (take 1 [rs `traceFractran` floor (fromIntegral n * r) | r <- rs, n `mod` denominator r == 0])

With all that said, the best submission by Herr Almo Sutedjo did employ some monadic operators to get down to 30 tokens for which the MC Jr Jr sincerely congratulates him. This is an impressive feat considering that he not only surpassed all the other students but also bested Herr Markus Großer by 1 token whose resources don't seem to be infinite after all. The details of Herr Sutedjos solution are explained below.

• Again, the operator <$> is used here instead of map.
• The expression liftM2 eqInteger truncate numerator constructs a function that compares the numerator of a rational number r with its truncated form (the integer closest to r from 0). Thus, the expression returns true if, and only if, r is an integer.
• fromMaybe unwraps a Maybe and uses the first argument as a default value in case it encounters Nothing.
• find tries to find an element in a list that satisfies the given predicate. This is also the function that Herr Oleksandr Golovnya was looking for. To find just the function you need, hoogle is a helpful tool.

traceFractran rs n = n : fromMaybe [] (traceFractran rs <$> numerator <$> (liftM2 eqInteger truncate numerator) `find` map (fromIntegral n *) rs)

Even though the above solution is impressive, there is still room for improvement: using mempty instead of [] and omitting the parentheses around liftM2 would have landed Herr Sutedjo at a comfortable 27 tokens. This brings us very close to the ever-unbeatable MC Sr who came up with the following solution that has 26 tokens:

• denominator &&& numerator <<< (* fromIntegral n) uses the combinators from Control.Arrow to construct a function that first multiplies a rational number r by n and then returns a tuple where the first component is denominator and the second component the numerator of r * n.
• After mapping this function over the list xs, we find the first numerator whose corresponding denominator is 1 using lookup 1.
• Ultimately, concatMap :: Foldable t => (a -> [b]) -> t a -> [b] is used to collect the results from the recursive calls into a list. Note that the we fold over the Maybes that are returned by lookup 1.

traceFractran xs n = n : traceFractran xs `concatMap` lookup 1 (map (denominator &&& numerator <<< (* fromIntegral n)) xs)

So what have we learned today?

• Until further notice, the MC Jr Jr kindly requests that the students annotate functions with their type within the WETT tags (type annotations are ignored when counting tokens).
• Short solution don't require material beyond that of the lecture.
• Using the MCCOMMENT tag, you may provide the MCs with pathological test cases to eliminate other competitors. But be careful not to eliminate yourself.
• Monadic operators are fun (at least to some people).

Lastly, we come to the the table of ultimate truth provided that the MC Jr Jr did not make any mistakes, which you should bring to his attention upon discovery.

Die Ergebnisse der siebten Woche

The MC Jr Sr was sorely disappointed to only receive 46 correct solutions this week. To make matters worse, some students are rather shy and omitted the WETT tags, leaving us with just 28 submissions. Passing up free Wettbewerbspunkte — in this economy? Maybe the students are getting weary after toiling in the Haskell mines for nigh on two months; maybe we should avoid arcana like transitive or closure in the problem statements. Anyhow, we shall have to make due with this meagre harvest.

This week's longest correct solution weighs in at a War and Peace-rivalling 356 tokens:

filterFor :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
filterFor [] = []
filterFor ((xc, (x1, x2)):xs) = case find (\(yc, (y1, y2)) -> y1 == x1 && y2 == x2 && yc <= xc) xs of
  Just _  -> filterFor xs
  Nothing -> (xc, (x1, x2)):filterFor xs

comp :: Eq b => [(Integer,(a,b))] -> [(Integer,(b,c))] -> [(Integer,(a,c))]
comp [] _ = []
comp _ [] = []
comp xs ys = [(xn + yn, (fst xt, snd yt)) | (xn, xt) <- xs, (yn, yt) <- ys, snd xt == fst yt]

trancl :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
trancl xs = (reverse
        . filterFor2
        . sortBy (\(x1, _) (x2, _) -> compare x2 x1))
        (multipleComp xs [] [])


filterFor2 :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
filterFor2 [] = []
filterFor2 ((xc, (x1, x2)):xs) = case find (\(yc, (y1, y2)) -> y1 == x1 && y2 == x2 && yc <= xc) xs of
  Just _  -> filterFor xs
  Nothing -> (xc, (x1, x2)):filterFor xs

multipleComp :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))] -> [(Integer,(a,a))] -> [(Integer,(a,a))]
multipleComp [] _ _ = []
multipleComp xs [] _ = multipleComp xs xs xs
multipleComp xs ys acc = let currComp = filterFor3 acc (comp ys xs) in
      if currComp == [] then acc else (multipleComp xs currComp (acc ++ currComp))

filterFor3 :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))] -> [(Integer,(a,a))]
filterFor3 _ [] = []
filterFor3 [] ys = ys
filterFor3 xs ((yc, (y1, y2)):ys) = case find (\(xc, (x1, x2)) -> x1 == y1 && x2 == y2 && xc < yc) xs of
  Just _ -> filterFor3 xs ys
  Nothing -> (yc, (y1, y2)):filterFor3 xs ys

There is some obvious code duplication here (One filterFor really ought to be enough for anybody) but other than that this is quite reasonable. The input is composed with itself until no new elements are generated (multipleComp) and then filtered to include only shortest paths. The additional sorting and reversing of the output should be unnecessary. Even the shortest solutions follow this basic approach, but are not quite as frivolous in introducing auxiliary functions.

One step up in conciseness is this particularly readable solution due to Herr Trost:

minRelations :: Eq a => [(Integer, (a, a))] -> [(Integer, (a, a))]
minRelations xs = nubBy (\(n1, (a1, b1)) (n2, (a2, b2)) -> a1 == a2 && b1 == b2) (sortBy (\(n1, a1) (n2, a2) -> compare n1 n2) xs) 


comp :: Eq b => [(Integer,(a,b))] -> [(Integer,(b,c))] -> [(Integer,(a,c))]
comp fs gs = [(n1 + n2, (fa, gc)) | (n1, (fa, fb)) <- fs, (n2, (gb, gc)) <- gs, fb == gb]


trancl :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
trancl xs = tranclRec (minRelations xs)
    where 
        tranclRec xs
            | minRelations (xs ++ comp xs xs) == xs = xs
            | otherwise = tranclRec (minRelations (xs ++ comp xs xs))

He avoids unneccessarily introducing multiple functions for composition and filtering. One area where this solution could be shortened and made more readable are the calls to nubBy and sortBy. Specifically, sortBy (\(n1, a1) (n2, a2) -> compare n1 n2 compares tuples by their first element. Luckily the combinator on from Data.Function facilitates just that. It is defined as (.*.) `on` f = \x y -> f x .*. f y, i.e. it applies a function f to both its arguments and then combines the results using the binary operator (.*.). In our case we want to apply fst to the tuples and the compare them, so the above expression can be written neatly as sortBy (compare `on` fst). To squeeze out an extra token we can write this as (comparing fst) using the comparing function from Data.Ord.

Similarly, nubBy (\(n1, (a1, b1)) (n2, (a2, b2)) -> a1 == a2 && b1 == b2) removes duplicates by comparing the second element of the input tuples for equality. This can be shortened to nubBy ((==) `on` snd).

This brings us to this week's winning solutions. We beginn with Herr Baumann, who wins a silver medal with the following 73 token solution, that manages to be concise and supremely readable:

trancl :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
trancl r = if r == new
           then r
           else trancl new
  where
    new = nubBy ((==) `on` snd)
          $ sortBy (comparing fst)
          $ r ++ [(c1+c2, (a, d)) | (c1, (a, b)) <- r, (c2, (c, d)) <- r, b == c]

The basic approach here remains the same, but he gains some tokens by inlining comp and the sorting and filtering steps. He also uses the previously described combinators comparing and on. Herr Baumann comes very close to the MC Sr, who manages to shave off an additional 4 tokens with the following 69 token solution:

trancl :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
trancl r = if r == r' then r else trancl r'
  where r' = nubBy ((==) `on` snd) . sortBy (comparing fst) $ r ++ 
             [(m + n, (fst x, snd y)) | (m, x) <- r, (n, y) <- r, snd x == fst y]

The only difference here is the slightly more token-efficient pattern matching on the tuples in the list comprehension. I does not end here however. For the first time this semester, a student has managed to outtoken the Master of Tokens himself. Herr Nguyen beats him by 3 tokens with one weird library function the MC does not want you to know about: sortOn. Okay, the function is not even that weird; sortOn f is simply equivalent to sortBy (comparing f). Here is Herr Nguyen's historic 66 token solution in its full glory:

trancl :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
trancl xs= if findTrancl == xs then xs else trancl findTrancl
 where findTrancl = nubBy (on (==) snd) $sortOn fst  $xs++[(i+j,(fst ab, snd cd))|(i,ab)<-xs, (j,cd)<-xs,snd ab==fst cd]

Before we conclude this week's competition, an honourable mention. The MC Jr Sr intended the weights of the relation to be nonnegative, but did not specify this in the problem statement. Most students — in particular all of the solutions we have looked at in this post — implicitly made this assumption anyway, and enter infinite loops if there is a negative length cycle in the input. Not so Herr Janelidze. He followed the problem statement to a tee, implementing the Bellman-Ford algorithm to handle arbitrary relations. As a token (haha) of respect and a little Aufwandsentschädigung, the Übungsleitung awards him 5 bonus points.

So what have we learned today?

• At its best, Haskell can be concise and readable.
• The Übungsleitung should try to pick more interesting problems for the Wettbewerb, or at least couch them in more attractive language.
• Relatedly, the MC Jr Sr should work harder to write clear problem statements, lest he sends some poor students down a rabbit hole. (cf. Herr Janelidze)
• Knocking the MC Sr of his perch — high atop an ivory tower — may be more feasible than previously imagined.

Here then, are this weeks results. As always, alle Angaben ohne Gewähr; let us know if anything is amiss. Addenda: We incorrectly ruled out Almo Sutedjo's 96 token solution and Martin Fink's 100 token solution, they are retroactively awarded 24 points.

Die Ergebnisse der achten Woche

There were 167 solutions this week, ‘this week’ being ‘the week before Christmas, about 4 weeks ago’. Sorry about that, but even the MC Sr celebrates Christmas to some extent, and then someone invited him to give a talk in Pittsburgh in the first week of January, so he did not have much time for Wettbewerb matters.

Anyway, now he is back, so enjoy the account of a severely jetlagged MC ploughing through 167 correct student submissions. The largest one has 160 tokens:

shoefa [] = 0
shoefa xs = checkV [x|x<-xs, x/=0] 0 0
            where checkV [] v n = n
                  checkV xs 0 0 = if (head xs < 0) then (checkV (tail xs) (-1) (0)) else (checkV (tail xs) (1) (0))
                  checkV xs 1 n = if (head xs < 0) then (checkV (tail xs) (-1) (n+1)) else (checkV (tail xs) (1) (n))
                  checkV xs (-1) n = if (head xs < 0) then (checkV (tail xs) (-1) (n)) else (checkV (tail xs) (1) (n+1))

There is quite a lot of duplication of code in there, plus some unnecessary parentheses. The recursion would also be expressed more idiomatically using pattern matching instead of head and tail. The general idea behind this solution is, however, perfectly fine: remove all the zeros from the list and recurse through it left-to-right, remembering the last sign that we have seen and the total number of sign changes so far. However, the non-tail-recursive approach would likely be better for saving tokens (at the cost of performance).

A much more streamlined and non-tail-recursive version of this approach was done by Herr Mayr in 48 tokens:

shoefa xs = help clean (head clean) where clean = filter (/= 0) xs
help [] _ = 0
help (x:xs) last = if signum x /= signum last then 1 + help xs x else help xs last

Note that he cleverly defines the auxiliary function on the toplevel (not using let or where). This is not good style, but it saves him one token. However, three tiny modifications could have saved him another 4 tokens: replacing parentheses with $, reordering the two equations for help so that we can replace [] by the wildcard _, and factoring the common part out of the if:

shoefa xs = help clean $ head clean where clean = filter (/= 0) xs
help (x:xs) last = help xs x + if signum x /= signum last then 1 else 0
help _ _ = 0

However, even that would unfortunately have been nowhere near enough for the Top 30 this week, since competition was quite tough. Herr Schneider just missed the Top 30 with the following very clever 33-token solution, which is the shortest recursive one:

shoefa (x:y:xs) = fromEnum (x*y<0) + shoefa (y*2+signum x:xs)
shoefa _ = 0

He exploits two things here: first, that fromEnum False = 0 and fromEnum True = 1, and second that for integers a and b, the sign of 2b+a equals the sign of a if b = 0, and the sign of b otherwise. This allows him to skip zeros in the list implicitly, while most other solutions have to filter them out first. The non-tail-recursive recursion here will likely make this quite inefficient for long input lists (linear space requirement vs constant space), but we do not care about that this week. It is sad that Herr Schneider's ingenuity was not rewarded with any points – unfortunately, it seems that it was simply not possible to enter the Top 30 with a recursive solution.

So what did it take to get into the Top 30? Dinh Luc managed it with the following approach:

shoefa xs = length (filter (<0) (zipWith (*) cs  $ tail cs)) 
  where cs = filter (/=0) xs

The idea here is to kick out all the zeros, then pair up every number in the list with the one after it, and count the number of such pairs where the two numbers in it have different signs. Note that this version also has fairly okay performance A number of students have similar solutions, culminating in the following work of abstract art by Herr Neubrand, which consists of a mere 17 tokens (not a single one of which is a parenthesis!):

shoefa = filter toBool              -- remove zeroes
     >>> map signum
     >>> zipWith subtract <*> tail  -- transform to differences of signs    (equals -> 0)
     >>> filter toBool              -- keep only steps with differing signs (values /= 0)
     >>> length

What is going on here? Well, first of all, Herr Neubrand does not refer to any variables in his code; he describes the shoefa function entirely using combinators such as function composition. This can save tokens if used wisely, and the name for this technique is point-free style (clearly a misnomer: since function composition is usually written as ., it tends to contain a lot of points. And as you can see with this submission, it is also often rewarded with points in the Wettbewerb.

To unravel the mystery of Herr Neubrands solution, one needs to know the following things:

• The operator (>>>) is just the flipped version of the (.) operator you know from the lecture (f >>> g = g . f, or (f >>> g) x = g (f x)).
• When given an integer, the toBool function from the depths of Haskell's foreign function interface simply returns False if the integer is 0 and True otherwise, mirroring the way ancient languages like C treat integers in conditionals.
• (<*>) is another appearance of the reader monad, whose details shall remain in the dark. Let it just be said that (f <*> g) = \x -> f x (g x).

You may wonder why he chose to use (>>>) instead of (.). The reason is that unlike (.), (>>>) has a lower precedence than (<*>) and can therefore be used here without any parentheses.

The MCs' solutions and all of the top 20 solutions (other than Herr Neubrand's) use the following approach, e.g. Herr Khitrov with 19 tokens:

shoefa = max 0 . pred . length . group . map signum . filter (/= 0)

This approach uses the group function to partition the list into blocks of adjacent numbers having the same sign and then counts how many of these blocks there are: clearly, the number of sign changes is just that number minus one – except in the case of an empty list, in which case we would get -1 instead of 0, which is rectified by putting a max 0 in the front. The winning solutions by the Herren Haucke and Soennecken are virtually identical to the MCs' combined solution:

shoefa = length . drop 1 . group . map signum . filter toBool

The toBool instead of (/= 0) saves 3 tokens, and writing length . drop 1 instead of max 0 . pred . length saves another 2, which gets us from 19 to 14.

And that brings us to the results. What a delightfully competitive week! There are quite a lot of ties (especially for 4^th place), which is why the MC decided to adjust the usual place-to-points scheme a little bit in order to avoid giving the ten people in place 4 almost as many points as the two in first place:

Lessons for this week:

• Duplication of code is usually bad.
• Haskell has good high-level combinators that can lead to code that is both shorter and more understandable.
• <*> in the reader monad is not one of them.
• Some students are really catching up with the MCs
• The MC saw quite a lot of unnecessary parenthesis in the code this week, including things like map (signum) xs. For operators like ++ and :, the precedence rules in Haskell are indeed not quite obvious and unnecessary parentheses are fine in those cases (at least outside the Wettbewerb). But in the absence of binary operators, there is really no excuse for them. The MC would therefore really like to encourage you to learn how function application works. Haskell is a functional language, so it's kind of an important concept. 😉

Die Ergebnisse der neunten Woche

I doubt that anyone implemented a CDCL-solver.

This week's challenge ("efficient SAT-solving 101") left room for many different optimisations and an endless amount of time could be spent on tuning one's implementation to the extreme. And without a doubt: our excellent students did indeed surpass the expectations.

For the evaluation, the MC Jr decided to run all submissions against 9 different test-suites and measure the performance. Most of the test-suites have already been mentioned on the exercise sheet, but also a few new ones have been added. Let's see who is going to win the prestigous SAT-championship of 2020 🏆!

Test 0: The Simplifier

As a warm-up test, the MC Jr measured the performance of the submissions' simplifier (simpConj on the exercise sheet). However, nothing exciting happened at this point and all submissions performed almost equally well.

Test 1: Positive Literals

The first test-suite consisted of instances where each clause C_i contained at least one positive literal L_i. Such instances are always trivially satisfiable: set the variable of each L_i to True and all remaining variables to arbitrary values. The MC Jr generated 3 instances using the following parameters:

Although it was stated on the exercise sheet, no student explicitly implemented any optimisations for this case. Nevertheless, 30 out of 35 submissions still made it in the given timeframe of 40 seconds. Some submissions were even very close to being on a par with the MC Jr, whose submission contained a special optimisation for these kind of formulas. How come you might wonder? Well, many students decided to simply pick the first unassigned variable in each round and assign it to True. This works pretty well in this case of course, but will fail horribly in the next test-suite...

Test 2: Negative Literals

Test-suite numéro deux is the dual of numéro uno: each clause C_i contained at least one negative literal L_i. Hence, we can simply set the variable of each L_i to False and all remaining variables to arbitrary values. The MC Jr generated 3 instances using the following parameters:

Again, the MC Jr granted each solver 40 seconds of his precious laptop computing power. While this time submissions that carelessly tried to set each variable to True got punished, efficient implementations – though not having any special case optimisation for this test-suite – climbed up the ladder, being almost equally fast as the MC Jr's special case optimisation. We shall see in the upcoming test-suites what kind of optimisations these students applied. But first, here is the ranking for test-suite 2:

Test 3: Pure Literals

For the third test-suite, the MC Jr checked whether his brave students paid attention in their discrete structures classes: the pure literal rule, as you all should remember, says that if some variable v occurs strictly positively or negatively, then it is safe to set v to True or False, respectively.

To generate the problem set, the MC Jr introduced two new variables: b_n and b_p. Each variable of index ≤ b_n will be generated strictly negatively and each variable of index ≥ b_p will be generated strictly positively. Variables between b_n and b_p will be generated according to the passed frequency of negative and positive variables. The following parameters were used to create 6 instances:

45 seconds, the MC Jr decided, shall suffice for all 6 instances... but only 4 tough submissions made it in time. Congrats to Herr Megdiche at this point who left his competitors far behind.

So did only 3 students pay attention in their discrete structures classes? Of course not! To the MC Jr's great delight, he saw that many more students did indeed remember what they were taught in year one at TUM. And since the MC Jr has a good heart – he hopes you agree ❤️ – submissions that solved 5 out of 6 problems in time shall be ranked in a separate list:

Test 4: Frequent Variables

Test-suite 0b100 was designed to check if students applied any heuristics that favour variables occuring almost everywhere. To this end, the MC Jr introduced three variables b_l, b_u, and n (with b_l < b_u). Each clause C was then created as follows:

1. Pick a random number r in [1,...,b_l] and set C=[(¬)1,...,(¬)r] (polarity is chosen with equal probability).
2. Pick a random number m in [1,...,n].
3. Add m random variables from [b_l+1,...,b_u] to C (polarity is again chosen with equal probability).

This way, variables in [1,...,b_l] occur very frequently whereas variables in [b_l,...,b_u] occur very rarely provided that n is way smaller than b_u-b_l. Here are the exact parameters that were used to create 5 satisfiable instances:

This time, 60 seconds were set as a limit to solve all instances, and 20 submissions were able to make this race. To the MC Jr's surprise, many of the top-ranking students in this category actually just submitted very simple solutions. For example, Herr Schuler's selection strategy simply picked the first variable when traversing the list of clauses from left to right. The MC Jr, on the other hand, provided a solution that picks from the smallest clause the variable that occurs the most often in the formula. This might sound like a good idea at first, but actually caused a lot of overhead as he re-computed this frequency measure at every step, ranking him just at spot number 9.

However, one can do better, like Herr Strauß: He avoids re-computing the frequency of all variables at every step by keeping the variables organised in priority buckets. Just like the MC Jr, he assigns variables that occur in smaller clauses and more frequently a higher priority. Moreoever, for each variable, he stores a list of indices that directly point him to all clauses containing the variable. This speeds up substitution since only clauses containing the substituted variable can be visited this way. Very nice optimisation Herr Strauß – the MC Jr is very impressed!
Update 03.02.2020: The MC Jr was informed by Herr Strauß that his submitted implementation does not use the priority buckets for he could not get rid of all bugs in time. Instead, his algorithm uses a more simple approach: select a variable from a clause containing the least amount of variables. Nevertheless, the MC Jr stays impressed even if Herr Strauß's priority buckets did not make it to production at the end of the day.

Again, the MC Jr also decided to separately rank all students that at least solved the first 4 instances in time:

Test 5: One Literal Rule/Unit Propagation

For the fifth test-suite, the MC Jr once more checked whether his students paid attention in their discrete structures classes: the one literal rule (aka unit propagation) says that if there is some clause C containing only one literal using variable v, then v needs to be set to

1. True if it occurs positively in C or
2. False if it occurs negatively in C.

To generate the test-suite, he fixed two variables l and m with l < m and then generated the following clauses:

[1]
[¬1, 2]
...
[¬1, ¬2,...,¬(m-1), ¬m]
[¬1, ¬2,...,¬(m-1), m, m+1]
[¬1, ¬2,...,¬(m-1), m, ¬m+1, m+2]
...
[¬1, ¬2,...,¬(m-1), m, ¬m+1,...,¬(2m-1), ¬2m]
[¬1, ¬2,...,¬(m-1), m, ¬m+1,...,¬(2m-1), 2m, 2m+1]
[¬1, ¬2,...,¬(m-1), m, ¬m+1,...,¬(2m-1), 2m, ¬2m+1, 2m+2]
...
[¬1, ¬2,...,¬(m-1), m, ¬m+1,...,¬(2m-1), 2m, ¬2m+1,...,l]
[¬1, ¬2,...,¬(m-1), m, ¬m+1,...,¬(2m-1), 2m, ¬2m+1,...,¬l]


Explanation: The first time a variable occurs, it occurs positively. From that point onwards, it always occurs negatively. This rule is reversed if the variable is equal to 0 modulo m. This way, the first clause forces variable 1 to be True. Then the second clause becomes a unit clause and forces the next variable assignment, and so on. The last clause then causes a contradiction, i.e. all instances are unsatisfiable. The parameters used to create the test-suite are as follows:

Some 35 seconds were granted to each submission to solve all 5 tasks, but only 5 submissions made it in time. Needless to say, all top-5 submissions implemented the one literal rule. The best-scoring submissions – such as Herr Schneider's, the winner of this category (*tips hat*) – moreover use HashSets or IntSets for optimised lookups in the formula.

But many more diligent students implemented the one literal rule in a rather efficient way, and so 7 more submissions finished at least the first 4 tests. One of them, Frau Chernikova, even made it to the top of the second round using simple lists and very very clean code – congrats!

And 32 submissions in total made it at least up to problem 3:

Test 6: Short Clauses

Alright, for test-suite Succ(5), the MC Jr wanted to check if students did not only optimise their selection strategy for unit clauses but short clauses in general. For this, he fixed two numbers l and b. He then created l clauses of size 1 up to l with random literals. Then, for each clause C, he added r more literals to C where r is a random number in [1,...,b]. The following parameters were then used to create 4 satisfiable instances:

For this round, the MC Jr decided to let 40 seconds pass for each submission – more than enough for 22 students! The top submissions are all pretty much on a par, and it seems like no submitted optimisation had a relevant impact. The MC Jr's variable frequency and shortest clause length computation even made matters worse and put him on spot 21 for this round 😢 Sometimes simple things simply work better.

Here are all missing submissions that solved the first 3 instances:

Test 7: 2SAT

For this test-suite, the MC Jr wanted to check if any submission implemented an opimised version for the 2SAT problem. In 2SAT, each clause contains 2 variables. In contrast to 3SAT (3 variables in each clause; not to be confused with the TV channel 📺), which is NP-complete, the 2SAT problem can be solved in linear time. The motivated student shall be referred to the linked Wikipedia article that does a good job at giving an overview on different algorithms. The following parameters were used to create 6 instances:

6 Problems. 70 seconds. 0 2SAT optimisations, but 22 winners. Though no one (including the MC Jr – he also needs a break occasionally) implemented a subexponential 2SAT algorithm, submissions that at least implemented some sort of DPLL variant performed better than the completely naive submission on average. Congrats to all 2SAT champions!

And again, here is the ranking for students cracking the first 5 problems:

Test 8: Horn-SAT

For the second last test-suite, the MC Jr checked one more special satisfiability problem: the Horn-satisfiability problem. The Horn-satisfiability problem consists of a set of Horn clauses. A Horn clause is a clause with at most one positive literal. As it is the case for 2SAT, the Horn-SAT problem can be solved in linear time. Again, the motivated student shall be referred to the linked Wikipedia article for details.

To create problem instances, the MC Jr assigned frequencies to the following 3 categories of horn clauses:

1. A fact is a horn clause with no positive literal.
2. A rule is a horn clause with at least one negative and positive literal.
3. A goal is a horn clause with no negative literal.

He then created 5 tests using the following parameters:

Though, yet again, no submission implemented any special optimisation for Horn-SAT, submissions that have an effective unit propagation rule tend to perform better in this case (any goal clause is a unit clause). Here are the results – congrats to Herr Neubrand for winning this round and using higher-order functions like a champ!

Test 9: Random Input & Pigeonhole

Last but not least, the MC Jr challenged all students' submissions to solve two randomly generated formulas and a very special SAT-problem: the pigeonhole formula. The pigeonhole formula tries to put n+1 pigeons into n holes such that each hole contains at most 1 pigeon. Obviously, such an assignment is impossible. However, SAT-solvers have a provably hard (i.e. exponential) time showing that this is indeed the case. In the words of SAT-master Marijn Heule (paraphrased from a talk the MC Jr attended):

My 8-year old nephew was immediately able to tell that there cannot be any such assignment. My fancy SAT-solver, on the other hand, simply exploded 🔥🔥🔥

To create the two randomly generated formulas, the MC Jr used the following paramters:

The pigeonhole formula (for n=15) consisted of the following clauses:

1. [x_i,1,...,x_i,14] for each i in [1,...,15] (each pigeon needs to be in at least one hole)
2. [¬x_i,k, ¬x_j,k] for each i≠j in [1,...,15] and k in [1,...,14] (there cannot be two pigeons in the same hole)

For the last test-suite, he granted each submission a generous 130 seconds. Here are the results:

Sadly, no wonders were done this day and so the pigeonhole formula remains the Endgegner of SAT-solving. Most students did, however, solve the first two formulas in a reasonable time. Once more, the MC Jr tips his non-existent hat for this accomplishment! 🎩 Again, many simple submissions performed very well in this ranking whereas over-engineered solutions, such as the MC Jr's, took too much time computing non-important heuristics.

Special Shout-Outs and More Optimisations

At this point, the MC Jr wants to give a few shout-outs to some beyond average implementation efforts:

1. Herr Strauß and Herr Schneider knew no pain and implemented a CDCL-solver. Broadly speaking, a CDCL-solver not only backtracks in case of an unsatisfiable branch, but also analyses which literals caused the contradiction and adds new clauses, blocking analagous future assignments.

   Whereas Herr Strauß's implementation was very successful, especially in combination with his above-mentioned bucket data structure for variables, Herr Schneider realised that his CDCL-solver actually performs worse than his more basic DPLL implementation and only submitted it using the {-MCCOMMENT-}-feature. The MC Jr was sadly able to verify this worry with a few testcases but still wants to say: respect!
   Update 03.02.2020: As noted above, Herr Strauß actually ended up submitting a more simple DPLL solver for he could not fix all bugs for his priority buckets and CDCL solver in time.

   Btw (neben dem Weg) Herr Strauß's submission unarguably also wins the award for the most over-engineered submission or as he himself put it:

   --Das ist wohl etwas aus dem ruder gelaufen

   🚣🚣🚣 Yes indeed, but it surely was great fun! 🚣🚣🚣

2. Herr Janelidze wrote an impressive amount of optimisation code; sadly, the optimisations were not actually that helpful and quite costly, making him lose against primitive submissions in many cases. But cheer up! You deserve the MC Jr's respect which obviously is worth a lot!
3. Herr Haucke wrote a very involved but also effective unit propagation algorithm that puts unit clauses at the front of the formula in each step. Nice work! On a side note, Herr Haucke also made use of an efficient integer encoding of literals: instead of storing literals in the form "Pos \"n\"" and "Neg \"n\"", one can simply store them as "n" and "-n", respectively. This allows one to model clauses using IntSets, which are more efficient than lists for lookups. Herr Haucke left some nice comment regarding this matter:

   Use IntSets... because I low-key hate the fact that variables are Strings...

4. YOU! Yes, you deserve a special shout-out too for participating in the contest, making functional programming great again, keeping our classes fun and interactive, and also reading this very long blog post!

As a last note, the MC Jr wants to describe one more very effective optimisation that was out of scope for this competition: restarts. SAT-solvers easily run into very long, non-successful branches that they might not be able to exit in time. For this reason, modern SAT-solvers give up on their current run after a given time and restart with a new selection of variables.

Final Ranking

To combine all previous rankings into a final SAT-score, the MC Jr distributed 1+...+30=30*31/2=465 points to each previous ranking multiplied by the following factors:

The resulting SAT-score is then used to distribute the final 465 competition points of this week. And here it is: the final 2020 SAT-championship ranking!

As usual, the MC Jr tried his best to avoid any errors. If you think something is wrong, please send him an e-mail.

So... what have we learnt this week?

• One can spend and infinite amount of time in optimising SAT-solvers.
• Life is finite, and hence the perfect SAT-solver cannot be written.
• Sometimes simple things simply work better.
• Putting birds into holes is painfully difficult for a computer 🐦🐦🐦 💻🔥.
• Giving up and restarting is actually not so much of a bad strategy 🏳️.
• Special memo to the MC Jr: always make your test results easily parsable from the beginning...
• SAT-solving is a lotta fun! The MC Jr knows that you think so too, and so he invites you to join the best seminar of the upcoming semester: Automated Reasoning (#Schleichwerbung)

Die Ergebnisse der zehnten Woche

For the Domineering game, we received a total of 182 submissions with WETT tags as per the game website. To enter the competition, you had to defeat the grandpa both as the vertical and the horizontal player. His strategy is quite simple: he always places the domino on the first free position he finds on the board. The more sophisticated strategy of the sister was a tougher nut to crack as only 17 students managed to beat her. Alas, beating the sister was no guarantee to enter the final evaluation for which the MC Jr Jr selected the top 30 students from the leaderboard (modulo ties). The final ranking was determined by a round-robin tournament where each student went up against every other student 40 times (20 times each as the vertical and horizontal player). To account for the variance brought on by randomised strategies, the MC Jr Jr decided to grant the same rank to all students which are not more than 9 wins apart. This, however, brings us to a whopping total of 25200 games that have to be simulated, which take several hours despite parallelising the simulation to 8 cores. Additionally, the MC Jr Jr initially made the mistake of working on the same machine while performing the simulation leading to several games with timeouts. The MC Jr Jr simluated the games again to eliminate all timeouts. With the logistical problems learning opportunities out of the way, we come to the truly interesting part of this week's Wettbewerb, namely the strategies.

A simple scoring mechanism for moves suffices to get your name on the leaderboard: evaluate all valid moves and pick the move that minimises the number of valid moves left for the opposing player. This stratgy was employed by 14-15 submissions (the MC Jr Jr has a hard time understanding Herr Florian Glombiks code) landing all of them on rank 18. Herr Jonas Hübotter submitted a particularly succinct implementation of this approach. Note that validMoves is not shown in the Codeschnipsel below but it just goes over all moves and selects all those for wich isValid holds. As Herr Markus Großer seemed to be slacking off in the recent weeks, the Übungsleitung pressured encouraged him to submit a solution in the Tutorbesprechung during the Wettbewerb. The MC Jr Jr is glad that he came up with a solution, an elegant one at that, because this always gives the MC Jr Jr something to write about. If you want to learn about some of the more obscure underappreciated operators that Haskell offers, look no further than the second solution below.

-- Solution by Jonas Hübotter
christmasAI _ game = fst $ minimumBy (comparing snd) (weightedMoves game)

weightedMoves :: Game -> [(Pos, Int)]
weightedMoves game = [(pos, length (validMoves (playMove game pos))) | pos <- validMoves game]

-- Solution by Markus Großer
christmasAI _ g@(Game b p) =
    (,) <$> [0..11] <*> [0..11]
    & filter (isValidMove g)
    <&> (,) <*> numValidMoves . playMove g -- yay for obscure combinator usage
    & (((-1, -1), maxBound):) -- Giving up if no valid moves left
    & minimumBy (comparing snd)
    & fst
  where
    numValidMoves g' =
        (,) <$> [0..11] <*> [0..11]
        & filter (isValidMove g')
        & length

Now, how do we improve on the above strategy? This is what Herr Roman Heinrich Mayr and Herr Thomas Ridder supposedly thought to themselves. Unfortunately for them, they both performed a Verschlimmbesserung which resulted in elimination from the top 30. Herr Mayr's strategy in particular performs much worse than all the other submissions despite the fact that his strategy, which he explains in his excellent documentation, seems reasonable enough. Herr Aleksandar Jevtic, on the other hand, made two noticable improvements on the above strategy:

• He uses an improved scoring function that maximises the difference between the number of moves for himself and for the opponent.
• To anticipate the moves of the opponent, he simulates not one but several moves successive moves where in each turn he takes a sampling of the best moves according to the scoring function. This is a restricted version of the minimax algorithm.

In code, his scoring mechanism for moves looks like follows:

-- Evaluation = (# valid moves opponent could make) - (# valid moves I could make) -- goal = minimize this value 
evalMoves [] _ = []
evalMoves (m:ms) game = (length (possibleMoves newGame) - length (possibleMoves $ switch newGame), m):(evalMoves ms game)
  where newGame = playMove game m

possibleMoves game = [(r,c) | r<-[0..11], c<-[0..11], isValidMove game (r,c)]

With this strategy, Herr Jevtic managed to beat the sister who uses the same scoring function but does not simulate several successive moves. A natural extension of this approach is to increase the number of moves one considers in each step; however, the search space quickly explodes if one considers too many moves. To mitigate the combinatorial explosion, Herr Le Quan Nguyen sets the number of moves to look ahead depending on the number of valid moves left for him. This change is small but yields a noticable improvement in the number of wins compared to the previous strategies. Herr Bilel Ghorbel restricts the search space even further with alpha-beta pruning where branches in the search tree are pruned if they cannot lead to a better score than the best known branch. The performance of alpha-beta pruning depends in large part on the effectiveness of the scoring function in judging the game state. For Domineering, there is one important observation to make when judging the game state: you want to create as many safe spots as possible where safe spots are positions on the board that only you can place dominos on. In the example below, the green spot is safe for the horizontal player since only they can place a domino there.

This observation was made by several competitors including Herr Steffen Deusch who achieved a high rank by scoring safe spots accordingly even without pruning. Herr Johannes Stöhr takes this further by pruning moves from the search space that would take up safe spots which allows him to explore larger parts of the search space. He also carefully tuned his scoring function by simulating over 250000 games with different parameters for the scoring function. Another optimisation is due to Herr Felix Rinderer who shuffles the valid moves before scoring them. This makes it likely to encounter a good move early on which can be used to prune subsequent moves.

With Herr Rinderer we are already in the top 3 of this week's leaderboard. Interestingly, this Triumvirate of Herr Felix Rinderer, Herr Simon Stieger, and Herr Simon Martin Bohnen got there with a diverse set of approaches. Herr Rinderer uses alpha-beta pruning with a relatively naive scoring function that does not account for safe spots while Herr Stieger came up with an intricate scoring function that doesn't use pruning. The scoring function of Herr Stieger not only accounts for safe moves but also prefers moves that are adjacent to the enemies moves to disrupt their strategy. Lastly, Herr Bohnen took a very human approach to the game: he enumerated a number of scored patterns that may occur on the board together with a prescribed move. One of these patterns is amusingly called Leibbrand which shows that the Wettbewerb really is competitive. Some examples of these patterns are shown below. Here, solid green positions are filled by some domino, light green are either filled or not, and blue positions indicate the move Herr Bohnen wants to make for the pattern.

Now, if you turn your eyes towards the top of the ranking, you will see a name that may be unfamiliar to many of you. The tutor Herr Fabio Madge Pimentel submitted the best solution by far. As the MC Jr Jr was unable to penetrate the depths of his code, he decided to let the man speak himself:

At the core of my strategy lies a good scoring function for a given game state that is implemented reasonably efficiently. It counts the remaining moves for both players and takes the difference of both as the score. It doesn’t count overlapping moves twice but it does count safe moves twice. These safe moves, which can not be blocked by the opposing player, that are thus created and saved for the later stages of the game because the move resulting in the locally optimal score is usually played. Scoring all possible moves results in a few equivalence classes with regard to the score. The top class is ordered by the distance to the opposing player. This heuristic can be overwritten by a small game tree. It has four levels and has a branching factor of four.

With this the last submission out of the way, we consider a sampling of the games before we come to this week's summary and the final scoreboard.

What did we learn this week?

• Round-robin is an inefficient tournament format.
• Many students write beautiful code by now. Still, comments helped the MC Jr Jr immensely to understand the more complex submissions.
• The inability to retain a state between invocations of the strategy made it difficult to implement a Monte-Carlo approach as Herr Fink had to painfully experience.
• If you want to write an AI for a game, you should actually play it yourself to discover what makes a good move (as Herr Bohnen and others showed).
• Some students went through a lot of iterations for their AI. The MC Jr Jr appreciates the competitive spirit that the Wettbewerb brings out.
• One of the most important ingredients for a successful game AI is a scoring function that can judge the state of the game accurately.
• Formatting a table of videos in HTML is painful.

Die Ergebnisse der zwölften Woche

This week we received a whopping 116 submissions with WETT-tags. Clearly the students are beginning to feel the pressure of the exam period and are responding by procrastinating. As a demonstration of his Volksnähe the MC Jr Sr decided to procrastinate on the writing of this blog post.

We will dispense with the customary shaming showing of the longest correct solution, because it is a truly unreadable 370 token mess. Let us instead head directly for the Top 30, where Mihail Stohan manages to just squeak in with this 113 token solution:

encrypt :: String -> String
encrypt s = map (\p -> s!!(p-1)) (ps ++ foldr delete [1..n] ps) where
  n = length s
  ps = primes n

decrypt :: String -> String
decrypt cs = reverse $ decryptAux n n (length $ primes n) where
  n = length cs
  decryptAux 0 _ _ = "" 
  decryptAux l taken acc
    | isPrime l = cs!!(acc-1):decryptAux (l-1) taken (acc-1)
    | otherwise = cs!!(taken-1):decryptAux (l-1) (taken-1) acc

Herr Stohan's encrypt function constructs a list of indexes that starts with the primes up to the length of the plaintext, and ends with the nonprimes up to the same limit. He then maps these indices over the message to get the ciphertext. This is an approach taken by most solutions in the Top 30, although we will of course see it executed with greater parsimony. In order to decrypt, he keeps around indexes into the prime and nonprime portions of the ciphertext (acc and taken) and decrements them while iterating.

A few steps up the ranking, we find Wenjie Hou's 96 token solution which features a more elegant 36 token version of encrypt:

encrypt :: String -> String
encrypt str = let ps = primes $ length str
                  (l, r) = partition (isPrime . fst) $ zip [1..] str in
                      map snd $ l ++ r

The partition function will be a mainstay of the submissions further up the ranking; it takes a predicate and a list, splitting the list into those elements that satisfy the predicate and those that do not. Here it is of course used to partition the natural numbers into primes and nonprimes.

An even shorter version using the same approach comes courtesy of Tal Zwick:

encrypt :: String -> String
encrypt = map snd . uncurry (++) . partition (isPrime . fst) . zip [1..] 

Like the previous version, he zips the plaintext with an index and then partitions according to whether the index is prime. He then just needs to append the two resulting lists together, which he cleverly does by uncurrying the ++ function. All that remains is to extract the ciphertext by throwing away the indices. Pointfree, concise, and readable. By employing a couple of tricks, Almo Sutedjo manages to shave another 3 tokens off of encrypt:

encrypt :: String -> String
encrypt = map snd <<< biconcat <<< partition (isPrime .fst)  <<< zip (enumFrom 1)

We have already seen enumFrom 1 as a token-efficient version of [1..]. The biconcat function from Data.Bifoldable is a generalisation of concatenation to structures containing two lists, such as the tuple of lists we have here. The arrow operator <<< is mainly here to look cool.

This brings us to the shortest self contained version of encrypt, penned by Johannes Neubrand:

encrypt :: String -> String
encrypt x =
      isPrime `map` enumFrom 1 `zip` x
    & partition fst
    & biconcat
  <&> snd

<<< infixr 1
>>> infixr 1
=<< infixr 1
>>= infixl 1
 $  infixr 0
 &  infixl 1
 .  infixr 9
<*> infixl 4
<$> infixl 4
<&> infixl 1
 &  infixl 1

(>>=) :: (a -> b) -> (b -> a -> c) -> (a -> c)
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c)

encrypt :: String -> String
encrypt = map snd . sortOn (not . isPrime . fst) . zip (enumFrom 1)

Instead of using partition he sorts the indices with the primality test. Since Haskell's sort is stable, the order within the prime/nonprime elements stays the same, thus producing the desired result.

Let us now turn our attention to decryption. Most competitors simply reversed the operation of their encryption function. Here, for instance, Herr Glöß:

decrypt :: String -> String
decrypt = map snd . sort <<< zip =<< sortOn (not . isPrime) . enumFromTo 1 . length

He computes the same list of indices as in his encryption, but this time uses it to sort the ciphertext, thus producing the plaintext. Like some other students, Herr Glöß noticed that if he were allowed to generalise the type signatures of the functions to Ord a => [a] -> [a] he could save a few tokens by reusing encrypt to compute the appropriate list of indices:

decrypt :: Ord a => [a] -> [a]
decrypt = map snd . sort <<< zip =<< encrypt . enumFromTo 1 . length

decrypt :: String -> String
decrypt s = until ((s ==) . encrypt) encrypt s

  A brief analysis of this beautiful encryption scheme with short messages led
  me to the assumption that applying the encryption algorithm to a message
  several times will always result in the original message in plain text again
  at some point, and that decrypting using this theorem is usually more
  efficient (and even better in terms of token counting) than checking all
  permutations (as proven by the submission system).

  How many iterations (worst-case)?

  Let I(n) denote the worst-case number of encrypt iterations until we get the
  plain text again, as a function of the message length n.
  Trivial cases: I(0) = 0, I(1) = 0.
  For all other numbers, quite obviously, I(n) = I(p), whereas p denotes the
  largest prime number <= n, as characters at a one-based index > p will by
  design never change their position, no matter how often we apply the
  encryption algorithm.
  Furthermore, for finding I(n), no characters can appear more than once in the
  message substring given by the characters at the indexes from 1 to p (both
  included), otherwise we may not get the worst-case number of iterations.

  Unfortunately, I did not have the time to investigate further, but I did
  compute I(n) for most of the first 200 prime numbers (timeout at 5×10^10
  iterations), which leads to the series of the so-called Kappelmann numbers
  (not to be confused with the much less important Catalan numbers):

  2, 3, 5, 12, 18, 13, 24, 88, 102, 40, 31, 300, 390, 43, 120, 592, 858, 450,
  3360, 330, 132, 2310, 1508, 1600, 630, 525, 861, 2850, 434682, 210, 117180,
  3948, 4650, 645, 414, 211068, 462, 37620, 17980, 2080, 4588, 127920, 104280,
  389340, 81696, 36195, 172050, 11026, 3376, 23256, 1269975, 32604, 17460, 251,
  3023280, 1027110, 24108, 46620, 9976, 41400, 210420, 107880, 2536872, 1228,
  3080, 112752, 1680, 33264, 3781050, 7644, 6632208, 275094, 2092440, 3960,
  27387360, 55944, 69048, 43419, 7602945, 705870, 3702888, 86955, 47878740,
  14630, 953724, 49902077576, 29064420, 6845652, 206040, 34650, 2590740, 56980,
  380688, 556920, 18520, 122032680, 9780, 869616, 2028, 15810, 372960, 231595,
  11994840, 1544382, 20254, 351204, 570353952, 657600, 2970, 388360, 514280,
  111264, 72629340, 73966620, 144604460, 11700, 2940, 335240, 264605352,
  13355370, 8674488900, 1844400, 506610, 2979900, 18956784, 24043740, 5922,
  19546580, 325520, 1497420, 6424236, 115960, 925572840, 8498599200, 41328,
  24990, 1543984650, 20524356, 130032, 83480880, 2635812900, 633228960,
  47723508, 34078548, 5414976, ???, 2596909392, 104932, 29751528, 71730108,
  27775440, 39009426414, 134371578,  ???, 294414120, 2386800, 6521788, 2797080,
  316008000, 152040, 98532, 3281653284, 1298009160, 85645560, 41694372720, ???,
  ???, 29010, 35799960, 267267, 7035, 115389474, 16484841750, 381420,
  11748241680, 3422193840, 12373218, 178080474, 1600556958, 4289010, ???,
  20165600, 109956132, 110258232, 214030440, 9810, 854856, 2370632550, 48231690,
  2485560, 31086146520, 66588930, 17340, 22354728, 2231439210, ???, 176280174,
  731816085, 688602, 54435480, ...

  This makes me hope that my initial assumption holds.
  OEIS request to be submitted.

  (The computations were performed in Java with arrays of unique ints instead of
  strings.)

  Summary:

  Let κ(n) denote the n-th Kappelmann number, Π(n) the index of the prime number
  n in the sequence of prime numbers, λ(n) the largest prime number <= n:

    I(0) = 0
    I(1) = 0
    I(n) = (κ ∘ Π ∘ λ) (n)

  The values of I(n), for reasonably small ns, are small enough to pass the
  decryption tests on the submission system without timeouts (which could, of
  course, partly also be due to the fact that individual characters may also
  occur more than just once).

  Cheers!

            "The time you enjoy wasting is not wasted time."
                                                              — Bertrand Russell

My only quibble with this impressive note is that Russell, although a prodigious waster of time — (360 pages to prove 1 + 1 = 2, Bertrand?) — almost certainly never said this. The MC Sr provides a more rigorous argument as to why this process terminates:

   This uses the fact that "encrypt" is a permutation of the set {1..n}, and the permutations of
   the set {1..n} form a group w.r.t. function composition (The symmetric group S_n).
   
   "encrypt" is therefore an element of S_n and "decrypt" is its inverse element. Since S_n has finite order
   (n! in fact), there exists a k with 0 < k ≤ n! such that (encrypt^k) = id, i.e. in particular
   "encrypt (encrypt^(k-1) s) = id s = s". We just find such a k and return "encrypt^(k-1) s".

To finish, let us have a look at Simon Stieger's (yet again) winning submission in its full 31 token glory:

encrypt :: String -> String
encrypt = liftM2 map genericIndex is

decrypt :: String -> String
decrypt = ap zip is >>> sortOn snd >>> map fst

is :: String -> [Int]
is = length >>> enumFromTo 1 >>> partition isPrime >>> biconcat >>> map pred

Herr Stieger factors out the computation of the index list and uses genericIndex, which is just a version of (!!) that accepts arbitrary integral values as indices, saving two tokens. liftM2 and ap are monadic lifting operators.

What did we learn this week?

• It pays to be familiar with Haskell's zoo of operators, although humble dots and dollars will already get you quite far.
• A solid grounding in abstract algebra can help you prove your conjectures, but simply trying whether something works is sufficient for the Wettbewerb.
• The MCs will miss the Wettbewerb but will certainly relish not having to write blog entries in the near future, see you tomorrow for the grand conclusion.

Addendum: We mistakenly omitted submissions by Marco Haucke, Le Quan Nguyen, and Anton Baumann when making the initial ranking. They are awarded points without changing the rest of the Top 30.