Algorithms and Datastructure

SudokuSolver

Task

Implement a Sudoku solver that takes a Sudoku puzzle as input and returns a valid solution.

1
fn solve(puzzle: string) -> solution: string

Assume the input to be in the form of a string containing multiple liens of comma separated values:

1
5, 3, 0, 0, 7, 0, 0, 0, 0
2
6, 0, 0, 1, 9, 5, 0, 0, 0
3
0, 9, 8, 0, 0, 0, 0, 6, 0
4
8, 0, 0, 0, 6, 0, 0, 0, 3
5
4, 0, 0, 8, 0, 3, 0, 0, 1
6
7, 0, 0, 0, 2, 0, 0, 0, 6
7
0, 6, 0, 0, 0, 0, 2, 8, 0
8
0, 0, 0, 4, 1, 9, 0, 0, 5
9
0, 0, 0, 0, 8, 0, 0, 7, 9

The empty fields are designated by the invalid value 0.

Prepare comprehensive unit tests.Strive for a unit test coverage of 100% (where sensible.)

Minimum Requirements

• Use the classic Sudoku rules. Additional variants are optional.
• Be able to solve 9x9 Sudoku puzzles. Additional sizes are optional.
• Implement at least a backtracking algorithm. More sophisticated approaches are appreciated.
• Be able to detect invalid/unsolvable puzzles.

Useful Web-Links:

• Wikipedia | SudokuLink
• Wikipedia | Sudoku Solving AlgorithmsLink
• NUnit unit-testing frameworkLink
• NUnit InstallationLink
• Unit test your code | MSDNLink

Data Driven Unit Tests

1
[TestCase(-1)]
2
[TestCase(0)]
3
[TestCase(1)]
4
public void ReturnFalseGivenValuesLessThan2(int value)
5
{
6
    var result = _primeService.IsPrime(value);
7

8
    Assert.IsFalse(result, $"{value} should not be prime");
9
}

1
[DataTestMethod]
2
[DataRow(-1)]
3
[DataRow(0)]
4
[DataRow(1)]
5
public void ReturnFalseGivenValuesLessThan2(int value)
6
{
7
    var result = _primeService.IsPrime(value);
8

9
    Assert.IsFalse(result, $"{value} should not be prime");
10
}

Sources:

• Nunit
• MsTest

SplayTree

A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. All normal operations on a binary search tree are combined with one basic operation, called splaying.

Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this with the basic search operation is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top.

Displays the search algorithm of the splay tree.

Task

Provide at least the following functionality:

Implement a splay tree for storing integer values

• # insert a new value into the treefn insert(value: int)
• # remove a value from the tree# returns the count of removed valuesfn remove(value: int) -> int
• # remove all values from the treefn clear()
• # return the total number of stored valuesfn count() -> int
• # find the smallest value stored in the treefn minimum() -> int
• # find the largest value stored in the treefn maximum() -> int
• # return the number of occurances of a specific valuefn count(value: int) -> int
• # check for the occurance of a specific valuefn contains(value: int) -> bool
• # traverse the tree pre-order, in-order (default) or post-orderfn traverse(order: OrderEnum) -> list«int»

Prepare comprehensive unit tests.Strive for a unit test coverage of 100% (where sensible.)

Bonus Tasks

• Implement a generic tree that can store different data types with a defined order relation.
• Implement traverse in an iterative fashion.
• Visualize the tree (or even the rotations)

Useful Web-Links

• Splay Tree | WikipediaLink
• Splay Tree VisualizationLink

Befunge Interpreter

Task

Write an interpreter for the esoteric language Befunge-93. The interpreter must accept valid Befunge-93 programs, handle user input and print output.

Befunge is a stack-based, reflective, esoteric programming language. It differs from conventional languages in that programs are arranged on a two-dimensional grid. “Arrow” instructions direct the control flow to the left, right, up or down, and loops are constructed by sending the control flow in a cycle.

Bonus Tasks

• Visualize the execution of the program
• Let the user step through individual steps
• Display the contents of the current stack
• Allow interactive editing of the program

Useful Web-Links

• Befunger | Interactive InterpreterLink
• Befunge Doku
• Befunge-93 SpecificationLink
• Example programsLink

Maze Generator

Task

Generate a sigma (hexagonal) maze of arbitrary size using Wilson’s algorithm.

1
fn generate(width: int, height: int) -> Maze

Visualize the maze in a way of your choosing

Prepare comprehensive unit tests.Strive for a unit test coverage of 100% (where sensible.)

Bonus Tasks

• Visualize the generation of the maze
• Support different maze and/or room shapes

