## Functional Programming Competition 2019

#### part of the Formal Methods and Functional Programming (FMFP) course at ETH Zürich

Every week a special Haskell programming exercise is published here and in Code Expert. Each exercise is carefully selected by the *Master of Competition* (*MC*)—Martin Raszyk—to separate the wheat from the chaff. After 7 weeks, the intersection of the wheat with the FMFP students will receive delicious prizes in a in-lecture ceremony.

Participants submit their solutions via Code Expert. Submissions by mail are accepted only in two exceptional cases: (1) the participant is not enrolled at ETH and therefore cannot use Code Expert, and (2) the solution uses a Haskell library/pragma that is not available on Code Expert. In case (2) precise instructions of how to run the submission (including version numbers) are a necessary requirement for the solution to be evaluated.

Every week, MC's favorite submissions are discussed in a blog post. The submissions are evaluated with respect to different criteria (but the function's correctness is always a must have), which are announced along with the exercise. The best 10 solutions receive from 1 to 10 points (more is better). The points and the names of the participants are made public in a *Top 10 of the Week* and aggregated in a *semester ranking*.

**Note**: Only *correct* solutions are considered in the ranking. Please write to the MC if you suspect an error in the ranking.

**Important**: If you don't want your name to appear on a publicly visible
webpage (but still want to participate),
write to the MC and suggest a pseudonym.

Finally, the MC employs a zero tolerance policy against plagiarism. Please compete fairly and individually. Submissions that have been developed jointly by two contestants have to be clearly marked as such. Violations of those rules may result in arbitrary point deductions.

Outline:

- Final Semester ranking
- Week 1 (Task statement, Results, Discussion, Follow-up)
- Week 2 (Task statement, Results, Discussion, Follow-up)
- Week 3 (Task statement, Results, Discussion)
- Week 4 (Task statement, Results, Discussion, Follow-up)
- Week 5 (Task statement, Results, Discussion)
- Week 6 (Task statement, Results, Discussion)
- Week 7 (Task statement, Results, Art gallery)

Top 10 of the Semester | |||||||||
---|---|---|---|---|---|---|---|---|---|

# | name | W1 | W2 | W3 | W4 | W5 | W6 | W7 | Total |

1. | Sebastian Haslebacher | 10 | 6 | 8 | 10 | 8 | 5 | 5 | 52 |

2. | Nicolas Emmenegger 🐝 | 0 | 8 | 7 | 9 | 6 | 9 | 9 | 48 |

3. | Julian Schilliger ♾ 🦊 🤝 | 10 | 10 | 0 | 4 | 9 | 5 | 8 | 46 |

4. | Jan Schär 🏆 🦊 | 10 | 3 | 5 | 6 | 10 | 8 | 0 | 42 |

5. | Lorenz Holzhauer 🦊 ♟ | 7 | 0 | 3 | 5 | 9 | 10 | 6 | 40 |

6. | EnYu Jenp 🏆 🦊 | 0 | 0 | 8 | 7 | 7 | 6 | 10 | 38 |

7. | Enrico Bianchi 🏆 | 10 | 1 | 6 | 8 | 5 | 0 | 0 | 30 |

8. | Niklas Neugebauer | 10 | 7 | 0 | 0 | 5 | 7 | 0 | 29 |

9. | Flavio Schneider 🏆 | 10 | 1 | 6 | 0 | 5 | 0 | 0 | 22 |

10. | Moritz Schneider | 8 | 0 | 0 | 8 | 4 | 0 | 0 | 20 |

10. | Christian Ulmann | 0 | 0 | 9 | 0 | 0 | 4 | 7 | 20 |

### Task of Week 1

Write a function `grade`

that takes three `Int`

arguments as input — point percentages for the two quizzes and the final exam — and computes the overall percentage^{1} (rounded down, i.e., a percentage of 99.99% is expressed as 99).

`max4`

which computes the maximum of four `Int`

arguments, a possible implementation of the function `grade`

