Google Code Jam: Mousetrap in 4 languages - GAME OVER

First of all, I would like to thank the Google team for Code Jam opportunity, and its organization: AMAZING!

Yesterday I have lost my Round without a single commit.
This time I have not excuses, it was simply my fault.
I did not understand properly first two problems, or better, expected results, but I was sure the reason was my poor English knowledge, and I wouldn't be silly, asking silly questions (some question was silly enough, so, next time, I'll be less shy than this time).

Accordingly, since Code Jam is a challenge, I chose to solve the most difficult problem, the Mousetrap. First of all, because the problem, and the expected result, was so simple to understand, secondly, because it was the best one for points :geek:

Problem Analysis

Ok, we had 2 hours to analyse the problem, to find the best solution, and to commit results, and this time I did not even download the test, because I would like to be sure that my solution was good enough to solve the problem.

Count positions ... no, don't do it, count movements, no, do not count at all!

My first 3 versions of Mousetrap were so tricky, that no one worked as expected :D
After about one hour trying to find the perfect algorithm to know where each card has to be during the game, I realized that I was trying to solve them in a complex way (a sort of home made equation), and without results, instead of simply think exactly what was going on in the deck during the game.
Anyway, I wasn't able to finish the code, specially because my "perfect solution" was trying to destroy my CPU! So, honestly, for my brain and my knowledge, time was not enough to complete that task.

Brainstorming

My approach was simple: create the perfect deck!
Once we have a perfect deck, find positions is something extremely simple, since each number is, at the begin, a deck index itself minus 1 (i.e. 1,2,3,4,5 as indexes: 0,1,2,3,4), so once you have moved each card over indexes, you can find card positions simply using created array.

card = "5"
result[(int)card - 1] = ... moved card.

At this point, we need to create the deck, and nothing else.
The first version was based on movements, and removed cards, to know the position of each card in that index. A sort of tracing, using a simple function like this one:

function movements(card){
    return 0 < card ? card + movements(card - 1) : 0;
}

In this way we can know that when we are looking for card N, we have removed N-1 cards beforfe, and moved movments(N-1) time other cards.
This was probably the right direction, but it was exponential, and results completely wrong ... and snce we had 2 hours, I though to change strategy.

The most simple, logical, and expensive solution at all

Try to imagine we have 5 cards, so the deck will be: 1,2,3,4,5
The sequence, during the game, will be this one:

12345 [card = 1, pos 1]
2345  // remove one, and count fr next card
3452  [card = 2, pos 3]
452   // remove one, and count for next card
524   // counting ...
245   [card = 3, pos 2]
45    // remove one ... 
54    // counting ...
45    // counting ...
54    [card = 4, pos 5]
4     // counting ...
4     // counting ...
4     // counting ...
4     // counting ...
4     [card = 5, pos 4]

Above operation is exponential as well, but in my mind it was the best one ever to be sure about the result. That is why I started to play the game!

Mousetrap with JavaScript

When I realized that in that simple way the code was truly slim, I though about 2 possibilities: 1 - I am a f#*@in genius, 2 - There is something wrong, it cannot be that simple, I am an idiot!
Once I have created the code:

// JavaScript
function perfectDeck(cards){
    for(var
        deck    = range(cards),
        result  = range(cards),
        count   = 0,
        i       = 0;
        i < cards; i++
    ){
        while(count++ !== i)
            deck.push(deck.shift()); // move cards
        result[deck.shift()] = count;// remove one
        count = 0;                   // start counter again
    };
    return  result;
};

// JavaScript Extra
function    range(length){ // return an array with 1:1 index/value integers
    for(var i = 0, result = new Array(length); i < length; i++)
        result[i] = i;
    return  result;
};

// example
alert(perfectDeck(5))
// 1,3,2,5,4

I did some test, and I checked results in my minds, and those were expected. Well done?

Mousetrap, PHP implementation

At this point, I need to parse the input file, and to produce an output file.
Since the code was extremely simple, I have though about PHP, to be able to read the input, and produce the output to upload.

