Skip to content

A square grid path problem

Sunday, January 20, 2008

Last November I have solved Problem 15 of Project Euler (a counting problem involving paths in square grids), and, although the problem admits a simple solution, some of the solutions presented in their forums are very complicated. Thus, I thought it would be a good idea to present my solution, as I consider it very simple.

Problem statement

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

Path diagram for 4×4 square grid

How many routes are there through a 20×20 grid?

My solution

In order to make the problem more interesting, let us investigate the more general problem of counting the number of routes in a n×n grid. Our argument is based on three observations:

  1. all the paths have size 2×n (the reason is obvious: you have to go right n positions and down another n positions);
  2. since we can only go right or down, we can identify every path by a string of Rs and Ds, where a R means going right and a D means going down; as an example, the paths illustrated in the problem statement are (from left to right and from top to bottom): RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
  3. the strings mentioned above must contain the same number of Rs and Ds.

From these three observations, we can transform the problem to the following:

How many different strings of size 2×n, consisting of n Rs and n Ds, there are?

The solution is now very simple, because the positioning of n Ds (or Rs) determines the positioning of the other n Rs (or Ds). Hence, the number we are interested in is the number in which we can choose n positions from 2×n available. The answer, using the traditional notation for the binomial coefficient, is:

LaTeX Formula

Instantiating n with 20, we get the answer to the initial problem of the 20×20 grid.

Generalization to m×n grids

The generalization to a m×n grid is also simple. The only difference is that the strings have length m+n. Using the same reasoning as above, the number of paths through a m×n grid is:

LaTeX Formula

Final note: If you want to access the forum of the problem, you have to solve it.

Filed in Algorithms, Mathematics | Comments (31)

How to be more confident about your own programs: an example using Perl

Thursday, July 26, 2007

Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians.

Perl Camel

It was Edsger W. Dijkstra, the famous computer scientist, who wrote these words in his note named “How do we tell truths that might hurt?“. I am sure that many people didn’t like to read them, and didn’t understand what he meant.

Although it is not my intention to discuss his words, I want to present a simple example that demonstrates how mathematics can be used to program better and to make you more confident about your own programs.

This post includes a fair amount of mathematical definitions and concepts, but they should not be difficult to understand. After the mathematical discussion, I present an example using the Perl programming language (it also applies to languages like C or Java).

The Problem

The problem I am going to deal with, involves the ceiling and floor functions. If you don’t remember, the floor of a real number LaTeX Formula is (usually) written as LaTeX Formula and it is defined as the greatest integer that is at most LaTeX Formula. Similarly, the ceiling of a real number LaTeX Formula is written as LaTeX Formula and it is defined as the smallest integer that is at least LaTeX Formula.

The goal is to implement the ceiling function supposing that our programming language only provides the floor function to round numbers. Formally, given a real LaTeX Formula, we want to calculate an expression LaTeX Formula such that:

LaTeX Formula

(Continued)

Related Articles:

Filed in Algorithms, Mathematics, Perl, Programming | Comments (5)

Swapping the values of two variables

Wednesday, July 11, 2007

In my previous post I have promised that I would put here some of my technical notes (JFFs). Today I am posting JFF1, which presents a very well-known problem in a non-traditional way. The problem is how to swap the values of two variables without using another temporary one.

I start by presenting the properties involved in the traditional solution and then I generalize it for arbitrary operators. I finish the note with a simple refinement. If you have any nice example instantiation for the last set of assumptions, I would be glad to know it. Other than that, comments or corrections are more than welcome!
The note is available in PDF. Click the following link to get it:

JFF1 – Swapping the value of two variables

Related Articles:

Filed in Algorithms, Mathematics, Programming | Comments (2)

I am still alive!

Friday, June 15, 2007

That’s true: the last post was exactly 5 months ago, but I’m still alive! A lot of new stuff happened during these 5 months. Two days after writing the last post, I went with my group (Foundations of Programming) to a very nice hotel in Ruddington, where, during two days, each member had to present something about his/her work. I’ve talked about a result I’ve derived related with distributivity through the Greatest Common Divisor. My slides are available at the event’s webpage and I will put online a note with all the details.

A few days later Alexandra got ill with some strange pain in the abdominal area. The following weeks were really hard, since she had to go to the hospital emergency services. So that you have an idea of how strange the whole thing was, the doctors still don’t know what the problem is! Now, she has occasional pain, but it seems to be much more controlled.

Anyway, more or less at the same time I started to read a very nice article (a Functional Pearl) written by Jeremy Gibbons, Richard Bird and David Lester named “Enumerating the Rationals“. The paper presents some algorithms encoded in Haskell to enumerate the positive rational numbers. In particular, it presents algorithms to construct the famous Stern-Brocot and Calkin-Wilf trees. It also presents a very efficient algorithm to enumerate the rationals in Calkin-Wilf order just by using as current state the previous rational (i.e., two integer numbers). However, the authors claim that “it is not at all obvious” how to create a similar efficient algorithm for enumerating the rationals in Stern-Brocot order. Well, after reading it, Roland (my supervisor) and me found a way of doing it. The key idea is that rational numbers are pairs of coprime numbers (numbers which greatest common divisor is 1) and thus, we can use Euclid’s algorithm as a basis for enumerating these pairs. By using the Extended Euclid’s algorithm written using matrix multiplication, we were able to derive both Calkin-Wilf and Stern-Brocot enumerations from the same algorithm. We wrote a paper named “Recounting the Rationals: Twice!” that was submitted to the journal American Mathematical Monthly.

(Continued)

Filed in Algorithms, Mathematics, Personal, Programming | Comments (0)

On Programming and Mathematical Methodology — Part II

Monday, January 15, 2007

In the last post I have presented some historical context about programming and mathematical methodology. If you read it, then you should have an idea when and why programmers started to investigate on mathematical methodology. However, I haven’t mentioned any aspects of mathematical methodology that can help us to improve our programming or mathematical skills.

In this post, I’ll talk about mathematical proofs. And what’s the relevance of this topic to programmers? Well, computer programs are mathematical formulae, with a precise formal meaning and embodying constructive theorems about the systems they implement (as well-written in “Mathematics and Programming – A Revolution in the Art of Effective Reasoning“, by Roland Backhouse). The difference between theorems embodied by computer programs and the ones usually studied in mathematics is that they are applied by an unforgiving machine, with the effect that the smallest error can cause a huge damage. This means that computer programmers must create trustworth designs, i.e., the constructive theorems embodied by their programs must be programmed correctly.

Mathematical Proofs

Mathematicians job is to do mathematics, i.e., to design and present theorems, arguments, algorithms and in some cases whole theories. However, the traditional mathematical curriculum is more concerned with teaching mathematical facts — existing theories and concepts — than with the doing of mathematics. And even when design and presentation get some attention, they are treated separately: design of solutions is viewed as a psychological issue, while presentation is viewed as a matter of personal style (words from this Dijkstra’s note on Mathematical Methodology).
(Continued)

Related Articles:

Filed in Algorithms, Mathematics, Methodology, Programming | Comments (11)

On Programming and Mathematical Methodology

Thursday, December 28, 2006

First of all, welcome to my new blog. Being this my first post, I will present myself, give you some background on what I am doing and explain what are my intentions about this blog. My name is João Fernando Ferreira and I am a research student at the Foundations of Programming research group at the University of Nottingham (visit the About page to find out more).

My research is on algorithmic problem solving and its main goal is to develop calculational problem-solving techniques resulting in educational material supporting the use of a calculational approach to algorithmic problem solving. The focus of the project will be on the dynamics of problem solving – the processes of mathematical modelling and effective calculation in the formulation of concise and precise algorithmic methods.

As any other researcher, I spend most of my time reading and writing. That is one of the reasons I have created this blog: to organise my written notes. Using a blog system brings me some advantages like:

  • I can tag my notes and use the system search capabilities to find them;
  • I can access and change them from any place in the world, as long as I have Internet access;
  • I can add new content from any place in the world, as well;
  • I can share my notes and get feedback from my colleagues, supervisors, friends or anyone who is just interested in the same topics.

Other important reason to share my notes and thoughts is that I think they may be of interest for programmers. Since this is my first post, and (probably) most of you don’t really understand what I am doing, I will start by presenting some historical facts (mixed with personal opinions) and motivations. It is my hope that these facts will help you understand the relation and importance of mathematical methodology to programming. Please note that to read the entire post, you may need to click the “Read more” link.

Historical context

In the 1960s, programmers started recognising that there were serious problems in the programming field and that it was necessary to prove the correctness of programs. At the time, software engineering was facing a software crisis and programming was not very well understood. Many software projects ran over budget and schedule and some of them even caused property damage and loss of life (see the RISKS-FORUM Digest for some examples).

To solve these problems, computer scientists focused on programming methodology and on ways to build programs in a systematic way. A common consensus was that programs should be proved correct, and in the late 1960s, some important articles had an important impact on the field. In 1968, Edsger W. Dijkstra published an article on the harmfulness of the Go To statement, where he claims that its use makes it impossible to determine the progress of a program. Also, one year later, Tony Hoare published a seminal article where he introduces the Hoare triples and an axiomatic approach to language definition.
(Continued)

Related Articles:

Filed in Algorithms, Mathematics, Methodology, Personal, Programming | Comments (10)