Elevator Algorithm - A perfect interview question

For many years now, puzzle like questions have been very commonly asked during an interview for a Software Engineering job. If my memory serves me right, these were called the Microsoft Interview Questions during the 1990s. These days, they are more commonly referred to as Google Interview Questions.

Not everyone agrees with the strategy of asking these seemingly non-technical questions. For example, a famous question used to be about 4 people who walk at different speeds, and need to cross a bridge at night. The constraints being, there is only one flashlight available, and the bridge can safely take the weight of only two people. The task was to find the sequence that transports all of them in the shortest time, given the need that the flashlight has to be brought back once a pair uses it to cross the bridge. I liked that question, but I also understand, that it is only indirectly related to scheduling algorithms.

On the other hand, the “Elevator Algorithm”, as it is often called, is a much broader problem, and it is absolutely related to actual day to day coding tasks.

Let’s start with the simplest version. There is a very tall building, with one elevator to transport people. It’s just a regular elevator. On the inside there are command buttons corresponding to every floor, and every floor has request buttons for up and down. We have to design an algorithm to respond to the command buttons pressed by people inside the elevator, and the request buttons on the floors.

I am not giving a solution here, because the candidate has to treat it as a design problem, and more importantly as an “optimization problem”. There are different strategies available, and they optimize on different parameters.

The simplest strategy is of course, FCFS, First Come First Served. The elevator would respond to the first request button, go to that floor, drop the person to the requested floor and then move on to the next person. At first glance, it’s clear that this will generate excessive up and down movement of the elevator. It also will not be the most time efficient. But it’s not all bad. It’s very fair in terms of serving, if fairness means relative wait time. Choosing the next request would be very fast, based on a simple queue data structure.

A completely different strategy would be SSF, Shortest Seek First. Whenever the elevator drops a person to the desired floor, it can look at all the requests, and pick the request that’s originating at the nearest floor. It will minimize the distance that elevator has to travel to start serving another request. Clearly, there is a possibility that requests keep coming from a region of nearby floors, and the elevator doesn’t get a chance to serve older requests from floors that are far away. This can lead to starvation for some requests, as there is no upper bound on the wait time. Note that a slightly more complex structure than a queue, would be needed to store the requests, so that they can be searched quickly to find out the next best request. That would be another side question.

The two strategies above try to optimize different goals - fairness and the distance our elevator has to travel. These goals are in conflict of each other. A candidate can be expected to observe this conflict, and realize that this is an optimization problem, and not a simple coding exercise.

There can be other considerations as well, which will matter in more sophisticated strategies. For example the travel time once the person is on board, and the cost of stopping/restarting the elevator for picking up a person. 

It’s easy to see the relation of this problem to Computer Science. This is an old and very well known problem of Disk Arm Scheduling. The cost of seek as measured in time, and the movement of disk arm, both need to be minimized. A very similar problem exists for sorting items that are on tape, and is addressed by Knuth in his book.

The elevator problem, itself has been described on the Wikipedia page. It’s possible to tweak FCFS and SSF to add other considerations. For example, adding an upper bound on wait time in SSF, so that a request waiting over that bound gets priority over the nearest request etc. But the most widely used compromise relies on moving the elevator in one direction, serving as many requests as possible, and then changing the direction to serve requests in that direction, and so on. That's what is actually known as the Elevator Algorithm.

More fundamentally, the core of the problem is sequential access. In my opinion, that realization is more important than knowing an implementation of Elevator Algorithm. The idea behind this problem will appear in one form or another whenever you are restricted to sequential access. For example, the data in memory could in a very big doubly linked list. Today, in the world of Big Data, sequential read is the most common access pattern, and a variation of this problem will confront you, whether you do map-reduce or some other implementation.

Hence, in my opinion, this is one of the best interview questions to gauge the candidate’s grasp on the fundamentals of Computer Science. In addition, this one can be extended in many different directions, making it an ideal problem to see how the candidate thinks. It's easy to make it an object oriented design problem. It can be used to discuss different data structures that will help in the implementation. If needed, it can be made even more complicated by adding multiple elevators serving the building, where a request button summons the most appropriate elevator. That is another nice optimization problem. But the core single elevator problem is often good enough to judge the ability of a candidate to see different trade-offs inherent in any design.

As a side note, the original elevator analogy for sequential access and/or processing is not as straightforward anymore. Real life elevators have other complex considerations, such as time of day, special floors etc. Some have more complex floor controls, where people can also express where they intend to go. And so on. It’s a topic in itself, as can be seen by a rather large tome named Elevator Traffic Handbook. You can preview that book on Google Books if you want to dig deeper on this topic. :-)

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Sum Of Consecutive Primes - Part 2

When I wrote the blog post on “Sum Of Consecutive Primes” I said that it was a pure D! activity. This is D!^2 :-)

One of the comments on the post suggested to do the analysis to find even more special primes. I liked the suggestion and modified my code to look for even more special primes. What kind of specialty are we talking about?

Please read the original blog post for more details. As a quick recap, we are looking for primes that can be written as sum of consecutive primes.

Obtaining primes from adding consecutive primes is just beautiful. As the analysis shows, many of these prime numbers can be written as multiple different sequences of consecutive primes. Some of these sequences are surprisingly large.

Within such primes, how about finding some more specializations, as follows.
1. The length of at least one the sequence itself is prime.
2. More specialization of the first, length of EVERY sequence is prime.
3. For a particular prime, the number of different generating sequences is also a prime.
4. Intersection of 2, and 3 : the number of sequences is prime, and length of every sequence is also prime.

In each case, we are looking for the primes below an arbitrary limit, which is 1 million for Problem 50 in Project Euler.

So here are the answers.

1. At least one sequence with prime length

The largest prime is
999983 = 34337 + 34351 + … + 34613 (29 primes)

The largest sequence is for
981391 = 71 + 73 + … + 3917 (523 primes)

The prime 442019 is noteworthy, as it has the six generating sequences, maximum for this subset. Only the first sequence is of prime length.
442019 = 419 + 421 + … + 2621 (301 primes)
442019 = 7529 + 7537 + … + 8017 (57 primes)
442019 = 13229 + 13241 + … + 13567 (33 primes)
442019 = 17569 + 17573 + … + 17807 (25 primes)
442019 = 49069 + 49081 + … + 147347 (9 primes)

2 All generating sequences are of prime length

There have to be more than 1 generating sequences to be qualified for this criterion.

The largest is
999863 = 13723 + 13729 + … + 14447 (71 primes)
999863 = 199933 + … + 200003 (5 primes)

The largest sequence in this subset is for
973691 = 61 + 67 + … + 3907 (523 primes)
Interestingly it’s the same length (523) for the largest sequence for the previous subset above.

Most prime sequences are for
999049 = 4801 + 4813 + … + 6337 (179 primes)
999049 = 7013 + 7019 + … + 8231 (131 primes)
999049 = 21019 + 21023 + … + 21493 (47 primes)
999049 = 199799 + … + 199819 (5 primes)

3. Number of generating sequence is prime

The largest is same as above 999863.

The largest sequence is for a prime that is an answer to the Project Euler : Problem 50, so I cannot give it here.

The most sequences are for
988321 = 113 + 127 + … + 3923 (515 primes)
988321 = 4673 + 4679 + .. + 6247(181 primes)
988321 = 5107 + 5113 +  … + 6577 (169 primes)
988321 = 89797 + 89809 + … + 89899 (11 primes)
988321 =  329419 + 329431 + 329471
Note that 2nd and 3rd of the above are overlapping sequences!

4. Primest of primes

Now let’s see which are the most special of these. These have ONLY a prime number ways of generating sequences, and length of each of these sequences is also prime.

The largest is 999863, same as subset 2 above.

The largest sequence in this subset is also for the same prime as for subset 2 above.
973691 = 61 + 67 + … + 3907 (523 primes)
973691 = 6841 + 6857 + …  + 8039 (131 primes)
So there are 2 sequences, each has prime number of primes.

And the most sequences are for
993367 = 13679 + 13681 + … + 14387 (71 primes)
993367 = 141863 + 141871 + … + 141941 (7 primes)
993367 = 331099 + 331127 + 331141
Now that’s one beautiful number. It’s the largest prime below 1 million that can be written in most prime number of different ways as sum of prime number of consecutive primes :-)

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Project Euler : Probelm 78

The Project Euler : Problem 78 has been solved by comparatively less number of people than other problems on the same page. It is stated as

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
Find the least value of n for which p(n) is divisible by one million.

This is exactly the same as integer partitions - which is the number of ways in which a given natural number can be written as sum of smaller natural numbers. You can find the proof of the formula in this discussion.

I previously described two algorithms to calculate the integer partitions. The recursive algorithm suffers from being very slow, to the point of being useless. The iterative algorithm has acceptable speed, but its memory requirements prohibit it from being used for solving this problem.

So we need a much better way to calculate integer partitions. Fortunately, we can use some mathematics. You can check Wikipedia article on integer partitions, which mentions the following formula.

P(n) = P(n-1) + P(n-2) - P(n-5) - P(n-7) + …

There 2 things to notice.

1. The sign of each term changes based on the formula mentioned below.
2. Every term on the right hand side is of the form N-x. This x has to be a “Pentagonal Number” and is also given by the same formula below.

More concisely,

P(n) = SUM of [ (-1)^k . P (n - k(3k-1)/2) ]
for both positive and negative values of k as it goes from 1 to N.
Of course P(m) = 0, for any m less than 0.

We can use it to solve the Project Euler Problem 78 in a straight-forward way.

We start with calculating P(n) from 1 onwards up to an arbitrary number, say 1 million. To calculate P(N) at any iteration we have a nested loop that goes from N down to 1, examining only those numbers given by N-x, where x is a pentagonal number. We must consider both negative and positive values of x at every iteration and use proper sign to either add or subtract P(N-x). We will stop when we find a value of P(n) which is divisible by 1 million.

One thing to keep in mind is, the values for P(N) can get fairly large. There is no need to use anything like BigInteger, as we are only interested in the divisibility test, hence we can use the modulo arithmetic.

Here is an outline of the algorithm.

public static long GetNWithModulo1MPartitions () {

    final int MOD = 1000000 ; // divisible by 1M, from problem description
    finat int MAX = 1000000 ; // arbitrarily choosing max value for N
    int [] NumPartitions = new int [MAX] ;

    NumPartitions [0] = 1 ;
    NumPartitions [1] = 1 ;
    NumPartitions [2] = 2 ;

    for (int i = 3 ; i <= MAX ; i++ ) {
   
    long pn = 0 ;

    int sign = 0 ;
    long m1val = 0 ;
    long m2val = 0 ;

    int j ;
    for (j = 1 ; j <= i ; j++) {
        int m1 = i - (j * (3*j - 1) / 2) ; // using positive j
        int m2 = i - ((-1*j) * (3*(-1*j) - 1) / 2) ; // using negative j
        sign = (j%2 == 0) ? -1 : 1 ; // do we add or subtract ?
        // NOTE : in the following
        // if m1 or m2 is negative, the number of partitions is 0 by definition
        // We will add both, as one of them will be zero.
        m1val = (m1 < 0) ? 0 : (NumPartitions[m1] % MOD) ;
        m2val = (m2 < 0) ? 0 : (NumPartitions[m2] % MOD) ;

        pn = (pn + (sign * m1val) + (sign * m2val) ) % MOD ; // the real equation

        if ( pn < 0 ) {
            pn += MOD ; // force positive values
        } //
    }

    NumPartitions[i] = pn ;

    if ( pn == 0 ) {
        System.out.println ("Found N where P(N) is divisible by " + MOD + " and N = " + i) ;
        return ;
    }
    }

} //

That's a bit complicated. It certainly is too much for an interview question, even after giving the formula. The previous article on a recursive, as well as an iterative algorithm,  is a much better choice for a programming interview.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Calculating Integer Partitions

This post can serve as a nice interview question. Because some problems can be deceptively simple. Knowing the formula MAY NOT be enough to write an algorithm to compute it. Allow me to explain using the example of Integer Partitions. If you want the explanation on how this formula is derived, you can read it here.

To recap, Integer Partitions of a number, are ways the number can be expressed as sum of smaller numbers. And, P(N), the number of integer partitions of a positive integer N can be expressed as

P(N) = PP(N,1) = PP(N-1, 1) + PP(N, 2)

Where PP(N,k) is the number of partitions in which the smallest addend is at least k. And

PP(N,k) = 0 if N < k
PP(N,k) = 1 if N = k
otherwise
PP(N,k) = PP(N-k,k) + PP(N,k+1)

Here is how it can serve as an interview question to test the programming skills. The “natural” recursive solution can be easily implemented as follows.

public static int recursivePP (int N, int k) {
    if ( N <= 0 ) return 0 ;
    if ( N < k ) return 0 ;
    if ( N == k ) return 1 ;
    return recursivePP(N-k, k) + recursivePP(N, k+1) ;
}

This is grossly inefficient. Because intermediate results are unnecessarily computed multiple times. Every time the recursion reaches a particular pair (a,b) it will issue another recursion and calculate it all over again. So the code is natural, but not smart. It would take forever to compute say P(100) this way. What’s needed is a solution based on dynamic programming that builds P(i) as i goes from 1 to N. To do that we need to store the table of values for P(N,k).

Consider the following code.

public static long[][] PPvalues = new long[100][100] ;

public static long iterativePP (int N) {

    if ( N <= 0 ) return 0 ;

    // init P(N,k) for N=1, k=1
    PPvalues[1][1] = 1 ;

    for (int i = 1 ; i <= N ; i++) {
       
    // mark PP(N,k) where N == k
    PPvalues[i][i] = 1 ;

    for (int j = i-1 ; j > 0 ; j--) {

        long pp1 = ((i-j) < j) ? 0 : PPvalues[i-j][j] ;
        long pp2 = (i < (j+1)) ? 0 : PPvalues[i][j+1] ;
        PPvalues[i][j] = pp1 + pp2 ;

    } //
    } //

    return PPvalues[N][1] ;
}

Now this performs incredibly faster than the recursive solution. O(N^2) is not ideal, but it’s not bad either. This answer should usually be enough for an interview question.

Unfortunately, it’s not enough for finding out the value of P(N) for large values of N. The reason is the memory complexity of the algorithm which is also O(N^2), and our computers have a very finite memory.  For example, even with 8G of RAM I could not calculate the value of P(10000) because there is simply not enough memory to allocate the table.

That was a real bummer. There is no quick and easy way to optimize this to take less memory. Using a better data structure to store only half the table, as P(N,k) = 0 for N < k, of course won’t help much, only by a factor of 2.

One possibility is to compute only a section of the table at any given time. Note that the formula requires only the current column and the previous column, to calculate the value of any cell. You can start from last 2 (rightmost) columns, and keep computing the table leftwards. So you have to store only 2 columns (current and previous), thus significantly reducing memory. That’s a good optimization. The resulting code will be too complex for an interview question though.

