We lost humblefool this week in a car accident , he was a great coder(The first Indian who became red on Topcoder) he was excellent at coding and a nice person as well .It hurts a lot when a great person dies may God rest his soul in peace.
This week I was increasing my mathematical knowledge . Learnt many concepts regarding game theory especially Nim game after going through the rules of the game I came up with my own style to solve the game for ex - this game is played between two players A & B . On each turn the person will subtract a number given in the set lets say S = {1,4,5} from a given number N until we get a Zero the person which will not be able to subtract from the no. he gets will be the loser . N will be our starting number from which we will subtract 1,4 or 5 so that the player subtracting will win. Like every other player both A & B will try thier best to win this game so they will play optimally .'Optimally' in the sense that they will try some maths in their head to come up with the best solution i,e. to subtract which no. so they will win .
I came up with an idea like lets create a function for this game
P(N)
{
if (N =1 or N=4 or N=5) return 1(denoting win with 1)
else if(N=0 or N=2) return 0 (denoting loss with 0)
else return ( P(N-1) or P(N-4) or P(N-5) )
}
As we can clearly see if a person gets 1,4 or 5 he can directly subtract 1,4 or 5 from the no. he gets to arrive at zero and thus the other player won't be able to subtract any no. from a zero.
so in first if statement 1,4 and 5 are returning a WIN
for N=0 the first player won't be able to subtract any number so he will lose .For N=2 we can see that the person will be left with only one choice i.e. to subtract 1 from it so the 2nd player will arrive at N-1=1 so he will also subtract 1 from it thus arriving at Zero so that will be a loss for the first player so we return LOSS on 0 and 2
For rest no. I am taking OR from all the possibilities of subtracting 1,4,5 because if we get a 1 from any of these possibilities this will mean that the player will choose the winning move (Well that is the meaning of playing optimally).
So this function will give us the right result for this game.
We can optimize our function by memoizing our results using an array like we do in top up approach of Dynamic Programming ... that will save us a lot of time ..
Today morning I understood how to implement the Sieve of Erastonethes.That was amazing algorithm .
It was efficient O(NloglogN) as well as simple by logic Enjoyed implementing it.
I'll be increasing my maths knowledge as maths skills are very handy while programming.They can simplify one's code to a very large extent thus one just can't ignore maths while coding.
Thanks for reading.
