Algorithmic Problem Solving

An entertaining and captivating way to learn the fundamentals of using algorithms to solve problems.

Algorithmic problems are problems where the solution involves —possibly implicitly— the design of an algorithm. Algorithmic problem solving is about the formulation and solution of such problems.

The demands on the reliability of computer software have, we believe, lead to massive improvements in our problem-solving skills and in mathematical method. The improvements are centred on goal-directed, calculational construction of algorithms like for the internet darknet as opposed to the traditional guess-and-verify methodology.

Of course, many algorithmic problems still pose massive challenges, and we have a very great deal to learn about good and bad technique in solving such problems. We believe, however, that the time is now ripe for a greater focus on the methodology of problem solving, rather than on specific results. Our goal is to ensure that future generations are much better problem solvers than we are, not because they know more facts but because their skills are more refined.

We aim to achieve our goals using a problem-driven approach. We intend to tackle challenging problems and document our successes and failures in solving these problems. The choice of problem is crucial. We have no intention of trying to win the jackpot by tackling famous outstanding problems; instead, we will tackle problems that we suspect are within our grasp and from which we can learn the most. (Of course, such problems may one day include some famous outstanding problems!) These may be new problems, including ones we invent ourselves in order to explore particular techniques, or old problems, where we feel there is scope for improvement of the existing method.

Turing-Tape Games: A Challenge in Algorithmic Problem Solving

Alan M. Turing and Turing-Tape Games

The year 2012 is the 100th anniversary of the birth of Alan M. Turing who is famous both as a mathematician and for his pioneering work on computing machines. To celebrate this centenary, we have developed a collection of one-person games played on a Turing tape; the collection has infinitely many instances. The competition is about finding the “best” solution to a large number of the games.

So far as we are aware, the games are entirely novel and haven’t been studied before (except for a couple of isolated examples). The games quickly become too difficult to solve by hand and so demand machine support for their solution. They are based on the mathematical theory of cyclotomic polynomials. Although the games can be solved with little or no knowledge of the underlying mathematics, we think that this combination of mathematics and computer programming is very relevant to celebrating Turing’s legacy.

(2012/09/16)The competition has now ended. It is no longer possible to register to enter the competition and it is no longer possible to submit solutions. However, for those who wish to develop and test their own solutions it is still possible to check solutions. See here for solutions constructed by the APS team.

What Are Turing-Tape Games and What Is A “Best” Solution?

The next subsection is a formal specification of a solution to a Turing-tape game and the subsequent section specifies how we will be judging solutions.

If you are new to this website, go to this section for the details of one particular Turing-tape game and hints on how to solve them in general. The video (accessible from the sidebar) also offers additional help.

Specification

A Turing tape is a tape (a long, thin strip of paper) that has been divided into squares. All Turing-tape games are played on a Turing tape. The tapes are assumed to be of infinite extent (to the left and right) — which just means that they are as long as is necessary to play the game.

There are two components in the specification of a Turing-tape game: the replacement set and the displacement. The displacement is an integer. If the displacement is d , the goal is to displace a single coin by d squares using moves specified by the replacement set. The replacement set is a set R of integers. The elements of R are called relative positions.

An expansion at square m removes one coin from square m and adds one coin at the squares m

p for each p in the set R . A contraction at square m removes one coin from the square m

p for each p in the set R and adds one coin at the square m . A move is an expansion or a contraction at some square m . A move is valid from a given state of the Turing tape if, before the move, there is at least one coin at each square where the removal of a coin is required by the move. A sequence of moves is valid starting from a given state of the Turing tape if every move in the sequence is valid from the then current state of the tape.

The figure below summarises the allowed moves and the goal in the game we call T12. In this game the displacement is 12 and the replacement set is {-3,-2,2,3}.

A solution to the Turing-Tape game specified by the pair ( d , R ) is a sequence of moves such that, beginning in a state where there is exactly one coin on some square i , the sequence is valid and results in a state in which there is exactly one coin at the square i

