Source

ScalaEuler / src / com / mklinke / euler / Problem39.scala

/**
 * *
 *  Copyright 2012 Martin Klinke, http://www.martinklinke.com.
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package com.mklinke.euler

/**
 * @author Martin Klinke
 *
 */
object Problem39 {
  def main(args: Array[String]) {
    val start = System.currentTimeMillis;
//    println("Result for 120: " + calcSolutions(120, (1, 1, 1), List()))
    println((1 to 1000).map(i => (i, calcSolutions(i, (1, 1, 1), List()))).maxBy(t => t._2.length))
//    for(i <- 1 to 1000){
//      println("Result for "+i+": "+calcSolutions(i, (1, 1, 1), List()))
//    }
    println("Duration: " + (System.currentTimeMillis - start) + " ms");
  }

  def calcSolutions(perimeter: Int, currentTry: Tuple3[Int, Int, Int], solutions: List[Tuple3[Int, Int, Int]]): List[Tuple3[Int, Int, Int]] = {
    val next = nextTry(perimeter, currentTry)
    if (next == None)
      solutions
    else
      calcSolutions(perimeter, next.get, if (isSolution(perimeter, currentTry) && !solutions.contains((currentTry._2, currentTry._1, currentTry._3))) currentTry :: solutions else solutions)
  }

  def isSolution(perimeter: Int, sideLengths: Tuple3[Int, Int, Int]): Boolean = {
    if (sideLengths._1 + sideLengths._2 + sideLengths._3 != perimeter)
      false
    else
      ((sideLengths._1 * sideLengths._1) + (sideLengths._2 * sideLengths._2)) == (sideLengths._3 * sideLengths._3)
  }

  def nextTry(perimeter: Int, currentTry: Tuple3[Int, Int, Int]): Option[Tuple3[Int, Int, Int]] = {
    if (currentTry._1 > perimeter/2)
      None
    else if (currentTry._2 < perimeter)
      Some(currentTry._1, currentTry._2+1, perimeter-currentTry._1-currentTry._2-1)
    else
      Some(currentTry._1+1, 1, perimeter-currentTry._1-1-1)
  }
}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.