A dépend de B

Cette semaine, c'est Adrien qui vous propose un #KataOfTheWeek : Expansion de dépendances transitives

Briefing du Kata : Input:L'algorithme prend pour paramètre un ensemble de lignes où le premier mot est le nom d'un objet. Les autres mots de la ligne sont les dépendances directes de l'objet.

Exemple: L'ensemble de dépendances:

• A dépends de B et D
• B dépends de C

Est noté:

A B D
B C

Output:La liste complete des dépendances de chaque objets référencés en entrée dans le format que vous voulez.

Exemple:

A: B, C, D
B: C
C:
D:

Test cases:

• Input:

A B C
B C E
C G
D A F
E F
F H

Output:

H: 
F: H
E: F, H
G: 
C: G
B: C, E, F, G, H
A: B, C, E, F, G, H
D: A, B, C, E, F, G, H

• Input:

A B
B C
C A

Output:

Circular Dependency

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposé par l'auteur 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
}

Votre équipe TakiVeille