Hexagon Grid

To generate hexagon’s you need to work with axial coordinates (q, r, s).

Hexagons are 6-sided polygons. Regular hexagons have all the sides the same length. I’ll assume all the hexagons we’re working with here are regular. The typical orientations for hex grids are vertical columns (flat topped) and horizontal rows (pointy topped).

Hexagons have 6 sides and 6 corners. Each side is shared by 2 hexagons. Each corner is shared by 3 hexagons. For more about centers, sides, and corners, see my article on grid parts (squares, hexagons, and triangles).

Full article here!

Wilson’s Maze Algorithm

Wilson’s algorithm uses loop-erased random walks to generate a uniform spanning tree — an unbiased sample of all possible spanning trees. Most other maze generation algorithms, such as Prim’s, random traversal and randomized depth-first traversal, do not have this beautiful property.

The algorithm initializes the maze with an arbitrary starting cell. Then, a new cell is added to the maze, initiating a random walk (shown in magenta). The random walk continues until it reconnects with the existing maze (shown in white). However, if the random walk intersects itself, the resulting loop is erased before the random walk continues.

Initially, the algorithm can be frustratingly slow to watch, as the early random walks are unlikely to reconnect with the small existing maze. However, as the maze grows, the random walks become more likely to collide with the maze and the algorithm accelerates dramatically.

Source: https://bl.ocks.org/mbostock/11357811

The algorithm goes something like this:

1. Choose any vertex at random and add it to the UST.
2. Select any vertex that is not already in the UST and perform a random walk until you encounter a vertex that is in the UST.
3. Add the vertices and edges touched in the random walk to the UST.
4. Repeat 2 and 3 until all vertices have been added to the UST.

Monte Carlo Simulation

Task

Simulate individual games of Snakes and Ladders using a Monte Carlo Simulation.

• Allow for variably sized boards, different distributions of snakes and ladders, and various die sizes.

• Determine the average number of moves needed for a single player to reach the end.

• Record the lowest number of moves and its die rolls.

• Prepare comprehensive unit testsStrive for a unit test coverage of 100% (where sensible).

Bonus Tasks

• Run simulations in parallel
• Allow for non-uniformly distributed die-rolls.
• Plot the results of your simulations.
• Compare your results to the expected number of moves provided by the fundamental matrix of the corresponding absorbing Markov Chain.

Useful Web-Links

• Snakes and Ladders | Wikipedia

  Any version of Snakes and Ladders can be represented exactly as an absorbing Markov chain, since from any square the odds of moving to any other square are fixed and independent of any previous game history.  The Milton Bradley version of Chutes and Ladders has 100 squares, with 19 chutes and ladders. A player will need an average of 39.2 spins to move from the starting point, which is off the board, to square 100. A two-player game is expected to end in 47.76 moves with a 50.9% chance of winning for the first player. Those calculations are based on a variant where throwing a six does not lead to an additional roll; and where the player must roll the exact number to reach square 100 and if they overshoot it their counter does not move.

• Markov Chain | WikipediaLink

• Markov Chain SimulatorLink

• Analysis of Chutes and LaddersLink

• Absorbing Markov Chain | WikipediaLink

• Math.NET NumericsLink

Encryption

Task

• Implement two substitution cipher algorithms to encrypt and decrypt text in the ISO basic Latin alphabet (A-Z):

  • Chaociper

    1
    class Chaocipher:
    2
      lAlphabet: string
    3
      rAlphabet: string

    1
      fn encrypt(plaintext: string) -> ciphertext: string
    2
      fn decrypt(ciphertext: string) -> plaintext: string

  • Autokey Cipher (using a tabula recta)

    tabula recta

    1
      fn encrypt(plaintext: string, primer: string) -> ciphertext: string
    2
      fn decrypt(ciphertext: string, primer: string) -> plaintext: string

• Prepare comprehensive unit tests

  Strive for a unit test coverage of 100% (where sensible.)

  ---

Chaocipher

Full article here! The Chaocipher was invented by J.F.Byrne in 1918 and, although simple by modern cryptographic standards, does not appear to have been broken until the algorithm was finally disclosed by his family in 2010.

Autokey Cipher

Full article here!

The autokey cipher, as used by members of the American Cryptogram Association, starts with a relatively-short keyword, the primer, and appends the message to it. If, for example, the keyword is QUEENLY and the message is attack at dawn, the key would be QUEENLYATTACKATDAWN.

1
Plaintext:  attackatdawn...
2
Key:        QUEENLYATTACKATDAWN....
3
Ciphertext: QNXEPVYTWTWP...