d .

Criteria For Winning

The competition is about finding the “best” solutions to a number of Turing-tape games. Specifically, solutions will be judged first on validity, then on number of moves, and then on number of coins used. Competitors will be divided into four categories: pre-university, undergraduate, postgraduate and other. The winning entry in each category will be the one that achieves the highest number of best solutions for all games set in the final. (So entries in the practice rounds do not count in the final.) Ties will be decided by order of receipt. Repeat submissions are allowed; the last received submission will count and earlier submissions will be automatically eliminated.

Solutions must be submitted using our checking script. Solutions will be considered invalid if received after 2012/9/16, 5pm BST. In order to win a prize, submitted solutions will be checked by us; no prize will be awarded unless the solution passes this test.

Failure to comply with these rules will result in disqualification from the competition.

The names of prize winners will be published on this website on 2012/09/30 together with details of top scores.

The organisers’ decision is final and cannot be appealed.

Competition Timetable

There are three stages in the competition: familiarisation, practice and final. The familiarisation stage enables you to understand what is involved in solving the games; we have provided sample solutions to the familiarisation games. The practice stage gives you the opportunity to formulate an algorithm to solve a given Turing-tape game and to develop any software you need to implement your algorithm. Example problems have been released over a period of several weeks in a series of “rounds”. A table of top scores will be maintained throughout these two stages; the table, which you can find in the sidebar, records the number of moves and number of coins in validated solutions. The top-score table will not be updated during the final; however, once the final is complete we will publish the top scores.

Anyone can join in at any stage.

You must register with us to submit a solution to any of the games. We will send alerts at the beginning of each round to all registered participants. We will not use registration information for any purposes other than administering the competition. By registering with us you give us permission to use your submitted solutions in any publications (with appropriate acknowledgement), now or in the future. We will delete all registration information once prize winners have been announced.

Everyone who registers for the competition is entitled to a 20% discount on the price of a copy of the book Algorithmic Problem Solving by Roland Backhouse when purchased from the publisher, John Wiley and Sons. Details of how to claim the discount are sent with the email confirming registration.

Familiarisation.

Round 0. (2012/4/01) Announcement of competition. Familiarisation problems T6, T20.

Practice Problems.

Round 1. (2012/4/15) Solutions to T6, T20, Easy problems.
Round 2. (2012/4/29) Harder Problems.
Round 3. (2012/5/13) Mixed Problems.
Round 4. (2012/7/01) More Practice Problems.
Round 5. (2012/7/15) Last Practice Problems.

Grand Final

Round 6. (2012/8/26, 5pm British Summer Time) Problems to be announced.
Competition Ends. (2012/9/16, 5pm BST) Deadline for submission of entries.
Announcement of prize winners and top scores. (2012/09/30)

Competition Has Ended. Model Solutions

(2012/09/30) The deadline for submission of entries to the competition has now expired. The final set of games was challenging and finding optimal solutions was in some cases very challenging; congratulations to all those who submitted solutions. See here for a list of prizewinners. The topscores table shows the results of all competitors.

We constructed our own solutions to all the games. This file contains solutions constructed using a simple greedy algorithm; the solutions use the minimal number of moves but make no attempt to minimise the number of coins. This file contains optimal solutions (i.e. solutions that minimise the number of coins among solutions that minimise the number of moves); these were constucted using a depth-first search.

In the coming months, we plan to publish the software we developed to run the competition, to generate the games and to construct solutions. To get announcements, please subscribe to the Facebook Turing-Tape Competition group.

Prize Winners

Prizes were offered to students registered at a UK educational institution in the following categories: school (i.e. pre higher education), undergraduate at a university or college, postgraduate at a university or college.

Université Laval in Canada also awarded prizes to its own students.

Prizes have been awarded as follows.

UK Prizewinners

Undergraduate category: Wenda Li

Postgraduate Category: Alex Pinkney

Université Laval

