twitter_iq.R

wall.test <- c(2,5,1,2,3,4,7,7,6)
fn_puddle(wall.test)  # 10
wall.test <- c(2,5,1,3,1,2,1,7,7,6)
fn_puddle(wall.test)  # 17
wall.test <- c(2,5,1,3,1,2,1,7,7,0,7)
fn_puddle(wall.test)  # 24

## my initial attempt
#.. works on 1 big puddle, does not work for c(5,1,5,1,5)
fn_1puddle <- function(walls) {
  
  # no puddle possible if less than 3 walls
  if (length(walls) < 3)
    return(0) 
  
  # find the tallest wall on Left and Right sides
  id.maxL <- 1  # R indexing starts at 1
  id.maxR <- length(walls)
  for (i in 2:ceiling(length(walls)/2)) {
    if (walls[i] >= walls[id.maxL])
      id.maxL <- i
    if (walls[length(walls)-i+1] >= walls[id.maxR])
      id.maxR <- length(walls)-i+1
  }
  
  # no puddle if no space between tallest walls from both sides
  if (id.maxR - id.maxL <= 1)
    return(0)
  
  # puddle = lower of max walls on either side * distance between walls
  #           - heights of all walls in between
  puddle.area <- min(walls[id.maxL],walls[id.maxR])*(id.maxR-id.maxL-1) -
    sum(walls[(id.maxL+1):(id.maxR-1)])
  
  return(puddle.area)
}

## solution by mkozakov converted to R
#.. works on any number of puddles
fn_puddle <- function(walls) {
  
  # initialize variables
  id.L <- 1
  id.R <- length(walls)
  max.L <- walls[id.L]
  max.R <- walls[id.R]
  puddle.area <- 0
  
  while (id.L < id.R) {
    
    # update current Left and Right tallest walls
    if (walls[id.L] > max.L)
      max.L <- walls[id.L]
    if (walls[id.R] > max.R)
      max.R <- walls[id.R]
    
    # move id from lower of Left and Right tallest walls
    if (walls[id.L] > walls[id.R]) {
      puddle.area <- puddle.area + (max.R - walls[id.R])
      id.R <- id.R - 1
    } else {
      puddle.area <- puddle.area + (max.L - walls[id.L])
      id.L <- id.L + 1
    }
  }
  return(puddle.area)
}