I Solve Problems in the Shower

I like to solve problems. It’s in my blood. I have a feeling if you are in this industry, it’s in your blood too. I think this is why I was drawn to Math and Physics growing up, and ended up studying them in college (along with CompSci of course). I think this is also why I like the type of games that I like to play. RPG’s, and RTS’s tend to be problem solving type games. Think of the missions you are assigned, or Civilization and SimCity. Those are problem simulators. Anyway…

When a problem gets in my head, I can’t shake it. There are times when I will hit a roadblock for days. One of my strategies is to take a break from the problem, get my mind off it. When I come back to the problem I usually have some fresh ideas on how to approach it. The time off gives me the ability to come back with a different perspective on the problem. That's why, when meeting with customers, I like to give some initial feedback, and then spend a day or two digesting what we talked about. This time gives me the perspective to give the best feedback I can.

Another approach I use is to list out all of the possible solutions on a whiteboard, aka Solo Brainstorming. This helps me get my thoughts together, gets some kinetics into the equation (Brain mapping software doesn’t seem to work for me in this scenario). The ideas seem to build on each other, and it makes for an easy ‘rule out the crap' process as well.

But my best solutions to problems, the biggest breakthroughs I have are always in the shower. I don’t know why. I think the isolation, the removal of distractions maybe? Anyway, that's where my best thinking happens.

There were many times when I would go into work, and start out with :

“I was thinking about you in the shower this morning, and I think we should …”

As part of keeping my problem solving skills fresh, I thought I would take a crack at the www.projecteurler.net problems. I got to the seventh problem in a few hours. One of the problems, #3, is stated:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Side note: At one point I had to refactor my code from int to Int64 because of the size of the number. I should have seen that in the first place.

At the surface, the algorithm to use is straight forward. Find the factors for the number, then determine which of those is prime, then determine the largest one of those. This is of course a brute force solution. We often just use brute force because cpu’s and RAM are so cheap today.

While the first order goal of the problems on the list is to solve them, your code is also expected to solve them in a minute. You don’t upload your code, you just type in the final answer. People post their code in the forum dedicated to each problem. Many people use assembly. Brings me back to the college days.

My first cut at the code took a while to calculate this, as a matter of fact, a whole conference call on the upcoming fiscal year.

While I didn’t use a timer, I think I didn’t make the one minute mark.

My process for finding factors was as tight as it could be. Finding primes is a brute force thing, there isn’t a formula that will tell you the nth prime number. That’s why there are those distributed computing screen savers out there.

I considered using the concurrency framework to split the work across my cores. But that would be a new fx to learn, and I wasn’t sure it would help.

So I started my isPrime loop at the top of list! While there were hundreds of factors, and only a few of them were primes, I figured the largest prime factor was likely to be found on the upper end of the list.

Didn’t help, time wise at least.

So I took a shower (advantage of working from home). By the end, I had come up with ways of speeding up the process.

I recalled that there were better ways for testing the primality of a number besides making sure it didn’t have any other divisors besides 1 and n. This lead to finding out a different way of approaching the problem. I looked up the math, and implemented the code. It was done in only a few minutes.

You basically divide the number by primes until you have nothing left. Track the primes you used, and the answer is the largest one in the list. This is an inversion of the original approach. Why find all of the factors? Just test each prime that is less than the target number to see if it is a factor. Then, instead of testing hundreds of numbers for primality, I am only checking a few numbers.

I had an isPrime method.I did need to write a new helper method. I implemented a nextPrime method, that given any number, finds the next largest number that is a prime. I implemented a few optimizations here as well. For example, not checking even numbers past two.

I am sure I could tighten this code further, but it is ‘MeWare’, and I wanted to move on to the next problem.

I love solving problems.

private void button1_Click(object sender, RoutedEventArgs e)
{
    List<Int64> answers = new List<Int64>();

    Int64 remaining = Convert.ToInt64(textBox1.Text);
    Int64 divisor = 2;

    while (remaining > 3)
    {
        if (remaining % divisor == 0)
        {
            answers.Add(divisor);
            remaining = remaining / divisor;
        }
        else
            divisor = nextPrime(divisor);
    }

}

public static Int64 nextPrime(Int64 start)
        {
            Int64 numToCheck = 0;

            if (start > 2)
            {
                if (start % 2 == 0)
                    numToCheck = start + 2;
                else
                    numToCheck = start + 1;
            }
            else
                numToCheck = 3;

            while (!isPrime(numToCheck))
            {
                numToCheck++;
            }

            return numToCheck--;
        }

public static bool isPrime(Int64 target)
        { 
            // assumes target is > 2. I know, but it’s meware.

            if (target % 2 == 0)
                return false;

            for (Int64 i = 3; i < target; i=i+2)
            {
                if (target % i == 0)
                    return false;
            }

            return true;
        }