public
Created

fib sums (coding dojo)

  • Download Gist
gistfile1.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
import org.scalatest.matchers.ShouldMatchers
import org.junit.Test
 
//object Sums {
// def main(args: Array[String]) {
// for(i <- 1 to 20) { println(i + " is " + new Sums().fibonacciZeckendorfRepresentationOf(i).mkString(" or "))}
// }
//}
 
class Sums extends ShouldMatchers {
@Test def shouldFindRepresentationsOfOneToThirteen() {
def result = (for(i <- 1 to 13) yield fibonacciRepresentationOf(i))
result(0) should equal(Vector("1"))
result(1) should equal(Vector("10"))
result(2) should equal(Vector("100", "11"))
result(3) should equal(Vector("101"))
result(4) should equal(Vector("1000", "110"))
result(5) should equal(Vector("1001", "111"))
result(6) should equal(Vector("1010"))
result(7) should equal(Vector("10000", "1100", "1011"))
result(8) should equal(Vector("10001", "1101"))
result(9) should equal(Vector("10010", "1110"))
result(10) should equal(Vector("10100", "10011", "1111"))
result(11) should equal(Vector("10101"))
result(12) should equal(Vector("100000", "11000", "10110"))
}
 
@Test def shouldFindZeckendorfRepresentationsOfOneToThriteen() {
def result = (for(i <- 1 to 13) yield fibonacciZeckendorfRepresentationOf(i))
result(0) should equal(Vector("1"))
result(1) should equal(Vector("10"))
result(2) should equal(Vector("100"))
result(3) should equal(Vector("101"))
result(4) should equal(Vector("1000"))
result(5) should equal(Vector("1001"))
result(6) should equal(Vector("1010"))
result(7) should equal(Vector("10000"))
result(8) should equal(Vector("10001"))
result(9) should equal(Vector("10010"))
result(10) should equal(Vector("10100"))
result(11) should equal(Vector("10101"))
result(12) should equal(Vector("100000"))
}
 
@Test def miscTests() {
fibonacci should equal(Seq(1, 2, 3, 5, 8, 13))
 
combinationsOfLength(1, 5) should equal(Seq(Seq(5)))
 
allFibonacciCombinationsOf(5) should equal(Seq(Seq(5), Seq(2,3)))
 
asFibonacciString(Seq(Seq(5), Seq(2,3))) should equal(Seq("1000", "110"))
}
 
lazy val fibonacciSize = 6
lazy val fibonacci = calculateFibonacci(fibonacciSize)
 
def fibonacciZeckendorfRepresentationOf(n: Int): Seq[String] = {
fibonacciRepresentationOf(n).filterNot{ _.contains("11") }
}
 
def fibonacciRepresentationOf(n: Int): Seq[String] = {
asFibonacciString(allFibonacciCombinationsOf(n))
}
 
private def allFibonacciCombinationsOf(n: Int): Seq[Seq[Int]] = {
(for (length <- 1 to fibonacciSize) yield combinationsOfLength(length, n)).flatten
}
 
private def combinationsOfLength(count: Int, n: Int) : Seq[Seq[Int]] = {
fibonacci.combinations(count).filter(xs => xs.sum == n).toList
}
 
private def asFibonacciString(ints: Seq[Seq[Int]]) : Seq[String] = {
def oneFibonacciString(ints: Seq[Int]) =
(for (n <- fibonacci) yield if (ints.contains(n)) '1' else '0').reverse.dropWhile(_ == '0').mkString
 
ints map oneFibonacciString
}
 
private def calculateFibonacci(count: Int): Seq[Int] = {
def f(n: Int, current: Int, previous: Int): List[Int] =
if (n > 0) current :: f(n - 1, current + previous, current)
else Nil
f(count, 1, 1)
}
 
private def calculateFibonacciStream: Stream[Int] = {
def f(current: Int, previous: Int): Stream[Int] =
current #:: f(current + previous, current)
f(1, 1)
}
 
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.