Programming Praxies – Egyptian Fractions, C# solution.

This post presents C# solutions to a coin change problem as described in http://programmingpraxis.com/2013/06/04/egyptian-fractions.

An Egyptian fraction was written as a sum of unit fractions, meaning the numerator is always 1; further, no two denominators can be the same. As easy way to create an Egyptian fraction is to repeatedly take the largest unit fraction that will fit, subtract to find what remains, and repeat until the remainder is a unit fraction. For instance, 7 divided by 15 is less than 1/2 but more than 1/3, so the first unit fraction is 1/3 and the first remainder is 2/15. Then 2/15 is less than 1/7 but more than 1/8, so the second unit fraction is 1/8 and the second remainder is 1/120. That’s in unit form, so we are finished: 7 ÷ 15 = 1/3 + 1/8 + 1/120. There are other algorithms for finding Egyptian fractions, but there is no algorithm that guarantees a maximum number of terms or a minimum largest denominator; for instance, the greedy algorithm leads to 5 ÷ 121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225, but a simpler rendering of the same number is 1/33 + 1/121 + 1/363.

Your task is to write a program that calculates the ratio of two numbers as an Egyptian fraction…

As presented in the original post, you can use a greedy algorithm. Thats not fun! Let’s try and improve it: i.e. to return the smallest amount of unit fractions. You cannot devise an algorithm to guarantee the smallest amount of terms, since the problem space has infinite possibilities (genetic algorithm? food for thought).

So what approach can we take to improve on the greedy solution? I began by writing out a few iterations of calculations for 5 ÷ 121: from 1/25 up to 1/33 (part of an optimal solution presented in the problem definition). I noticed that when choosing 1/33, the remaining fraction (that we are pulling apart) can be simplified: where as all other fractions leading up to 1/33 leaves a fraction that cannot be further simplified! If you think about it, simplifying keeps the size of the denominator down, keeping smaller denominators helps yields a smaller amount of terms. This is because when we are dealing with very small numbers (large denominators), we are getting to the final target at a slower rate that we would with larger numbers. Simple huh?

So how can you simplify a fraction? It can be done by calculating the gcd (greatest common divisor) between the numerator and the denominator, then dividing the numerator and the denominator by the gcd. If the gcd is 1, then the fraction cannot be simplified. Hmmm… so maybe we can decide on the next unit fraction (for subtracting) only if the result can be simplified.  Using this informal idea as the basis of our algorithm, we get the following solution:

public class EgyptionFractions
{
	public static List<int[]> GetFractions(int numerator, int denominator) {
		if (numerator >= denominator)
			throw new ArgumentOutOfRangeException ("denominator");
		if (numerator <= 0)
			throw new ArgumentOutOfRangeException ("numerator");

		var fractions = new List<int[]> ();
		int subDenominator = 2;

		do {
			// First find the next fraction to substract from that is small enough
			int leftNumerator = numerator * subDenominator;
			while (leftNumerator < denominator) { // Note: rightNumerator == denominator
				subDenominator++;
				leftNumerator += numerator;
			}

			// Now we have a valid unit fraction to substract with, lets continue
			// searching for the next unit fraction that yeilds a remainder that 
			// can be simplified (to keep the denominators small).
			while (true) {
				int remainingNumerator = leftNumerator - denominator;
				if(remainingNumerator == 0) {
					// The fractions are the same
					numerator = 0;
					fractions.Add (new [] {1, subDenominator});
					break;
				}
				int remainingDenominator = denominator * subDenominator;
				int gcd = GCD (remainingNumerator, remainingDenominator);
				if (gcd > 1 || remainingNumerator == 1) {
					// The resultant fraction can be simplified using this denominator
					numerator = remainingNumerator / gcd;
					denominator = remainingDenominator / gcd;
					fractions.Add (new [] {1, subDenominator});

					// Finished?
					if(numerator == 1) 
						fractions.Add (new [] {1, denominator});
					break;
				}
				subDenominator++;
				leftNumerator += numerator; // i.e. additive version of subDenominator * numerator;
			}

			subDenominator++;
		} while (numerator > 1);

		return fractions;
	}

	private static int GCD(int n1, int n2) {
		if (n2 == 0)
			return n1;
		return GCD (n2, n1 % n2);
	}
}

If you pass in 5, 121, the result will be:
1/33, 1/91, 1/33033

Advertisements

Find the character position using javaScript: FAST, BIG pages, ALL browsers, NO preprocessing.

