Category Archives: Development - Page 3

Project Euler #6

Project Euler problem #6 is

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

When I first began looking at this problem I wanted to experiment a bit with the Parallel Extensions for .NET, so I started where any parallel algorithm begins: with a sequential algorithm. The algorithm here is rather trivial: Loop over the natural numbers from 1 to 100. In order to sum the squares I will sum the square of each number. In order to square the sum I will sum the numbers and then square them. The difference is the answer. So, first, I came up with two functions: SumOfSquares and SquareOfSums.


My first attempt at these functions ended up something like this:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
static double SumOfSquares(int min, int max) {
    double result = 0;
    for(int x = min; x <= max; x++) {
        result += Math.Pow(x, 2);
     }
     return result;
}
static double SquareOfSums(int min, int max) {
    double result = 0;
    for(int x = min; x <= max; x++) {
        result += x;
    }
    return Math.Pow(result, 2);
}

Both of those functions are very straight forward. My first thought after writing these was, "Hey, why not use some LINQ?" So I did. Here is how the functions change:


1
2
3
4
5
6
static double LinqSumOfSquares(int min, int max) {
    return Enumerable.Range(min, max).Select(d => Math.Pow(d, 2)).Sum();           
}
static double LinqSquareOfSums(int min, int max) {
    return Math.Pow(Enumerable.Range(min, max).Select(d => d).Sum(), 2);    
}

Wow! Talk about incredible, shrinking functions! I love finding a way to make code more succinct, readable, and elegant and these changes seem to have hit the nail on the head! Anyways, that is basically all the pieces for the sequential algorithm. All you have to do is call each of those functions and take the difference. Simple, huh? But the real question is how can we parallelize these bad boys? I have a few thoughts.

  1. Call each function in parallel. In other words let the sumOfSquares and SquareOfSum function run at the same time in different threads.
  2. Parallelize each function invidvidually. In other words leverage the loops inside of each function in order to parallelize them.

So let's take a look at each method using the Parallel Extensions for .NET. The first method is calling each function in parallel. My first thought here was to use Parallel.Invoke in order to call each function at the same time. A little further research quickly revealed that Parallel.Invoke cannot return any values. My initial response to that: "Well that sucks." Luckily there's another class in the Parallel library called Futures. What's a future? From DevX -

"In TPL terms, a Future is basically a task that returns a value. It's like a deferred function. You start it running and then use its value later. If the Future hasn't finished calculating its value by the time you need it, it makes you wait while it finishes."

Sounds good to me. So how do we use futures? Like this:


1
2
3
4
5
6
7
8
static long Problem6Futures(int min, int max) {
 
    Future<double> fSumOfSquares = Future.Create(() => SumOfSquares(min, max));
    Future<double> fSquareOfSums = Future.Create(() => SquareOfSums(min, max));
    double result = fSquareOfSums.Value - fSumOfSquares.Value;
 
    return result;
}

Easy, huh? All you have to remember is that Futures are deferred functions that return values. The result of Future operation gets stored in an object of type Future and the value is stored in Object.Value. So how about the second method of parallelizing this algorithm? Well, it's even easier because of PLINQ - or Parallel LINQ. Let's see what it looks like.


1
2
3
4
5
6
static double ParallelSumOfSquares(int min, int max) {
    return Enumerable.Range(min, max).AsParallel().Select(d => Math.Pow(d, 2)).Sum();
}
static double ParallelSquareOfSums(int min, int max) {
    return Math.Pow(Enumerable.Range(min, max).AsParallel().Sum(), 2);
}

Hah! Even easier! All that I did was add .AsParrallel() to our data. That tells LINQ to do the processing in parallel!

So, there's Project Euler Problem #6 for you. Was it a hard problem? Not really. Are you going to see major performance results through the parallelization of this algorithm? No. But you gotta' start somewhere when you're learning how to parallelize algorithms using a new library. Today I used Futures and PLINQ and that sound's like a pretty solid start to me.

Project Euler #3

Project Euler #3 is :

Find the largest prime factor of a composite number.

My first attempt at this whipped up some typical code that simply brute forced my way to the solution. My code looked like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static void Problem3() {
    long n = 600851475143;
    int factor = 2;
    int lastFactor = 1;
 
 
    if(n % 2 == 0) {
        lastFactor = 2;
        n = n / 2;
        while(n % 2 == 0) {
            n = n / 2;
        }
     } else {
         lastFactor = 1;
     }
     factor = 3;
 
     double maxFactor = Math.Sqrt(n);
     while(n > 1 && factor <= maxFactor) {
          if(n % factor == 0) {
              n = n / factor;
              lastFactor = factor;
              while(n % factor == 0) {
                  n = n / factor;
              }
              maxFactor = Math.Sqrt(n);
          }
          factor += 2;
      }
 
      if(n == 1) {
          Console.Write(lastFactor.ToString() + " ");
      } else {
          Console.Write(n.ToString() + " ");
      }
}



Not very elegant, but it works. So I set out to find something a bit prettier and I came across I LINQ solution here. All I did was tack on the .AsParallel() in order to give it a little speed boost. The code looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static void LinqProblem3() {
    long largeNumber = 600851475143;
    var allPrimeFactors = from p in Primes.PrimeFactors(largeNumber).AsParallel()
                                 orderby p descending
                                 select p;
 
    foreach(var f in allPrimeFactors){
        Console.WriteLine(f);
    }
}
 
public static class Primes {
 
    // Find all prime factors.
    public static IEnumerable<int> PrimeFactors(long number) {
        // Start by removing the lowest prime (2)
        return MorePrimeFactors(number, 2);
    }
 
    // This recursive method finds all prime factors.
    private static IEnumerable<int> MorePrimeFactors(long number, int factor) {
        // Find the next prime factor
	while(number % factor != 0)
	    factor++;
	// Return it.
	yield return factor;
 
	// look again...
	if(number > factor)
		// recursively look for this factor again, using Num/factor
		// as the new big number
		foreach(int factors in MorePrimeFactors(number / factor, factor))
			yield return factors;
	}
}

Left Joins in LINQ

For some reason it seems that I often need to perform a left join in LINQ. Every time I need to do this I find myself scouring the web one more time in order to remember how a left join works in LINQ. So how does it work? The best example that I've found is here. The example looks something like this:


1
2
3
4
5
6
7
8
9
10
var list = from r in dc.tblRooms
             join ui in dc.tblUserInfos
             on r.UserName equals ui.UserName into userrooms
             where r.CourseID == 1848
             from ur in userrooms.DefaultIfEmpty()
             select new{
                 FirstName = (ur.FirstName == null) ? "N/A" : ur.FirstName,
                 LastName = (ur.LastName == null) ? "N/A" : ur.LastName,
                 RoomName = r.Name
              };

I like this example a lot because it is very straight forward. Personally I would like to make the statement a bit more generic. In order to do that all we need to remember is that every Left Join has a left table A and a right table B. All the results from the A will be returned regardless of the join with B. In my example I will call table A the LEFT_TABLE and table B the RIGHT_TABLE.


1
2
3
4
5
6
var list =  from LT in LEFT_TABLE
	      join RT in RIGHT_TABLE
	      on LT.key equals RT.KEY into NEW_TABLE
              where <CONDITIONS>
              from NT in NEW_TABLE.DefaultIfEmpty()
              <SELECT_STATEMENT>;

The only problem that may occur with this left join occurs with the DefaultIfEmpty() operator. A better practice would be to pass in a default value so that we can know what to expect in return.

The Future of Web Pages

This morning I came across this jQuery library and it got me to thinking a little bit. All of the web sites that I currently have coded ( I don't really do the design) tend to use .NET or PHP that is mashed up with some Javascript here and there.


I'm wondering why we tend to still use PHP and .NET except for things that are absolutely on the back end. Why would I use .NET or PHP to manipulate elements in a page when I can just use JavaScript?


Maybe the web community should start developing pages that are JavaScript run and call PHP/.NET WebServices. That puts all the processing for display on the JS and all the data manipulation and retrieval where it should be - on the server.


Any thoughts?

Syncing WordPress Databases

Whenever I'm doing any WordPress development, I eventually have the need to sync the data between the current dev server, possibly a staging server, and a live server. What's the easiest way to move a WordPress database between 2 servers?


Let's start this example by saying that we have 2 servers: Dev and Live. Each server has a mostly identical WordPress installation and each server has it's own database. In order to sync the initial database from Dev to Live the following steps may be used:

  1. Use PHPMyAdmin to export the Dev database as a file
  2. Use PHPMyAdmin to export the Live database as a file (this is a backup, just in case)
  3. Import the Dev Database into the Live Database using PHPMyAdmin
  4. Run the following 5 SQL commands in order to update the domain name in your site:
    UPDATE wp_multirss SET URL=REPLACE(URL,'Dev_Address','Live_Address');
    UPDATE wp_multirss SET Favicon=REPLACE(Favicon,'Dev_Address','Live_Address');
    UPDATE wp_posts SET post_content=REPLACE(post_content,'Dev_Address','Live_Address');
    UPDATE wp_posts SET guid=REPLACE(guid,'Dev_Address','Live_Address');
    UPDATE wp_options SET option_value=REPLACE(option_value,'Dev_Address','Live_Address');
  5. And now, as long as you've written all your relative links correctly inside of your content, you're finished!

Once you have the initial transfer completed, future transfer are much simpler. Then you only need to complete the above steps by exporting, dropping, and importing the tables that are relevant to the changes that have been made. What tables are those? Honestly, it depends on what you have changed since last time. The best way to figure this out is to go to the Database Description over at WordPress.org to see what you need to move.


Happy migrating!

Project Euler #2

Problem #2 in the Project Euler series is:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void Problem2() {
    int term1 = 0;
    int term2 = 1;
    int term3 = 1;
    int max = 4000000;
    double sum = 0;
 
    while(term1 < max && term2 < max && term3 < max) {
        term1 = term2 + term3;
        term2 = term1 + term3;
        term3 = term2 + term1;
 
        if(term1 % 2 == 0) {
            sum += term1;
        }
        if(term2 % 2 == 0) {
            sum += term2;
         }
         if(term3 % 2 == 0) {
            sum += term3;
         }
 
    }
}

Capitalize A String in C#

Capitalizing a string is a rather trivial task in C#. There are 2 ways to approach single word capitalization where each method includes 3 steps. Method 1 uses only strings and string methods while method 2 treats the letter to be capitalized as a char.

Method 1:

  1. Get the first character as a string ( stringToCapitalize.Substring(0,1) )
  2. Transform the first character to uppercase ( stringToCapitalize.Substring(0,1).ToUpper() )
  3. Append the rest of the string ( stringToCapitalize.Substring(0,1).ToUpper() + stringToCapitalize.Substring(1) )


1
2
3
4
5
6
7
8
9
10
public static string Capitalize(string toCapitalize) {
    try {
        if(toCapitalize.Length > 1) {
            toCapitalize = toCapitalize.Substring(0, 1).ToUpper() + toCapitalize.Substring(1);
        }
    } catch(Exception ex) {
        ExceptionHandling.ExceptionLogging(ex, "Error:Capitalize.");
    }
    return toCapitalize;
}


Method 2:

  1. Get the first character as a char ( stringToCapitalize[0] )
  2. Transform the first character to uppercase using the char.toUpper method ( char.toUpper(stringToCapitalize[0]) )
  3. Append the rest of the string ( char.toUpper(stringToCapitalize.Substring[0]) + stringToCapitalize.Substring(1) )


1
2
3
4
5
6
7
8
9
10
public static string Capitalize(string toCapitalize) {
    try {
        if(toCapitalize.Length > 1) {
            toCapitalize = char.ToUpper(toCapitalize[0]) + toCapitalize.Substring(1);
        }
    } catch(Exception ex) {
        ExceptionHandling.ExceptionLogging(ex, "Error:Capitalize.");
    }
    return toCapitalize;
}

Using either of these methods you could create an extension method as well. Something like this:

1
2
3
4
5
6
7
8
9
10
public static class MyExtensions
{
    public static string Capitalize(this String toCapitalize)
    {
        if(toCapitalize.Length > 1) {
            toCapitalize = toCapitalize.Substring(0, 1).ToUpper() + toCapitalize.Substring(1);
        }
        return toCapitalize;
    }
}

Replace HTML Text without Regular Expressions

One of my latest job requirements was replacing some basic American English words with some more British words ( color-colour, favor-favour, etc.). The original iteration of this project used JavaScript to scan the page content and the replace the words properly. The only problem with this version is that AJAX calls would make browsers complain about breaking the DOM. The script for this iteration was:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function replaceTerms(){	
	var searchArray = new Array("favors","labors","colors","favor","labor","color");
	var replaceArray = new Array("favours","labours","colours","favour","labour","colour");
 
	if (!document.body || typeof(document.body.innerHTML) == "undefined") {
		//alert("Sorry, for some reason the text of this page is unavailable. Searching will not work.");
		return false;
	}
 
	var bodyText = document.body.innerHTML;
	for (var i = 0; i < searchArray.length; i++) {
		bodyText = doReplace(bodyText, searchArray[i], replaceArray[i]);
	}
 
	//document.body.innerHTML = bodyText;
	return true;
}
 
function doReplace(bodyText, searchTerm, replaceWith) {
 
	// find all occurences of the search term in the given text, and add some "highlight" tags to them (we're not using a
	// regular expression search, because we want to filter out matches that occur within HTML tags and script blocks, so
	// we have to do a little extra validation)
 
	var newText = "";
	var i = -1;
	var lcSearchTerm = searchTerm.toLowerCase();
	var lcBodyText = bodyText.toLowerCase();
 
	while (bodyText.length > 0) {
 
		//Get index of search term
		i = lcBodyText.indexOf(lcSearchTerm, i+1);
 
		//if we can't fine it, replace the newText with the BodyText and return
		if (i < 0) {
			newText += bodyText;
			bodyText = "";
		} else {
 
			// skip anything inside an HTML tag
			if (bodyText.lastIndexOf(">", i) >= bodyText.lastIndexOf("<", i)) {
				// skip anything inside a <script> block
				if (lcBodyText.lastIndexOf("/script>", i) >= lcBodyText.lastIndexOf("<script", i)) {
 
					//Get Ascii Representation
					var	charCode = bodyText.charAt(i).charCodeAt(0);
 
					//Is this uppercase
					var isUpper = (charCode >= 65 && charCode <= 90);
 
					//Do replacing
					if(isUpper){
						newText += bodyText.substring(0, i) +  replaceWith.charAt(0).toUpperCase() + replaceWith.substr(1) + " ";
					}else{
						newText += bodyText.substring(0, i) +  replaceWith + " ";
					}
					bodyText = bodyText.substr(i + searchTerm.length);
					lcBodyText = bodyText.toLowerCase();
					i = -1;
				}
			}
		}
	}
 
	return newText;
}

Since we could not have our site breaking the DOM, the filtering was moved into the Visual Basic code behind of the project. The trick to filtering content in .NET is to leverage the Response.Filter property along with a custom class. This class will intercept the content and re-write it to however you see fit. More details on this can be found here.

The first version of our filter used regular expressions in order to replace the appropriate words in the page. This also caused a severe problem: The RegEx was replacing properties of tags, css, and control names ( understand that the word 'color' was being replaced ). My first attempt at a solution was to find the proper RegEx to replace words only inside paragraph tags. It turns out that writing a RegEx to parse HTML is nearly impossible ;)

The solution? The original JavaScript code was migrated into the Visual Basic filter. This worked like a charm as it was using no RegExes and was also based upon the original code that worked. The final Visual Basic code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
Private Function doReplace(ByVal bodyText As String, ByVal searchTerm As String, ByVal replaceWith As String) As String
	Private Function doReplace(ByVal bodyText As String, ByVal searchTerm As String, ByVal replaceWith As String) As String
	Dim newText As String = ""
	Dim i As Integer = -1
	Dim lcSearchTerm As String = searchTerm.ToLower()
	Dim lcBodyText As String = bodyText.ToLower()
 
	While bodyText.Length > 0
		'Get the index of the search term
		i = lcBodyText.IndexOf(lcSearchTerm, i + 1)
 
		'If it isn't there, just return
		If i < 0 Then
			newText += bodyText
			bodyText = ""
		Else
			'Avoid tags
			If bodyText.LastIndexOf(">", i) >= bodyText.LastIndexOf("<", i) Then
				'Avoid scripts
				If lcBodyText.LastIndexOf("/script>", i) >= lcBodyText.LastIndexOf("<script", i) Then
					'Is the first character uppercase?
					Dim isUpper As Boolean = Char.IsUpper(bodyText.Chars(i))
 
					'If it is, then capitalize the replacement
					If isUpper Then
						newText += bodyText.Substring(0, i) + Char.ToUpper(replaceWith.Chars(0)) + replaceWith.Substring(1) + " "
					Else
						newText += bodyText.Substring(0, i) + replaceWith + " "
					End If
 
					'Truncate body text
					bodyText = bodyText.Substring(i + searchTerm.Length())
 
					'Reset current text
					lcBodyText = bodyText.ToLower()
					i = -1
				End If
			End If
		End If
	End While
 
	Return newText
End Function

The lesson learned here? Think before you code. If I would have simply migrated the JavaScript code I would have saved a lot of time.

ISAPI Rewrite 3 with WordPress

If you're using these 2 tools together, you have to make small effort in order to get rewriting working properly. 

  1. Do what it says here
  2. Open wp-includes/classes.php
  3. Go to line 158. You should see something like $req_uri = $_SERVER['REQUEST_URI'];
  4. Replace that with $req_uri = $_SERVER['HTTP_X_REWRITE_URL'];
  5. You're good to go!

Run Javascript when UpdatePanel request ends

This was helpful.