function perfectDeck($cards){
    for(
        $deck   = range(0, $cards - 1),
        $result = range(0, $cards - 1),
        $count  = 0,
        $i      = 0;
        $i < $cards; $i++
    ){
        while($count++ !== $i)
            array_push($deck, array_shift($deck));
        $result[array_shift($deck)] = $count;
        $count  = 0;
    }
    return  $result;
}

Damn it, literally 1 minute to create my PHP perfectDeck version.
Now, lets do some test to be sure everything is correct ... ok, that's correct.
At this time, I read the problem again, and I realized that I was debugging with 3, 4, 5 or 7 cards, thinking that a deck could not have more than 15 cards (poker addicted!) ... well, things are a bit different, since limits are clear, and we are talking about a maximum of 5000 cards, and for the small input!!! :o

Python version

Since trying to generate the perfect deck with PHP, and 2500 cards, was extremely slow, I though that I could try to use another language, maybe faster, thanks to Psyco module.

from psyco import full
full()

// Python
def perfectDeck(cards):
    deck    = range(cards)
    result  = range(cards)
    count   = 0
    i       = 0
    while i < cards:
        while count != i:
            deck.append(deck[0])
            deck    = deck[1:]
            count   = count + 1
        result[deck[0]] = count + 1
        deck    = deck[1:]
        count   = 0
        i       = i + 1
    return  result

Of course, in this case Psyco cannot help that much, since the most expensive operation is with the deck, and not with math.

Need for speed, C# Mousetrap

As last chance, and since the code was producing expected results, I though about fixed Arrays, without a single scriptish operation.
Instinctively, I opened my visual C# Express Edition, instead of Dev C++ to create a C version ... maybe because it's long time I am not using them, but anyway, I know that using fixed length arrays I should not have speed problems at all.

// C# with fixed lengths
static int[] perfectDeck(int cards){
    int[]   deck    = range(cards),
            result  = range(cards);
    for(int i = 0, count = 0; i < cards; i++){
        while (count++ != i)
            move(ref deck);
        result[deck[0]] = count;
        deck = shift(deck);
        count = 0;
    }
    return  result;
}

// C# with fixed lengths - Extra
static int[] range(int Length){
    int[]   result = new int[Length];
    for (int i = 0; i < Length; i++)
        result[i] = i;
    return result;
}

static int[] shift(int[] deck){
    int     i       = 0,
            Length  = deck.Length - 1;
    int[]   result = new int[Length];
    for (; i < Length; i++)
        result[i] = deck[i + 1];
    return  result;
}

static void move(ref int[] deck){
    int     last = deck[0],
            i = 1,
            Length = deck.Length;
    while (i < Length)
        deck[i - 1] = deck[i++];
    deck[i - 1] = last;
}

Good enough? NO WAY, speed is more close to Python than C, so I promised myself that next version of perfectDeck function will be written in C.
At the same time, it will never be enough fast, because big input as these limits:

T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K

This means that my code will perform a factorial 1000000 changes, so honestly, the next step, will be to download some code from the competition, and learn which algorithm is the most clever and simple, to perform this task, in my mind, and in my implementation, completely mechanical.

Conclusion

I like challenges, and this one was amazing. I have learned at least these things yesterday, and I hope next year, I'll be more prepared:

• Code Jam is fantastic!


• Do not choose the most difficult task only to be in the top 100, but read in every case all of them before you start to write a single line of code


• Do not use mechanical procedures, but think about efficient algorithms


• Do not focus in a code, that for more than 2 times produced wrong results, or simply it is too slow, because it means there is something wrong in the logic, or in the algorithm


• Go back to school, because even if you are a senior programmer, you do not work for the N.A.S.A. and you do not deal, daily, with algebra, math, geometry, and related stuff

If you are still reading, thank you too, I only would like to share my Google Code Experience, and my perfect costly nightmare Mousetrap solution.

Kind Regards