The BullsNCows Application in AngularJS

About 5 years back, when I was still dabbling with client-side technologies for the first time, I had written the BullsNCows game in pure Javascript.

My knowledge of Javascript and client side technologies has evolved quite a bit since then. So, recently when I was looking at this code I thought, “This code could be better if we use AngularJS“.

So today I thought of rewriting this in AngularJS and using Bootstrap for styling. Here is the code in Github in case you want to play with it and here is the game in case you want to play.

bullsncows

So what’s changed?

  • All the code related to styling has been moved to Bootstrap. The alternate table coloring seems so much easier now!
  • The update of the table is done with AngularJS so I don’t need to do complex DOM manipulation – it is a straight-forward binding to the tr element of the table.
  • The data handling and algorithm to compute bulls and cows is slightly improved. It used to be a O(n^2) algorithm. It’s now linear.
  • Elimination of globals – except the app object nothing is global now.

Bulls and cows and the Javascript challenge

About 2 years back, I had conducted an experiment with the Bulls and Cows game[1] [2]. I now wanted to see what the 'human average' for the game is. So I wanted to build a small Facebook application to add the social aspect to the game and conduct my experiments.

But before I continued, I had to solve a major problem.

If I continue to make it a Javascript game, as is hosted here, I need to ensure that the random number generated by the browser is secure and not manipulated or found out by the player using illegal ways.

Anyone who knows a bit of Javascript and is used to looking at code using Firebug will soon be able to 'guess' the number in one step:

Yeah, that's right. I store the random number generated in a variable randomNo. And you can find out the value using Firebug. Now this is fine, as long as it is not a competition and you play the game because you actually like it and not because you are winning a million dollars. But what if this game was being played for money?

So my next attempt was to think of storing a MD5 of the number and then match it with the MD5 of the number entered by the player. This works well as long as the random number is generated on the server side and only the MD5 is sent to the client.

Can the random number and its MD5 be generated on the client side without the user being able to 'debug' and get the random number?

My first attempt towards this was the following piece of code:

function getRandomNo(){
        var md5OfRandomNo = MD5(Math.floor(Math.random()*10001)+'');
	return md5OfRandomNo;
}

But unfortunately:

and you step into the function and:

🙁

Right now, I am still not able to find a fool-proof way to generate the random number on the client side. Is there a solution?

Ok, let's say the number is securely generated in some way (client or server) and we only store the MD5 value on the client. Now, there is a second problem:

What if the player just changes the random number altogether?

>>> randomNo
"948f847055c6bf156997ce9fb59919be"
>>> randomNo = MD5('7839')
"ca91c5464e73d3066825362c3093a45f"

We need to maintain a session and include some verification code to ensure that the MD5 was not manipulated.

Is there a solution for this if we want to write the entire game using only Javascript? Are there any other issues other than the 2 described?

Bulls and cows – computer simulation results

Context:
My experiments with Javascript – The Bulls and Cows Game
The bulls and cows game

I started off writing the Bulls and Cows game just to pass time when I am bored, but soon it turned out to be an interesting mathematical problem. Also thanks to for the interest shown.

I continued my experiments yesterday. I started off by writing a small function that analyzes the already entered numbers and gives the list of possible numbers that can match all the criteria (in the previously entered numbers) and be a possible solution. This was supposed to be a hint to the user.

I saw that the list of possible solutions diminishes as the user enters more and more numbers (this is quite obvious, but I want to make it clear). In order to assist the user to select the next number, I created a weighted system (explained later) that gives the user the most probable solution.

This finally led to the simulation of an environment, where player 'A' thinks of a number and player 'B' tries to guess it, both player 'A' and 'B' being computer controlled. (Computers are so dumb that a single program can contain both player 'A' and 'B' without them knowing about each other 🙂 )

I ran the simulation for each and every possible number (1 to 9999) and guess what? With some tweaks, the computer is able to find the solution in an average of 6 steps. The maximum steps it requires is 10.

Here is a graph showing the result:

The algorithm that I wrote is as follows:
1. Player 'A' thinks of a number.
2. Player 'B' starts of with number 1234 as the first try and player 'A' responds with the number of bulls and cows in the number. (I haven't tried other numbers, but I guess it will give similar results)
3. Player 'B' tries to find out the set of solutions that can match each of the previous steps.
4. 'B' then finds out how many times each digit occurs in the list of possible solutions. These form the weights of the digits.
5. Using this, 'B' computes a weight for each possible solution as folows:
If 'abcd' is a possible solution and the digits 'a','b','c','d' have weights 'p','q','r','s' respectively, then weight of 'abcd' is 'p'+'q'+'r'+'s', such that 'a','b','c','d' are distinct. If they are not distinct, then each digit is considered only once to compute the weight -> (This is the tweak I had to apply).
6. 'B' then finds the number with the highest weight and uses this as the next step.
7. Repeat Steps 3 – 6 until you get the solution.

I ran this simulation for all the numbers from 1 – 9999 and got the following results:
Algorithm 1 result sheet.
It took me about 20 minutes to run the simulation in my system (an average of about 10 games per second).

I am not sure if this is the best solution, but there are learnings from this:
* It is possible for a computer to find out a solution in an average of 6 steps or less.
* The maximum number of steps required to arrive at a solution is 10 or less.

Please note that the algorithm was not tested (i.e. I am not sure if it works exactly as I have mentioned it here), but the answers it provides and the steps have been authenticated.

Is there any better solution?