[2019-05-20] Challenge #378 [Easy] The Havel-Hakimi algorithm for graph realization. Demo at https://repl.it/repls/OpulentExcitableInterfaces

havelHakimi.R

havelHakimi <- function(data) {
  result <- F
  
  repeat {
    # Remove all 0's.
    data <- data[data != 0]
    if (length(data) == 0) {
      result <- T
      break
    }
    
    # Sort the counts.
    data <- sort(data, decreasing = T)
  
    # Remove the first answer.
    n <- data[1]
    data <- data[-1]

    if (n > length(data)) {
      result <- F
      break
    }
    
    # Subtract 1 from the first n counts.
    data <- sapply(seq_along(data), function(count) { ifelse(count <= n, data[count] - 1, data[count]) })
  }
  
  result
}

output.txt

> source('~/.active-rstudio-document')
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"
[1] "Success"

test.R

testCases <- list(
  list(case = c(5,3,0,2,6,2,0,7,2,5), result = F),
  list(case = c(4, 2, 0, 1, 5, 0), result = F),
  list(case = c(3, 1, 2, 3, 1, 0), result = T),
  list(case = c(16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16), result = T),
  list(case = c(14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12), result = T),
  list(case = c(15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3), result = F),
  list(case = c(6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1), result = F),
  list(case = c(2, 2, 0), result = F),
  list(case = c(3, 2, 1), result = F),
  list(case = c(1, 1), result = T),
  list(case = c(1), result = F),
  list(case = c(), result = T)
)

sapply(testCases, function(testCase) {
  print(ifelse(havelHakimi(testCase$case) == testCase$result, 'Success', 'Fail'))
})