Fortunately, there is a better formula for coming up with an algorithm to calculate integer partitions. It is based on pentagonal numbers. But that’s a math question, not a programming question. I will explain that in another blog post.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Integer Partitions

Integer Partitioning is a standard problem that arises in many situations. If math is what you do, then perhaps you would classify this as a simple problem. For the rest of us, it's far from straightforward.

The basic problem can be stated as follows.

For any given positive integer N, in how many different ways can it be partitioned, that is, written as sum of smaller positive integers ?

Let's define the function P(N) as the number of integer partitions of N.

For example, 4 can be written in 5 different ways (partitions)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
4

So P(4) = 5.

Note that
1. Order of integers does not matter. So 1 + 4 is considered as the same partition as 4 + 1.
2. An integer can appear multiple times in a partition.

As is often the case, if you don't already know the trick, it's not easy to figure it out. For example, the first thing I tried was using induction, as in, can P(N+1) be expressed in terms of P(N)? I couldn't find any easy way to express it. Maybe there isn't a natural way.

The common trick in solving combinatorics problems is to use the principle of mutual exclusion. But how do I break the problem down to mutually exclusive smaller problems ? I couldn't find a way, so I gave up and surrendered myself to the all-knowing Wikipedia. Sure enough, the answer is there and this time the trick is to use an intermediate function.

Well that gave me the formula, but the explanation wasn't lucid enough on the Wikipedia page. So I decided to try to explain it in much simpler way.

It's a very nice trick and worth writing about.

Let's define another function - I am calling it partial partitions - PP(N,k) as the number of integer partitions, in which the smallest addend is at least k. It's important to note the language. The smallest addend doesn't have to be k, it can be more than k. In other words, no addend can be less than k.

For PP(4,2) we have 2 partitions in which every addend is equal or greater than 2
2 + 2
4
So PP(4,2) = 2.

For PP(4,3) and PP(4,4) we have just one same partition
4
So PP(4,4) = PP(4,3) = 1

Now, note that P(N) = PP(N,1). So if we can find a formula for PP(N,k), we will be able to determine P(N).

This neat trick of considering a more general problem, allows us to use the divide and conquer strategy. Now PP(N,k) can be divided into categories.

1. Where the smallest addend is exactly k. Let's call it PP(N,=k)
2. Where the smallest addend is strictly greater than k. Let's call it PP(N,>k).

It's easy to see that the second category is same as PP(N,k+1) because every addend must be strictly greater than k, so it's at least k+1.

What about the first category ? In this, every partition has to have k as an addend. There may be more than one addend equal to k. Since every partition has k, if we remove it, then we get partitions for N-k, and each of this partition satisfies the condition that no addend is less than k. This is PP(N-k,k). A diagram might help visualize this.

We must make sure that it is indeed the case that PP(N,=k) = PP(N-k,k) for all values of 1 <= k <= N for all integers N.

Consider a partition in PP(N,=k). As we have noticed already, removing the addend k, leaves us with a partition that adds up to N-k, with every addend >= k. Since we removed the same addend k, and every partition was different no two remaining partitions can be same. So we get proper set of distinct partitions. So PP(N,=k) must be a subset of PP(N-k,k).

Now let’s try from the other side. Consider PP(N-k,k). If we add the addend k to every partition, each partition will add up to N. Since we added the same term to each partition, they still remain distinct, so we have a proper set. Also, since we added the addend k to it, every partition of course has an element that's exactly k. So this PP(N-k, k) must be a subset of PP(N,=k).

Since PP(N-k,k) and PP(N,=k) are subsets of each other, they must be equal.

Combining all this together

PP(N,k) = PP(N,>k) + PP(N,=k) because of mutual exclusion
PP(N,k) = PP(N,k+1) + PP(N-k,k) as explained above

Now this is a recursive formula, so we need terminating conditions

PP(N,k) = 0 if k > N
PP(N,k) = 1 if k = N

To wrap up,

P(N) = PP(N,1) = PP(N-1, 1) + PP(N, 2)
That’s one pretty looking formula. In such recursive formulas, like partial derangement, both the terms reduce N and k to terminate the recursion. Here, one term reduces N, while other increases k. That’s got to put a smile on your face if you like recursion!

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Sum of consecutive primes

When I was in college there was a term for such kind of activities - “D!” - pronounced as “D not”. which was an acronym for “Dhandaa not” - meaning someone who has nothing better to do. The following can be classified as a pure "D!" activity!

The Problem 50 in Project Euler is stated as

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?

I had no idea that consecutive primes can be added to get another prime ! That’s simply beautiful.

Once you have a prime number generator, solving problems related to prime numbers becomes easier, if not easy. The best generator is of course the Sieve Of Eratosthenes, for which you can find the code here.

Using it, you can generate primes up to the required limit, and implement a brute force algorithm. Just have a loop iterating over the list of primes, and keep adding up all the primes starting from that position. The sum is prime if it exists in our list. Note it down and how many primes were added to get it. Keep only the sum that was generated using more number of primes than the last one.

