Euler1

Euler1.java

package euler;

import org.apache.commons.functor.UnaryPredicate;
import org.apache.commons.functor.UnaryProcedure;
import org.apache.commons.functor.core.composite.ConditionalUnaryProcedure;
import org.apache.commons.functor.generator.Generator;
import org.apache.commons.functor.generator.util.EachElement;
import org.apache.commons.functor.generator.util.IntegerRange;

/**
 * An adder, or a summer, whatever.
 * 
 * @author Bruno P. Kinoshita - http://www.kinoshita.eti.br
 */
class Adder implements UnaryProcedure<Integer> {

	private int total = 0;

	public void run(Integer obj) {
		if (obj != null) {
			total = total + (obj.intValue());
		}
	}

	public int getTotal() {
		return total;
	}

}

/**
 * Problem from Euler that loiane resolved in Java, now in Functional
 * Programming :)
 * 
 * I'm quite new to FP, so there may have other ways (maybe better) of using FP
 * to solve this problem.
 * 
 * @see {@link http://www.loiane.com/2011/10/project-euler-problema-1/}
 * 
 * @author Bruno P. Kinoshita - http://www.kinoshita.eti.br
 */
public class Euler1 {

	// A predicate that represents our condition for this problem: a number 
	// is multiple of three (3) or five (5).
	private static final UnaryPredicate<Integer> IS_MULTIPLE_OF_THREE_OR_FIVE = new UnaryPredicate<Integer>() {
		public boolean test(Integer obj) {
			if (obj != null) {
				if (obj % 3 == 0 || obj % 5 == 0) {
					return true;
				}
			}
			return false;
		}
	};

	public int test(Integer left, Integer right){

		Generator<Integer> generator = EachElement.from(new IntegerRange(left,
				right).toCollection()); // From 0 to 1

		Adder summer = new Adder(); // :-) We create an adder

		ConditionalUnaryProcedure<Integer> proc = new ConditionalUnaryProcedure<Integer>(
				IS_MULTIPLE_OF_THREE_OR_FIVE, summer);  // And a procedure that
														// executes another one  
														// if a condition is 
														// valid.

		generator.run(proc); // Run our generator, executing the procedure above

		return summer.getTotal(); // Return the total
	}

}

OK, that's great creating predicates and programming in functional style and so on, but can you make it faster? Oh, and by faster I mean both in terms of complexity and in real time.

Nope :-) Not faster than using imperative. I will execute some performance tests in this code against the original one, wrote with two for's I guess. I'll post the results here

No, not with two loops or whatever. That's (almost) surely going to be worse. A hint here: what about not even taking the time to process the numbers that you know that won't be multiples of 3 or 5 anyway? OK, I guess that this is more than a simple hint... :)

Hmm, I will think about it tomorrow morning (that's when my brain works better :), here's the link to the original post about this problem with the source code and for's: http://www.loiane.com/2011/10/project-euler-problema-1/

BTW, perhaps what you meant is what another user commented on the blog entry I just sent to you...

0 -> 1000

Functional Programming
Took 9003354 nanos

Imperative Programming
Took 24005 nanos

What about this one: https://gist.github.com/1331277 ?

It has some features that the other solutions don't:

• it does only one pass through 0..1000 (or 1..1000, whatever you prefer).
• it does not use any kind of division (which is expensive), either explicit or implicit (via mod).
• it only considers the numbers that we know for sure that are multiples of 3 or of 5.

I initialized both candidates to be included in the sum with 0, but I could have just similarly have initialized them to 3 and 5, but this doesn't buy us anything good (one iteration of the body of a loop that is way lighter right now).

Comments?

Damn!!! That's neat!