How can you check whether a sequence is an 'almost increasing sequence' in R?

user_17934180 0
Viewed 94

A sequence (e.g. c(1,2,3,4)) is almost increasing when we can remove exactly one element from the sequence and get a strictly increasing sequence (i.e. a0 < a1 < ... < an). I'm trying to find a way to check whether a sequence is almost increasing. If it is, I want to return TRUE; if it isn't I want to output FALSE. I've got this far:

solution <- function(sequence) {
  sequence1 <- unlist(sequence)
  if (length(sequence1) == 1) {
    next
  }
  count <- 0
  for (i in (length(sequence1) - 1)) {
    if (sequence1[i + 1] > sequence1[i]) {
      next
    } else if (((sequence1[i + 2] > sequence1[i]) & count == 0) & i != 
length(sequence1)-1) {
      sequence1 <- sequence1[- (i + 1)]
      count <- count + 1
    } else if ((sequence1[i + 1] > sequence1[i - 1]) & count == 0 & i != 1) {
      sequence1 <- sequence1[-i]
      count <- count + 1
    } else {
      return(FALSE)
    }
  }
  return(TRUE)
}

I've used unlist() because codesignal, for some reason, doesn't accept you to refer to the function argument within the function. This works for some sequences: solution(c(4,1,5)) correctly returns TRUE. It doesn't work for others: solution(c(1, 1, 1, 2, 3)) incorrectly returns TRUE. solution(c(2,1,2,1)) correctly returns FALSE and yet solution(c(1,2,1,2)) incorrectly returns TRUE. I've lost my grip on what's going on. I wonder if anyone can spot anything?

Clarification: the basic idea of my code is to iterate through the sequence and for each element check whether its right neighbour is a bigger number. If it isn't, then we have two options: get rid of i or get rid of i+1, so I check those in turn. Since we can only make one change, i've added the condition that if count is 1, then we skip to finish. Also, if the index is 1 then we can't check i-1, and if the index is length(sequence)-1, then we can't check i+2, so i've added those conditions in to make sure my code skips to the other option if appropriate.

if-statement sequence r for-loop
1 Answers

Here is a solution which works for me. The idea is that diff(x) has negative elements for every downwards step in x. For example, min(diff(x)) is positive, if x is strictly increasing. If diff(x)[i] <= 0 for exactly one index i, we have to check whether either removing x[i] or removing x[i+1] makes the sequence strictly increasing. The following function passed all tests I tried:

check_almost <- function(x) {
  if (length(x) < 2) {
    return(TRUE)
  }
  
  d <- diff(x)
  i <- which(d <= 0)
  if (length(i) == 0) {
    return(TRUE) # strictly increasing
  } else if (length(i) > 1) {
    return(FALSE)
  }

  return(i == 1 || # we can remove x[1]
           i == length(d) ||  # we can remove x[length(x)]
           d[i-1]+d[i] > 0 || # we can remove x[i]
           d[i] + d[i+1] > 0) # we can remove x[i+1]
}
user_6487410
Related