POV challenges to build Tree data structure, and manipulate it by “reparenting” the Tree.
This practice exists on some tracks including Go, Java, Lua, Haskell.
In my opinion this practice is suitable as a Hard difficulty exercise in Rust, but not too difficult as long as Tree does not contain back reference to parents, which is not strictly necessary to implement a working solution.
@senekor If this sounds like a good idea, I’ll start working on it this week
That sounds good. The most similar exercise we have is probably Simple Linked List. The basic structure is similar with Option<Box<Node<T>>>. Let’s make sure the new exercise adds something meaningful that the simple linked list doesn’t have.
Ideally, we’d check if there is something suitable in problem-specifications so we don’t reinvent the wheel.
Here’s what I found:
binary-search-tree deals with trees, but the tests only include operations “find” and “insert”. That’s a bit sad, because the really interesting operation would be “remove”, including reparenting. The exercise could be extended upstream, but that’s more work, so maybe not the best choice.
pov looks like exactly what we want. Trees and reparenting, including test cases.
zipper is not about reparenting, but also an interesting exercise about operating on trees. We could keep it in mind for later.
Btw. I just noticed that my script to add new exercises doesn’t suggest the slugs of unimlemented exercises from problem-specifications like it should. But if you give it the correct slug, it will still fill in all the information from problem-specifications that it can. For example:
just add-exercise --slug pov
Sounds good, I’ll come up with initial draft in a few days, by then should I keep posting here or make a pull request and discuss in github?
Also about zipper, it’s a great exercise, one of my favorites in Haskell track. I’m down to implementing that too, and a minor note on Zipper is, Java track’s Zipper test cases expect left/up/right to be a member variable which made a purely functional/immutable zipper implementation basically impossible. My opinion is that those should be a method, so that both mutable version and functional versions are accepted
Once we start discussing code, a PR ist best. Just post a link here (and a backlink to this forum post on the PR) so there’s a trail of bread crumbs for people to follow.
I haven’t solved the zipper exercise on any track, so I’m happy for you to draft what you think is best and iterate from there. I generally agree that cementing certain struct fields in an API is usually not idiomatic.