Commits

Martin Klinke committed 493c659

solved further problems

Comments (0)

Files changed (10)

File contents unchanged.
File contents unchanged.
File contents unchanged.

.settings/org.eclipse.jdt.core.prefs

File contents unchanged.

src/com/mklinke/euler/Problem18.scala

          List(91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48),
          List(63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31),
          List(04, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60, 04, 23))
-
+   
+  def reduceTriangle(head: List[Int], tail: List[List[Int]]) : Int =
+  {
+     if (head.length == 1)
+       return head(0)
+     reduceTriangle(addLongToShort(head, tail.head), tail.tail)
+  }
+  
+  def addLongToShort(long: List[Int], short: List[Int]) : List[Int] =
+  {
+    if (short == Nil)
+      return Nil
+    val first = long.head
+    val second = long.tail.head
+    (short.head + Math.max(first, second)) :: addLongToShort(long.tail, short.tail)
+  }
+         
   def main(args: Array[String]) {
-    //as yet unsolved
+    val reverseTriangle = triangle.reverse
+    println(reduceTriangle(reverseTriangle.head, reverseTriangle.tail))
   }
+  
 }

src/com/mklinke/euler/Problem30.scala

File contents unchanged.

src/com/mklinke/euler/Problem31.scala

File contents unchanged.

src/com/mklinke/euler/Problem32.scala

 package com.mklinke.euler
 
+import scala.collection.mutable.Set
+
 object Problem32 {
+
+  val atoms = List('1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '=')
+
+  def listToNum(head: Char, tail: List[Char], factor: Int): Int =
+    {
+      if (tail == Nil)
+        return (head.toInt - 48) * factor
+      ((head.toInt - 48) * factor) + listToNum(tail.head, tail.tail, factor * 10)
+    }
+
+  def multiplicand(permutation: List[Char]): Int = {
+    val revList = permutation.splitAt(permutation.indexOf('*'))._1.reverse
+    listToNum(revList.head, revList.tail, 1)
+  }
+
+  def multiplier(permutation: List[Char]): Int = {
+    val temp = permutation.splitAt(permutation.indexOf('*'))._2.tail
+    val revList = temp.splitAt(temp.indexOf('='))._1.reverse
+    listToNum(revList.head, revList.tail, 1)
+  }
+
+  def product(permutation: List[Char]): Int = {
+    val temp = permutation.reverse
+    val revList = temp.splitAt(temp.indexOf('='))._1
+    listToNum(revList.head, revList.tail, 1)
+  }
+
+  def isValid(permutation: List[Char]): (Boolean, Int, Int, Int) = {
+    if (permutation.indexOf('=') != 6 || permutation.indexOf('*') < 3 || permutation.indexOf('*') > 4)
+      return (false, 0, 0, 0)
+    val multiplic = multiplicand(permutation)
+    val multiplie = multiplier(permutation)
+    val actualProduct = multiplic * multiplie
+    if (actualProduct == product(permutation))
+      (true, actualProduct, multiplic, multiplie)
+    else
+      (false, actualProduct, multiplic, multiplie)
+  }
+
+  def calc(permutations: Iterator[List[Char]]): Set[Int] =
+    {
+      val products = Set[Int]()
+      for (perm <- permutations) {
+        val result = isValid(perm)
+        if (result._1) {
+          products.add(result._2)
+          println(result._3 + "*" + result._4 + "=" + result._2)
+        }
+      }
+      products
+    }
+
   def main(args: Array[String]) {
-     
+    println(calc(atoms.permutations).sum)
   }
 }

src/com/mklinke/euler/Problem33.scala

File contents unchanged.

src/com/mklinke/euler/Problem35.scala

 package com.mklinke.euler
 
 object Problem35 {
- def main(args : Array[String]) {
 
-    for (n <- 1 to 1000000; if (smallestDivisor(n) == n)) {
-
-      val d = smallestDivisor(n)
-      println(n + " prime!" )
-    }
+  def main(args: Array[String]) {
+    val start = System.currentTimeMillis;
+    val c = countCircularPrimes(2, 1000000, 0)
+    println("Number of circular primes: " + c)
+    println("Duration: " + (System.currentTimeMillis - start) + " ms");
   }
 
-  def isPrime(n : Int) : Boolean = {
+  def countCircularPrimes(currentN: Int, maxN: Int, currentCount: Int): Int = {
+    if (currentN >= maxN)
+      currentCount
+    else   
+      countCircularPrimes(currentN + 1, maxN, currentCount+(if (isPrime(currentN) && isCircularPrime(currentN)) 1 else 0))
+  }
 
+  def isCircularPrime(n: Int): Boolean = {
+    val digits = n.toString.toList.map(c => c.toInt - 48)
+    return isCircularPrime(digits, 1)
+  }
+
+  def isCircularPrime(digits: List[Int], count: Int): Boolean = {
+    if (count == digits.length)
+      return true
+    val reverseDigits = digits.reverse
+    val newDigits = reverseDigits.head :: reverseDigits.tail.reverse
+    if (!isPrime(newDigits.mkString.toInt))
+      return false
+    else isCircularPrime(newDigits, count + 1)
+  }
+
+  def isPrime(n: Int): Boolean = {
     n == smallestDivisor(n)
   }
 
-  def smallestDivisor(n : Int) : Int = {
-
+  def smallestDivisor(n: Int): Int = {
     findDivisor(n, 2)
   }
 
-  def findDivisor(n : Int, testDivisor : Int) : Int = {
-
-    if (square(testDivisor) > n)
+  def findDivisor(n: Int, testDivisor: Int): Int = {
+    if (testDivisor * testDivisor > n)
       n
-    else if (divides(testDivisor, n))
+    else if (n % testDivisor == 0)
       testDivisor
     else
       findDivisor(n, testDivisor + 1)
   }
-
-  def square(n : Int) : Int = {
-
-    n * n
-  }
-
-  def divides(d : Int, n : Int) : Boolean = {
-
-    (n % d) == 0
-  }
 }