score:0

the following is a translation of the top-down algorithm into scala. the memoized values are local to memoizedcutrod so they have no impact on the environment, i.e., without side effects. i changed a couple of the names. the interior, recursive function uses p from the exterior function since it is not changing, and memo is share across all instances of the recursive function.

i also changed the use of - infinity to an option[int], so that we have a clear indicator that the value is not yet defined. i prefer that to the method of using an "impossible" number as a flag.

def memoizedcutrod(p: array[int], n: int): int = {
  val memo = new array[option[int]](n+1)
  (0 to n).foreach(memo(_) = none)

  def memoizedcutrodaux(n: int): int = {
    if ( memo(n).isdefined ) memo(n).get
    else if ( n == 0 ) 0
    else {
      val q = (1 to n).map(i => p(i) + memoizedcutrodaux(n - i)).max
      memo(n) = some(q)
      q
    }
  }

  memoizedcutrodaux(n)
}

score:0

i tried my best to make it purely functional. hope it satisfies

type p = seq[int]
type r = seq[option[int]]
type m = (int, r)
type n = (p, m)
type ~>[a, b] = partialfunction[a, b]

val r: int => r = seq.fill(_)(none)

val exists: n ~> m = {
  case (_, (n, r)) => 
    r(n).fold(throw new matcherror)((_, r))
}

val zero: n ~> m = {
  case (_, (n, r)) if n == 0 =>
    (0, r.updated(n, some(0)))
}

val other: (n => m, n) => m = {
  case (f, (p, (n, r))) =>
    ((0, r) /: (1 to n)) {
      case ((q, r), i) =>
        val (q1, r1) = f(p, (n - i, r))
        (math.max(q, q1), r1)
    }
}

val cut: n ~> m = exists orelse zero orelse {
  case n: n => other(cut, n)
}

Related Query

More Query from same tag