Skip to content

Instantly share code, notes, and snippets.

@rcgonzalezf
Created August 11, 2017 08:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rcgonzalezf/e30f8e693bf044e8b6b80f8c05d4ac12 to your computer and use it in GitHub Desktop.
Save rcgonzalezf/e30f8e693bf044e8b6b80f8c05d4ac12 to your computer and use it in GitHub Desktop.
Trying to achieve pure functions with Kotlin.
package org.rcgonzalezf.onetoten
import java.math.BigInteger
/**
*
* https://projecteuler.net/problem=2
*
* 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.
*
*/
class Problem2 {
val fibonacciValues = hashMapOf<Int, BigInteger>(0 to BigInteger.ONE, 1 to BigInteger.ONE);
fun solve(fibonacci: Int, maxValue: Int = 4000000): BigInteger {
calculateFibonacci(fibonacci)
return fibonacciValues.filter {
it.value < BigInteger.valueOf(maxValue.toLong()) &&
it.value.mod(BigInteger.ONE.add(BigInteger.ONE)).equals(BigInteger.ZERO)
}.values.fold(BigInteger.ZERO, BigInteger::add)
}
// * TODO investigate how to do dynamic programming with a pure function ** //
private fun calculateFibonacci(n: Int): BigInteger? {
if (fibonacciValues.contains(n)) {
return fibonacciValues.get(n)
} else {
val f = calculateFibonacci(n - 2)!!.add(calculateFibonacci(n - 1))
fibonacciValues.put(n, f)
return f
}
}
}
@rcgonzalezf
Copy link
Author

This was the end result:


package org.rcgonzalezf.onetoten

import java.math.BigInteger

/**
 *
 * https://projecteuler.net/problem=2
 *
 * 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.
 *
 */
class Problem2 {

    fun solve(fibonacci: Int, maxValue: Int = 4000000): BigInteger {

        // the list is based on index 0, so we add one
        val fibonacciValues = fibonacci().take(fibonacci + 1).toList()
        val max = BigInteger.valueOf(maxValue.toLong())

        return fibonacciValues
                .filter { filterCriteria(it, max) }
                .fold(BigInteger.ZERO, BigInteger::add)
    }

    /**
     * Make sure that value doesn't exceed the max value and it's an even number.
     */
    fun filterCriteria(value: BigInteger, max: BigInteger): Boolean {
        val two = BigInteger("2")
        return value.compareTo(max) == -1 && value.mod(two).equals(BigInteger.ZERO)
    }

    // based on https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/generate-sequence.html
    fun fibonacci(): Sequence<BigInteger> {
        return generateSequence(Pair(BigInteger.ONE, BigInteger.ONE),
                { Pair(it.second, it.first.add(it.second)) })
                .map { it.first }
    }

}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment