Codefights subsequence

Question

I am solving https://codefights.com/challenge/Qjts7cukDvYpDW4Bc/main

My approach is simple. Get all subsequences by combination. Simple loop over combinations. Find minimum.

closestSequence2 <- function(a, b) {
LA = length(a);
LB = length(b);
minimum = Inf;

indexes = utils::combn(1:LB, LA);

for(i in 1:ncol(indexes)) 
{ 
 suma = (sum(abs(b[indexes[,i]]-a)));
 if(suma < minimum )
 {
   minimum = suma; 
 }
}  
return(minimum);   
}

I am not sure but I think it is failing due to the time because it pass the sample tests. Are there some easy tricks how to speed this up ot do I need different approach?

Answer 1

You can speed up your code by replacing the for loop with more efficient (vectorized) functions. Your code can then be reduced to a simple one-liner:

closestSequence2 <- function(a, b) min(colSums(abs(combn(b, length(a)) - a)))

Looking at it step-by-step:

1. combn is applied directly to b rather than 1:b. The output is a matrix where each column is a length(a)-long sub-sequence of b.
2. combn() - a takes advantage of R's recycling rules to compute, for each item in each sub-sequence, the signed distance to the corresponding element of a.
3. abs() converts to absolute (unsigned) distances.
4. colSums summarizes each column into a single value: the total distance from a for that sub-sequence.
5. min picks the minimum total distance across all candidates.

However, as pointed, an exhaustive search will not work well for large input vectors. A much faster approach is indeed to use dynamic programming. Here is a tentative implementation:

closestSequence2 <- function(a, b) {
  La <- length(a)
  Lb <- length(b)
  d <- abs(outer(a, b, FUN = `-`)) # matrix of all distances

  # x[1 + i, 1 + j] will hold the optimal distance between
  # the i first elements of a and the best sub-sequence
  # within the i+j first elements of b.
  x <- matrix(NA, La + 1, Lb - La + 1)
  x[ 1,  ] <- 0                             # init case where i = 0
  x[-1, 1] <- cumsum(d[cbind(1:La, 1:La)])  # init case where j = 0
  for (i in 1:La) {
     if (Lb > La) for (j in 1:(Lb - La)) {
        x[1 + i, 1 + j] <- min(x[1 + i, j],
                               x[i, 1 + j] + d[i, i + j])
     }
  }
  min(x[La + 1, ]) # min value on the last row
}

Answer 2

Obviously you need another approach. Taking all combinations is the most simple solution, but the most slow.

You should use some dynamic programming techniques to solve this. I think there's solution in O(len(a)*len(b)) or something like this.