During my masters year at University, I set out to experiment with a modeless editing model. I decided to use the web at my content environment: the challenge became to making the web editable. I did, for all browsers/OSs (tested and worked for IE 6.0+, All webkit:Chrome/Safari, FF 1.5+, Konqueror, Opera 9+, on apple, windows and linux). One of the interesting problems to solve was finding the nearest character location when a user clicks on the web page. This post explains my solution.

Building Blocks
Microsoft’s Internet Explorer 4 (1997) introduced attributes for all element nodes in the DHTML model that describes the physical dimensions of an element in a web page. These attributes are offsetParent; offsetWidth; offsetHeight;
offsetTop and offsetLeft. Most, if not all, web browsers followed Internet Explorer’s footsteps and the attributes are well supported in contemporary browsers. The W3C drafts for the upcoming CSSOM (CSS Object Model) specification have included these properties and thus must be supported by all modern web browsers in the future.

Figure 1

Figure 1: DHTML/CSSOM offset properties

Figure 1 displays the top part of a web page that contains a <p> element inside a <div> element. The offsetWidth and offsetHeight attributes refer to the dimensions of an element in pixels (excluding margins). The offsetTop and offsetLeft attributes are the distances from the offsetParent in pixels. The offsetParent is the closest positioned containing element. For example, in Figure 1 the offsetParent of the <p> element is the containing <div> element. Note that the hierarchical parent in the DOM tree is not always the same as offsetParent due to CSS positioning schemes such as relative positioning.

The offset attributes can be used to locate the position of an element relative to the document. This is achieved by summing the offsetTop and offsetLeft attributes of all the offsetParent ancestry up to the document’s <body> element. In some cases, depending on the browser, and whether it is in quirksmode or not, the document’s CSS border must be manually added (if one exists). To determine the position of an element relative to the window, the document’s horizontal and vertical scroll-bar positions are subtracted from the calculated x and y positions of the element relative to the document respectively.

Another widely supported method is elementFromPoint(), which is currently included in the CCSOM specification drafts. This method returns an element in a document at the given (x, y) pixel coordinates. These coordinates are relative to the browser window for Gecko and Trident based browsers, where other browsers use coordinates relative to the document. This method is not as well supported as the offset properties (for example Firefox versions below 3 do not support this), so an alternative JavaScript implementation was written for legacy browser support.

Total Isolation Approach (Preprocessing)

One solution for determining a cursor position from a mouse click is to encapsulate every character within an editable section in a <span> element. Thus, when a user clicks in an editable section, the elementFromPoint() method can be used to directly discover the clicked character. Since the characters are isolated in dedicated <span> elements, the position and size of the characters can also be determined using methods described in the previous section. <span> elements are chosen because they are the only element that can reside in any element where there is text (according to HTML 4.01 and XHTML 1.0 specifications). As simple as this approach appears, it has too many pitfalls to be regarded as a practical solution:

  • The pre-processing step to isolate every character with <span> elements takes noticeably long periods of computation time. During this period, the browser becomes unresponsive (except for Opera which runs JavaScript on a separate thread to the window event thread). The pre-processing phase must occur either when a page loads or on the first cursor placement. The former approach would thwart bursty/rapid navigation through seamlessly editable web pages. The latter approach would lose the illusion of direct manipulation since the response time for the first edit would be too long.
  • The amount of memory used is bloated because of the large amount of DOM tree nodes required.
  • The large amount of <span> elements create a large DOM tree. In general, the larger the DOM tree, the slower the performance of the browser. Manipulating the DOM for performing editing operations becomes more expensive.
  • The elementFromPoint() method becomes slower because there is a larger amount of nodes to search.
  • The approach increases complexity in the rest of the framework’s implementation. All operations which manipulate the DOM must ensure that all text nodes always have exactly one character that is encapsulated in a dedicated <span> element.

Rather than total isolation of every character, you can break down this character location problem into a smaller problem effeciently using a more coarse grained preprocessing method: splitting just the lines using <div> tags. Codemirror does this for there code editor. This is a great idea if you don’t want to wrap lines. However if you want to retain text wrapping then you need to use another method. Let’s look more closely at the search space we are scanning to locate the nearest character.

Search space

When a user clicks on a web page, the (x, y) coordinates of the mouse pointer are supplied by the DOM in a mouse event object. The elementFromPoint() method is used to get the element which the mouse cursor is pointing at (if not already supplied by the mouse event object). A list of all the text nodes within the element is collected by traversing the element’s DOM tree in-order. Text nodes where cursor placements cannot occur are excluded. For example, text nodes within <script> or <style> elements, or text nodes consisting purely of white-space for HTML source-code formatting purposes.

In a common case, the element which a user clicks on is a type of container element that is not fully visible by the user. These container elements are only partially visible due to the web browser’s scroll-bar state only revealing part of the element, or the container element happens to be larger than the web browser’s window. An extreme, but typical scenario where this occurs is when a user clicks near the edges of a web page just outside of a <p> element. The element actually clicked is the document <body> element, and therefore includes every text node in the entire web page as part of the search space. To minimise the search space to yield faster performance when searching for the nearest cursor position, the search space is capped to include only nodes that are visible to the user.

Dual Binary Search

The binary search algorithm is an efficient algorithm for locating an item in a sorted collection (on average O(Log N)). It turns out that a two-pass binary search can be used against the search space to discover the closest cursor position.

In the general case when performing an in-order traversal on a DOM tree,the nodes are visited such that each node is either visually below or to the right of the previously visited node. The search space is collected using an in-order traversal, thus forming a spatially sorted collection. Search spaces are readily organised in ascending order by the y coordinate in the web page, therefore the characters in the search space are grouped by the line where they reside.

Figure2

Figure 2: The dual binary algorithm’s perspective of the search space.

Figure 2 conveys this grouping by surrounding characters on the same line with a box in the search space view of a paragraph of text. Furthermore, the x coordinates of the characters are in ascending order within each line-group. For example, the first character in the last group (the right-most group with text “words.”) is at an x coordinate of 6 pixels, and each successive character’s x coordinate increases by roughly 6 pixels all the way up to the last character on the line at an x coordinate of 38 pixels.

Two separate binary searches are used to quickly locate the nearest cursor position to the target coordinate. The first search performs a vertical position based binary search over the whole (y-ordered) search space to locate the line group which the target coordinate resides. The second search performs a horizontal position based binary search over the (x-ordered) line group to locate the nearest character to the target coordinate.

Unfortunately the JavaScript code for this implementation is on CD at home (in another country). However I present to you the pseudo code to whci leaves you the fun of implementing it:

find-cursor-at(target-coordinate) {
  search-space = get-search-space(target-coordinate);
  start = measure(first character in the search-space );
  end = measure(last character in the search-space );
  sample-set = [start,end];
  current-closest = closest(start, end, target-coordinate);
  if (target-coordinate within best.bounds ) {
    return current-closest;
  }
  # First pass
  y-search(start,end);
  (lower, upper) = select-bounds(sample-set);
  # Second pass
  x-search(lower, upper);
  return current-closest;
}

y-search(lower, upper) {
  if (lower.abs-index) == (upper.abs-index - 1) {
    # Upper and lower bounds have met, no more characters to search
    return;
  }
  # Half way point between upper and lower samples
  current.abs-index = (lower-sample.abs-index + upper.abs-index)/2;
  # Get node and relative index from absolute index
  (current.node,current.rel-index) = get-rel-dom-position(current.abs-index);
  # Measure the sample
  (current.x, current.y, current.width, current.height) = measure(current.node, current.rel-index);
  # Store it in the sample set if doing a line search
  sample-set.add(current);
  if (current is closer to target than current-closest ) {
    current-closest = current;
  }
  if (current is same line as the target y ) {
    # Goto second pass: the x binary search
    return;
  } else if (current.y > target-y) {
    upper = current;
  } else {
    lower = current;
  }
  y-search(lower, upper);
}

x-search(upper,lower) {
  if (lower-sample.abs-index) == (upper.abs-index - 1) {
    # Upper and lower bounds have met, no more characters to search
    return;
  }
  # Half way point between upper and lower samples
  current.abs-index = (lower-sample.abs-index + upper.abs-index)/2
  # Determine node and relative index from absolute index
  (current.node,current.rel-index) = get-rel-dom-position(current.abs-index);
  # Measure the sample
  (current.x, current.y, current.width, current.height) = measure(current.node, current.rel-index);
  if (current is closer to target than current-closest ) {
    current-closest = current;
  }
  if(current on line above current-closest ) {
    lower = current;
  } else if (current on line below current-closest ) {
    upper = current
  } else {
    # Current is on same line as current-closest
    if (current.x > target.x) {
      upper = current;
    } else {
      lower = current;
    }
  }
  x-search(lower, upper);
}

That’s a lot of code! Let’s go through it. The search begins by measuring the first and last characters in the search space, becoming the lower and upper
bounds of the search space respectively. If one of the initial measurements is displayed directly at the target coordinate, the search is finished. The first binary search is then entered.

Once the first binary search, the y-search, finds a measurement on the same line as the target coordinate, the search ends. The upper and lower bounds are selected from measurements stored in a sample-set (gathered during the y-search) for the second search, the x-search. The upper and lower bounds for the second search are determined as follows: if the current closest measurement is visually positioned to the left of the target x coordinate, then it becomes the lower bound and the upper bound is set to the closest sample in the sample-set with a larger absolute index to the lower bound. Conversely, if the  current closest measurement lies to the right of the target x coordinate, then it becomes the upper bound and the lower bound is set to the closest sample in the sample-set with a smaller absolute index to the upper bound.

Even though the upper and lower bounds selected for the second pass may contain characters on different lines, the search space is still sorted by distance. The x-search pseudo code shows how samples found to be on different lines to the target y coordinate during the x-search are considered to be more distant regardless of their x coordinates compared to samples that lie on the same line at the target y coordinate.

Some white-space characters are not rendered due to the HTML layout engine collapsing the white-space. When a character is found to be not rendered (where the offset attributes are zero or non-existent), the algorithm sequentially searches in the left direction to discover the nearest occurring rendered character. If the search reaches the lower bound, then the sequential search switches direction and locates the nearest rendered character to the right of the sample. If no other characters are found that are rendered within the upper and lower search space bounds then the search is complete.

The dual binary search algorithm requires the search space to be sorted. There are exceptions to the in-order traversal method for creating a spatially sorted collection of DOM nodes. For example, CSS positioning allows elements to be manually positioned in a web page regardless of where they reside in the DOM tree. CSS Floats are another example that can lead to unordered collections. However positioning styles are usually used for the presentation and structure of a web page rather than actual content. Furthermore the algorithm works within manually positioned elements/floats since an in-order traversal within these elements is spatially ordered.

Homing Dual Binary Search

I had experimented with a homing dual binary search, which is the same as the binary search, except instead of halving the search space for each new sample, the search space is narrowed down to an estimation of the closest absolute index. The estimation step uses the container elements bounds together with previously measured characters to choose a more informed search space split. But this doesnt preform very well, since estimations can’t take in account text wrapping and whitespace collapsing (life would be easy if the characters where uniformly spread throughout the container!). What happens is that the estimations often slightly miss the actual character each split, which sometimes can great reduce the search space, or hardly reduce it at all. So best stick with your vanilla binary search 50/50 split.

Conclusion

You dont have to pre-process the DOM to quickly find a character position in a web page document. If you want a flexible cross browser solution, try using a dual binary search as described by this post. This solution was devised during the days of HTML 4.01 and CSS2.0. You may need to handle more complicated cases with CSS 3.0, I’d imagine it would work just fine with HTML 5, given its basic use of standard DOM features.

Programming Praxis – Coin Change, Part 1, C# Solutions

This post presents C# solutions to a coin change problem as described in http://programmingpraxis.com/2013/05/17/coin-change-part-1.

It is a classic problem from computer science to determine the number of ways in which coins can be combined to form a particular target; as an example, there are 31 ways to form 40 cents from an unlimited supply of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), ranging from the 3-coin set (5 10 25) to the 40-coin set consisting only of pennies.

Your task is to write two functions, one to determine the count and one to determine the list of coins. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

As the original post for this problem states, it appears to be most easily solvable using a recursive approach. Let’s start the thought process of solving such a problem like this. I naturally would begin by figuring out a systematic process of coming up with all the possibilities of combinations. Once the process is devised, you can the deduce an algorithm.

Start out with a simple concrete example. Naturally I thought: “at each step in the process, keep subtracting the largest allowable coin from the remaining total, until you reach a solution”. A coin would be allowable if it is equal or less than the remaining total. So if n = 40:

n = 40, set = []

Step 1: The largest allowable coin is 25 (25 < 40)

n = 15 (40 - 25), set = [25]

Step 2: The largest allowable coin is 10 (10 < 15)

n = 5 (10 - 15), set = [25, 10]

Step 3: The largest allowable coin is 5 (5 < 10)

n = 0 (5 - 5), set = [25, 10, 5]

Done!

Where to from here? Well lets enumerate all solutions with the 25 coin:

25, 10, 5

25, 10, 1, 1, 1, 1, 1

25, 5, 5, 5

25, 5, 5, 1,1,1,1,1

25, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

25, 1,1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

For each successive solution, we are breaking down each coin from the previous solution in as many ways as possible. However you wouldn’t want to break down the same coin in a previous solution more than once. e.g. for set [25,5,5,5] you wouldn’t want break down the coin 5 any more than once: [25, 5, 5, 1,1,1,1,1], [25, 5, 1,1,1,1,1, 5], [25, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1] etc. How do you avoid this? Look at the concrete example of coin sets above. Notice any patterns? There are a few. In relation to these cases we want to avoid, we could avoid duplicating coin sets by ensuring that for each breakdown the new coin selection is less or equal to the previous step’s selected coin (see the concrete example above, all the coins are ordered descendingly). Lets code it using recursion:

public class CoinChange1
{
	private int[] cs = new [] {25, 10, 5, 1};

	private List<ICollection<int>> solutions = new List<ICollection<int>> ();

	public static IList<ICollection<int>> GetCoinSets(int total) {
		// Handle corner case outside of recursive solution
		if (total == 0)
			return new List<ICollection<int>> ();

		// Get all possible sets
		var cc = new CoinChange1 ();
		cc.GetCoinSets (total, 0, new Stack<int>());
		return cc.solutions;
	}

	private void GetCoinSets(int n, int csi, Stack<int> combo) {
	        // Find largest allowable coin (exploiting that cs is ordered descendingly)
		while (cs[csi] > n)
			csi++;
		int c = cs [csi];

		combo.Push (c); // Track coin selection
		if (n == c)
			solutions.Add(combo.ToArray()); // Base case
		else
			GetCoinSets (n - c, csi, combo); // Recursion 1: with a selected coin
		combo.Pop ();

		// Recurse for all other possibilities beyond this point with a combo of smaller coin units
		if(csi < (cs.Length - 1))
			GetCoinSets (n, csi + 1, combo);
	}
}

And there we have it. This problem does have overlapping subsolutions, and so it could possibly be optimized using memoization. However this would add a lot of overhead: as it would mean caching collections of all possible coin subsets, and many memory copy operations to build up new sub-sets off other sub solutions. Sounds more costly than being worthwhile. So we will stick with this solution.

But we are not finished: the problem statement said to write another function to count the total possible coin sets for a given total (n). A naive approach would be to re-use our solution above, and return the length of the collection. But we can do better:

        private int GetCoinSetCount(int n, int csi) {
		while (cs[csi] > n)
			csi++;
		int c = cs [csi];

		int count;
		if (n == c)
			count = 1;
		else
			count = GetCoinSetCount (n - c, csi);

		if(csi < (cs.Length - 1))
			count += GetCoinSetCount (n, csi + 1);

		return count;
	}

I’ve omitted a wrapper function to neatly package the API (passing 0 for csi argument and a sanity check for total = 0). The performance has improved since we don’t need to maintain a list of selected coins throughout the recursive calls. But we can still do better!

Now that we don’t have to deal with passing around complex data per sub solution (lists), and so memoization is worthwhile here:

public class CoinChange1
{
	private Dictionary<ulong, uint> cache = new Dictionary<ulong, uint>();

	public static uint GetCountSetCount(uint total) {
		if (total == 0)
			return 0;
		return new CoinChange1().GetCoinSetCount (total, 0);
	}

	private uint GetCoinSetCount(uint n, byte csi) {
		while (cs[csi] > n)
			csi++;
		uint c = (uint)cs [csi];

		uint count;
		if (n == c) {
			count = 1;
		} else {
			uint nextn = n - c;
			ulong key = ((ulong)nextn << 32) | (ulong)csi;
			if(!cache.TryGetValue(key, out count)) {
				count = GetCoinSetCount (nextn, csi);
				cache[key] = count;
			}
		}

		if(csi < (cs.Length - 1)) {
			ulong key = ((ulong)n << 32) | ((ulong)csi + 1);
			uint subCount;
			if(!cache.TryGetValue(key, out subCount)) {
				subCount = GetCoinSetCount (n, (byte)(csi + 1));
				cache[key] = subCount;
			}
			count += subCount;
		}
		return count;
	}
}

I’ve changed the arguments and return types to unsigned, since I’m making a performance enhancement for the cache key. Since the key is composite (the arguments to the recursive functions), I pack them in a single unsigned long rather than using a Tuple or some custom class/struct. A petty improvement but an improvement nonetheless.