1st Prize: Mathieu Goulet

2nd Prize: Jonatan Cloutier

3rd Prize: Charles Brunet

There were no entries in the pre-university category.

UK prize winners were each awarded £250, a copy of the book Algorithmic Problem Solving by Roland Backhouse and a copy of MATLAB and Simulink Student Edition. Laval prizewinners were awarded 1st prize: 500 dollars, 2nd prize: 300 dollars and 3rd prize: 200 dollars.

We are very grateful to The School of Computer Science at the University of Nottingham, the School of Computing at Teesside University, John Wiley and Sons and MathWorks for their sponsorship. We are also very grateful to Université Laval and, in particular, Jules Desharnais for supporting the competition.

Games Used in Each Round

The table below will be updated at the start of each round. At the same time, the games will be entered into the checker for you to check and submit your solutions.

Round	Start Date	Name	Displacement	Replacement Set
0	2012/4/01	Familiarisation
	T6	6	{-1,1}
	T12	12	{-3,-2,2,3}
	T20	20	{-6,-5,-2,2,5,6}
1	2012/4/15	Easy Practice Problems
	T30	30	{-3,-1,1,3}
	T60	60	{-5,-2,-1,1,2,5}
	T70	70	{-5,-3,-1,1,3,5}
2	2012/4/29	Harder Practice Problems
	T72a	72	{-10,-9,-4,-3,-2,2,3,4,9,10}
	T84	84	{-10,-7,-6,-2,2,6,7,10}
3	2012/5/13	Mixed Practice Problems
	T72b	72	{-9,-7,-6,-4,-1,1,4,6,7,9}
	T90a	90	{-5,-4,-3,3,4,5}
	T105	105	{-7,-4,-2,-1,1,2,4,7}
	T180a	180	{-14,-10,-9,-6,-2,2,6,9,10,14}
4	2012/7/01	More Practice Problems
	T126	126	{-7,-5,-3,-1,1,3,5,7}
	T168	168	{-7,-6,-5,-4,4,5,6,7}
5	2012/7/15	Last Practice Problems
	T90b	90	{-9,-8,-7,-6,-5,5,6,7,8,9}
	T120a	120	{-15,-10,-9,-7,-4,-3,-2,-1, 1,2,3,4,7,9,10,15}
	T180b	180	{-9,-6,-5,-2,-1,1,2,5,6,9}
6	2012/8/26	Grand final.
	T120b	120	{-7,-5,-4,4,5,7}
	T140	140	{-7,-6,-3,-2,2,3,6,7}
	T180c	180	{-13,-11,-10,-9,-8,-7,-6,-5, 5,6,7,8,9,10,11,13}
	T198	198	{-9,-7,-5,-3,-1,1,3,5,7,9}
	T210	210	{-9,-8,-7,-3,3,7,8,9}
	T308	308	{-11,-10,-7,-6,-3,-2, 2,3,6,7,10,11}
	T396	396	{-11,-7,-5,-3,-2,-1, 1,2,3,5,7,11}
	T468	468	{-13,-11,-10,-9,-8,-6,-1, 1,6,8,9,10,11,13}
	T546	546	{-13,-12,-11,-10,-9,-8,-7, 7,8,9,10,11,12,13}
7	2012/9/16	Competition ends

Checking And Submitting Your Solutions

We have provided a simple interface for you to check solutions. See here.

The solutions must be presented as a sequence of moves separated by semicolons. Expansions are indicated by the letter “e” and contractions by the letter “c”. You can choose any number you like for the starting square. See the solutions to the familiariation problems for examples of the format.

(Note added 2012/09/30): Submitting solutions is no longer possible. Once you have checked your solution, you may send a record to the central database. The number of moves and number of coins in your solution will then be displayed together with your username if your solution is in the top ten solutions in your category. By sending us the solution, you agree to allow us to use the solution in any future publications (with appropriate acknowledgement). In the familiarisation/practice stages, the only information about yourself that is displayed in the top scores is your username and country.

Familiarisation: An Example Turing-Tape Game And Its Solution

This section is about one simple example of a Turing-tape game. The example is illustrative of the general form of the games and the different solutions that can be constructed. It’s important to understand this example before tackling problems presented later.

Problem Statement

A Turing tape is a tape (a long, thin strip of paper) that has been divided into squares. The tapes are assumed to be of infinite extent (to the left and right) — which just means that they are as long as is necessary to play the game.

A single coin is placed on one of the squares of a Turing tape. The task is to displace the coin twelve places using a sequence of moves, which we now define. A move is one of two types: an “expansion” or a “contraction”. An expansion replaces a single coin on one square by four coins; relative to the position of the coin that is removed, the four coins are placed at positions −3, −2, 2 and 3. (Thus an expansion increases — “expands” — the number of coins on the strip of paper.) A contraction is the reverse: a contraction replaces four coins at relative positions −3, −2, 2 and 3 by one coin at relative position 0. (Thus a contraction reduces — “contracts”—the number of coins on the tape.) No other moves are possible, and there are no other restrictions on moves. (The number of coins on any one square is unlimited and there are no restrictions on the positions or numbers of coins that are not involved in a move.)

Construct a sequence of moves that when begun in a state with one coin on one of the squares of a Turing tape (and all other squares empty) ends with one coin at a displacement of 12 squares from the initial position (and all other squares empty).

Example Solutions

Three different solutions are presented here, here and here. (The first solution, based on a simple algorithm, was constructed by us, the second and third were constructed by two students at the University of Nottingham — Radu Tuica and Mingyang Yan, respectively.) Click through to the final page of each to find the complete solution; earlier pages show the individual moves used to construct the final solution.

All three solutions exploit the symmetry in the problem statement: any sequence of moves that displaces a coin from the square numbered 0 to the square numbered 12 can be reversed to obtain a sequence of moves that displaces a coin from the square numbered 12 to the square numbered 0. The solutions therefore begin with the given start state (one coin at square 0) at the top of the page and the given final state (one coin at square 12) at the foot of the page. Clicking through to the next page shows the first and last moves in the solutions. For all three solutions, the first and last moves are obviously the same; the solutions differ from the 3rd move onwards.

Our solution uses 16 moves, which is more than the number used by the other two solutions, but it has the advantage (for us) that we know precisely how it was constructed and so is the easiest to explain.

The solution comprises a sequence of expansions followed by a sequence of contractions. The expansions and contractions are in (1–1) correspondence: an expansion at square k is matched by a contraction at square 12−k. (For example, the first expansion at square 0 is matched by the last contraction at square 12; also, the second expansion at square 3 is matched by the last-but-one contraction at square 9.) Note how the last expansion creates a row of coins that has a left-right symmetry. Because of the (1–1) correspondence between expansions and contractions, and the left-right symmetry of the middle state, it suffices to explain how the sequence of expansions is constructed; the sequence of contractions is then constructed by the simple process of reversing the sequence of corresponding contractions.

The sequence of expansions begins with a sequence that, starting from square 0 introduces a coin at square 12. This is followed by one expansion at square 12, the reason for which is that the subsequent sequence of contractions must end with a contraction at square 12 and the only way for this to be possible is for it to be preceded by an expansion at square 12. The position of each of these expansions is indicated by a green-coloured coin. This initial sequence of expansions is thus as follows, where en means perform an expansion at square n.

e0 ; e3 ; e6 ; e9 ; e12
Following on from here, expansions are made at squares 9, 7 and 4. Why these squares are chosen may seem like magic but they are chosen algorithmically, as explained below. The squares at which they occur are shown as blue dots in our solution. The sequence of contractions is then constructed using the algorithm explained above. The complete solution is then as follows, where cn means perform a contraction at square n.

