The Canister Company

The canister company stores various liquids for their customers. Each type of liquid, such as copy cola, ethanol and grade A machine oil must be stored in a different container.

The Canister Company wants to save floor space by minimizing the number of containers they store. To do this, they need a program to calculate how to re-organize their store room so that minimum number of containers are used.

Level 0

Assume that the Company can cheaply build containers for any amount of liquid.

Level 1

Assume that the Company only has 1000l barrels.

Level 2

Instead of returning the list of optimized containers the program should return list of instructions how to move the liquids from one container to another so that the optimum storage configuration is achieved

Level 3

The company has found that it can store the following liquids in the same container since they can be easily separated:

Modify your program accordingly.

Suitability

Monoids

The Kimble

Kimble

Kimble

Kimble is a childrens board game. In my experience, a major tragedy that can fall upon an adult is to be forced to play this game during an otherwise fun party. The suggested playing time of the game is a whopping 45 minutes and the gameplay is seems almost entirely based on luck.

Can the pain of playing a game of Kimble be made shorter by using an appropriate strategy? Create a simulator that plays thousands of games of Kimble according to the following strategies and find out which of the strategies is most likely to lead to a) shortest playing time (counted as number of dice rolls) and b) victory.

Strategies

  1. Move a random piece
  2. Move the piece nearest to the goal
  3. Move the piece farthest from the goal
  4. Same as a but capture opponent pieces if possible
  5. Same as b but capture opponent pieces if possible
  6. Same as c but capture opponent pieces if possible

Assume that in all strategies, the roll of 6 is used to bring new pieces to play.

Level 2

As is.

Level 3.

Demonstrate a better strategy that is either significantly more likely to win the game or to shorten the gameplay.

The Web forum

The Web Forum Company needs to upgrade their web discussion service. They want a system, where users can post messages to message boards. They also want users to be able to reply to the messages of other users. Furthermore, they need function to access all messages written by a specific user and a quick way to find replies to a specific message so they can display this information on the web page.

Also, the company has found that they need a quick way to remove offensive posts. Usually just one message is needs to be removed, but in some cases they want to remove all messages posted by a single user, optionally with all of their replies as well.

The Company already has a user management system and is willing to do the actual web site if you provide them with the basic datatypes and functions for manipulating a message board.

Level 0

Implement the requirements specified above. You can store the message board to the memory

Level 1

Same as Level 0, but you need to save the message board data to the filesystem

Level 3

The messaging board is operated concurrently by hundreds of users that view and post messages. Ensure that the messaging board can be used concurrently.

Level 4

The Company wants you to make the actual web service. Do not bother with logins.

Suitability

Monads, Traversible, Foldable, Functors

The digital cookbook

Create a program that can store cooking recipes. Each recipe consists of ingredients and list of steps needed to cook the recipe. Steps consists of actions such as

Each step takes a certain amount of time, either prescribed by the recipe (such as time to cook some ingredient) or time that is estimated necessary to complete the action.

Create a program to store and fetch the recipes. Additionally, the program should automatically scale recipes when user indicates the intended number of persons the food is for and it should print out the time needed to complete the recipe.

Level 0

Create a the necessary datatypes and functions for modelling the cookbook program. Aim for enough functionality that this library of types and functions can be used for storing recipes by using GHCi as the user interface

Level 3

Create an usable GUI for your program.

Suitability

Monads, Free monads, data structures

Boggle

Boggle is a boardgame designed by Alan Turoff. In Boggle the players first assemble a random 4 by 4 grid of letters and then try to find as many words as possible hidden in this grid. The words are formed by tracing paths through adjacent letters without revisiting the same letter. Adjacency can be either horizontal, vertical or diagonal.

Example of finding a word in Boggle

Example of finding a word in Boggle

In this project you need to build a computer opponent for this game. The computer opponent should find as many words as possible in the given boggle grid. To recognize words, you can use this list of 2000 most common words.

Level 2:

As is.

Suitability

Data structures

N-Queens

Create to calculate all ways to place N queen-pieces on a NxN chessboard in such way that there is no more than one piece in each column, each row and each diagonal of the board.

This is easiest to solve by noticing that we must place exactly one piece in each column.

Level 0

As is.

Level 2

Make a program that computes the possibilities in parallel using multiple processor cores. Demonstrate a concrete speedup.

Suitability

Parallelism, monoids

The JSON Parser

JSON is a common data exchange format that looks like this:

{books: [{title:"Childhoods end"
         ,author:"Arthur C. Clarke"
         ,year:1953}
        ,{title:"Excession",author:"Ian M Banks"
         ,year:1996}

        ,{title:"I, Robot"
         ,author:"Isaac Asimov"
         ,year:1950}]}

Level 1

Create a parser that can extract all book titles from the above json snippet.

Level 2

Design a Haskell datatype that represents a generic JSON object and create a parser that can parse any JSON snippet into this data type.

Level 3

Extend the above in such a way that you can easily parse JSON snippets to task specific datatypes. For example, to parse the book snippet, you might want to use the following data type:

data BookCollection = [Book]
data Book = Book {tile,author::String, year :: Int}

Suitability

Monads (almost required), Applicative functors (almost required), Functors, Monoids, Traversables, Foldables, Lenses.

The maximal generality

Choose two programs from this page that you have done. This choice can even be random. Then find all parts that are even remotely similar in the programs and extract them as a library.

Level 0

Extract common structures such as folds, filters, monoids etc.

Level 1

Expose more similarities by rewriting the programs. Extract IO from computations, find different recursion patterns, extract those from the actual computation and use general tools like monoids, foldable/traversible to rewrite the programs so that they share as much code as possible.

Level 3

Find new abstractions that you can use to share code between programs.

Suitability

Everything.

The Arithmetic Logic Unit simulator

Design the datatypes for simulating simple logic gates such as AND, OR, XOR and NAND. Then design functions that can be used to compose these gates to more complex logical units. Then create a simulator that you can use to test the various circuits. Show that your compositions work by implementing models of an Arithmetic Logic Unit (ALU) that is able to do the following unsigned 8 bit integer operations

Level 1

Model each of the above operations as a separate model.

Level 2

Create a single ALU that can do all of the operations.

Level 3

Create a graphical visualization of the ALU structures.

Level 4

Create an animated visualization of ALU behaviour.

Level 10

Add support for recurrence and model a four general purpose register CPU capable of executing programs composed with the following instructions:

Level 15

Model memory as logic gates and add stack to your CPU

Level 30

Compile lambda calculus programs to the instructions supported by your simulated computer.