Anagrams Within Words in Python

I implemented the Anagrams Within Words programming puzzle from Programming Praxis in Python, a language I haven’t used since my college days when I used it to  implement a REST service as part of my final year project.

Needless to say, I had forgotten most of the syntax and had to repeatedly refer to the Python docs.

Problem Statement
Given two words, determine if the first word, or any anagram of it, appears in consecutive characters of the second word. For instance, cat appears as an anagram in the first three letters of actor, but car does not appear as an anagram in actor even though all the letters of car appear in actor.

Solution

class AnagramChecker:
    #Temporary list that contains the first word. We will remove matching
    #characters from here
    #Python doesn't insist on explicit declaration of class variables but
    #this variable was declared for purposes of clarity
    tempFirstWord = []

    def checkChar(self, charOfSecondWord):
        if charOfSecondWord in self.tempFirstWord:
            #Remove matching character from temporary first word
            self.tempFirstWord.remove(charOfSecondWord)
        else:
            #Reset first word as we need to start checking from beginning
            self.tempFirstWord = list(self.firstWord)

        #If our tracking variable runs down to 0 then we have a complete and continuous match
        if len(self.tempFirstWord) == 0:
            return True
        else:
            return False

    def checkAnagram(self, userInput):
        #Python's wonderful list unpacking feature means we don't need a temporary
        #variable to store the split results
        self.firstWord, self.secondWord = userInput.split(" ")

        self.tempFirstWord = list(self.firstWord)

        anagramFound = False
        for c in self.secondWord:
            if self.checkChar(c):
                anagramFound = True
                break

        return anagramFound

userInput = raw_input("Please enter two words: ")

checkerObj = AnagramChecker()
print "Anagram found: ", checkerObj.checkAnagram(userInput)

Also here on GitHub Gists.

Sample use

Please enter two words: act tractor
Anagram found:  True

Please enter two words: car actor
Anagram found:  False

Park-Miller random number generator in Common Lisp

Below is a Common Lisp implementation of the Minimum Standard Random Number Generator described by Park and Miller in 1988.

Problem statement
Read the problem statement here at Programming Praxis. Be warned that the blog post mixes up the values for lo and hi. It took me ages to figure out why my program wasn’t returning correct results. I finally got the correct formulas from the paper the post links to.

Solution
Programming Praxis talks about 3 different implementations but I just implemented the first two:

(defun get-msrn-naive (x n)
	(let ((a 16807) (m 2147483647))
	(mod (*
		  a
		 ;Multiply either by x or recursive call
		  (if (eq n 1)
		   x
		   (get-msrn-naive x (- n 1))))
	 m)))

(defun get-next-msrn (x)
	(let (
			(a 16807)
			(m 2147483647)
			(q 127773)
			(r 2836)
		 )
		(let
			(
				(result
						(-
							(* a (mod x q))
							(* r (floor (/ x q)))
						)
				)
			)
			(if
				(<= result 0)
				(+ result m)
				result
			 )
		)
	)
)

(defun get-msrn-schrage (x n)
	(if (eq n 1)
	 (get-next-msrn x)
	 (get-msrn-schrage (get-next-msrn x) (- n 1))))

It can also be viewed here on Github Gist.

Sample use

(get-msrn-schrage 1 10000)
1043618065

(get-msrn-schrage 1 5)
1144108930

(get-msrn-naive 1 5)
1144108930

Minimum Hamming Distance in Common Lisp

Problem statement
From Programming Praxis:

The Hamming distance between two numbers is the number of bits that must be changed to make the bit representations of the two numbers equal. Read a list of numbers and find the two with the minimum Hamming distance between them.

Solution
This problem took me all day because i’m very new to Lisp.

;XOR p q => (p V q) ^ !(p ^ q)
(defun xor (p q)
	(and
		(or p q)
		(not (and p q))
	)
)

