Project Euler

Project Euler is a list of 193 mathematical problems that can be solved by computers. They vary in complexity from simple to hard. The goal is to test ShapeLogic's new declarative and functional constructs on real problems and make sure they are terse and intuitive.

Remarks

Here is the Java file containing the 10 first problems, where each problem will be turned into a junit test: http://shapelogic.googlecode.com/svn/trunk/src/test/java/org/shapelogic/euler/ProjectEuler1Test.java

The best way to get familiar ShapeLogic's new functional constructs is to create a Java project with just this file. All you need for this to run is junit.jar and shapelogic_1.0.jar.

Comparison to the Scala language

The blog http://scala-blogs.org/2007/12/project-euler-fun-in-scala.html is showing off the strength of Scala to solve some of the problems defined in Project Euler. This is as easy as it gets, however, the APL, Erlang, Haskell, Mathematica, Perl and Python programmer will surely argue. These simple solutions are the benchmarks by which to measure ShapeLogic's success.

The solution in Scala clearly use less code, but is not substantially simpler, especially when you are using Eclipse which will generate the methods you have to override in order to customize the lazy stream constructs. Java is inherently verbose, so it will never be that terse.

This is the assessment based on a few first simple examples, maybe ShapeLogic will buckle under more complex examples.

Commonly used classes

NaturalNumberBrick

Generate a stream of natural numbers, can take a start and stop number

BaseListFilterBrick

A filter that takes an Iterator as input, and an evaluate method.

SumAccumulator

An accumulator that run through an Iterator and add all the number in it.

1 Add all the natural numbers below 1000 that are multiples of 3 or 5

Solution in ShapeLogic

```NaturalNumberStream naturalNumberStream = new NaturalNumberStream(1,999);
ListFilterStream<Integer> filter = new BaseListFilterStream<Integer>(naturalNumberStream) {
public boolean evaluate(Integer object) {return object % 3 == 0 || object % 5 == 0;}
};
SumAccumulator accumulator = new SumAccumulator(filter);
System.out.println(accumulator.getValue());```

2 Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million

Solution in ShapeLogic

```BaseListIndexedStream1<Object,Integer> fibonacci = new BaseListIndexedStream1<Object,Integer>(){
public Integer invoke(Object input, int index) {return get(index-2) + get(index-1);}
};
ListFilterStream<Integer> filter = new BaseListFilterStream<Integer>(fibonacci) {
public boolean evaluate(Integer object) { return object % 2 == 0; }
};
SumAccumulator accumulator = new SumAccumulator(filter) {
{_inputElement = 0;}
public boolean hasNext(){ return _inputElement < 1000000; }
};
System.out.println(accumulator.getPreviousValue()); //Test fails after value go over 1000000```

3 Find the largest prime factor of 317584931803

```NaturalNumberStream naturalNumberStream = new NaturalNumberStream(2,null);
BaseAccumulator<Integer,Long> accumulator = new BaseAccumulator<Integer,Long>(naturalNumberStream) {
long theNumber = 317584931803l;
{_inputElement = 0;}
public Long accumulate(Integer element, Long out) {
while (theNumber % element == 0l) { theNumber /= element; }
return theNumber;
}
public boolean hasNext(){ return _inputElement <= theNumber; }
};
System.out.println(accumulator.getValue());```

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

```NaturalNumberStream naturalNumberStream = new NaturalNumberStream(1,999);
BaseListStream2<Integer, Integer, Integer> cartesianProduct =
new BaseListStream2<Integer, Integer, Integer>(naturalNumberStream, naturalNumberStream) {
public Integer invoke(Integer input0, Integer input1, int index) {return input0 * input1;}
};
ListFilterStream<Integer> filter = new BaseListFilterStream<Integer>(cartesianProduct) {
public boolean evaluate(Integer object) {return palindrome(object);}
};
MaxAccumulator accumulator = new MaxAccumulator(filter);
System.out.println(accumulator.getValue());```

5 What is the smallest number divisible by each of the numbers 1 to 20?

