A dépend de B - Solution

On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Adrien en début de semaine !

En kotlin:

fun expandDependencies(input: String) {
  val dependencies = input.lines()
    .map { line -> line.split("\\s+".toRegex()) }
    .associateBy(
      keySelector = { it.first() },
      valueTransform = { it.drop(1).distinct() }
    )

  val expanded = expandDependencies(dependencies)
  for ((name, deps) in expanded) {
    println("$name: ${deps.joinToString(", ")}")
  }
}

fun expandDependencies(unexpanded: Map<String, List<String>>): Map<String, List<String>> {
  val expanded = mutableMapOf<String, List<String>>()

  val stack = unexpanded.keys.toMutableList()
  val alreadyBumped = mutableSetOf<String>()

  while (stack.isNotEmpty()) {
    val name = stack.removeAt(stack.lastIndex)
    if (name in expanded) continue

    val directDeps = unexpanded[name]
    if (directDeps.isNullOrEmpty()) {
      expanded[name] = emptyList()
      continue
    }

    val unexpandedDeps = directDeps.filter { it !in expanded }
    if (unexpandedDeps.isNotEmpty()) {
      require(unexpandedDeps.none { it in alreadyBumped }) { "Circular dependency for dependency \"$name\"" }
      stack.add(name)
      stack.addAll(unexpandedDeps)
      alreadyBumped.addAll(unexpandedDeps)
      continue
    }

    expanded[name] = directDeps
      .flatMap { expanded.getValue(it) + it }
      .distinct()
      .sorted()
  }

  return expanded
}

A bientôt pour un nouveau #KataOfTheWeek !