;Represent a number as a boolean list
(defun getbinary (n)
	(map 
		'list
		;"111" becomes (T T T)
		(lambda (x)
			(if (eq #\1 x) t nil)
		)
		;7 becomes "111"
		(format nil "~b" n)))

;Find hamming distance between two *binary* numbers using XOR
(defun hammingdistance (n1 n2)
	(count t
		(append
			(map
				'list
				(lambda (x y)
					(xor x y)
				)
				n1
				n2)
			;map will not work when lists are not of the same length,
			;we need to count extra digits in case of length differential.
			;taking everything after certain point is fine
			(nthcdr (length n1) n2)
			(nthcdr (length n2) n1)
			)))

;find minimum element in a list
(defun findmin (l &optional m)
	(if l 
		(findmin 
			(cdr l) 
			(min 
				(car l) 
				;optional parameter is initially nil so
				;we replace it first element of list
				(if m m (car l))))
		;terminating condition
		m))

;gets all unique pairings between elements in a list
(defun uniquepairs (l)
	(if l
		(append 
			;start from beginning element and pair with every element *head*
			;in (1, 2, 3), 1 gets paired with 2 and 3 in first iteration
			(loop for x in (cdr l)
				collect (list (car l) x))
			;generate pairs for remaining elements
			(uniquepairs (cdr l)))
		;terminating condition
		nil))

;find minimum hamming distance between any two elements in input list
;(minhd '(79 83)) => 3
;(minhd '(13500 1935 9645 5790)) => 4
(defun minhd (i)
	(findmin 
		(map
			'list
			;input is a pair, list of two elements
			(lambda (x)
				(hammingdistance  (getbinary (first x)) (getbinary (second x))))
			;generate a list of all possible pairings
			(uniquepairs i))))

It can also be viewed here on Github Gist.

Fletcher’s checksum in C#

I implemented Fletcher’s checksum as an exercise from Programming Praxis.

I planned on using generics for the 16, 32 and 64-bit variations of the algorithm but that didn’t pan out. Here is the implementation:

using System;
using System.Text;
using System.Collections.Generic;

namespace Checksums
{
	/// <summary>
	/// Calculates Fletcher's checksums
	/// Sample outputs: 
	/// Fletcher16: "abcde" -> 51440
	/// Fletcher32: "abcde" -> 3948201259
	/// Fletcher64: "abcde" -> 14034561336514601929
	/// </summary>
	public class FletcherChecksum
	{
		/// <summary>
		/// Transforms byte array into an enumeration of blocks of 'blockSize' bytes
		/// </summary>
		/// <param name="inputAsBytes"></param>
		/// <param name="blockSize"></param>
		/// <returns></returns>
		private IEnumerable<UInt64> Blockify(byte[] inputAsBytes, int blockSize)
		{
			int i = 0;

			//UInt64 used since that is the biggest possible value we can return.
			//Using an unsigned type is important - otherwise an arithmetic overflow will result
			UInt64 block = 0;
			
			//Run through all the bytes			
			while(i < inputAsBytes.Length)
			{
				//Keep stacking them side by side by shifting left and OR-ing				
				block = block << 8 | inputAsBytes[i];
				
				i++;
				
				//Return a block whenever we meet a boundary
				if(i % blockSize == 0 || i == inputAsBytes.Length)
				{
					yield return block;
					
					//Set to 0 for next iteration
					block = 0;
				}
			}
		}
		
		/// <summary>
		/// Get Fletcher's checksum, n can be either 16, 32 or 64
		/// </summary>
		/// <param name="inputWord"></param>
		/// <param name="n"></param>
		/// <returns></returns>
		public UInt64 GetChecksum(String inputWord, int n)
		{
			//Fletcher 16: Read a single byte
			//Fletcher 32: Read a 16 bit block (two bytes)
			//Fletcher 64: Read a 32 bit block (four bytes)
			int bytesPerCycle = n / 16;
			
			//2^x gives max value that can be stored in x bits
			//no of bits here is 8 * bytesPerCycle (8 bits to a byte)
			UInt64 modValue = (UInt64) (Math.Pow(2, 8 * bytesPerCycle) - 1);
						
			//ASCII encoding conveniently gives us 1 byte per character 
			byte[] inputAsBytes = Encoding.ASCII.GetBytes(inputWord);
			
			UInt64 sum1 = 0;
			UInt64 sum2 = 0;
			foreach (UInt64 block in Blockify(inputAsBytes, bytesPerCycle))
			{					
				sum1 = (sum1 + block) % modValue;
				sum2 = (sum2 + sum1) % modValue;
			}
				
			return sum1 + (sum2 * (modValue+1));
		}
	}
}

It can also be viewed here.

Debugging Challenge 1

The Challenge

Below you will find a program that does not work as expected due to coding errors. Prove that your C# skills are up to scratch by fixing the bugs in it. Expected output is included in the source code.

This challenge is meant to be solved in 10-15 minutes max and does not require any software. Your browser is enough.

Click here to run the code on ideone.com

using System;

public class Launcher
{
 public static void Main()
 {
 Challenge1 challengeObj = new Challenge1();

challengeObj.Test();
 }
}

///
/// Challenge1.
///
public class Challenge1
{
 private void ChangeTime(DateTime targetTime, string hhmm)
 {
 int hh = Convert.ToInt32(hhmm.Substring(0, 2));
 int mm = Convert.ToInt32(hhmm.Substring(2, 2));

 targetTime.AddHours(targetTime.Hour * -1).AddHours(hh);
 targetTime.AddMinutes(targetTime.Minute * -1).AddMinutes(mm);
 }

 /// RULE#1: Thou shalt not change the return type of this method
 private void CalculateSchedule(DateTime wakeupTime, DateTime bedTime)
 {
 ChangeTime(wakeupTime, "0600");
 ChangeTime(bedTime, "2230");
 }

 public void Test()
 {
 //Get objects with current date and time
 DateTime bedTime = DateTime.Now;
 DateTime wakeupTime = DateTime.Now;

 //Leave dates the same but change the time part
 CalculateSchedule(wakeupTime, bedTime);

 /// EXPECTED OUTPUT (if program runs on 12/22/2013):
 /// I hope you woke up at 12/22/2013 6:00:40 AM
 /// Your bedtime is 12/22/2013 10:30:40 PM
 Console.WriteLine("I hope you woke up at " + wakeupTime.ToString());
 Console.WriteLine("Your bedtime is " + bedTime.ToString());
 }
}

Notes

If you’re unable to fix the defects above read the following notes:

1. DateTime is immutable

   DateTime, like String and primitive types like int and float, is immutable. What this means is that when you change an object of DateTime using a method like AddHours() it returns a *new* object with the hours added instead of modifying the existing one.

   This is why we had to capture the output of targetTime.AddHours() back into targetTime.

2. Passing variables by reference
   The widely misunderstood ref keyword is used to pass variables by reference. This means that if we replace the value in a parameter with an entirely new one then the calling function gets the new object – this won’t happen without use of the ref keyword.

   Without using ref the Test() method would not recieve the newly created (since DateTime is immutable) objects from CalculateSchedule().

Solution

Click here to run the code on ideone.com

using System;

public class Launcher
{
 public static void Main()
 {
 Challenge1 challengeObj = new Challenge1();

challengeObj.Test();
 }
}

/// <summary>
/// Solution to Challenge1.
/// </summary>
public class Challenge1
{
 private DateTime ChangeTime(DateTime targetTime, string hhmm)
 {
 int hh = Convert.ToInt32(hhmm.Substring(0, 2));
 int mm = Convert.ToInt32(hhmm.Substring(2, 2));

 targetTime = targetTime.AddHours(targetTime.Hour * -1).AddHours(hh)
 .AddMinutes(targetTime.Minute * -1).AddMinutes(mm);

 return targetTime;
 }

/// RULE#1: Thou shalt not change the return type of this method
 private void CalculateSchedule(ref DateTime wakeupTime, ref DateTime bedTime)
 {
 wakeupTime = ChangeTime(wakeupTime, "0600");
 bedTime = ChangeTime(bedTime, "2230");
 }

 public void Test()
 {
 //Get objects with current date and time
 DateTime bedTime = DateTime.Now;
 DateTime wakeupTime = DateTime.Now;

 //Leave dates the same but change the time part
 CalculateSchedule(ref wakeupTime, ref bedTime);

 /// EXPECTED OUTPUT (if program runs on 12/22/2013):
 /// I hope you woke up at 12/22/2013 6:00:40 AM
 /// Your bedtime is 12/22/2013 10:30:40 PM
 Console.WriteLine("I hope you woke up at " + wakeupTime.ToString());
 Console.WriteLine("Your bedtime is " + bedTime.ToString());
 }
}

Heapsort in C#

• Building the heap takes O(n)
• Sorting using the heap takes O(nlogn) 
• Sorts in place (useful when space is critical)
• Not used often in production because of poor cache performance (does not compare array elements which are close by)
• Used in construction of priority queues (job scheduling)

Firstly, we implement a heap data structure. I included the traditional (and easy to understand) recursive version of MaxHeapify() as well a sequential version.

using System;
using System.Collections.Generic;

namespace Utility
{
	/// <summary>
	/// A max-heap
	/// </summary>
	public class Heap<T>
	{
		/// <summary>
		/// Used to compare elements to be sorted
		/// </summary>
		private Comparison<T> comparer;
		
		/// <summary>
		/// Internal list on which the heap is based
		/// </summary>
		public List<T> InternalList;
		
		/// <summary>
		/// Length of the heap
		/// </summary>
		public int Length { get; set; }
		
		public Heap(List<T> inputList, Comparison<T> comparer)
		{
			InternalList = inputList;
			Length = inputList.Count;
			this.comparer = comparer;
						
			//Build a max-heap from the input list
			BuildMaxHeap();
		}
		
		/// <summary>
		/// Returns index of parent of the element at index i
		/// </summary>
		/// <param name="i"></param>
		private int Parent(int i)
		{
			return i / 2;
		}
		
		/// <summary>
		/// Returns index of left child of the element at index i
		/// </summary>
		/// <param name="i"></param>
		private int Left(int i)
		{
			return 2 * i;
		}
		
		/// <summary>
		/// Returns index of right child of the element at index i
		/// </summary>
		/// <param name="i"></param>
		private int Right(int i)
		{
			return (2 * i) + 1;
		}
		
		/// <summary>
		/// Swaps elements at index i and j with each other
		/// </summary>
		/// <param name="i"></param>
		/// <param name="j"></param>
		public void Swap(int i, int j)
		{
			T temp = InternalList[i];
				
			InternalList[i] = InternalList[j];
			InternalList[j] = temp;
		}
		
		/// <summary>
		/// Builds a max-heap (without using recursion to heapify child trees)
		/// </summary>
		/// <param name="i"></param>
		public void SequentialMaxHeapify(int root)
		{	
			bool heapified = false;
			
			while(!heapified)
			{			
				int largest;
				int l = Left(root);
				int r = Right(root);
				
				//Check if left child exists and if it is larger than the root
				if(l < Length && comparer(InternalList[l], InternalList[root]) > 0)
				{
					largest = l;
				}
				//If not then we assume that the root is largest
				else
				{
					largest = root; 
				}
				
				//Now compare largest of left child or parent with the right child,
				//find the largest of the three
				if(r < Length && comparer(InternalList[r], InternalList[largest]) > 0)
				{
					largest = r;
				}
				
				//If largest is not the root then we need to switch
				if(largest != root)
				{
					Swap(root, largest);
					
					//On next loop start from largest child as swap might have resulted
					//in child
					root = largest;
				}
				else
				{
					heapified = true;
				}
			}
		}
		
		/// <summary>
		/// Builds a max-heap (assumes that left and right child of i
		/// are already max-heaps)
		/// </summary>
		/// <param name="i"></param>
		public void MaxHeapify(int i)
		{
			int largest;
			int l = Left(i);
			int r = Right(i);
			
			//Check if left child exists and if it is larger than the root
			if(l < Length && comparer(InternalList[l], InternalList[i]) > 0)
			{
				largest = l;
			}
			//If not then we assume that the root is largest
			else
			{
				largest = i; 
			}
			
			//Now compare largest of left child or parent with the right child,
			//find the largest of the three
			if(r < Length && comparer(InternalList[r], InternalList[largest]) > 0)
			{
				largest = r;
			}
			
			//If largest is not the root then we need to switch
			if(largest != i)
			{
				Swap(i, largest);
				
				//Swap might have caused the child to lose its max-heap property so perform
				//a recursive call
				MaxHeapify(largest);
			}
		}
		
		/// <summary>
		/// Builds a max-heap from an unordered input list
		/// </summary>
		public void BuildMaxHeap()
		{
			//Start from the left-most parent element in the heap
			//Everything after this are leaf nodes
			int i = Length/2;
			
			while(i >= 0)
			{
				MaxHeapify(i);
				
				i--;
			}
		}
	}
}

The actual heapsort algorithm implementation is small:

using System;
using System.Collections.Generic;

namespace Utility
{
	/// <summary>
	/// An implementation of the heapsort algorithm
	/// </summary>
	public class HeapSorter : ISorter
	{
		/// <summary>
		/// Sorts an input list using the heapsort algorithm
		/// </summary>
		/// <param name="inputList"></param>
		/// <returns></returns>
		public List<T> Sort<T>(List<T> inputList, Comparison<T> comparer)
		{
			Heap<T> heapObj = new Heap<T>(inputList, comparer);
			
			for(int i = inputList.Count - 1; i >= 0; i--)
			{
				//Swap top of heap with last element
				heapObj.Swap(0, i);
				
				//Decrease the length of the heap to exclude top element
				heapObj.Length--;
				
				//Re-build the heap (ignoring the last few elements 
				//due to decreased length)
				heapObj.MaxHeapify(0);
			}
			
			return heapObj.InternalList;
		}
	}
}

The sorter class is used as follows:

HeapSorter sorter = new HeapSorter();
			
List<int> outputList = sorter.Sort(inputList, (x, y) => x.CompareTo(y));

The second argument is a lambda expression that matches the inbuilt delegate Comparison<T>. It tells the generic sorter how to compare two elements of class T. We’re sorting just integers here but if we were sorting a class of Person the Comparison<T> delegate might look as follows if we wanted to sort by age:

HeapSorter sorter = new HeapSorter();
			
List<Person> outputList = sorter.Sort(inputList, (x, y) => x.Age.CompareTo(y.Age));

The entire code is available here.

Binary search in C#

Here is a generic implementation of binary search in C#. It can be used to sort any kind of list as long as the elements implement the IComparable interface.

         /// <summary>
         /// Searches through a list using binary search algorithm
         /// </summary>
         /// <param name="source"></param>
         /// <param name="searchKey"></param>
         /// <returns></returns>
         public static int BinSearch<T>(this List<T> source, T searchKey)
             where T:IComparable
         {
             int low = 0;
             int high = source.Count - 1;
             int mid;

             do
             {
                 mid = low + ((high - low) / 2);

                 int compareResult = searchKey.CompareTo(source[mid]);

                 //If item is at current mid position we can stop
                 if(compareResult == 0)
                 {
                     return mid;
                 }
                 //Otherwise look at either lower half or upper half of the list
                 else
                 {
                     //If searchKey < source[mid] then we need to look at
                     //left half of the list
                     if(compareResult < 0)
                     {
                         high = mid - 1;
                     }
                     else
                     {
                         low = mid + 1;
                     }
                 }
             } while (low < high);

             return -1;
         }

The entire code is available here.

Sample output

Enter source list:
6 7 9 11 67 98 123 156
Enter number to search for:
67
Output of binary search: 4

Enter source list:
6 7 8 9 11
Enter number to search for:
11
Output of binary search: 4

Enter source list:
1 3 6 7 8
Enter number to search for:
4
Output of binary search: -1

Lessons learned

• Extension methods cannot be written for static classes (I tried to extend System.Console)
• IComparable.CompareTo() returns values as follows for objA.CompareTo(objB):
  • 0 if objA == objB
  • >1 if objA > objB
  • <1 if objA < objB

C# solution for ‘Store Credit’ from code jam 2010

Problem statement: https://code.google.com/codejam/contest/351101/dashboard

A naive solution to this problem is to repeatedly loop over the previously entered numbers for every input entered by the user. This would have resulted in a nested for-loop so I tried to think of a better solution.

My final solution is one in which the program loops over the list of items only once. How is this achieved? By using a marker array. Each position in this array represents an amount. If position 54 in the marker array contains 4 it means that the 4th item in the input list costs 54.

Here is the algorithm:

1. Create an array of size ‘credit’.
2. For every item look for a matching item in the marker array. This ‘matching item’ is an item that costs (credit – cost).
3. If a match is found then stop.
4. Otherwise make an entry in the marker array.

Solution

		/// <summary>
		/// Returns a string "A B" where A and B are the two indices whose
		/// price adds up the store credit
		/// </summary>
		/// <param name="items"></param>
		/// <param name="credit"></param>
		/// <returns></returns>
		private static string FindItems(List<Int32> items, int credit)
		{
			//Create an integer array of size 'credit' since we can safely ignore
			//items that cost more than the credit we have
			int[] itemCosts = new int[credit];

			int currentItem;
			for (int i = 0; i < items.Count; i++)
			{
				currentItem = items[i];

				if(currentItem < credit)
				{
					//Find the amount required in order to fill credit with current item
					//and another item
					if(itemCosts[credit - currentItem] != 0)
					{
						return String.Format("{0} {1}", itemCosts[credit - currentItem], i+1);
					}
					else
					{
						itemCosts[currentItem] = i + 1;
					}
				}
			}

			return "";
		}

Full source-code available here.

FizzBuzz in Haskell

Problem statement

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Solution

--Tells us if x is divisible by y
divby :: (Integral x) => x -> x -> Bool
divby x y =
	(x `mod` y) == 0

--Internal function that returns output for a single number
isfizzbuzz :: (Integral x) => x -> String
isfizzbuzz x
	| divby x 3 &&  divby x 5 = "FizzBuzz"
	| divby x 3 = "Fizz"
	| divby x 5 = "Buzz"
	| otherwise = show x

--Method that returns FizzBuzz output on a list of numbers
fizzbuzz :: (Integral x) => [x] -> [String]
fizzbuzz x =
	map isfizzbuzz x

As WordPress does not support Haskell source formatting I have opted to format the code as Erlang so you will see some strange highlighting above.

You can also view the code here on GitHub Gists.

Sample output

fizzbuzz [1..100]
[“1”, “2”, “Fizz”, “4”, “Buzz”, “Fizz”, “7”, “8”, “Fizz”, “Buzz”, “11”, “Fizz”, “13”, “14”, “FizzBuzz”, “16”, “17”, “Fizz”, “19”, “Buzz”, “Fizz”, “22”, “23”, “Fizz”, “Buzz”, “26”, “Fizz”, “28”, “29”, “FizzBuzz”, “31”, “32”, “Fizz”, “34”, “Buzz”, “Fizz”, “37”, “38”, “Fizz”, “Buzz”, “41”, “Fizz”, “43”, “44”, “FizzBuzz”, “46”, “47”, “Fizz”, “49”, “Buzz”, “Fizz”, “52”, “53”, “Fizz”, “Buzz”, “56”, “Fizz”, “58”, “59”, “FizzBuzz”, “61”, “62”, “Fizz”, “64”, “Buzz”, “Fizz”, “67”, “68”, “Fizz”, “Buzz”, “71”, “Fizz”, “73”, “74”, “FizzBuzz”, “76”, “77”, “Fizz”, “79”, “Buzz”, “Fizz”, “82”, “83”, “Fizz”, “Buzz”, “86”, “Fizz”, “88”, “89”, “FizzBuzz”, “91”, “92”, “Fizz”, “94”, “Buzz”, “Fizz”, “97”, “98”, “Fizz”, “Buzz”]