YieldJS

YieldJS

As part of creating a JS library for relational data manipulation, I went on to create this library called YieldJS for creating Iterators, Generators and Continuation methods for Arrays. Continuation Passing Style (CPS) is utilized for chaining continuation methods along-side iterators and generators.

I had unveiled YieldJS partially as part of my presentation (JS: Good Parts In Action) for HTML5 developer conference. I wanted to add Generators to the library and hence waited till now to publish it officially.

I would consider this Beta (pending performance profiling and exception handling). I would love feedback (from any interested developer) on this especially in par with usage of UnderscoreJS and other prevalent libraries in use today,

I plan to add my share of benchmarks with more usage scenario documentation.

Advertisements

Change Calculator

A dig at one of those code puzzlers from dzone. Thanks to Abhi (a buddy) for sharing it with me and instilling the urge for this adventure. I have utilized a subset generation algorithm (highlighted in code) from my mentor and friend (Pai) here.

Change Calculator 

Say you are given an infinite number of coins in the following denominations:

  • 25 cents
  • 10 cents
  • 5 cents
  • 1 cent

Write a method that would take an integer parameter named change. Work out all the permutations that can return that amount given the coins that you have available. For example, calculateChange(5) would return

  1. 1 x 5c
  2. 5 x 1c
var calculateChange = function (denominations, amount) {
	'use strict';
	var changeSets = 0,
		printChangeSet = function (denominationSet) {
			var matchFactors = [],
				findCombinationSet = function (denominationIndex, cumilativeSum) {
					var transientSum = 0,
						i = 1,
						denomination = denominationSet[denominationIndex],
						factorCount = denominationSet.length;
					while (transientSum <= amount) {
						//Pretty Printing
						matchFactors[denominationIndex] = i.toString() + " x " + denomination.toString() + "c";
						transientSum = cumilativeSum + (denomination * i);
						if ((denominationIndex + 1) === factorCount) {
							if (transientSum === amount) {
								changeSets += 1;
								console.log(changeSets + ". " + matchFactors);
							}
						} else {
							findCombinationSet(denominationIndex + 1, transientSum);
						}
						i += 1;
					}
				};
			findCombinationSet(0, 0);
		},
		// This function computes the possible denomination sets
		generateChangeSets = function () {
			var bitcount = denominations.length,
				mask = Math.pow(2, bitcount),
				i = 1,
				j = 0,
				k = 1,
				denominationSet = null,
				denominationSum = 0;
			while (i < mask) {
				j = 0;
				denominationSet = [];
				denominationSum = 0;
				while (j < bitcount) {
					if ((i & (k << j)) > 0) {
						denominationSet.push(denominations[j]);
						denominationSum += denominations[j];
					}
					j += 1;
				}
				if (denominationSum <= amount) {
					printChangeSet(denominationSet);
				}
				i += 1;
			}
		};
	generateChangeSets();
};
/*jslint indent: 4, maxerr: 1, passfail: false, browser: false, devel: true, windows: false, rhino: false, undef: true, node: true, bitwise: true */

To test this, simply execute:

calculateChange([1, 5, 10, 25], 5);

The decomposition technique utilized here (that of finding all the denomination sets first and then searching for the combinations that would yield the amount) doesn’t hold good against this classic NP-Hard problem where despite parallelization, you cannot cheat death owing to stack overflow for the larger sets, lower denominations and higher amounts.

JSpell

I was able to implement a JavaScript based spelling corrector based on an article by Peter Norvig (How to Write a Spelling Corrector) and wanted to share this with any interested reader. I always wanted to do this the moment I was shared this link by my mentor and friend (almost 2-3 years now). I always had it in my wish-list and now it’s an accomplishment (a good note to end the year I guess). It is so special and unique in regards to employing Bayes theorem in devising the actual algorithm for the spelling corrector. The code has been optimized to a great extent yet preserved adequate styling for brevity. Future work as suggested by Norvig (in his original article) hasn’t been accommodated though. I have enjoyed using currying extensively especially for the precedence-based filtering part in the algorithm. The Spelling Corrector is an object with the following 2 interfaces:

  1. train – use this function to provide the text for the training model.
  2. correct – use this function to provide the words (or a list) for corrections.

Please read the article (link provided above) for all the details. Additional information (especially training text information) could be found here . I have also documented the code for readability.

var NorvigSpellChecker = function () {
	var that = {},
		filter = /([a-z]+)/g,
		alphabets = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'],
		NWORDS = {};//Training Model
	
	var train = function(trainingText) {
		var features = trainingText.match(filter);
		for(var f in features) {
			var feature = features[f];
			if (NWORDS.hasOwnProperty(feature)) {
				NWORDS[feature] += 1;
			}
			else {
				NWORDS[feature] = 1;
			}
		}
	};
	
	var edits1 = function (words) {
		var edits1Set = [];
		for(var w = 0; w < words.length; w++) {
			var word = words[w];
			for (var i = 0; i <= word.length; i++) {
				//splits (a & b)
				var a = word.slice(0,i),
					b = word.slice(i),
					c = b.slice(1),
					d = b.slice(2);
				if (b != '') {
					//deletes
					edits1Set.push(a + c);
					//transposes
					if (b.length > 1) {
						edits1Set.push(a + b.charAt(1) + b.charAt(0) + d);
					}
					//replaces & inserts
					for (var j = 0; j < alphabets.length; j++) {
						edits1Set.push(a + alphabets[j] + c);//replaces
						edits1Set.push(a + alphabets[j] + b);//inserts
					}
				}
				else {
					//inserts (remaining set for b == '')
					for (var j = 0; j < alphabets.length; j++) {
						edits1Set.push(a + alphabets[j] + b);
					}
				}
			}
		}
		return edits1Set;
	};
	
	var edits2 = function (words) {
		return edits1(edits1(words));
	};

	Object.prototype.isEmpty = function () {
		var that = this;
		for(var prop in that) {
			if(that.hasOwnProperty(prop))
				return false;
		}
		return true;
	};

	Function.prototype.curry = function () {
		var slice = Array.prototype.slice,
			args = slice.apply(arguments),
			that = this;
		return function () {
			return that.apply(null, args.concat(slice.apply(arguments)));
		};
	};
	
	var known = function () {
		var knownSet = {};
		for (var i = 0; knownSet.isEmpty() && i < arguments.length; i++) {
			var words = arguments[i];
			for (var j = 0; j < words.length; j++) {
				var word = words[j];
				if (!knownSet.hasOwnProperty(word) && NWORDS.hasOwnProperty(word)) {
					knownSet[word] = NWORDS[word];
				}
			}
		}
		return knownSet;
	};
	
	var max = function(candidates) {
		var maxCandidateKey = null,
			maxCandidateVal = 0,
			currentCandidateVal;
		for (var candidate in candidates) {
			currentCandidateVal = candidates[candidate];
			if (candidates.hasOwnProperty(candidate) && currentCandidateVal > maxCandidateVal) {
				maxCandidateKey = candidate;
				maxCandidateVal = currentCandidateVal;
			}
		}
		return maxCandidateKey;
	};

	var correct = function () {
		var corrections = {};
		for (var i = 0; i < arguments.length; i++) {
			var word = arguments[i];
			var candidates = known.curry()([word],edits1([word]),edits2([word]));
			corrections[word] = candidates.isEmpty() ? word : max(candidates);
		}
		return corrections;
	};
	
	that.train = train;
	that.correct = correct.curry();
	
	return that;
};
I have also hosted the source code (free for use) and sample test code. Please provide the training text as a string in the sample test code for trying JSpell. Happy New Year!

A Good Day In My Life

This anniversary ended on a great note!

  • The entire 24 hrs I was with my family.
  • Visited an underprivileged organization and offered a helping hand.
  • I accomplished yet another item on my wish-list (I promise this would be my next blog).
  • My Project Manager called me and said that we had made a good delivery.
  • We had a peaceful dinner with a very good friend and his family.
  • And last but not least we were all happy the entire 24 hours.

Couldn’t ask for more. Thank you Lord!

 

Intriguing JavaScript – 1

JavaScript as a first-class language… something that never occurred to me or never was a mandate till now.

I typically spend lot of time mashing up my experiences to put together a blog, but the pace at which I work doesn’t give me the luxury to put together and convey something the way I want to. So, just a change in strategy, it’s just going to be a travelogue (to the extent it would just be a snap-shot/crumb-trail of my browser history).

It’s really amazing how this language has evolved.

Created in 10 days by Brendan Eich (A good video to watch… “JavaScript at 17” – http://www.youtube.com/watch?v=Rj49rmc01Hs)

There’s a beautiful set of videos from Douglas Crockford (A must-see ones for any JS programmer) – http://yuiblog.com/crockford/

And finally to wrap this blog an amazing jump-start book for JS programming  – http://eloquentjavascript.net/

Have fun with JS!

A String’s Tale

This is something that went into being as a result of an interesting “Q” faced by a close associate as part of his technical interview. The “Q” being – How would one represent a String as a value type in DotNET to which his answer was an immediate “No, you can’t!”  Theoretically he is correct in DotNET realms and nothing ordinary would mandate you to even think about it.  I guess Mr. Hyde got better off and sent me reeling on such a realization (but still not sure if this was what the interviewer had in mind) to this “Q”.

This has nothing special to pay attention to apart from usage of certain CSharp (C#) language features like Dynamic code generation using Reflection, Extension Methods, LINQ, Anonymous functions etc. TypeAttributes.SequentialLayout (Highlighted line) does have lot of significance the way the structure is created here!

The major short-coming would be the structure itself for String encoding. It would have been ideal to have the structure to just have one field each for every single character and the corresponding positions. The use of bit array was explored but abandoned due to its cap at 32 & 64. I didn’t really spend much time on getting the right structure as this was more an adventure to somehow try and see if it was really possible as opposed to finding a smart way. Any other intelligent encoding schemes or data compression techniques (Huffman coding, Arithmetic coding, LZW coding etc.) would really uplift this adventure to a different level. The journey itself is the reward here!


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Reflection;
using System.Reflection.Emit;

namespace StringVal
{
    public static class StringHelper
    {
        /// <summary>
        /// Returns the Value Type equivalent of a String.
        /// </summary>
        public static ValueType GetValue(this string s)
        {
            int _stringLength = s.Length;
            string _typeName = "StringVal";
            AssemblyName _assemblyName = new AssemblyName();
            _assemblyName.Name = "IamOnTopOfTheWorld";
            AssemblyBuilder _newAssembly =
            System.Threading.Thread.GetDomain().DefineDynamicAssembly(_assemblyName, AssemblyBuilderAccess.Run);
            ModuleBuilder _newModule = _newAssembly.DefineDynamicModule("StringUtils");
            TypeBuilder _newType = _newModule.DefineType(_typeName,
                                 TypeAttributes.Public | TypeAttributes.Sealed | TypeAttributes.SequentialLayout | TypeAttributes.Serializable,
                                 typeof(ValueType));
            FieldBuilder field;
            for (int i=0;i<_stringLength;i++)
            {
                field = _newType.DefineField(string.Format("c{0}_{1}", i, Char.ConvertToUtf32(s, i)), typeof(bool), FieldAttributes.Public);
            }
            Type type = _newType.CreateType();
            return (ValueType)_newAssembly.CreateInstance(_typeName);
        }

        /// <summary>
        /// Returns the String equivalent of Type :: StringVal
        /// </summary>
        public static string GetString(this ValueType valType)
        {
            string sOutput = @"Error::Expected Value Type-""StringVal""";
            if (valType.GetType().Assembly.GetName().Name.Equals("IamOnTopOfTheWorld") &&
                valType.GetType().Module.ScopeName.Equals("StringUtils") &&
                valType.GetType().Name.Equals("StringVal"))
            {
                var query = from m in valType.GetType().GetFields()
                            select m;
                StringBuilder sBuilder = new StringBuilder(query.Count<FieldInfo>());
                string fldName;
                int utfCharCode;
                foreach (FieldInfo fldInfo in query)
                {
                    fldName = fldInfo.Name;
                    utfCharCode = int.Parse(fldName.Substring(fldName.IndexOf("_") + 1));
                    sBuilder = sBuilder.Append(Char.ConvertFromUtf32(utfCharCode));
                }
                sOutput = sBuilder.ToString();
            }
            return sOutput;
        }

        /// <summary>
        /// Returns the byte size of a structure whose type is 'type', as stored in managed memory.
        /// Courtesy: <a href="http://msdn.microsoft.com/en-us/library/eahchzkf.aspx">MSDN</a>
        /// </summary>
        public static int GetManagedSize(this Type type)
        {
            var method = new DynamicMethod("GetManagedSizeImpl",
              typeof(uint),
              new Type[0],
              false);
            ILGenerator gen = method.GetILGenerator();
            gen.Emit(OpCodes.Sizeof, type);
            gen.Emit(OpCodes.Ret);
            var func = (Func<uint>)method.CreateDelegate(typeof(Func<uint>));
            return checked((int)func());
        }
    }

    /// <summary>
    /// Test Harness!
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            string x = @"Mary had a little lamb!";//Provide your Input String here...
            Console.WriteLine(String.Format(@"Initialized String -> {0}",x));
            ValueType y = x.GetValue();//Converts the string to a value type
            Console.WriteLine(String.Format(@"String Converted to Value of Type -> {0} || Size -> {1} bytes",
                y.GetType().Name,
                y.GetType().GetManagedSize()));
            Console.WriteLine(String.Format(@"Recovered String from it's equivalent Value Type -> {0}",
                y.GetString()));//Converts the value type to String
            Console.Read();
        }
    }
}

The Right Way!

It’s been an amazing March and the journey so far has been exhilarating. Fighting dragons, crossing bridges, running races, going in “Strange Loops” etc. Looks like an excerpt from a fairy tale adventure except for the fact that the prince (supposedly me) is definitely not living happily anymore. Big thanks to a couple of colleagues (that includes my mentor Mr. Pai) who helped open the window:

CreateWindowEx(
        WS_EX_CLIENTEDGE,
        g_szClassName,
        “Hello Linear-Programming”,
        WS_OVERLAPPEDWINDOW,
        CW_USEDEFAULT, CW_USEDEFAULT, ∞, ∞,
        NULL, NULL, hInstance, NULL);

Well! It all started when my colleague got this wonderful problem from his friend. It went like this:

“What would be the maximum messages that you could send using any given number of senders and dispatchers with varying capacities plus other defined constraints?”

This was the “Larger than Life” generic version of the problem that we yearned to crack. The real problem (the one I believe I have solved rightfully below) was too tempting to be conquered, especially after having slain the dragon (I was able to contain a trojan-horse in my PC without having to forfeit/format my kingdom/hard-disk), I ended up with a naïve procedure that of iteratively, proportionally dividing the load based on sender/dispatcher capacities. My mentor knew from day one that, this was a classic Linear Programming (LP) problem (which I couldn’t fully comprehend then) and he was quite adamant in trying to get this solved “the right way”.

Thus began my captivating journey on Mr. Well’s “Time Machine” across Prussia, along with Euler trying to cross all the 7 Konigsberg bridges “exactly once” (Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani) and Greece, where I pitted against the tortoise in place of Achilles trying to prove Zeno wrong and then going in “Strange Loops” over Escher’s paintings (Godel-Escher-Bach: An Eternal Golden Braid by Douglas R. Hofstadter). And finally after pounding through various other Finite Mathematics & LP books ranging from (A Beginner’s Guide To Finite Mathematics: For Business, Management, And The Social Sciences by W. D. Wallis) to (Linear and Nonlinear Programming: International Series in Operations Research & Management Science by David G. Luenberger & Yinyu Ye), I finally was able to comprehend the problem at hand, and more importantly confront the beast that we intended to leash, “the right way”.

The Problem:

Three senders S1, S2 and S3 can send 50, 100 and 60 messages respectively. These senders need to consume three dispatchers namely D1, D2 and D3 with message capacities 40, 80 and 60 respectively. Determine the message distribution across the senders and dispatchers for maximum throughput provided:

  • S1 can consume only D2 and D3 for sending messages
  • S2 can consume only D1 and D2 for sending messages
  • S3 can consume only D1 and D3 for sending messages

 

:: My Take On It ::

The problem has been modeled into the following matrix and LP problem as shown in figure below:

The Problem Matrix In LP Terms

The Problem Matrix In LP Terms

I have adopted the “Simplex Method” for solving it as shown in figure below:
The Simplex Solution

The Simplex Solution

:: And now we have the distribution with maximum possible messages (180) as shown in figure below::
The Distribution For Maximum Messages

The Distribution For Maximum Messages

In case, you are still wondering why I live unhappily, you need to take a look at the “size” of the window again that my colleagues have opened.
Yeah it certainly is Infinity ()!