Cracking Codechef hard problems - Python

In this blog post, i will be discussing about the hard problems at Codechef.com and how to handle them effectively using Python. This is going to be a "learn by example" post.

So, let's begin.

Consider the Orders Problem. The problem is big, and i am not going to post it anywhere here.

Now, at one go, you might find it easy, but as you start off with pen and paper, things go a little complicated. A close look will reveal that this is one of the most common sorting technique. Yes, it is Insertion Sorting, that is being done by Sgt Johnny. Let's analyze how.

The pseudocode for insertion sort goes as follows:

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i-1;
        while j ≥ 0 and A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j-1;
        end;
        A[j+1] := value;
    end;
end;

What we have to do is the opposite of it. We have the sorted list, we have partially the steps covered by each soldier, now we need to find the unsorted list.

Proceeding with the sample input/output given at Orders Problem, we do the following

Input -    0   [1]    0
position - 1st 2nd 3rd

Now move the 2nd soldier 1 place to the left. This is our first iteration. So, at the end of first iteration, we have the following

Position -       2nd  1st  3rd
Modified Input - 1    0    [0]

Next, we will see if there are any further iterations possible. So, we move onto next position in modified input and find that it is 0. This means that the 3rd soldier will not move from it's place. Now, since there are no more iterations that can be done, we arrive at the position being

2 1 3

which is the solution to the problem.

See if it works good for second sample too. The input is

0 1 2 0 1

So, placing the list in a nice format it becomes. This is iteration 0 (no iteration at all)

Input   -  0   1   2   0   1
Soldier - 1st 2nd 3rd 4th 5th

Scan the input from left. See, if there is any non-zero value. Yes, we get a non zero value (1). So, now move the 2nd soldier 1 position left. This is our iteration 1. Note that the first iteration was performed at 2nd element of the Input array. This is important, so that we can start our 2nd iteration at the third element.

At the end of 1st iteration::
MInput -   1   0   2   0   1
Soldier - 2nd 1st 3rd 4th 5th

The third element in MInput (Modified Input) is 2. So, we move the 3rd soldier to two steps on its left. This is what we get at the end of second iteration

MInput -  2   1   0   0   1
Soldier - 3rd 2nd 1st 4th 5th

Is there any scope for further iteration? yes, there is ! So, at the end of third iteration, we get something like

Minput -   2   1   0   1   0
Soldier - 3rd 2nd 1st 5th 4th

Now there is no scope for iterations, and hence we stop and end up with the original list as

3 2 1 5 4

Creating the code
When it comes to programming languages, i am comfortable with only one language - Python. So, i will be posting the code in Python only. Hard luck Java guys :-)

def SgtJohnnySort(il):
"""Follows the reverse Sgt Johnny Sort and displays the original
unsorted list.
il = input list ex: 0 1 2 0 1
sl = the sorted list; which gradually becomes the unsorted list
"""
    n = len(il)
    sl = range(1, n+1)
    last_moved = 0
    for i in range(last_moved, n):
        if il[i] != 0:
            el = sl[i]
            sl.remove(el)
            sl.insert(i - il[i], el)            
            el = il[i]
            il.remove(el)
            il.insert(i-1, el)
            last_moved = i
    return sl

In my opinion, this should work. However, i tried this on Codechef, and i could get some runtime error which i am unable to understand. While i am trying to figure out the runtime error, why don't you have a look at above code and notify if something is wrong :-)