```NaturalNumberStream naturalNumberStream = new NaturalNumberStream(2,20);
@Override
public boolean evaluate(Integer input) {
return input <= 20;
}
};
Accumulator<Integer, Map<Integer,Integer> > accumulator =
new BaseAccumulator<Integer, Map<Integer,Integer> >(naturalNumberStream) {
{_value = new TreeMap<Integer,Integer>();}

@Override
public Map<Integer,Integer> accumulate(Integer element, Map<Integer,Integer> out) {
if (element < prime)
break;
int rank = rankOfDivisor(element,prime);
Integer currentRank = out.get(prime);
if (0 < rank && (currentRank == null || currentRank < rank))
out.put(prime,rank);
}
return out;
}
};
System.out.println(productWithPower(accumulator.getValue()));```

6 What is the difference between the sum of the squares and the square of the sums?

```NaturalNumberStream naturalNumberStream = new NaturalNumberStream(1,100);
BaseListStream1<Integer, Integer> squaredStream =
new BaseListStream1<Integer, Integer>(naturalNumberStream) {
public Integer invoke(Integer input, int index) {
if (input == null) return null;
return input * input;
}
};
SumAccumulator sumOfSquares = new SumAccumulator(squaredStream);
SumAccumulator sumOfNumbers = new SumAccumulator(naturalNumberStream);
long result = sumOfNumbers.getValue() * sumOfNumbers.getValue() - sumOfSquares.getValue();
System.out.println(result);```

7 Find the 10001st prime

```PrimeNumberStream primeNumberStream = new PrimeNumberStream();
System.out.println(result);```

8 Discover the largest product of five consecutive digits in the 1000-digit number

```final String inputNumbers =
"73167176531330624919225119674426574742355349194934" +
"96983520312774506326239578318016984801869478851843" +
"85861560789112949495459501737958331952853208805511" +
"12540698747158523863050715693290963295227443043557" +
"66896648950445244523161731856403098711121722383113" +
"62229893423380308135336276614282806444486645238749" +
"30358907296290491560440772390713810515859307960866" +
"70172427121883998797908792274921901699720888093776" +
"65727333001053367881220235421809751254540594752243" +
"52584907711670556013604839586446706324415722155397" +
"53697817977846174064955149290862569321978468622482" +
"83972241375657056057490261407972968652414535100474" +
"82166370484403199890008895243450658541227588666881" +
"16427171479924442928230863465674813919123162824586" +
"17866458359124566529476545682848912883142607690042" +
"24219022671055626321111109370544217506941658960408" +
"07198403850962455444362981230987879927244284909188" +
"84580156166097919133875499200524063689912560717606" +
"05886116467109405077541002256983155200055935729725" +
"71636269561882670428252483600823257530420752963450";
final int numberLength = inputNumbers.length()-1;
BaseListStream0<Integer> inputNumberStream =
new BaseListStream0<Integer>(numberLength) {
@Override
public Integer invoke(int index) {
char c = inputNumbers.charAt(index);
return Integer.parseInt(""+c);
}
};
BaseListIndexedStream1<Integer, Integer> productStream =
new BaseListIndexedStream1<Integer, Integer>(inputNumberStream,numberLength) {//XXX you should not need to set length
public Integer invoke(Integer input, int index) {
if (index<4) return 0;
int result = 1;
for (int i=index-4; i<=index;i++) {result*=getInput(i);};
return result;
}
};
MaxAccumulator maxAccu = new MaxAccumulator(productStream);
System.out.println(maxAccu.getValue());```

9 Find the only Pythagorean triplet, a, b, c, for which a + b + c = 1000

```NaturalNumberStream naturalNumberStream = new NaturalNumberStream(1,500);
final int[] EMPTY_ARRAY = new int[0];
BaseListStream2<Integer, Integer, int[]> cartesianProduct =
new BaseListStream2<Integer, Integer, int[]>(naturalNumberStream, naturalNumberStream) {
public int[] invoke(Integer a, Integer b, int index) {
int c = 1000 - a - b;
if (b<=a) return EMPTY_ARRAY;
if (c*c == a*a + b*b) return new int[] {a,b,c};
else return EMPTY_ARRAY;
}
};
ListFilterStream<int[]> filter = new BaseListFilterStream<int[]>(cartesianProduct) {
public boolean evaluate(int[] object) {return EMPTY_ARRAY != object;}
};
int[] result = filter.next();
long resultNumber = ArrayOperations.product(result);
System.out.println("result: "+ ArrayOperations.product(result));
System.out.println("a: " + result[0] + ", b: " + result[1] + ", c: " + result[2]);```

10 Calculate the sum of all the primes below one million

```PrimeNumberStream primeNumberStream = new PrimeNumberStream();