Sunday, July 27, 2008

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

6 comments:

alsanan said...

I've solved both A and B as seen here but the complexity of the data sets has made impossible to get the results.

Congratulations anyway. May be some more examples would help to understand the problems.

Andrea Giammarchi said...

Thank you Alsanan, and congratulations to you too.

I am sure I have solved the problem, but speed was not enough (about half an hour to parse the small input with C# and my poor PC).

At the same time, this is the reson I am sure I used the wrong procedure as well, since it costs too much for every kind of CPU / processor.

Factorial switches are the main limit of my code, and I am sure there is a truly simple way to perform N switches with a single operation, that will bring Mousetrap execution close to zero.

I would like to find them, but at the same time I have to admit that for me, in two hours, I am not that clever to solve in a correct way, test results, and commit them.

So Google Code Jam is not for me, and I will follow next week problems too, and try to solve them in two hours, for a personal challenge (but I am sure, I will not be able to do that)

Kind Regards

Miguel Sánchez said...

Same experience here. I'm glad I have participated in Code Jam 2008 till round 1. I do too think the problems and the organization was good (though the time frames do not always fit my time zone nicely, I guess there is not a global optimum solution for this).

I've failed to create a fast enough solution for Ugly Numbers. As you said, my procedural approach worked in theory but it was too slow.

Other people however came up with a better (and faster) idea. Those continue the game :-)

Andrea Giammarchi said...

Miguel, this is absolutely true, other guys have been more clever than us :)

Somebody was so smart that was able to commit all of them, 3 problems, finding directly a fast way to solve the problem.

The main difference I have spotted between their code and mine, for example, is that as was for the qualification, I simply though about a "universal solution" able to solve the problem, and not about an algorithm that is able to get quickly only "that" index.

At the same time, usage of bitwise operators, and other algos, is something I could not think at all in two hours, so that is why I would like to say good luck to every other developer, but before, I have to say Good stuff guys! :)

Anonymous said...

I finally solved it using binary tree. Counting to find the space to create perfect deck is fine, but normal counting is O(n^2). To solve this issue, I use binary tree to do partitioning of the available space. This would help reduce to O(n log n), which is feasible for large set.

Andrea Giammarchi said...

Well done, that's why I am not good for GCJ, I use different stuff every day, and think about a binary tree or log something is not my daily tasks, while somebody solved all problems in two hours: respect!

Anyway, the next post shows my poor solution, implemented in a better C language, the fifth one :D

Fast enough to solve up to 5000 cards deck, not enough, as you said, for large data set.

Kind Regards