fork download
copy 
  1. import groovy.transform.Memoized
  2.  
  3. @Memoized
  4. BigInteger factorial(int n) {
  5.     switch (n) {
  6.         case 0:
  7.         case 1: return 1g
  8.         default: return n * factorial(n - 1)
  9.     }
  10. }
  11. //assert factorial(3) == 6
  12.  
  13. BigInteger C(int k, int n) {
  14.     if (k == 0 || k == n) return 1
  15.     //TODO: factorial(n) / factorial(k) == (k..n).inject(0g) { a, b -> a*b }
  16.     return (factorial(n) / factorial(k)) / factorial(n - k)
  17. }
  18. //assert C(5, 52) == 2598960
  19.  
  20. //TODO: do something with stack overflows?
  21. @Memoized
  22. BigInteger solveLinear(int size, int current, int target, int moves) {
  23.     if (!(current in (0..<size))) return 0g
  24.     if (current == target && moves == 0) return 1g
  25.     int minMoves = Math.abs(target - current)
  26.     if (moves < minMoves) return 0g
  27.     return solveLinear(size, current - 1, target, moves - 1) + solveLinear(size, current + 1, target, moves - 1)
  28. }
  29. //assert solveLinear(5, 2, 3, 3) == 3
  30. //assert solveLinear(5, 0, 1, 3) == 2
  31.  
  32.  
  33. BigInteger solve(int N, int M, int x0, int y0, int x1, int y1, int k) {
  34.     int xDist = Math.abs(x1 - x0)
  35.     int yDist = Math.abs(y1 - y0)
  36.     int manhattanDistance = xDist + yDist
  37.     int additionalMoves = k - manhattanDistance
  38.     if (additionalMoves < 0 || additionalMoves & 1) return 0g
  39.  
  40.     BigInteger result = 0g
  41.     for (int additionalXMoves = 0; additionalXMoves <= additionalMoves; additionalXMoves +=2) {
  42.         int xMoves = xDist + additionalXMoves
  43.         int yMoves = k - xMoves
  44.         result += C(xMoves, k) * solveLinear(N, x0, x1, xMoves) * solveLinear(M, y0, y1, yMoves)
  45.     }
  46.     return result
  47. }
  48.  
  49. println solve(100, 100, 50, 50, 60, 60, 200)
  50.  
Runtime error #stdin #stdout #stderr 1.58s 332416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Caught: java.lang.StackOverflowError
java.lang.StackOverflowError
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
	at prog.factorial(prog.groovy)
	at prog.memoizedMethodPriv$factorialint(prog.groovy:8)
	at prog$_closure1.doCall(prog.groovy)
https://ideone.com/XZPGR5
language:
Groovy (groovy 2.5.6)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!