Well, what’s the fun in doing only that ? So I just added a data structure to keep track of which primes can be generated by adding a set of consecutive primes, and if there are more than one set of consecutive primes that add up to a prime, keep a track of that as well. The results are fun to analyze.

It’s not that just 2 or 3 primes can be added to get another prime, some of the primes below 1 million, can be constructed by adding over 500 consecutive primes. More, some of these can be constructed using more than one list ! Astonishing.

The number 41, mentioned in the problem, can also be written as sum of a different set of consecutive primes, 41 = 11 + 13 + 17. That’s the only 2-digit prime that can be obtained via adding more than one set of consecutive primes.

So what other primes can be written as sum of more than 1 set of consecutive primes ? To save typing, I am going to define a new function SCP for “sum of consecutive primes”.

SCP(n) = the number of sets of consecutive primes that can be added to get n.
So SCP(41) = 2

There are many 3 digit primes that have SCP number more than 1. For example

983 = 23 + 29 + … + 89 + 97 (17 primes)
983 = 47 + 53 + … + 101 + 103 (13 primes)
So SCP(983) = 2.

There are no 3 digit primes with SCP = 3. But There are 2 primes with SCP number as 4.

311 = 11 + 13 + .. + 43 + 47 (11 primes)
311 = 31 + 37 + … +  53 + 59 (7 primes)
311 = 53 + 59 + 61 + 67 + 71
311 = 101 + 103 + 107

The other prime is 863.

On the other hand, the smallest prime with SCP number 3 is 1151.

The smallest prime with SCP number 5 is 34421.

34421 = 269 + 271 + … + 701 + 709 (71 primes)
34421 = 1429 + 1433 + … + 1567 + 1571 (23 primes)
34421 = 3793 + 3797 + … + 3851 + 3853 (9 primes)
34421 = 4889 + 4903 + … + 4933 + 4937 (7 primes)
34421 = 11467 + 11471 + 11483

Below one million, the largest prime with SCP number as 5 is 988321. One of the set of consecutive primes that add up to that number is

988321 = 113 + 127 + … + 3919 + 3923
This has a whopping 515 consecutive primes !

And it’s NOT the answer to the Project Euler problem. The SCP number for the answer is just 3.

Below 1 million, there is only one prime with SCP number as 6, and that is 442019.

442019 = 419 + 421 + … + 2617 + 2621 (301 primes)
442019 = 7529 + 7537 + … + 8011 + 8017 (57 primes)
442019 = 13229 + 13241 + … + 13553 + 13567 (33 primes)
442019 = 17569 + 17573 + … + 17791 + 17807 (25 primes)
442019 = 49069 + 49081 + … + 49139 + 49157 (9 primes)
442019 = 147331 + 147341 + 147347

That’s a special number. There is no prime below 1 million with SCP = 7.

What’s the point of all this ? Not much, except that prime numbers are fascinating. If you want to know more about the mathematical research done on them, I highly recommend reading Prime Obsession. Don’t let the topic turn you away from reading it. It’s a very easy book to read, and is enormous fun. I know that’s hard to believe, but it really is, and that’s why it’s one of my all time favorite books.

UPDATE : Added some more analysis in a follow-up post.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Anand-Morozevich 2007 Mexico WCC

Every true sports fan has his or her unforgettable moments, both happy and sad. I am no exception. From Cricket, Soccer, Tennis, Field Hockey, NFL etc and Chess. Yes, chess does that too. I often watch chess games live on the internet, and sometimes get goose bumps when my favorite player is playing an exciting, razor sharp position. Once in a while, there is simply a "Wow" moment, and it's etched in the memory forever.

This is from the Round 11 game of 2007 World Chess Championship in Mexico.Anand won the tournament to become the unified world chess champion. Later he successfully defended that title against Kramnik, Topalov and most recently Gelfand. He was at the height of his chess creativity in those years, which has sadly been absent from his recent play.

Let's first look at the position before the final move.

Morozevich has just played

55. ... Qe4

Position after Black's 55 ... Qe4

What would you do in this position ? White has 3 connected passed pawns that will net him a win easily, as long as the black queen can be neutralized. Right now, the black queen is attacking both the white knight and the e pawn. The pawn needs only 2 moves to become a queen, but just the rook alone is not enough of a support. So giving up the knight to protect the pawn may be risky. Giving up this advanced pawn, means a long hard struggle to queen the other 3 pawns. So what should be done ?

Before we look at Anand's brilliant trick, let's take a few steps back.

During the game following position arose.

Position after Black's 32. ... Rh4-h5

In this position, Morozevich indicated a desire to draw by repetition of moves. It's roughly even but unclear position. Anand could have accepted the draw and still kept a comfortable lead. But he decided to press on. White then went on to capture the queen side pawns, Black captured pawns on the king side.Eventually queens got exchanged. Morozevich had sacrificed his central pawns to gain tempo, and reached a position where he was guaranteed to get the queen. Still White is better.

Position after Black's 50. ...Kh7-h6

At this point Black is willing to sacrifice the bishop to get his queen. Anand played the following move. Later it became clear that he had calculated all the way till the end.

51. Rc4!

Position after White's 51. Rc4!

Game continued ...

51. ...  h3
52. Rxc5 h2
The race is getting closer, and there is nothing to stop black from getting his queen. My heart had started beating faster.

Position after Black's 52. ... h2

53. Ne3! blocks the rook from attacking the pawn
53. ... Ra1+

Position after Black's 53. ... Ra1+

This helps Black get his queen with a check.
54. Kxa1 h1Q+
55. Ka2 Qe4

This is the problem position mentioned earlier. I thought Morozevich's queen could be enough to prevent Anand from winning, and I was on the edge of my seat.

Now comes the knockout punch
56. Re5!

1-0
Black resigned.

Whit's e4 pawn is unstoppable now ! Because if
56. ... Qxe5
57. Ng4
forks the king and the queen.

As beautiful as 56. Re5! is, here is why it's great. Anand had seen this when he played 51.Rc4!, meaning he had seen the problem position in his mind, and solved it before even being played. So if you solved the puzzle, ask yourself, can you "see" it in your mind 4 moves before and solve it too ?

Anand played all his last 5-6 moved very fast. And when I saw the last rook move, it was the ultimate wow moment, forever etched in the memory.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Project Euler : Problem 49

If you want to challenge yourself at writing algorithms to solve mathematical problems, then Project Euler is a nice site for you. The problems have a wide range of difficulty. I found the problem 49 surprisingly rich in terms of strategies that can be employed to solve it.

The problem statement is :

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Unusual indeed. The numbers have to be prime and permutations of each other, and make up an arithmetic sequence.

Of course, there are many ways to solve the problem. One obvious candidate is use some sort of brute force approach. But what's the fun in doing that ? So I decided to try an efficient approach. I am sure there are many alternatives. The one I tried is as follows.

Note that there are 3 unusual properties. I used them to break the problem in 3 steps and wrote a small, efficient program for each step.

1. Generate Prime Numbers.
Obviously, if we inspect only the 4 digit prime numbers, it's going to reduce the problem space and speed up the solution. As long as generating prime numbers is not expensive. The standard textbook solution for this is to use "Sieve Of Eratosthenes", that offers a near linear algorithm to generate the prime numbers. You can find more explanation here. Using this program, we generate a list of 4-digit primes in ascending order.

2. Group the numbers that are permutations of each other
By treating the numbers as string of digits, we can compare any two numbers to check if they are permutations of each other. The brute force algorithm will have O(N^2) complexity. I wrote an algorithm with linear complexity that works especially well when the cardinality of alphabet set is not very high. You can find the algorithm here. With this step done, we have grouped together all the 4 digit primes that are permutations of each other. Since the original list of all the primes was already in sorted order, each group is also sorted in ascending order.

3. Find the arithmetic sequence
This is bit harder than the first 2 steps. Now, if you just want to examine a given sequence of numbers to decide if it is an arithmetic sequence, then that's very easy to do. But that's not what I wanted. I wanted to write an algorithm to find all the arithmetic sequences within a given sequence. Solving this more generic problem is NOT necessary to solve the Project Euler problem. Becase we are told that the sequence contains only 3 numbers. Moreover, we have already grouped the numbers based on permutations. So either the group is a desired sequence or not. That's simple to test. But if you were not given the problem specific information, then you have to find an arithmetic sequence within  a larger sequence. For example, I found a set of 11 primes that are permutations of each other. The entire set is not an arithmetic sequence. But a subset could have been. You can find the details of my solution to the generic problem here.

By connecting these steps, you can find the solution of the problem. On my MacBook Pro, it took less than one minute for my Java program to generate all the prime numbers, group them based on permutations and find the sequence.

Some interesting facts. There are 174 permutation groups within the 4 digit primes that have more than 3 members in it. For example
[3253, 5233, 5323] 
[6899, 8699, 8969, 9689] 
[2039, 2309, 2903, 3209, 9203].

The longest two have 11 primes in each !
[1237, 1327, 1723, 2137, 2371, 2713, 2731, 3217, 3271, 7213, 7321] 
[1279, 1297, 2179, 2719, 2791, 2917, 2971, 7129, 7219, 9127, 9721].

But none of these contain any sequences.

The most curious fact is not mentioned in the problem. The other prime permutaiton sequence, has exactly the same difference in it's terms, 3330 !! That means : The only 2 arithmetic sequences of 4 digit primes such that the numbers are permutations of each other, have exactly the same difference. The one was already given in the problem. The other one we have to find. Both sequences have the same difference, 3330. Really interesting.

The Project Euler guidelines suggest not to disclose the solution. It's OK to explain the strategy. Hence I have not given the solution here.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Astounding Optical Illusion