looks as follows:
grade q1 q2 e = max4 p1 p2 p3 p4 where p1 = (80 * e + 10 * q1 + 10 * q2) `div` 100 p2 = (90 * e + 10 * q1) `div` 100 p3 = (90 * e + 10 * q2) `div` 100 p4 = (100 * e) `div` 100 max4 p1 p2 p3 p4 = max p1 $ max p2 $ max p3 p4

For example:

grade 0 0 80 = 80 grade 100 0 80 = 82 grade 0 100 80 = 82 grade 100 100 80 = 84

The shortest (in terms of number of tokens^{2}) solution wins! Library imports and type signatures are excluded from the token count. As a measure of reference: the above solution consists of 78 tokens.

^{1. Refer to lecture slides for mode details.}

^{2. This competition continues a long-standing tradition of in-lecture functional programming competitions established at TU München and continued at ETH Zürich. The definition of tokens is borrowed form there. Our official token-counting program is available here.}

### Results of Week 1

Here are the best 10 47 performers in the first competition task.Top 10 of Week 1 | |||
---|---|---|---|

# | name | #tokens | |

0. | MC emeritus | 19 | |

1. | Claudio Abart | 20 | |

1. | Michael Aerni | 20 | |

1. | Enrico Bianchi | 20 | |

1. | Fabian Bosshard | 20 | |

1. | Mauro Bringolf | 20 | |

1. | Damian Cordes | 20 | |

1. | Daniel Frey | 20 | |

1. | Sebastian Haslebacher | 20 | |

1. | Pascal Huber | 20 | |

1. | Loris Reiff | 20 | |

1. | Rasmus Lüscher | 20 | |

1. | Niklas Neugebauer | 20 | |

1. | Luca Näf | 20 | |

1. | Dominic Oertle | 20 | |

1. | Janis Peyer | 20 | |

1. | Simone Riedi | 20 | |

1. | Lukas Ruflair | 20 | |

1. | Carlo Saladin | 20 | |

1. | Julian Schilliger | 20 | |

1. | Flavio Schneider | 20 | |

1. | Luca Schweri | 20 | |

1. | Jan Schär | 20 | |

1. | Remo Senekowitsch | 20 | |

1. | Daniel Sparber | 20 | |

1. | Andras Strausz | 20 | |

1. | Zilin Wang | 20 | |

2. | Alice | 24 | |

2. | Fiona Muntwyler | 24 | |

2. | Dominic Steiner | 24 | |

2. | Pascal Troxler | 24 | |

3. | Manuel Nowack | 26 | |

3. | Moritz Schneider | 26 | |

4. | Lorenz Holzhauer | 27 | |

4. | Remo Kellenberger | 27 | |

4. | Roberto Starc | 27 | |

5. | Aurel Feer | 28 | |

5. | Peter Jolles | 28 | |

5. | Renato Kunz | 28 | |

5. | Nicolas Marxer | 28 | |

6. | Martin Fiebig | 29 | |

7. | Jonas Hansen | 30 | |

8. | Diluxion Marku | 31 | |

9. | Roman Böhringer | 32 | |

10. | Thore Göbel | 33 | |

10. | Michael Sommer | 33 | |

10. | Viturin Züst | 33 |

### Task of Week 1 – Follow-Up

Define the function `grade`

or `grade'`

(from Discussion of Week 1)
with strictly less than 19 tokens.
The first submission (per e-mail to the MC) to improve the current leading `t`

token solution
to a `t'`

token solution would get `(t - t' + 1)^2`

extra points for the semester ranking.

Current **leading** solutions:

grade = queer `id` replicate 10 .: flip div 10 .:. sum .:. drop 2 .:. on compose1 insert

consisting of 19 tokens,

grade' = flip div 10 .:. sum .:. drop 2 .:. robinstar `id` on compose1 insert `compose1` replicate 10

consisting of 19 tokens.

### Task of Week 2

The MC has recently got a list of 1024 integers he would like to sum. Since lists have still not appeared in the lecture, the MC is going to provide his integers as separate arguments to a function`sum10`

.
Your task is to write this function `sum10`

that takes 1024 `Int`

arguments as input
and computes their sum.

The MC has implemented a trivial solution with 112 tokens,
but this is *too much* for the desparate MC!
Can you help out?