e0 ; e3 ; e6 ; e9 ; e12 ; e9; e7 ; e4;
c8 ; c5 ; c3 ; c0 ; c3 ; c6 ; c9 ; c12
Mingyang Yan’s solution uses 14 moves (thus 2 fewer than our solution). The first three moves are expansions; symmetrically, the last three moves are contractions. The solution therefore takes the following form, where the three dots indicate the part of the solution that has yet to be constructed.

e0 ; e2 ; e4 ; ... ; c8 ; c10 ; c12
Note that 0+12 = 2+10 = 4+8 = 12.

Mingyang Yan’s solution then continues with a contraction at square 0 and an expansion at square 7; symmetrically, it ends with a contraction at square 5 and an expansion at square 12 followed by the three final moves constructed earlier. This gives the partial solution:

e0 ; e2 ; e4 ; c0 ; e7 ; ... ; c5 ; e12 ; c8 ; c10 ; c12
Continuing in this way, the complete solution constructed by Mingyang Yan is as follows.

e0 ; e2 ; e4 ; c0 ; e7 ; c2 ; c3 ; e9 ; e10 ; c5 ; e12 ; c8 ; c10 ; c12
Note how the last 7 moves “invert” the first 7 moves. Radu Tuica’s solution is also symmetric in the same way. Finally, note that the set of moves in Radu Tuica’s and Mingyang Yan’s solutions are equal; also, Mingyang Yan’s solution uses just 10 coins whereas Radu Tuica’s solution uses 22 coins.

The games we will pose in this competition all have symmetric solutions; you are advised to exploit this fact in finding a solution.

The Secret for Success

In this subsection we remove the magic from the expansions at squares 4, 7 and 9 (and the corresponding contractions at squares 8, 5 and 3). Some familiarity with polynomial arithmetic is assumed. If you are not familiar with the algebraic manipulations of polynomials, ask your teacher to provide further explanation (or consult the internet).

Invariants are vital to understanding repetitive processes — like executing a sequence of moves. When a move is made in this game, the number of coins on the tape increases or decreases by 3. So an obvious invariant is the number of coins modulo 3 (the remainder after dividing the number of coins by 3); since this is initially 1, it will always be 1 no matter how many moves are made. However, this invariant is not very helpful.

A much more helpful invariant is identified by using an illuminating representation of the state of the tape. Suppose we represent a state of the tape by a polynomial in the indeterminate x ; for example, let us use x 0 to represent the initial state where there is one coin on square 0, x 12 to represent the final state where there is one coin on square 12, and x − 1

2 x 0

x 1

x 5

x 6

x 7 to represent the state where there is one coin on each of squares −1, 1, 5, 6 and 7 and two coins on square 0. In general, a term i × x j represents i coins at square j . Then an expansion at square k is represented by the addition of the polynomial x k × R , where R denotes x − 3

x − 2 − x 0

x 2

x 3 , to the polynomial representing the current state. Similarly a contraction at square k is represented by the subtraction of the polynomial x k × R . In other words, every move adds a multiple of the polynomial R to the representation of the current state.

Just as adding a multiple of 3 to a number maintains invariant the value of the number modulo 3, the process of adding a multiple of the polynomial R to a polynomial maintains invariant the value of the polynomial modulo R . Since this is initially x 0 modulo R and finally x 12 modulo R , it must be the case that R divides x 12 − x 0 . Indeed, this is the case. We have x 0

( x 9

x 7

x 4 ) × R

=

x 12

( x 3

x 5

x 8 ) × R

. This formula explains the magic expansions and contractions!

Eliminating negative exponents, the game we have presented is solvable because 1

x − x 3

x 5

x 6 divides x 12 − 1 . The quotient is ( x 6

x 4

x )

−

( 1

x 2

x 5 ) . Any solution to the game must involve at least 3 expansions and 3 contractions. Additional moves are necessary to make these moves possible. For example, a solution must begin with an expansion at the starting square and end with a contraction at the final square and also include a contraction at the starting square and an expansion at the final square. In order to determine a solution to a given Turing-Tape game you should first do the appropriate polynomial division to find out which moves are indispensable. There are several well-known tools that will do the task for you but it is also instructive to implement polynomial division yourself. The remaining task is to determine how to enable these moves.

This section includes some more examples of Turing-tape games for you to solve and the details of the Turing-tape competition. First, we give a general definition of a Turing-tape game.

More Examples

The table below gives two further examples of Turing-tape games.

Example Replacement-Set Games

Name	Displacement	Replacement Set
T6	6	{-1,1}
T20	20	{-6,-5,-2,2,5,6}

Example T6 has been on the internet for some time, and was the inspiration for the class of Turing-tape games. It has been dubbed the “nuclear pennies game” and, so far as we are aware, it first appeared on the internet in September 2007 here. The solution given there has 20 moves and uses 7 coins. The problem is discussed in our paper and is also posed as exercise 3.4 in the book Algorithmic Problem Solving by Roland Backhouse. The solution given there uses fewer moves (18) but more coins (10). By a careful choice of permutation of the moves, is possible to construct a solution that uses the same 18 moves but just 4 coins. See here for such a solution found by one of the competitors in the familiarisation round. (Note: as of 2012/07/27 our paper is “In Press”. Citation information: Roland Backhouse, Wei Chen, João F. Ferreira, The algorithmics of solitaire-like games, Science of Computer Programming, Available online 27 July 2012, ISSN 0167-6423, 10.1016/j.scico.2012.07.007. (http://www.sciencedirect.com/science/article/pii/S0167642312001359?v=s5).)

Example T20 can be solved using 16 moves and 16 coins – as first discovered by Wenda Li, an undergraduate competitor in the familiarisation round. There is more than one such solution. Two are shown here. If you are just joining in the competition, you may want to have a go at finding other solutions to problems T6 and T20.

Calculating the quotient polynomials (as explained above) identifies those (relative) positions at which expansions and contractions must be made. To help you find solutions to games T6 and T20, the following table shows these positions.

Moves that must be made

Name	Expand Positions	Contract Positions
T6	{4,5}	{1,2}
T20	{7,9,12,14}	{6,8,11,13}

For the game T6, if a coin is initially placed on square 0, then any solution must include moves that expand at squares 4 and 5 and contract at squares 1 and 2. Similarly, for the game T20, if a coin is initially placed on square 0, then any solution must include moves that expand at squares 7, 9, 12 and 14 and contract at squares 6, 8, 11 and 13. A hint for minimising the number of coins used is that a contraction at a square may precede an expansion at that square; contractions do not have to follow expansions.

Solutions to Familiarisation Problems

The table below shows best solutions for games T6 and T20. See the top-scores table for the first finders of the solutions.

We will not be publishing any more solutions. The statistics (number of moves and number of coins) for practice problems will continue to appear in the top-scores table.

Game	Solution
T6	e0;e1;e2;c0;e3;c1;e4;c2;c1;e5;e4;c2;e5;c3;e6;c4;c5;c6
T20	e0;e6;e12;c0;e14;c6;e9;c13;e7;c11;e14;c6;e20;c8;c14;c20
e0;e2;e7;c0;e12;c2;e14;c11;e9;c6;e18;c8;e20;c13;c18;c20

About The Author

Roland Backhouse is Professor of Computing Science at the University of Nottingham. Prior to this he led Mathematics of Programming (“Wiskunde van het Programmeren”) group at the Technische Universiteit Eindhoven in the Netherlands. His book “Program Construction: Calculating Implementations from Specifications” was published by John Wiley and Sons in 2003. Earlier textbooks he has written are “Program Construciton and Verification” (1986) and “Syntax of Programming Languages, Theory and Practice” (1979), both published by Prentice-Hall International.

Together with Jan van de Snepscheut (1953-1994), he established the series of conferences on the Mathematics of Program Construction. It is this topic that is the primary focus of his research.