Skip to content

Instantly share code, notes, and snippets.

@AndrewTweddle

AndrewTweddle/JHMWorksheet.scala

Last active August 29, 2015 13:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save AndrewTweddle/9177884 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save AndrewTweddle/9177884 to your computer and use it in GitHub Desktop.
Download ZIP
A Scala worksheet to compare the performance of the various solvers written to solve the Johnny Hates Math problem found at http://www.spoj.com/problems/ANARC07J/
Raw
JHMWorksheet.scala
import jhm.JHMSolver
import jhm.SolverUsingFlatMap
import jhm.SolverUsingFor
import jhm.SolverUsingFoldLeft
object JHMWorksheet {
implicit val repetitions: Int = 20 //> repetitions : Int = 20
// Adapted from code found on: http://stackoverflow.com/questions/9160001/how-to-profile-methods-in-scala ...
// UPDATE: see the following article for why this is a bad idea... http://shipilev.net/blog/2014/nanotrusting-nanotime/
def time[R](block: => R)(implicit repetitions: Int): R = {
val t0 = System.nanoTime()
var result: R = block
var repsLeft = repetitions - 1
while (repsLeft > 0) {
result = block // call-by-name
repsLeft -= 1
}
val t1 = System.nanoTime()
println("Elapsed time: " + (t1 - t0) / 1.0e6 / repetitions + " ms")
result
} //> time: [R](block: => R)(implicit repetitions: Int)R
JHMSolver.getSolutions("3", 3) //> res0: List[List[Int]] = List(List(3))
JHMSolver.getSolutions("41", 5) //> res1: List[List[Int]] = List(List(4, 1))
JHMSolver.getSolutions("41", 41) //> res2: List[List[Int]] = List(List(41))
JHMSolver.getSolutions("4123", 19) //> res3: List[List[Int]] = List(List(4, 12, 3))
JHMSolver.getSolutions("0412030", 19) //> res4: List[List[Int]] = List(List(0, 4, 12, 0, 3, 0))
JHMSolver.getSolutionsAsString("111", 8) //> res5: String = IMPOSSIBLE
var digits = "15442147612367219875" //> digits : String = 15442147612367219875
var target = 472 //> target : Int = 472
var solns = time { JHMSolver.getSolutions(digits, target) }
//> Elapsed time: 57.353846350000005 ms
//| solns : List[List[Int]] = List(List(1, 5, 4, 4, 2, 1, 4, 7, 6, 1, 236, 7, 2
//| 1, 98, 75), List(1, 5, 4, 4, 2, 1, 4, 7, 6, 123, 6, 7, 219, 8, 75), List(1,
//| 5, 4, 4, 2, 1, 4, 7, 61, 2, 3, 67, 219, 87, 5), List(1, 5, 4, 4, 2, 1, 4, 7,
//| 61, 2, 36, 72, 198, 75), List(1, 5, 4, 4, 2, 1, 4, 76, 1, 2, 3, 67, 219, 8,
//| 75), List(1, 5, 4, 4, 2, 1, 4, 76, 1, 23, 6, 72, 198, 75), List(1, 5, 4, 4,
//| 2, 1, 4, 76, 1, 236, 7, 21, 98, 7, 5), List(1, 5, 4, 4, 2, 1, 4, 76, 123, 6
//| , 7, 219, 8, 7, 5), List(1, 5, 4, 4, 2, 1, 4, 76, 123, 6, 72, 1, 98, 75), Li
//| st(1, 5, 4, 4, 2, 1, 47, 6, 1, 2, 367, 2, 1, 9, 8, 7, 5), List(1, 5, 4, 4, 2
//| , 1, 47, 6, 1, 23, 67, 219, 87, 5), List(1, 5, 4, 4, 2, 1, 47, 6, 1, 236, 72
//| , 1, 9, 8, 75), List(1, 5, 4, 4, 2, 1, 47, 6, 123, 67, 2, 198, 7, 5), List(1
//| , 5, 4, 4, 2, 1, 47, 61, 2, 3, 67, 2, 198, 75), List(1, 5, 4, 4, 2, 1, 47, 6
//| 1, 2, 36, 7, 219, 8, 75), List(1, 5, 4, 4, 2, 1, 47, 61, 23, 6,
//| Output exceeds cutoff limit.
solns.length //> res6: Int = 741
time { new SolverUsingFoldLeft(digits, target).getSolutionsAsString }
//> Elapsed time: 46.8190768 ms
//| res7: String = 1+5+4+4+2+1+4+7+6+1+236+7+21+98+75=472
//| 1+5+4+4+2+1+4+7+6+123+6+7+219+8+75=472
//| 1+5+4+4+2+1+4+7+61+2+3+67+219+87+5=472
//| 1+5+4+4+2+1+4+7+61+2+36+72+198+75=472
//| 1+5+4+4+2+1+4+76+1+2+3+67+219+8+75=472
//| 1+5+4+4+2+1+4+76+1+23+6+72+198+75=472
//| 1+5+4+4+2+1+4+76+1+236+7+21+98+7+5=472
//| 1+5+4+4+2+1+4+76+123+6+7+219+8+7+5=472
//| 1+5+4+4+2+1+4+76+123+6+72+1+98+75=472
//| 1+5+4+4+2+1+47+6+1+2+367+2+1+9+8+7+5=472
//| 1+5+4+4+2+1+47+6+1+23+67+219+87+5=472
//| 1+5+4+4+2+1+47+6+1+236+72+1+9+8+75=472
//| 1+5+4+4+2+1+47+6+123+67+2+198+7+5=472
//| 1+5+4+4+2+1+47+61+2+3+67+2+198+75=472
//| 1+5+4+4+2+1+47+61+2+36+7+219+8+75=472
//| 1+5+4+4+2+1+47+61+23+6+7+219+87+5=472
//| 1+5+4+4+2+1+47+61+236+7+2+1+9+87+5=472
//| 1+5+4+4+2+1+47+61+236+7+2+19+8+75=472
//| 1+5+4+4+2+1+47+61+236+72+19+8+7+5=472
//| 1+5+4+4+2+14+7+6+12+367+21+9+8+7+5=472
//| 1+5+4+4+2+14+7+6+123+67+219+8+7+5=472
//| 1+5+4+4+2+14+7+61+2+3+67+219+8+
//| Output exceeds cutoff limit.
time { new SolverUsingFlatMap(digits, target).getSolutionsAsString }
//> Elapsed time: 31.361803600000002 ms
//| res8: String = 1+5+4+4+2+1+4+7+6+1+236+7+21+98+75=472
//| 1+5+4+4+2+1+4+7+6+123+6+7+219+8+75=472
//| 1+5+4+4+2+1+4+7+61+2+3+67+219+87+5=472
//| 1+5+4+4+2+1+4+7+61+2+36+72+198+75=472
//| 1+5+4+4+2+1+4+76+1+2+3+67+219+8+75=472
//| 1+5+4+4+2+1+4+76+1+23+6+72+198+75=472
//| 1+5+4+4+2+1+4+76+1+236+7+21+98+7+5=472
//| 1+5+4+4+2+1+4+76+123+6+7+219+8+7+5=472
//| 1+5+4+4+2+1+4+76+123+6+72+1+98+75=472
//| 1+5+4+4+2+1+47+6+1+2+367+2+1+9+8+7+5=472
//| 1+5+4+4+2+1+47+6+1+23+67+219+87+5=472
//| 1+5+4+4+2+1+47+6+1+236+72+1+9+8+75=472
//| 1+5+4+4+2+1+47+6+123+67+2+198+7+5=472
//| 1+5+4+4+2+1+47+61+2+3+67+2+198+75=472
//| 1+5+4+4+2+1+47+61+2+36+7+219+8+75=472
//| 1+5+4+4+2+1+47+61+23+6+7+219+87+5=472
//| 1+5+4+4+2+1+47+61+236+7+2+1+9+87+5=472
//| 1+5+4+4+2+1+47+61+236+7+2+19+8+75=472
//| 1+5+4+4+2+1+47+61+236+72+19+8+7+5=472
//| 1+5+4+4+2+14+7+6+12+367+21+9+8+7+5=472
//| 1+5+4+4+2+14+7+6+123+67+219+8+7+5=472
//| 1+5+4+4+2+14+7+61+2+3+6
//| Output exceeds cutoff limit.
time { new SolverUsingFor(digits, target).getSolutionsAsString }
//> Elapsed time: 83.43532775 ms
//| res9: String = 1+5+4+4+2+1+4+7+6+1+236+7+21+98+75=472
//| 1+5+4+4+2+1+4+7+6+123+6+7+219+8+75=472
//| 1+5+4+4+2+1+4+7+61+2+3+67+219+87+5=472
//| 1+5+4+4+2+1+4+7+61+2+36+72+198+75=472
//| 1+5+4+4+2+1+4+76+1+2+3+67+219+8+75=472
//| 1+5+4+4+2+1+4+76+1+23+6+72+198+75=472
//| 1+5+4+4+2+1+4+76+1+236+7+21+98+7+5=472
//| 1+5+4+4+2+1+4+76+123+6+7+219+8+7+5=472
//| 1+5+4+4+2+1+4+76+123+6+72+1+98+75=472
//| 1+5+4+4+2+1+47+6+1+2+367+2+1+9+8+7+5=472
//| 1+5+4+4+2+1+47+6+1+23+67+219+87+5=472
//| 1+5+4+4+2+1+47+6+1+236+72+1+9+8+75=472
//| 1+5+4+4+2+1+47+6+123+67+2+198+7+5=472
//| 1+5+4+4+2+1+47+61+2+3+67+2+198+75=472
//| 1+5+4+4+2+1+47+61+2+36+7+219+8+75=472
//| 1+5+4+4+2+1+47+61+23+6+7+219+87+5=472
//| 1+5+4+4+2+1+47+61+236+7+2+1+9+87+5=472
//| 1+5+4+4+2+1+47+61+236+7+2+19+8+75=472
//| 1+5+4+4+2+1+47+61+236+72+19+8+7+5=472
//| 1+5+4+4+2+14+7+6+12+367+21+9+8+7+5=472
//| 1+5+4+4+2+14+7+6+123+67+219+8+7+5=472
//| 1+5+4+4+2+14+7+61+2+3+67+219+8
//| Output exceeds cutoff limit.
target = 15442 + 14761 + 23672 + 19875
time { new SolverUsingFoldLeft(digits, target).getSolutionsAsString }
//> Elapsed time: 552.40112315 ms
//| res10: String = 1+5+4+4+2+1476+12+36+72198+7+5=73750
//| 1+5+4+4+214+7+6+1236+72198+75=73750
//| 1+5+4+4+214+76+1236+72198+7+5=73750
//| 1+5+4+42+1476+1+2+3+6+72198+7+5=73750
//| 1+5+44+2+1476+1+2+3+6+72198+7+5=73750
//| 1+54+421+4+761+236+72198+75=73750
//| 1+5442+14+76+123+67219+875=73750
//| 1+5442+147+61+2+3+67219+875=73750
//| 15+4+4+2+1476+1+2+36+72198+7+5=73750
//| 154+4+2+1+4+76+1236+72198+75=73750
//| 15442+14761+23672+19875=73750
time { new SolverUsingFlatMap(digits, target).getSolutionsAsString }
//> Elapsed time: 243.15815155 ms
//| res11: String = 1+5+4+4+2+1476+12+36+72198+7+5=73750
//| 1+5+4+4+214+7+6+1236+72198+75=73750
//| 1+5+4+4+214+76+1236+72198+7+5=73750
//| 1+5+4+42+1476+1+2+3+6+72198+7+5=73750
//| 1+5+44+2+1476+1+2+3+6+72198+7+5=73750
//| 1+54+421+4+761+236+72198+75=73750
//| 1+5442+14+76+123+67219+875=73750
//| 1+5442+147+61+2+3+67219+875=73750
//| 15+4+4+2+1476+1+2+36+72198+7+5=73750
//| 154+4+2+1+4+76+1236+72198+75=73750
//| 15442+14761+23672+19875=73750
time { new SolverUsingFor(digits, target).getSolutionsAsString }
//> Elapsed time: 442.56673115 ms
//| res12: String = 1+5+4+4+2+1476+12+36+72198+7+5=73750
//| 1+5+4+4+214+7+6+1236+72198+75=73750
//| 1+5+4+4+214+76+1236+72198+7+5=73750
//| 1+5+4+42+1476+1+2+3+6+72198+7+5=73750
//| 1+5+44+2+1476+1+2+3+6+72198+7+5=73750
//| 1+54+421+4+761+236+72198+75=73750
//| 1+5442+14+76+123+67219+875=73750
//| 1+5442+147+61+2+3+67219+875=73750
//| 15+4+4+2+1476+1+2+36+72198+7+5=73750
//| 154+4+2+1+4+76+1236+72198+75=73750
//| 15442+14761+23672+19875=73750
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment