The first five Euler problems. All the Euler problems are solved using a Java library I’m working on called jFunc, which implements many functional programming concepts.
Euler 01
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.
Loops are seen throughout mathematics and computer science. The first code snippet shows the use of a plain old for loop, each iteration of the plain old for loop counter is incremented and its divisibility is checked if the number is divisble by 3 or 5 its added to the overall sum.
int sum = 0;
for(int i = 1; i > 1000; i++) {
if(i % 3 == 0 || i % 5 == 0)
sum += i;
}
We can abstract over the idea of a loop with a list of numbers, each number in the list represents an iteration of the loop. The below code snippet uses jFunc instead of a plain old for loop. The functions range(int from, int to) creates a list of integers between from and to where from and to are inclusive. The method filter(P1<A> predicate) uses the given predicate to test each element within the list and removes elements that fail that test. The foldr(F2<B,A,B> fn, B b) reduces the list into a single value representing the sum of all the multiples of 3 and 5 below 1000. Declarative code really gets me going and is the reason I’m so interested in functional programming and like most list types in functional languages the sequential list type in jFunc is also lazy.
FList<Integer> list = range(1,999) //
.filter(i -> i % 3 == 0 || i % 5 == 0);
return list.foldr(Integers::add, 0);
Euler 02
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, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
FList<Integer> list = FList.sequence(1,2, Integers::add) // 1, 2, 3, 5, 8, 12, 20 ...
.filter(i -> i % 2 == 0)
.takeWhile(i -> i < 4000000);
return list.foldr(Integers::add,0);
In many sequences, the next element in a sequence is determined by the previous elements in the sequence. sequence(A a1, A a2, F2<A, A, A> fn) follows this idea a1 and a2 are the first two elements of the sequence and fn is a function that takes the previous two elements and produces the next element. filter(P1<A> predicate) removes any Fibnoacci numbers that are not even. takeWhile(P1<A> predicate) will take elements from the list as long as the predicate is true when the predicate is false the remaining elements in the list are dropped. sequence, filter, and takeWhile all return a type of FList which allows use to create fluent and readable code. On my Intel® Core™ i5-3339Y CPU @ 1.50GHz × 4, this computes in 0.076 seconds, which is fast enough for me.
Euler 03
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
FList<Long> primes = Numbers.primeFactors(600851475143L);
return primes.maximum(Long::compare);
jFunc inlcudes a function that returns all the prime factors of a number primeFactors(long num) and FList contains the method maximum which returns the maximum number in a list. This makes the solution a nice two liner.
Euler 04
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 didn’t think about this too hard, I just created a function that checks if a list of values is a palindrome. With my generic function, I ignored any fancy ways to check if an integer is a palindrome and decided to just convert each integer into a list of characters then used isPalindrome to check if it was indeed a palindrome. Two things to note that are unique, first the method visit(F1<Unit, B> nil, F2<A, FList<A>, B> cons) which return a value of type B and takes two functions. visit returns the value computed by nil or cons, which computed valued returned depends on if the FList on which visit is called on is empty. If the FList is empty then the first function nil is used otherwise cons is used. The values passed to cons are the head and tail of the list visit is called on. The second interesting piece of code is caseOf(A a), which is a beefed up switch statement. The function of takes a predicated and a supplier which yields a value. When the predicated passed to of is true the computed value supplier given to of is the value returned by the CaseOf.
public static <A> boolean isPalindrome(FList<A> chars) {
return chars.visit(n -> true
, (h,t) -> {
return CaseOf.caseOf(t)
.of(FList::isEmpty, () -> true)
.of(sizeOf(1), () -> h == t.head())
.of(lastEq(h), l -> isPalindrome(l.init()))
.otherwise(() -> false);
});
}
The For(F1<A, ? extends Monad<FList.μ, A>>, F2<A, B, ? extends Monad<FList.μ, A>> ) method sequences monadic operations and is analogous to a do-block in Haskell. guard(boolean b) returns an empty FList if b is false and FList<Unit> otherwise.
public static int euler04() {
Show<Integer> s = Show.showInt(); //Show<Integer> converts an Integer into a list of Characters.
FList<Integer> l =
range(100, 999)
.For(a -> range(a, 999)
,(a,b) -> {
int p = a * b;
return guard(isPalindrome(s.show(p))).semi(flist(p)); //semi is bind but ignores the value within the monad being binded over.
});
return l.maximum(Integer::compare);
}
Euler 05
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 positive number that is evenly divisible by all of the numbers from 1 to 20?
lcm is a function of arity two that takes two numbers and returns the least common multiple of those two numbers. lcm is a very straightforward function and the details of how to implement it can be found here. Whats more interesting about lcm is the fact that its associative and commutative, that is lcm(lcm(2,3),4) == lcm(2, lcm(3,4)) == lcm(4, lcm(2,3)) == 12. Because of this, we can simply fold over a least of numbers to find the least common multiple of all those numbers.
return range(1L,20L).foldr(Longs::lcm,1L);