Who doesn't like optical illusions ? It's been a while since I have seen something new, and this is one of the best I have seen. (This is not a new illusion, it's a few years old. I saw it only recently).

Which square is the darker shade of gray ? A or B ?

Of course, since you know this is an illusion, let me just give you the answer. They both are same shades of gray ! Now that you know it, can you see it ?

That's what makes this such a great illusion. It's irritating, no matter how hard you try, your brain just refuses to accept that they are the same shade.

There are many ways to prove this.

1. Print the image. Cut a small piece from both the squares and lay them side by side.

2. Copy and paste the image into an image editor like PaintBrush. Cut a small piece from each and compare.

3. Use a color inspector utility : like the Digital Color Meter on Mac. Hover over the squares to make sure that the RGB values are the same for both.

4. See this interesting proof ! (Focus your eyes on B).

You have to take the colors out of the surrounding context to see the same shade. That's pretty much the only way.

This image is courtesy of Prof Edward Adelson. You can find many similar examples on his site.

Another equally astounding and my favorite from this collection is the Koffka Ring.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Sudoku Bragging :-)

I like Sudoku, but I didn't solve too many puzzles in the printed form. If you make a mistake in deciding a number for a square - especially at hard levels - it becomes too much pain to figure out later what went wrong and how to fix it. But the iPad app is the best way to solve Sudoku. If you make a mistake it immediately lets you know. It also allows you take notes and helps in visualization.

I have been using Sudoku2, and definitely recommend it. It has a nice point system, in addition to the timer, to keep you motivated :-) I am no longer addicted to it, as I was a few weeks ago. Mainly because, I have reached my limit in improving the score. So here is what I think is my peak score :

Can you beat it ? :-)

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Partial Derangement

As part of a bigger problem, I wanted to solve what I decided to call "Partial Derangement". This may be part of standard course material on Combinatorics, but I couldn't quickly find anything similar. So I gave it a try on my own. I may be reinventing a wheel here, but it was a fun challenge.

The problem is similar in nature to "derangement". In the derangement problem, we want to find out all such arrangements, which do not have any object in its correct place. Here the restriction is placed on only a few items. Say you want to find out arrangements of letters [A B X Y] such that A cannot be in first place, and B cannot be in second place. There is no restriction on X and Y .

For example, [B X Y A] is a valid arrangement. But [X B A Y] is not. Because here B is in its natural second place.

Let's modify the problem we looked at, while discussing "derangement".

Say M men and W women went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, all the men deliberately put on a wrong name tag on their shirts. No man had the right name tag. The women, on the other hand can put the right name tag if they want. In how many ways can they do it ?

Note how this is quite different from simple derangement discussed before. Here a man can put a woman's name tag to satisfy the requirement of the game. For every man, there are (M-1) * W valid choices. Whereas in a simple derangement, every man would have had only M-1 choices. In other words, this is NOT a derangement only within a subset. Hence the answer cannot be D(M) * W! where D(M) is number of derangements of a set of M objects.

This problem is a bit harder than derangement. But very similar logic can be applied to solve it. First, let's define what we want to solve for.

Let's define, PD (N, K) as the number of arrangements of N items, out of which particular K predefined objects cannot be in their correct place. Note that there are specific K objects, already identified to be deranged.

Think of N numbered balls (from 1..K..N) to be put in N numbered bins (from 1..K..N) . The task is to arrange N balls so that no ball numbered (1..K) is in the bin with the same number.

We will solve it using the similar reasoning style for derangement.

Pick a ball, numbered between (1..K) This ball i can either

A : Be put in any unrestricted bin, which is numbered (K+1..N) In this case, any bin can be used, there is no restriction. There are N-K choices for such a bin.

OR

B : Be put in a restricted bin from (1..K) There are K-1 choices here, as ball i cannot be put in bin i .

Let's examine each case in more detail now.

A : When the ball i is put in an unrestricted bin, we lose one unrestricted bin, of course. But now the corresponding bin i for this ball becomes unrestricted, as any ball can be put there without violating the rule. Meaning the number of unrestricted bins remains same, and the number of restricted bins is now one less. So after this placement, we have N-1 balls, with K-1 restricted bins. This is same as PD(N-1, K-1) . And since there are N-K choices for choosing an unrestricted bin, the sub-total of these arrangements is (N-K) * PD(N-1, K-1) .

B : This is where I am copying the logic used in finding derangement. Here ball i was placed in a restricted bin, from (1..K) . Since it cannot be placed in its own bin, there are K-1 choices for this. Let's say it was placed in bin j . Now let's decide a place for the ball j corresponding to that bin. There are 2 choices - it is either placed in bin i or it isn't.

B1 : It is placed in bin i . This effectively removes the pair i and j from the set. We are left with N-2 balls, to be placed in N-2 bins, out of which K-2 are restricted bins. This is same as PD(N-2, K-2) .

B2 : If ball j is not be placed in bin i, let's represent that restriction by simply renaming bin i to bin j. This leaves us with exactly the same problem, with one less ball. That is, we have N-1 balls, with K-1 restricted bins. This is nothing but PD(N-1, K-1) .

Since B1 and B2 are mutually exclusive, for every choice of bin for ball i we have 

PD(N-2, K-2) + PD(N-1, K-1) 

arrangements. Since there are K-1 choices for bins, the subtotal here is 

(K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) ) .

Since, A and B are mutually exclusive, let's add them to get the final answer.

