Project Euler

Project Euler Problem Three

Optimus PrimeIt has been almost two years since I tackled Project Euler Problems One and Two. I really wanted to get back into it, so there really is no time like the present to do the work. I’m on my Mac Mini right now, so I developed this in C#.Net using MonoDevelop.

This problem needs us to find the largest prime factor of a very large number. Obviously, to do this, you need to be able to generate a set of prime numbers to work with. I have an IsPrime method that uses a very brute force method (with the shortcut of only checking as high as the square root of the number). I Googled around for ways to generate primes and looked into the Sieve of Eratosthenes, but it was a little complicated for the time I had allotted myself to work on this problem (basically the ten minutes until I had to put my son to bed). Plus, it turns out that this entire piece of code runs in under a second on my several year old Mac Mini, so there was no need to optimize yet. I know that later Project Euler problems also deal in primes, so I may need to break it out then.

Once I had that method in place, it was really a simple matter of working up to the square root of the number in the problem, 600851475143, using the same shortcut. If the number in my loop was prime and evenly divided into our number, I stored it as the current largest number. When I was done, whatever number was currently in that variable was our champion. Pretty simple logic.


using System;

namespace ProjectEuler
{
	/// <summary>
	/// The prime factors of 13195 are 5, 7, 13 and 29.
	///  What is the largest prime factor of the number 600851475143 ?
	/// http://projecteuler.net/index.php?section=problems&id=3
	///
	/// The answer is 6857
	/// </summary>
	public class Problem3
	{
		protected static double number = 600851475143;
		
		public static void Main(string[] args)
		{
			double limit = Math.Floor(Math.Sqrt(number));
			double currentLargestPrime = 0;

			for (double i = 2; i <= limit; i++)
			{
				if (IsPrime(i) && (number % i == 0))
				{
					currentLargestPrime = i;
				}
			}			
			
			Console.WriteLine(currentLargestPrime);
		}

		public static bool IsPrime(double n)
		{
			if (n%2 == 0) return false;

			var upperLimit = Math.Floor(Math.Sqrt(n));

			for (double i = 3; i <= upperLimit; i++)
			{
				if (n % i == 0) return false;
			}

			return true;
		}
	}
}

Have you attempted this problem yet? What is your solution? I’d love to see them. You can post it in the comments or post a link if you’ve blogged it already.

Windows Phone 7

Windows Phone 7 Launch Event

I’m excited about the new Windows Phone 7 device, especially developing for it. I’ve written two blogs posts about it as of this date (Filed here) and I plan on writing many more.

I also plan on buying a Windows Phone 7 when it launches and getting as many apps as I can in the marketplace.

Microsoft has long shown that it is very focused on developers and always does launch events up big. As such, the launch events that are available here:

Windows Phone 7 Launch Event - Click for Details (Edit: Link removed, since it was taken down)

are sure to be awesome.

I’ve also added a small banner in my sidebar to stay up while the events are going off for two reasons. 1) There is a contest and 2) My hope is that a lot of developers will get excited and get tons of fantastic apps in the marketplace.

Go download the tools and let’s make this platform great!

Agile

The Case for Requirements

RequirementsI was recently reading through some of my backlog of Dr. Dobb’s Journals (a PDF I receive monthly) and came across an article entitled The Requirements Payoff by Karl Wiegers. I’ve archived a copy of the PDF here and it can be found on pages 5-6.

A lot of people seem to equate “requirements gathering” with “big design up front”, which is now often vilified as being antiquated and bloated. Nothing could be further from the truth (about requirements, not BDUF). In the book Agile Principles, Patterns, and Practices in C#, Uncle Bob talks about practicing Agile in a .Net world. In every one of his examples, you have to know what your requirements are ahead of time. The process goes as follows:

  1. Gather requirements
  2. Estimate requirements to determine length of project
  3. Work requirements in iterations
  4. Gauge velocity in coding requirements against estimate
  5. Determine whether your velocity requires you to either cut requirements or extend timelines
  6. Lather, rinse, repeat

You see that the agile process doesn’t work without requirements. In the article, Wiegers says that according to a 1997 study, “Thirty percent or more of the total effort spent on most projects goes into rework, and requirement errors can consume 70% to 85% of all project rework costs”. That is a big penalty to pay for laziness or ineptitude in early requirements gathering. This doesn’t mean that the requirements collected at the beginning are rigid and inflexible. They are just a starting point. However, changing the requirements changes the estimate and also the expected cost in time and resources and can fall under the statistic quoted above.

Requirements are essential to TDD and BDD advocates, as well. The requirements are what a vast majority of the tests are written against. For instance, if the requirement is that the user name is an email address then a programmer will likely write a test (both positive and negative) verifying that the program behaves as expected when presented with an email address or a non-email address, etc. Without that requirement, a test might only be written to ensure the user name wasn’t blank and the stake-holders might be upset when the program behaves differently than they imagined in their heads (and you failed to ferret out in requirements gathering).

It is true that gathering proper requirements in advance costs time. Wiegers sums it up best, however, when he says, “These practices aren’t free, but they’re cheaper than waiting until the end of a project or iteration, and then fixing all the problems. The case for solid requirements practices is an economic one. With requirements, it’s not ‘You can pay me now, or you can pay me later.’ Instead, it’s ‘You can pay me now, or you can pay me a whole lot more later.'”

Code Tips

The Importance of jQuery ajaxSetup Cache

Johnny Cache
Just a quick note to document a “gotcha” that cost me quite a bit of time today. I am currently working on my company’s second Asp.Net MVC 2.0 application. Our first one was a huge success and (to me) MVC is way more fun and productive than WebForms, so doing as much new development using MVC instead of WebForms is a no-brainer.

Being good MVC-ites, we are doing a lot of AJAX calls. Since we are extensively using the jQuery library, we do a lot of $.ajax() and $(someSelector).load() in our code to make calls. Today, I was calling code like the following:

$('#theDivToUpdate').load('/Our/Url/Product/Edit/', {id : ourIdParameter}, function() { /* callback logic */ });

That code will call the Edit action on the ProductController and pass in the id of the product to edit. The controller gets the product details and then returns a partial to the page, which is then inserted into the div. I was trying to debug the controller action, but after I had edited a product once, the breakpoint wouldn’t catch anymore. I figured that I was dealing with a caching issue and the method wasn’t even being called, but I couldn’t find where I even had output caching configured in MVC.

I knew that I wasn’t having this problem in our previous application, so I started comparing files and looking for answers. Nothing was really giving me any clues, and everything appeared to be set up the same way. Finally, in exasperation, I did a “Find in Files” in Visual Studio in the other solution for just the word “cache” since searching for “outputcache” had failed me.

I dug through tons of results and then finally came across this little gem:

$.ajaxSetup({ cache: false });

I had seen that in the last application, had read the documentation on ajaxSetup, but I didn’t really understand all of the ramifications of it.

Apparently, jQuery in all of its awesomeness will actually cache ajax calls for you to speed up your page. That’s definitely awesome, but unexpected caching can certainly screw up your day.

Book Reviews

Contented Cows

Contented Cows Give Better Milk
I got the paperback version of Contented Cows Give Better Milk 8 or 9 years ago when I was working for a large financial institution. It was popular at the time to buy these by the crate and give them to anyone who was responsible for people. So, I did like any responsible employee… and finally got around to reading it this week. Better late than never, right? I want to warn you that this post is going to run a little long because I’m going to include several quotes from the book after I share some general thoughts and before I conclude.

I’m not much of a “business book” guy. In my experience, too often these books are “educationally low fat” and more about stuff that just about everyone already knows. Even this book draws some conclusions that I had already reached, however I know that I’ve worked for many employers that still don’t “get it”. In my opinion, this books deserves the reputation it gained and I think if more employers followed its guidelines, the average worker would be considerably better off. It covers topics like employee hiring and retention, productivity, corporate reputation, and enabling employees to do something great. Let me let the authors speak for themselves. (My thoughts or interjections are in bold italic)

On Hiring

“Contrary to popular belief, there really is an ample supply of conscientious, hardworking, capable, honest people.”  “You can (and must) find others like them.  You’ve got to expend a little effort doing it because ‘eagles don’t flock,’ but they are out there.” – p.37
(I love this quote, especially the notion that “eagles don’t flock”)

On Training

“We have an earnings problem, so we’re going to work out way out of it by ‘dumbing down’ the organization with less skilled, less competent people! Now the only problem will be to find dumb customers to purchase our goods and services and even dumber investors to buy our stock!” – p.154

In talking about an organization’s fading training program for air traffic controllers…
“At some point this practice was amended in favor of a train-to-proficiency approach, and the end result is now that nobody ever gets sent home or, as our friend Alex Nicholas calls it, de-selected.  Instead, you wind up with a situation where people who would have washed out under the old system are still in training and on the job years later, and every day must have their work carefully overseen by an experienced controller.  A competent employee ends up babysitting an inept one, making them both, at best, marginally productive; and both are making the same money!” – pp. 160-161
How many of you have l i v e d this?

“Why is it that no one ever ‘flunks’ a corporate training program?” – p.165

On Corporate Policies

“If you believe that most people who come to work for you are lazy, stupid, untrustworthy, inept, and just downright contrary, that assumption can’t help but show up in the way you run your business.  You’ll have all kinds of rules and regulations designed for numbskulls who couldn’t pour milk out of a boot with the directions printed on the heel.  You’ll no doubt have a supervisor for every six or seven folks, and will inevitably attract just the kind of people who will live down to your assumptions.” – p.35

Talking about how companies make mistakes and how policies can ruin a company:
“We do it through policies that are just plain dumb; systems that treat intelligent people like they’re complete morons; and cultures which ensue that no mistake goes unpunished.” – p.168

“In their private lives outside of work, your employees are heads of families, civic leaders, army reserve officers, mortgage holders, and a host of other things. Day in and day out they somehow manage to feed themselves and their families, pay their bills on time, stay out of jail, and behave normally by most reasonable standards.  In short, they tend to be rather competent individuals with a clear picture of the difference between right and wrong.  Why then, when at work, must they face a continual barrage of not-so-subtle signs of our mistrust in them as individuals?” – p.183

“If you’re unwilling to give credence to the employer/employee covenant by taking this important step, then by all means save your time, money, and breath.  Go out and hire dummies whenever your company has a job vacancy, pay them as little as possible, and don’t even think about training them–just hire a supervisor to stand guard over every two to three people.” – p.192
Wow… I know some places where this is basically the policy!

“There was no correlation between the reviews and terminations.”  Only three out of 986 people let go for poor performance received poor ratings on their prior review. “Incredibly, roughly two-thirds of these same people had also received merit increases in the six months preceding their termination!” – p.101

On Reputation

“Organizations which don’t measure up tend to be viewed as an employer of last resort; nobody with any brains, ability, or motivation wants to work there!  When this occurs, only two things can happen.  Either the organization is forced to pay market-premium wages and salaries in an attempt to secure better applicants, or it must accept the lower quality applicants, or do both” – p. 25

“We submit that inordinately high wages, salaries, and unwarranted benefits not only aren’t the answer, they are often a large part of the problem.  Moreover, they are often used as a counter-balance or way of compensating for serious deficiencies elsewhere in the organization.” – p.93

My Conclusion

Certainly not every developer is going to have an opportunity during their career to define many of these policies at their organization. However, with that said, we should not also have our heads in the sand when it comes to business. We should also remember that a strong majority of us are not paid to make software for software’s sake. We are paid to solve a business problem. These principles can help us find good solid companies to work for as well as making sure that we do our part to make the company great while we are there via the software that we write.