RSS Feed Subscribe to RSS Feed

 

Project Euler: Problem 5 (in Java)

Problem 5 in Project Euler is as follows:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Read my solution below

Tags:

Hiatus

It’s been a while since I posted last. Wedding planning (7 weeks to go…) and work have been getting the better of me. I have some ideas for future posts, but until I get the wedding out of the way, things are likely to be quieter. But I will post my next Project Euler solution soon at least…

Project Euler: Problem 4 (in Groovy)

Problem 4 in Project Euler is as follows:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

I found this problem significantly easier than problem 3, thankfully.

My first step was to write a helper method:


	boolean isPalindrome(int num)

My first attempt was, as usual, the brute force approach. Namely, go through every number from 100 to 999 and for each, multiply it by every number between 100 and 999. Check if the result of each of the roughly one million calculations is a palindrome – and store it if it is the biggest one yet.

My next approach was better and involved starting from the top (999 to 100) instead of the other way round. This means we can check if the largest palindrome we could possible find is smaller than what we have already found, thereby avoiding a large number of useless calculations.

This gave me a solution that runs in approx 500ms on my local PC.

Here is my final solution:


int largestPalindrome = 0;
for (i in 999..100) {			
	if ( (i*i) < largestPalindrome) {
		//the largest possible number we can now find (i*i) 
		//is smaller than the biggest palindrome already found
		break;
	}
	for (j in i..100) {
		int candidate = i*j;
		if ( candidate < largestPalindrome) {
			//largest number we can now find in this inner loop
			//is smaller than the biggest palindrome already found
			break;
		}
		if (isPalindrome(candidate)) {
			if (candidate>largestPalindrome) {
				largestPalindrome = candidate;
				break;//no point checking smaller numbers of j
			}
		} 
	}
}
println("largestPalindrome);

And finally, my isPalindrome method:


public static boolean isPalindrome(Integer num) {
	boolean isPalindrome=true;
	char[] numChars = num.toString().toCharArray();
	int endPoint = numChars.length() - 1;
	int midPoint = numChars.length() / 2;
	for (i in 0..midPoint) {
		char a = numChars[i];
		char b = numChars[endPoint-i];
		if (a != b) {
			isPalindrome=false;
			break;
		}
	}
	return isPalindrome;
}

Tags: ,

Project Euler: Problem 3

Problem 3 in Project Euler is as follows:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

I noticed some performance issues with Groovy when I was working on this solution. I will blog about my findings later (Update: see here), suffice to say I am switching to straight Java for this solution.

After experimenting with a brute force approach, I finally came up with this solution. It is not the most elegant, but it works (in <100ms).


long x = 600851475143L; 
long max = x / 2;
long factor = x;
long lastFactor = x;
for (long i=2; i= lastFactor-1) {
		for (long j=factor; j>2; j--) {
			i++;
			remainder = x % j;
			if (remainder == 0) {
				if (eule3.isPrime(j)) {
					printAndExit(j);
				}			
			}
		}
	}
}

There are 2 main parts to the solution. The first loop starts at x/2 (since no factor of x can be greater than x/2). Basically we are checking if x/2 (rounded) is a factor of x. Then 3, then 4 etc. And when we find a number that is a factor, we check if it is prime (if so, we stop obviously). So, for example, we check if 50, 33, 25 are factors of x.

This approach works great, until a certain point, which is when we switch into the second loop. Basically, it becomes more inefficient to start checking if sequential numbers are factors of x.

Again, not the most efficient algorithm, or very well explained! But I have spent enough time on this one.

On to Problem 4

Tags:

Project Euler, Problem 2 (in Groovy/Java)

Problem 2 in Project Euler is as follows:

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.

I found it fairly easy to code a basic solution to this problem:

 
	    def fibSeries = [0,1]
	    int sumOfEvenNums = 0  
	    int i = 0
	    while (fibSeries[i]<=4000000) {    
	       i = fibSeries.size
	       fibSeries[i] = fibSeries[i-1]+fibSeries[i-2]           
	       if (fibSeries[i]%2==0) {            
	    	   sumOfEvenNums+=fibSeries[i]
	       }           
	    }
	    println("Total = " + sumOfEvenNums)

This ran relatively quickly (~100ms), so I submitted my answer on projecteuler.net and it was confirmed as correct.

With heinsight, I realise that it is unnecessary for me to store the entire sequence of numbers (in fibSeries). I just need to store 3 numbers: the latest and the previous 2.

After checking the solution notes, there is of course a more 'perfect' solution. Reaching it involves making 2 breakthroughs, which I admit I didn't make on my own!

Breakthrough 1
The first breakthrough is to see the pattern (how could I have missed it!) that only every 3rd number is even, meaning we can safely ignore the rest. The provided solution says that this is easy to prove (I have no idea how to - perhaps a step for another day). But assuming this to be true, the code can be rewritten to


	    int a,b,c
	    b = 1 //1st seed value
	    c = 1 //2nd seed value
	    int sumOfEvenNums = 0
	    while (c<=4000000) {    
	       a=b+c
	       b=c+a
	       c=a+b          
	       sumOfEvenNums+=a
	    }
	    println("Total = " + sumOfEvenNums)

Breakthrough 2
The second, and waaay more difficult breakthrough is to spot (and prove!) that there is a pattern in the even numbers. If you look at them,
2, 8, 34, 144, 610, ...
They obey following recursive relation:
E(n)=4*E(n-1)+E(n-2).
e.g. 144=4(34) + 8
and 34 = 4(8) + 2
It can be proved that for the Fibonacci numbers, the formula F(n)=4*F(n-3)+F(n-6) holds true (I even managed to get the proof of this myself, after a little prodding).

So, this leaves the following 'ultimate' solution:


	    int a = 0
	    int b = 8 //1st seed value
	    int c = 2 //2nd seed value
	    int sumOfEvenNums = b+c
	    while (true) {    
	       a=(4*b)+c
	       if (a>4000000) break
	       sumOfEvenNums+=a
	       c=b
	       b=a	       
	    }
	    println("Total = " + sumOfEvenNums)

I am sure this could even be rewritten in a more elegant form. Especially if Groovy supported a do..while loop.

Anyway, on to Problem#3...

Tags: ,

Find files in Unix

I frequently end up searching an entire directory for an elusive file and I can never remember the exact command structure, so posting here:

    find /dir/to/search -name "filename.ext" 2>/dev/null

And wildcards are allowed. e.g.

    find . -name "filename.*" 2>/dev/null

The latter command searches the current directory AND all sub directories.

The ‘2>/dev/null’ avoids those annoying “find: cannot read dir …: Permission denied” errors.
You can even simplify it by creating your own find.sh script that takes the file name as a parameter:

    #!/bin/bash
    echo "Searching for files called $1 in current dir and all sub-dirs"
    find . -name "$1" 2>/dev/null

Meaning you just need to call, for example:

    find filename.*

Also, if you want to search for files containing specific text, try

    find /dir/to/search -exec grep -il "txtToSearchFor" {} \;

The “-il” means ignore case and print only the names of files with matching lines (as opposed to the line contents).

Update 4 May 2014: I have added variations of these scripts to my scripts repo on Github. Specifically findf (find files) and findt (find text in files);

See also:

Tags: , , , ,

Project Euler, Problem 1 (in Groovy/Java)

I have been wanting to get up to speed with Groovy for while but hadn’t really found a good excuse. So when I came across Project Euler, I decided to try to solve the problems using Groovy.

I managed to solve Problem#1 today.

Note that I would describe the solutions below as being in Groovy/Java because I still fall back on my old Java habits rather than using all the Groovy language constructs available to me. Anyway…

The problem is:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Unsurprisingly, I took the brute force approach first:


int n = 999, total=0;
for (int i in 1..n) {
    if ( (i%3==0) || (i%5==0) ) {
        total=total+i;
    }
}
println("Total=" + total)

A good first start, but far from perfect as it loops through every number between 1 and n. I could improve it slightly by tweaking the start and end points (e.g. starting at 3), but it would still roughly involve n iterations.
My second attempt was this:


int n = 999, total=0;
Set nums = new HashSet();
for (int i=3; iProblem#2...

Tags: ,

Spec’ing and Pricing Client Projects

One of the toughest tasks on a project can be coming up with estimates, so I was interested to see this blog post quoting some of Joel Spolsky‘s thoughts on creating specifications and coming up with quotes for client work, which I think makes a lot of sense.

Tags:

Back from Hiatus

It’s been a while since I have posted here; The last 2 months have been hectic. I started a new project at work (I’m “Tech Lead”, on site at a major bank here in California, using Java/XML/Spring), took a vacation in Europe, did a best man’s speech at a friends wedding, and completed the Escape From Alcatraz triathlon. Been a busy time!

I have a few ideas for upcoming articles, and I am also thinking about taking the Spring Certification exam. If so, I will be sure to post about it here…

Things Every Software Architect Should Know

There is an interesting article on TheServerSide today, about a book called “97 Things Every Software Architect Should Know”. It contains some good articles from some well known authors and architects, all short and easy to read. My personal favorites are