PD(N, K)
= (N-K) * PD(N-1, K-1)
+ (K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) )
Note the term PD(N-1, K-1)is common in both. So after simplifying, we get a nice elegant formula
PD(N, K) = (N-1) * PD(N-1, K-1) + (K-1) * PD(N-2, K-2)

To use this formula, we have to have certain definitions, to avoid negative values. This is similar to saying 0! = 1 by definition, to terminate the recursion of formula  N! = N * (N-1)!

PD(0, 0) = 1 (by definition)
PD(N, 0) = N! (No restricted bins, so all arrangements are valid)

We require one last definition, and it needs some explanation.

PD(N, 1) = (N-1) * (N-1)!

Here we want to know how many arrangements are there, in which one specific ball is not in its corresponding bin. The total arrangements are of course N!. How many invalid arrangements are there ? To find out put the ball in its corresponding bin and arrange the rest of the N-1 balls. This is nothing but (N-1)!. So we have

PD(N, 1)
= N! - (N-1)!
= N*(N-1)! - (N-1)!
= (N-1) * (N-1)!

Let's do a couple of quick checks.

PD(1, 1) = (1-1) * 0! = 0
Obviously, there is no way to arrange just 1 ball with our restriction.
And
PD(2, 1) = (2-1) * 1! = 1
Correct, as there is only 1 way to arrange 2 balls with out restriction.

Let's also check if we are in agreement with full derangement.

PD(N, N) is full derangement - no ball in its corresponding bin, so this should be equal to D(N) .

Let's see. Using our formula,

PD(N, N) = (N-1) * PD(N-1, N-1) + (N-1) * PD(N-2, N-2)
= (N-1) * ( PD(N-1, N-1) + PD(N-2, N-2) )
= (N-1) * ( D(N-1) + D(N-2) ) (using induction)
= D(N)

This was definitely harder than derangement, but it was also much more fun to prove a more general result.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Derangement

"Derangement" is a counting problem that commonly occurs in many puzzles, probability questions etc. I wanted to solve another counting problem, that required building upon derangements. So I brushed up on combinatorics to find a quick formula for derangement. It was so elegant, that I had to put it up here.

Derangement is such an arrangement, that no object is in its correct place. For example, if you are to create a derangement of all letters in the alphabet (A .. Z), then such an arrangement should NOT have A at the first place, and B at the second place, and so on, till Z cannot be at 26th place. There is precisely one "forbidden" spot for every object.

As an example, consider only 3 letters [A B C]. The only possible derangements for these letters are [BCA, CAB].

The question is, in how many ways you can do this for N objects ? Let's use the notation for derangement as D(N). Obviously, D(N) < N!.

This problem can be phrased in different ways.

Say N people went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, they deliberately put on a wrong name tag on their shirts. No person had the right name tag. In how many ways can they do it ?
Answer : In D(N) ways.

Another one.

Start with 2 deck of cards. Shuffle each of them separately, and put it next to each other on a table. Start picking one card from the top of each deck, compare and discard. Keep doing it till all 52 pairs have been compared. What is the probability that not a single pair had same cards ?

Answer : D(52) / 52!. Favorable outcomes divided by total number of outcomes.

But what's the formula for calculating D(N) ? It's very elegant.

Think of N numbered balls (from 1..N) to be put in N numbered bins (from 1..N). The task is to arrange N balls so that no ball is in the bin with the same number.

Start with any ball i. It cannot be put in bin i, so there are N-1 ways to choose a bin. Let's say it was put in bin k. For every such choice, following is true. We examine ball k, whose bin was chosen for ball i.

1. Either ball k was put in bin i.

2. Or ball k was NOT put in bin i.

These are mutually exclusive choices. So we can find the count of ways each can be done, and sum them up for getting final answer for D(N).

First choice, ball k was put in bin i. Just remove, the pair bin i and k, with balls k and i in them respectively. That leaves us N-2 balls to be put in an derangement. Each having exactly one forbidden spot. This is nothing but D(N-2).

Second choice, ball k is NOT to be put in bin i. Remove the bin k (with ball i in it). And rename the bin i to bin k, as the ball k is NOT to be put in it. That leaves with N-1 balls to be put in derangement. Each having exactly one forbidden choice. This is nothing but D(N-1).

So for every choice of k, there are D(N-1) + D(N-2) possible number of derangements. Since there are (N-1) choices for k, the formula is

D(N) = (N-1) * ( D(N-1) + D(N-2) )

This formula is very similar to Fibonacci numbers ! But the multiplication makes it grow really faster than Fibonacci sequence.

By defining D(0) = 1 and noting that D(1) = 0, we can calculate all derangements. For numbers up to 10, they turn out to be

D(2) = 1
D(3) = 2
D(4) = 9
D(5) = 44
D(6) = 265
D(7) = 1854
D(8) = 14833
D(9) = 133496
D(10) = 1334961

The math textbooks will also show another result that makes this even more beautiful.

The limit of (N!)/ D(N)  as  N  approaches infinity is the number
e (= 2.7182816576664037...).
This means, the answer to our probability question is very close to
1/e (= 0.367879464285714...).

I will be building on this in another problems soon.

UPDATE : See the solution to Partial Derangement which builds on this post.

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest