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.

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();
        }
    }
}