Jin Lee

I just learned that you can define properties in JavaScript like in c# in ECMAScript5 standard.

How interesting?

What does the BitVector32 class do?

BitVector32 is a wrapper (or you can call it abstraction) around c#'s bit operations. For example, the following two statements return the same result:

1 << 1

BitVector32.CreateMask(1)

Let's say there is an integer array containing some duplicate numbers. We want to find all duplicates. Of course, You can simply use the GroupBy function in Linq but let's pretend we don't have Linq.

The first option is brute force approach where each element will be compared against every element in the given array:

foreach(int i in list) { foreach(int j in list) { if (i == j) { // print this or store it in the result list } } }

Since the brute force approach will result in N square running time, which is pretty inefficient, we can think of utilizing HashSet which will provide a constant lookup time or O(1)

HashSet hashSet = new HashSet(); foreach(int i in list) { if (hashSet.Contains(i)) { // print the duplicate or add it to the result list } else { hashSet.Add(i); } }

This approach will result in the linear running time or O(n). However, it requires extra memory of n * 4 bytes (assuming we're talking about the 32 bit integer)

The third approach is similar to using a hashset except it requires less memory by using a boolean array

bool[] masks = new bool[maxNumber]; for (int i = 0; i < list.length; i++) { if (masks[list[i]]) { // print or add to the result list } else { masks[list[i]] = true; } }

it uses an boolean array instead of an HashSet. It has the same run time which is O(n) but requires 1/4th amount of the memory since the bool type takes up 1 byte (8bits) while integer takes up 4 bytes (32 bits)

Finally, we can solve this problem using the BitVector32 class or the native bit shifting operations.

int check = 0; for (int i=0; i < list.Length; i++) { int mask = 1 << list[i]; if (check & mask == mask) { // print or add list[i] to the result list } else { check = check | mask; } }

It will also result in a linear run time with only 32 bits of memory in total. So the memory usage is n/32. Of course, this is not going to work if the max value in the array is greater than 32. We can use 64 bit unsigned integer to increase the number of slots in the mask but it still has a very short limit. In that case, if you create an array of BitVectory32 and you can shift the bit to the BitVector32 object in the next index of the array. For instance, the code will go something like below

BitVector32[] bitVectorArray = new BitVector32[list.Length / 32]; bitVectorArray[list[i] / 32] = 1 << list[i] % 32;

This way, you don't have to be limited to the 32 bit size limit. You can grow the size of the big mask indefinitely as long as the memory capacity allows. So, put everything together:

BitVector32[] bitVectorArray = new BitVector32[maxNumber / 32]; for (int i=0; i < list.Length; i++) { int mask = 1 << list[i] % 32; if (bitVectorArray[list[i] / 32][list[i] % 32] & mask == mask) { // print or add list[i] to the result list } else { bitVectorArray[list[i] / 32] = bitVectorArray[list[i] / 32] | mask; } }

Conclusion

Draw something

Draw something is one game I really enjoy playing and don’t feel guilty wasting my time with. That said, occasionally, I have no clues what my friends drew for me which drives me insane. To be honest, I had to visit a cheat site a couple of times. I know it defeats the purpose of the game not to mention it’s not honest but I needed coins to buy more colors, desperately :).

Cheat

Cheat sites ask you to provide two things:

Letters 

The number of letters that make up the answer

and generates all possible combinations of the given letters that can form an English word.

Permutations and word validation

You need to do two things. 

Generate all possible permutations

Filter out permutations that are not English words

String permutation in javascript

Below is a Javascript I wrote to generate all possible permutations within the given length. It took me a while to get this right (and I am still a rookie in javascript world). 

results is an array to store permutations

input is a string from which you pick letters

output is an array that stores a single permutation

used is an array that stores flags to mark used letters

size is integer to pass the length of the word. i.e. size is 4 of the word jean

level is an integer to track the permutation is complete

var permutate = (function() { var results = []; function doPermute(input, output, used, size, level) { if (size == level) { var word = output.join(''); results.push(word); return; } level++; for (var i = 0; i < input.length; i++) { if (used[i]) { continue; } used[i] = true; output.push(input[i]); doPermute(input, output, used, size, level); used[i] = false; output.pop(); } } return { getPermutations: function(input, size) { var chars = input.split(''); var output = []; var used = new Array(chars.length); doPermute(chars, output, used, size, 0); return results; } } })();

Here is the working example on jsfiddle http://jsfiddle.net/jinwolf/Ek4N5/29/

Here are some patterns I used in the example

Singleton pattern

I used the typical Javascript singleton pattern.

Immediate instantiation

by putting parenthesis around the function, the function gets executed immediately and the permutate variable gets instantiated without an extra explicit invokation of the function. 

Closures

The permute object still has access to the private variable results andthe private method doPermute even though it’s been already returned from the main function. It’s called closure in Javascript

Visualize how it works

There is no tree style data structure in this algorithm but if you look at how it builds a permutation, it looks very similar to how Preorder Traversal works in a tree data structure. In other words, it starts from the element itself and moves down to the most left descendant. It keeps drilling down the path until it hits the bottom. Once it reaches the end of the tree, it moves to the right sibling at the same level. After all siblings are visited, it moves up one level and moves to the right sibling. And it keeps doing it until every element in the tree is visited

it starts from ‘a’ (level 1)

it moves one level down and visits ‘b’, skipping ‘a’ since it’s already taken (level 2)

it move one level down and visit ‘c’ skipping ‘a’ and ‘b’ (level 3)

‘c’ is the bottom of the tree and there is no siblings left at that level (level 3)

it moves up one level (level 2)

it visit ‘c’ which is the next sibling of ‘b’ (level 2)

it move one level down and visit ‘b’ skipping ‘a’ and ‘c’ since they are taken (level 3)

no siblings left on level 3 so it moves up one level (level 2)

Again, there is no siblings left on level 2 so it moves up one level (level 1)

Moves to the next sibling ‘b’ on level 1 which is not shown here (level 1)

Repeats the same process

Fibonacci example

The below example calculates the 20th element of Fibonacci series. The code takes top-down and recursive approach. But it's only a demo purpose. Bottom up and iterative approach is a lot more efficient in this case.

function getFib(n) { if (n == 0) return 0; if (n == 1) return 1; return getFib(n - 1) + getFib(n - 2); }

This algorithm returns the correct result which is 6765, however, the getFib method gets called 21891 times which is highly inefficient in terms of runtime and memory. And the number of the method call increases exponentially. In other words, this algorithm is not scalable for a large input. This is a typical issue with recursive functions.

Look at the second example. It uses a technique called "memoization" or you can simply call it "caching"

// Cache (Memoization) the result to avoid overlapping sub-problems var cache = new Array(); cache[0] = 0; cache[1] = 1; function getFibWithCaching(n) { if (cache.hasOwnProperty(n)) { return cache[n]; } cache[n] = getFibWithCaching(n - 1) + getFibWithCaching(n - 2); return cache[n]; }

In this example, the number of the function call has been reduced down to 39 which is about the double size of the input. And the number of the function calls increase lineally. 

Overlapping sub-problems

The first example contains lots overlapping sub-problems. So the memoization allows you to avoid re-processing the same subroutine, instead it grabs the result from the cache.

Iterative approach is much better

Lastly, below is an iterative version which is most space efficient

I think bit shifting is one of those things you learn at college and never use once in your life at work. Well, it might not be true for some people, it's been pretty much the case for me.

I came across some interesting code example where bit shifting is kind of useful as an alternative to the hash table which I

would normally use to find the intersection between two datasets. Let's say we want to create a method that checks if the given string has duplicate characters in it.

bool HasDuplicateChars(string anyString) { // TODO: return true if there are duplicate chars // otherwise false; }

Well, since I am a C# programmer, I will go like this in a sec.

bool HasDuplicateChars(string anyString) { return anyString.Distinct().Count() != anyString.Length; }

The end of the story. It exactly takes one line of code and I stop thinking from this point.

Don't get me wrong. I am a big fan of Linq and I love the high level of abstraction it brings to C# so you can write code in 4GL style. That said, the most fun part of the programming is in the intimate details of how things work which I don't want to miss either.

One simple approach to find a duplicate character within the string is to compare the every character against the every character in the string one by one.

bool HasDuplicateChars(string anyString) { char[] charArray = anyString.ToCharArray(); foreach (char c1 in charArray) { foreach(char c2 in charArray) { if (c1 == c2) { return true; } } } return false; }

It's probably the most straight forward solution and does not require extra storage but definitely not the most efficient one. The worst case senario is n * n, n square times of iterations, which can be pretty large if the string size is big (like 100 * 100 = 10,000).

Instead, we can leverage a data structure like the hash table to make it more efficient.

bool HasDuplicateChars(string anyString) { HashSet charHashTable = new HashSet(); foreach (char c in anyString.ToCharArray()) { if (charHashTable.Contains(c)) { return true; } else { charHashTable.Add(c); } } return false; }

The worst case senario here is n. So if the string length is 100, it takes 100 loops in the worst case senario. So it's much better than the previous one. However, it requires extra memory for the HashSet object.

Note that the "Contains" method is highly efficient since it does not perform any  type of searching. Instead, it uses the hash function to determine if the key exists in the table. So the lookup time is always the constant 1.

Now here is a little tricky one but maybe the most fun one, bit shifting. The code below shows how you can use bit shifting to accomplish the same task (in a hard way)

bool HasDuplicateChars(string anyString) { if (anyString.Length > 26) { return true; } UInt32 board = 0; UInt32 check = 1; for (int i = 0; i < length; i++) { int shiftCount = anyString[i] - 'A'; if ((board & (check << shiftCount)) > 0) { return return; } board |= (check << shiftCount); } return false; }

This example assumes the input characters are all ASCII and range only between 'A' and 'B'. The code above basically uses each bit of the 32 bit unsigned integer as place holders. I could just choose the signed 32 bit integer. The signed integer uses the most left bit to hold "+" or "-" so the bits that you can actually use are 31. But it does not matter in this case. I restricted the input to 26 chars which is small enough to be held in 31 bits.

Let's say you have a byte which has 8 bits which means you have 8 place holders to store 0 or 1. So you can turn each bit on or off like a switch. As an example, let's say the bye looks like this: 

0 0 0 0 0 0 0 1

if you shift a bit to the left by 1, it will look like this

0 0 0 0 0 0 1 0

C# has bit shift operators. "<<" and ">>". Using the two operators, you can shift the bit back and forth respectively.

if you have 16 bit signed integer of which value is 1 and if you shift the bit to the left 16 times, you will see the number turns to the negative all of a sudden. That puzzled me for a minute and realized that the most left bit indicates the number is minus, which was interesting to know. So if I use an unsigned 16 bit integer, I won't have the same issue since the most left bit is just another bit.

Back to the example, if I apply the "&" operator between the first and second byte.

0 0 0 0 0 0 0 1 & 0 0 0 0 0 0 1 0  = 0 0 0 0 0 0 0 0

since there are no intersections between those two. For "|", the result becomes

0 0 0 0 0 0 1 1

So from this, we can use this to check the duplicate chars.

anyString[i] - 'A' will give me the offset in the ASCII table and I can use the offset as the index of the bit place holder. As an example, if anyString[0] == 'A', the offset is 0 and I shift the first bit "0" times to the left which means the number remains the same. The next char is 'B' and the offset is 2 and I shift the bit 2 times to the left so the number will be:

0 0 0 0 0 0 1 0

This code: checker |= (matcher << val) combines the two result using "|" operator and the result becomes

0 0 0 0 0 0 1 1 

So far there are no duplicates. Let's  say third char is 'A' again, a duplicate char. I shift 0 times and the result is:

0 0 0 0 0 0 0 1

so for this code: if ((checker & (matcher << val)) > 0) returns true since

the result is 

0 0 0 0 0 0 0 1

So it's pretty good in terms of lookup times and space usage. The big O notation of the algorithm is O(n) where the best case senario is 2 and the worst is N. 

The Linq can save a lot of lines of your code. But the beauty of it is, instead of making the code more cryptic, it makes the code more self explanatory and easier to read.

The following code checks if the user agent string contains either iphone, ipad or ipod.

if (request.UserAgent.IndexOf("iphone") > -1 || request.UserAgent.IndexOf("ipad") > -1 || request.UserAgent.IndexOf("ipod") > -1 ) { return true; } return false;

The code appears to do the job but what if you have more than 3 iDevices to check?. Cramming 20 conditions in a if statement won't look very good.

The below loops through the list of the iDevices and check if the user agent string contains each iDevice string. 

foreach(string iDevice in new string[] { "iphone", "ipad", "ipod" }) { if (request.UserAgent.IndexOf(iDevice) > -1) { return true; } } return false;

This looks better. We can compress the above code into one line using a Linq expression as below

return new string[] { "iphone", "ipad", "ipod" }.FirstOrDefault(i => request.UserAgent.IndexOf(i) > -1) != null;