6 kyu

Prüfer sequences and labeled trees

47benjaminzwhite
Description
Loading description...
Algorithms
Mathematics
Graphs
Graph Theory
Trees
Combinatorics
View
AllIssues1Questions1Suggestions1Show Resolved
  • Please sign in or sign up to leave a comment.
  • ahmet_popaj Avatar

    Very nice.

  • dfhwze Avatar

    Am I mistaken or should a dict of dict be a dict of set ?

    • benjaminzwhite Avatar

      Yes, my bad, you are right - originally there was some additional information in there but now it's just a set.

      Updated everywhere in the description. Thanks for reviewing and solving @dfhwze !

      Question marked resolved by benjaminzwhite 3 years ago
    • dfhwze Avatar

      It was surprisingly easy to solve, but I think that's due to the very clear specification and examples used.

    • benjaminzwhite Avatar

      Thanks - well I think you may also be under-estimating your power level just a bit ;)

      But yes, it's a nice little "algorithmic" part of combinatorics; my hope is that the solvers feel rewarded after working through and thinking about the pseudocode in both directions.

      It also provides a way to generate random trees, which might be useful for some people's toolkit.

      Thanks again for solving - I like your link helper function, very clean!

    • dfhwze Avatar

      approved at kyu 6

  • Voile Avatar

    There's an implicit assumption that n > 1 throughout the kata that's not specified anywhere. (n = 1 and n = 0 has 1 unique labeled tree too)

    • benjaminzwhite Avatar

      Hi @Voile - thanks, as always, for solving and for the feedback.

      Good point - I've now made it explicit that tests will always have:

      • trees with n >= 3 vertices, in tree -> PS tests.
      • Prüfer sequence of length l >= 1, in PS -> tree tests.
      Issue marked resolved by benjaminzwhite 3 years ago