nkiesel
07/23/2022, 1:22 AMval tree = mapOf(2 to 1, 3 to 2, 4 to 3, 5 to 1)
fun allPath(tree: Map<Int, Int>, root: Int): Map<Int, List<Int>> {
return (tree.keys.associateWith { path(it, tree, root) } + mapOf(root to listOf(root))).filterValues { it.isNotEmpty() }
}
fun path(start: Int, tree: Map<Int, Int>, root: Int): List<Int> {
return buildList {
var n: Int? = start
while (n != null && n != root) { add(n); n = tree[n] }
if (n == null) return emptyList()
add(root)
}.reversed()
}
println(allPath(tree, 1)) // prints {2=[1, 2], 3=[1, 2, 3], 4=[1, 2, 3, 4], 5=[1, 5], 1=[1]}
ephemient
07/23/2022, 6:39 AMfun allPath(tree: Map<Int, Set<Int>>, root: Int): Map<Int, List<Int>> = buildMap {
DeepRecursiveFunction<Pair<Int, List<Int>>, Unit> { (node, path) ->
put(node, path)
tree[node]?.forEach { child ->
callRecursive(child to path + child)
}
}(root to listOf(root))
}
fun <K, V> Map<K, V>.invert(): Map<V, Set<K>> = entries
.groupingBy { it.value }
.aggregate<_, _, MutableSet<K>> { _, set, (key, _), _ ->
set?.apply { add(key) } ?: mutableSetOf(key)
}
fun <K, V> Map<K, V>.invert(): Map<V, Set<K>> = entries
.groupingBy { it.value }
.fold(
{ _, (key, _) -> mutableSetOf(key) },
{ _, set, (key, _) -> set.apply { add(key) } },
)
Michael de Kaste
07/25/2022, 9:19 AMfun paths(tree: Map<Int, Int>, root: Int): Map<Int, List<Int>> = buildMap {
fun path(key: Int): List<Int> = getOrPut(key){
when(val next = tree[key]){
null -> listOf(key)
else -> path(next) + key
}
}
tree.keys.forEach(::path)
}.filterValues { it.first() == root }
root can also be dynamic, you can just remove the filterValues at the end and then keep refiltering to get the paths for every root value. The map uses memoization so you don't recalculate stuff laternkiesel
07/25/2022, 7:25 PM