**Remark.** If compiling times out on Code Expert,
you can test your solution locally using this template.
Be patient, compiling may take some time!

### Results of Week 2

Here are the best 10 23 performers in the second competition task. All participants who have submitted a (non-trivial) correct solution that does not rely on any extra compiling options have been awarded a trophy for their*particularly nice*solutions.

Full Ranking of Week 2 | |||
---|---|---|---|

# | name | #tokens | |

0. | MC emeritus | 23 | |

1. | Julian Schilliger | 34 | |

2. | Shengyu Huang | 37 | |

3. | Nicolas Emmenegger | 39 | |

4. | Niklas Neugebauer | 40 | |

4. | Janis Peyer | 40 | |

5. | Sebastian Haslebacher | 41 | |

5. | Michael Sommer | 41 | |

6. | Andrin Bertschi | 46 | |

6. | Nicolas Wicki | 46 | |

7. | Loris Reiff | 49 | |

8. | Carlo Saladin 🏆 | 57 | |

8. | Jan Schär 🏆 | 57 | |

9. | Gabriel Giamarchi 🏆 | 60 | |

10. | Enrico Bianchi 🏆 | 61 | |

10. | Simone Riedi 🏆 | 61 | |

10. | Flavio Schneider 🏆 | 61 | |

11. | Daniel Sparber | 75 | |

12. | Moritz Schneider | 81 | |

13. | Nicolas Hoferer 🏆 | 114 | |

14. | EnYu Jenp 🏆 | 152 | |

15. | Rasmus Lüscher | 3073 | |

15. | Mathias Vetsch | 3073 |

### Task of Week 2 – Follow-Up

Define the function `sum`

without relying on any extra compiling options
(module imports are still allowed and do not contribute to the token count).
The first submission (per e-mail to the MC)
to improve the current leading `t`

token solution
to a `t'`

token solution would get `(t - t')`

extra points for the semester ranking.

Current **leading** solution:

module Sum where import Data.Aviary.Birds import Data.Composition --sum10 :: Int -> Int -> Int -> [...] (omitted here for clarity) sum10 = comb9 $ comb9 id 0 comb1 f = f .:. jay (+) comb3 = comb1 . becard comb1 comb1 comb1 comb5 = comb3 . becard comb3 comb3 comb3 comb7 = comb5 . becard comb5 comb5 comb5 comb9 = comb7 . becard comb7 comb7 comb7

consisting of 48 tokens.

### Task of Week 3

Announcement: the MC has decided to extend the deadline for Week 3 until Saturday, March 16th, 24:00. The MC wishes you much success at the QUIZ!

The MC has recently found a module `STR`

, but has no clue about its purpose.
He is particularly curious about the function `cnt`

.
But its running time grows so rapidly that the MC is not able to evaluate it on lists of length more than `5`

.

Could you help the MC by providing an efficient implementation of the module `STR`

such that the function `cnt`

from your implementation is equal to its counterpart
in the original module?

Your solution will be ranked based on the length of lists it can evaluate within a fixed timeout. In more detail, your solution will be run on a group of lists of the same length and will pass the group if the total running time to evaluate all lists from the group does not exceed the timeout. Solutions that do not implement the exact behaviour of the original module will NOT be considered.

As a measure of reference, the MC would like to be able to evaluate the funcion
`cnt`

on a list of length `250`

within a few seconds.

*Note.* You may assume that all values in the *input* list fit into the range
of `Int`

. Nevertheless, the type of the function `cnt`

must still be
`cnt :: [(Integer, Integer)] -> Integer`

.

module STR where import Data.List elem' = \x xs -> elem x xs || elem (swap x) xs swap (x, y) = (y, x) combine [] ys = [] combine (x:xs) ys = (map ((,) x) ys) ++ (combine xs ys) remeq = filter (\(v1, v2) -> v1 /= v2) prep _ [] = [] prep f (x:xs) = aux x $ prep f xs where aux x xs | f x xs = xs | otherwise = x:xs check vs es = (length es == length vs - 1) && (not $ elem False (map (\p -> elem (Just p) paths) pairs)) where pairs = remeq $ combine vs vs paths = map compress $ filter checkPath $ concatMap permutations $ subsequences $ concatMap maybeRev es maybeRev p = [p, swap p] checkPath es = snd $ foldr checkConsecutive (Nothing, True) es checkConsecutive (v1, v2) (Nothing, b) = (Just v1, b) checkConsecutive (v1, v2) (Just v, b) = (Just v1, b && (v2 == v)) compress [] = Nothing compress ((v1, v2):vs) = let res = compress vs in case res of Nothing -> Just (v1, v2) Just (v1', v2') -> Just (v1, v2') post [] = 0 post (x:xs) = 1 + post xs cnt :: [(Integer, Integer)] -> Integer cnt es = (post . filter (check vs) . subsequences . remeq . prep elem') es where vs = prep elem $ concatMap (\(x, y) -> [x, y]) es

You can also find the module here.

### Results of Week 3

Here are the best 10 11 performers in the third competition task. The MC received six more solutions before the extended deadline. Three of them were wrong and could not be further considered. Julian Schilliger — the leader of the ranking after Week 2 — had been on the second place in the preliminary ranking, but has introduced an infinite loop in his final solution and could not be included in the final ranking. He deserves the infinity emoji ♾ in the semester ranking. On the positive side, Nicolas Emmenegger has improved his solution during the deadline extension. He deserves the hard worker emoji 🐝 in the semester ranking.

Preliminary Ranking of Week 3 | |||
---|---|---|---|

# | name | max length | |

1. | Ke Yi Tan | 1540 | |

2. | Julian Schilliger | 224 | |

3. | Sebastian Haslebacher | 196 | |

4. | Enrico Bianchi | 65 | |

4. | Flavio Schneider | 65 | |

4. | Nicolas Emmenegger | 65 | |

5. | Fabian Bosshard | 32 | |

6. | Lorenz Holzhauer | 22 | |

7. | Lukas Schmid | 5 |

Full Ranking of Week 3 | |||
---|---|---|---|

# | name | max length | |

1. | Ke Yi Tan | 1540 | |

2. | Christian Ulmann | 241 | |

3. | EnYu Jenp | 196 | |

3. | Sebastian Haslebacher | 196 | |

4. | Nicolas Emmenegger 🐝 | 166 | |

5. | Enrico Bianchi | 65 | |

5. | Flavio Schneider | 65 | |

6. | Jan Schär | 37 | |

7. | Fabian Bosshard | 32 | |

8. | Lorenz Holzhauer | 22 | |

9. | Lukas Schmid | 5 |

### Task of Week 4

After the reverse engineering

task from last week, let's do some
stringology this week.
It is a standard problem to check if a string is a substring of another string (i.e.,
to search a *needle* in a *haystack*).
For example, the string `"FM"`

is a substring of the string `"FMFP"`

,
but the string `"FF"`

is not a substring of the string `"FMFP"`

.
Moreover, a string is a substring of itself and the empty string is a substring of any string.

Let's generalize the problem as follows: given a string `h`

and a list of strings `ns`

,
count for each string `n`

from the list `ns`

how many times `n`

occurs in `h`

as a substring. We also count overlapping occurrences of a substring, i.e., the string `"ABA"`

occurs twice in the string `"ABABA"`

as a substring.

Your task is to write a function `countRepeats :: String -> [String] -> [Int]`

that solves the generalized problem as fast as possible.
You may assume that the symbol `'$'`

(dollar sign) appears in neither the haystack nor any needle.

For example:

countRepeats "FMFP" ["FM", "FF"] = [1,0] countRepeats "ABABA" ["ABA", "A", "C", ""] = [2,3,0,6]

The function `countRepeats`

can be implemented as follows:

module Stringology where import Data.List countRepeats :: String -> [String] -> [Int] countRepeats h ns = map (\n -> length $ filter (isPrefixOf n) $ tails h) ns

but the time complexity of this implementation is not particularly impressive. Nevertheless, you can download the sample implementation here.

Your solution will be evaluated on inputs satisfying `(sum $ map length ns) ≤ (length h)`

, i.e.,
the sum of lengths of all needles in `ns`

does not exceed the length of the haystack `h`

.
Let `|h| = length h`

denote the length of the haystack.
Your solution will be ranked based on the maximum `|h|`

of inputs it can evaluate within a fixed timeout.
In more detail, your solution will be run on a group of inputs with the same `|h|`

and will pass the group if the total running time to evaluate all inputs from the group does not exceed the timeout.
Solutions that do not implement the exact behaviour of the sample implementation will NOT be considered.

As a measure of reference, the MC has a three-line solution that can evaluate any input satisfying `|h| = 100 000`

within a few seconds.

### Results of Week 4

Here are the best 10 10 (indeed!) performers in the fourth competition task.
The four participants sharing the bronze medal just handed in the provided sample solution!
On the other hand, the last four participants tried to optimize

it by using the KMP algorithm
or some smart refactoring. They deserve the Schlaufuchs

emoji 🦊 in the semester ranking.
Cordial CONGRATULATIONS go to the leader of the ranking — Sebastian Haslebacher —
who realized that the Aho-Corasick algorithm fits better than the KMP algorithm for this week's task.

Full Ranking of Week 4 | |||
---|---|---|---|

# | name | max length | |

1. | Sebastian Haslebacher | 313000 | |

2. | Nicolas Emmenegger | 49000 | |

3. | Enrico Bianchi | 42000 | |

3. | Gabriel Fringeli | 42000 | |

3. | Rasmus Lüscher | 42000 | |

3. | Moritz Schneider | 42000 | |

4. | EnYu Jenp 🦊 | 29000 | |

5. | Jan Schär 🦊 | 17000 | |

6. | Lorenz Holzhauer 🦊 | 15000 | |

7. | Julian Schilliger 🦊 | 9000 |

### Task of Week 4 – Follow-Up

**WARNING!** Solutions found on the web will not be awarded any points for the semester ranking,
but the MC would like to hear about them and will award the fairplay emoji 🤝 for them.

Write the function `countRepeats :: String -> [String] -> [Int]`

implementing the Aho-Corasick algorithm and taking `|h|`

steps,
where `|h|`

is the length of the haystack.
The assumptions from Week 4 apply here.
Instructions on how to extend the Aho-Corasick algorithm to achieve this time complexity
can be found in the Discussion of Week 4.

The first correct solution received by the MC by mail will be awarded 4 extra points for the semester ranking.

Current status: UNSOLVED.

Write a function `construct :: String -> MCSTree Char`

building a suffix tree in *linear time*.
The goal is to have an efficient construction of the suffix tree
which can be plugged in MC's solution from
the Discussion of Week 4.
A possible implementation that runs in super-linear time
is commented out below.

module Stringology where type MCEdge a = ([a], MCSTree a) data MCSTree a = MCNode [MCEdge a] Int | MCLeaf countMCSTree :: MCSTree Char -> Int countMCSTree MCLeaf = 1 countMCSTree (MCNode _ c) = c countNeedle :: String -> MCSTree Char -> Int countNeedle [] t = countMCSTree t countNeedle n (MCNode es _) = go es where go [] = 0 go (e:es') = aux es' (snd e) (suffix n $ fst e) aux es' _ Nothing = go es' aux _ t (Just n') = countNeedle n' t suffix (x:xs) (p:ps) | x == p = suffix xs ps | otherwise = Nothing suffix xs _ = Just xs countRepeats :: String -> [String] -> [Int] countRepeats h ns = map (\n -> countNeedle n tree) ns where l = length h tree = construct h construct :: String -> MCSTree Char construct = undefined {- SUPER-LINEAR TIME COMPLEXITY!!! construct h = foldTree $ SuffixTree.construct (h ++ "$") where foldTree SuffixTree.Leaf = MCLeaf foldTree (SuffixTree.Node es) = MCNode (zip ps es') (sum $ map countMCSTree es') where es' = map (foldTree . snd) es ps = map (SuffixTree.prefix . fst) es -}

The template can also be downloaded here.

The first correct solution received by the MC by mail will be awarded 4 extra points for the semester ranking.

Current status: UNSOLVED.

### Task of Week 5

You might have played the game Regex Golf whose objective
is to produce a short regular expression (*regex*) matching all strings from a given list
and, at the same time, matching no string from another given list.
This week, we make your life easier (or harder?) by relaxing the rules of the game as follows:
you are given a single list of strings and you need to come up with a short regex matching
at least one string and also **not** matching at least one string from the list.
A straightforward solution is to compute a regex matching exactly the first word from the list
and nothing else. But there might be better solutions in terms of size of the final regex.

Your task is to write a function `minregex :: [String] -> RE`

that takes a list
of strings as input and computes a short regex matching
at least one string and also not matching at least one string from the list.
The data type for a regex looks as follows:

data RE = Zero -- Zero matches nothing | One -- One matches only the word [] | Dot -- Dot matches any single letter word, -- e.g., ['a'] or ['b'], but neither [] nor ['a', 'b'] | Atom Char -- Atom c matches only the word [c] | Plus RE RE -- Plus r s matches all words matched by r or s | Concat RE RE -- Concat r s matches all words w = u ++ v -- such that u is matched by r and v is matched by s | Star RE -- Star r matches [] and all words w = u ++ v -- such that u is matched by r and v by Star r

**WARNING!** You are not allowed to change this data type!
You may download the module for regular expressions with a sample implementation here.

Announcement: The sample module has changed slightly — now the part of the module you may not modify excludes the first line of the module declaration so that you can import other modules if you wish.

Announcement: The way in which your solution will be evaluated has slightly changed — please make sure to check out the next paragraph again.

In addition to the function `minregex`

, you have to create a list of test cases
`tests :: [[String]]`

that will be used to evaluate *your* solution as follows.
Suppose there are `N`

submissions to this week's assignment.
Each of these `N`

submissions will be run on *your* tests and your final score
will be equal to twice the *median* sum of sizes of your competitor's regular expressions for your tests
minus twice the sum of sizes of your regular expressions for your tests (note that if `N`

is even,
then the median is the mean of the two middle values).
Note that your final score might also be negative.
Clearly, a higher score is better.
Also note that your final score depends on the quality of *both* your function `minregex`

and your test cases `tests`

.

If the function `minregex`

fails with an exception or does not complete within
a fixed timeout (corresponding roughly to evaluating `head $ drop 500000000 [1..]`

),
the default implementation will be used on that particular test case.
Each string must consist only of lower-case letters from the English alphabet.
Test cases with less than two different strings will be ignored.
Moreover, the total length of all strings must not exceed 1000, i.e.,
`length (concatMap concat tests) ≤ 1000`

must hold.

### Results of Week 5

Here are the best 10 13 performers in the fifth competition task.
Finally, we could observe an **increase** in the number of submissions (jay!).
To prevent potential unfair collaboration, the MC changed the evaluation
(see an announcement above). Recall that before the change, the final score was supposed to equal
the sum of sizes of your competitor's regular expressions for your tests
minus `(N - 1)`

-times the sum of sizes of your regular expressions for your tests (where `N`

is the total number of submissions).
However, the MC could not resist the temptation to evaluate the round in both ways.
Clearly, only the official one will be considered for the semester ranking.

Unofficial Ranking of Week 5 | |||
---|---|---|---|

# | name | score | |

1. | Jan Schär | 10893 | |

2. | Julian Schilliger | 9910 | |

3. | Lorenz Holzhauer | 8597 | |

4. | Sebastian Haslebacher | 6549 | |

5. | Enrico Bianchi | 5994 | |

6. | Nicolas Emmenegger | 2653 | |

7. | EnYu Jenp | 2493 | |

8. | Soel Micheletti | 4 | |

8. | Niklas Neugebauer | 4 | |

8. | Simone Riedi | 4 | |

8. | Flavio Schneider | 4 | |

9. | Moritz Schneider | -65 | |

10. | Fabian Bosshard | -1968 |

Official Ranking of Week 5 | |||
---|---|---|---|

# | name | score | |

1. | Jan Schär | 1978 | |

2. | Lorenz Holzhauer | 1972 | |

2. | Julian Schilliger | 1972 | |

3. | Sebastian Haslebacher | 1508 | |

4. | EnYu Jenp | 994 | |

5. | Nicolas Emmenegger | 618 | |

6. | Enrico Bianchi | 0 | |

6. | Fabian Bosshard | 0 | |

6. | Soel Micheletti | 0 | |

6. | Niklas Neugebauer | 0 | |

6. | Simone Riedi | 0 | |

6. | Flavio Schneider | 0 | |

7. | Moritz Schneider | -15 |

### Task of Week 6

Announcement: The deadline for this challenge has been extended to
**Tuesday, 2nd April, 23:59 CEST.**

Announcement: Timing the players and ASCII art output has changed in the module Quoridor to be more reliable. Please check out the updated module (uploaded on 31st March, 11.22 CEST).

Announcement: The winner of this round will receive a **special prize!**

This task is rather different from the ones before: implement a strategy for playing Quoridor. There is no Code Expert project this time. Instead, please submit your solutions by mail to the MC.

*Note that there are only two pieces on the board in our game.*

Quoridor is a strategy game played on a 9 × 9 board with two *pieces* and twenty *fences*
distributed equally between the two players.
Initially, the two pieces are centered at opposite sides of the board
and the goal of the game is to reach the opponent's side of the board.
In each move, a player may move its piece to an adjacent field or place one of its remaining fences
on the board (either horizontally or vertically). A fence always separates two pairs of fields.
Once placed, a fence may not be moved or removed. It also prevents any piece from jumping over it.
Nevertheless, the fences must be placed in a way that guarantees both players a path from their
field to the respective side of the board they need to reach (maybe via a detour).
Please check out the Wikipedia article
for the full rules of the game.
The MC also encourages you to try out the game before implementing your strategy.
To win, you must be the first player to move your piece on the opposite side of the board using only legal moves
and at most 5 minutes spent evaluating your step function (deciding on your moves).

The MC has prepared a module Quoridor defining data types for the state of the game, a player's move, and a player's strategy. It also contains functions for checking if a move is legal and a function simulating supplied two players' strategies. The MC further provides a sample module PlayerRANDOM implementing a simple strategy for the two players. Finally, the MC provides a tournament module Main illustrating how this week's task will be evaluated. You might need to install a few Hackage packages to load the modules. The instructions are in the sources.

The state (`State`

) of the game consists of the two player's positions (`Pos = (Int,Int)`

),
the numbers of the two player's remaining fences, and arrays storing the positions of the fences on the board.
The fields on the board are indexed by positions between `(1,1)`

and `(9,9)`

,
where `(1,1)`

is the bottom left corner of the board.
For the sake of implementation, the winning fields of the first player (above the board's topmost row)
are indexed by position between `(1,10)`

and `(9,10)`

.
The first player may reach those fields by jumping over the opponent's piece at the topmost row.
Analogously, the winning fields of the second player (below the board's bottommost row) are indexed
by position between `(1,0)`

and `(9,0)`

.
The array `hFence`

stores for each field with position `(x,y)`

between `(1,0)`

and `(9,9)`

whether there is a horizontal fence directly above it, i.e., separating the field `(x,y)`

from the neighbouring field `(x,y+1)`

.
Analogously, the array `vFence`

stores for each field with position `(x,y)`

between `(1,0)`

and `(8,10)`

whether there is a vertical fence directly to the right of it, i.e., separating the field
`(x,y)`

from the neighbouring field `(x+1,y)`

.
Finally, the array `cross`

stores for each field with position between `(1,1)`

and `(8,8)`

whether the junction at its top right corner is empty or taken by a fence.

A move (`Move`

) of a player has one of the following three forms (1) `Piece Bool Pos`

,
where the `Bool`

must be set to `True`

iff it is a move of the *first* player
and the `Pos`

denotes the field where the player wants to move its piece on;
(2) `HFence Bool Pos`

, where `Pos`

is a position `(x,y)`

between `(1,1)`

and `(8,8)`

such that the respective player (according to the `Bool`

) wants to place a *horizontal* fence
directly above the fields `(x,y)`

and `(x+1,y)`

;
(3) `VFence Bool Pos`

, where `Pos`

is a position `(x,y)`

between `(1,1)`

and `(8,8)`

such that the respective player (according to the `Bool`

) wants to place a *vertical* fence
directly to the right of the fields `(x,y)`

and `(x,y+1)`

.

A player's strategy for Quoridor is a pure function of type
`step: Double -> State -> m -> (m, Move)`

that inputs the remaining time (in seconds), a state, and some polymorphic memory slot, which you may instantiate with any type you want
and use it to store reusable information. The function should return the next move (`Move`

)
together with an update of the memory. Be careful to produce only legal moves (producing illegal ones is an additional losing condition).

A player (`Player`

) is then characterized by such a function extended with a name (please use your nethz in UPPER-CASE)
and an initial memory content.
Note that evaluating the initial memory contributes to your time limit of 5 minutes.

Please submit a single file called `PlayerNETHZ.hs`

which implements two `Player`

s: `player1`

that starts at the bottommost row (and has the first move)
and `player2`

that starts at the topmost row (and goes second).
In particular, you are not allowed to modify the content of the modules `Quoridor`

nor `Main`

,
but may implement your own optimized functions in the module `PlayerNETHZ`

that have the same functionality
as some of the functions from `Quoridor`

.

The submissions will be evaluated in a tournament.
For each pair of submissions, the `Main`

module will be instantiated with the provided strategies
(in both ways) and the winner scores one point.
In particular, if there are `N`

submissions this week, then `N * (N - 1)`

points will be
distributed in total.
The ranking will then be based on the total number of points your two player strategies have scored.

Graphical visualizations of the game that are nicer than the ASCII art of the MC are very welcome contributions, too. The MC is not sure, if they would yield any competition points, though (this depends on their beauty).

### Results of Week 6

Here are the best 10 8 performers in the game week. The winner — Lorenz Holzhauer — deserves the game emoji ♟ and a special prize awarded in the last lecture.

Full Ranking of Week 6 | |||
---|---|---|---|

# | name | total score | |

1. | Lorenz Holzhauer ♟ | 13 | |

2. | Nicolas Emmenegger | 11 | |

3. | Jan Schär | 8 | |

4. | Niklas Neugebauer | 7 | |

5. | EnYu Jenp | 6 | |

6. | Sebastian Haslebacher | 5 | |

6. | Julian Schilliger | 5 | |

7. | Christian Ulmann | 1 |

### Task of Week 7

This task is the final task of the competition. The submission deadline is on **Tuesday, 2nd April, 23:59 CEST.**
The results (of this task and the entire competition) will be announced (and followed by the award ceremony)
in the last lecture of the FP part of the course on Thursday, 4th April.
The last year's slides can be found here.

The actual task is very simple: Be original!

You are required to submit by mail to the MC a picture with any content you want (in one of the following formats: jpg, png, svg, pdf, gif) and a Haskell program (a single file: Art.hs) that was used to generate the picture. Here are some examples of graphics libraries that you are encouraged to use (others are welcome, too).

The pictures will be evaluated with respect to the aesthetics of the artwork (by an independent but highly subjective jury) and the aesthetics of the code (by the independent but highly subjective MC).

**Hint:** Such an artistic task is a traditional
ending of a competition.
You can look at previous year's submissions for some inspiration.
Various
fractals have been fairly popular among the past submissions.
If done properly (i.e., beautifully), they will guarantee you a secure place somewhere in the middle. But typically, to win this task
one has to create something more original and surprising.

### Results of Week 7

Here are the best 10 6 performers in the art gallery week. The jury comprised 7 members who ranked the submitted pieces of art relatively to each other (possibly with ties) and the MC then mapped the rankings to points as usual (10 is the best) and summed them together.

Full Ranking of Week 7 | |||
---|---|---|---|

# | name | total score | |

1. | EnYu Jenp | 64 | |

2. | Nicolas Emmenegger | 63 | |

3. | Julian Schilliger | 56 | |

4. | Christian Ulmann | 52 | |

5. | Lorenz Holzhauer | 45 | |

6. | Sebastian Haslebacher | 43 |