import scala.collection.mutable

trait Memorized[T,R] {
  val cache = new mutable.HashMap[T,R]
  def cacheOrApply( t:T )( f: => R ): R = cache.getOrElse(t, {
    val rv = f
    cache += t -> rv
    rv
  })
}

object Memoized {

  def apply[T1, R]( f:(T1) => R ): ((T1) => R) with Memorized[(T1), R] =
    new Function1[T1, R] with Memorized[(T1), R]{
      def apply(a1: T1):R = cacheOrApply((a1)){ f(a1) }
    }

  def apply[T1, T2, R]( f:(T1, T2) => R ): ((T1, T2) => R) with Memorized[(T1, T2), R] =
    new Function2[T1, T2, R] with Memorized[(T1, T2), R]{
      def apply(a1: T1, a2: T2):R = cacheOrApply((a1, a2)){ f(a1, a2) }
    }

  def apply[T1, T2, T3, R]( f:(T1, T2, T3) => R ): ((T1, T2, T3) => R) with Memorized[(T1, T2, T3), R] =
    new Function3[T1, T2, T3, R] with Memorized[(T1, T2, T3), R]{
      def apply(a1: T1, a2: T2, a3: T3):R = cacheOrApply((a1, a2, a3)){ f(a1, a2, a3) }
    }

  def apply[T1, T2, T3, T4, R]( f:(T1, T2, T3, T4) => R ): ((T1, T2, T3, T4) => R) with Memorized[(T1, T2, T3, T4), R] =
    new Function4[T1, T2, T3, T4, R] with Memorized[(T1, T2, T3, T4), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4):R = cacheOrApply((a1, a2, a3, a4)){ f(a1, a2, a3, a4) }
    }

  def apply[T1, T2, T3, T4, T5, R]( f:(T1, T2, T3, T4, T5) => R ): ((T1, T2, T3, T4, T5) => R) with Memorized[(T1, T2, T3, T4, T5), R] =
    new Function5[T1, T2, T3, T4, T5, R] with Memorized[(T1, T2, T3, T4, T5), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5):R = cacheOrApply((a1, a2, a3, a4, a5)){ f(a1, a2, a3, a4, a5) }
    }

  def apply[T1, T2, T3, T4, T5, T6, R]( f:(T1, T2, T3, T4, T5, T6) => R ): ((T1, T2, T3, T4, T5, T6) => R) with Memorized[(T1, T2, T3, T4, T5, T6), R] =
    new Function6[T1, T2, T3, T4, T5, T6, R] with Memorized[(T1, T2, T3, T4, T5, T6), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6):R = cacheOrApply((a1, a2, a3, a4, a5, a6)){ f(a1, a2, a3, a4, a5, a6) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, R]( f:(T1, T2, T3, T4, T5, T6, T7) => R ): ((T1, T2, T3, T4, T5, T6, T7) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7), R] =
    new Function7[T1, T2, T3, T4, T5, T6, T7, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7)){ f(a1, a2, a3, a4, a5, a6, a7) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8), R] =
    new Function8[T1, T2, T3, T4, T5, T6, T7, T8, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8)){ f(a1, a2, a3, a4, a5, a6, a7, a8) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9), R] =
    new Function9[T1, T2, T3, T4, T5, T6, T7, T8, T9, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10), R] =
    new Function10[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11), R] =
    new Function11[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12), R] =
    new Function12[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13), R] =
    new Function13[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14), R] =
    new Function14[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15), R] =
    new Function15[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16), R] =
    new Function16[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15, a16: T16):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17), R] =
    new Function17[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15, a16: T16, a17: T17):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18), R] =
    new Function18[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15, a16: T16, a17: T17, a18: T18):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19), R] =
    new Function19[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15, a16: T16, a17: T17, a18: T18, a19: T19):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20), R] =
    new Function20[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15, a16: T16, a17: T17, a18: T18, a19: T19, a20: T20):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21), R] =
    new Function21[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15, a16: T16, a17: T17, a18: T18, a19: T19, a20: T20, a21: T21):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20, a21)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20, a21) }
    }

  def apply[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, T22, R]( f:(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, T22) => R ): ((T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, T22) => R) with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, T22), R] =
    new Function22[T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, T22, R] with Memorized[(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15, T16, T17, T18, T19, T20, T21, T22), R]{
      def apply(a1: T1, a2: T2, a3: T3, a4: T4, a5: T5, a6: T6, a7: T7, a8: T8, a9: T9, a10: T10, a11: T11, a12: T12, a13: T13, a14: T14, a15: T15, a16: T16, a17: T17, a18: T18, a19: T19, a20: T20, a21: T21, a22: T22):R = cacheOrApply((a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20, a21, a22)){ f(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20, a21, a22) }
    }
}