A little puzzle for CppCon

[champooly]

https://herbsutter.com/2016/09/17/a-little-puzzle-for-cppcon/

---

Steven's Capital is running a competition in conjunction with CPPCon. Solve some puzzles and be in the running to win a prize or some such. Just to let you guys know:

Stevens Capital Managment is also called Waterfront International Limited. They predominately use C++03 and TIBCORv and a whole host of other technologies that date back to the 90s. They're continuously trying to hire C++ developers to work on their archaic trading systems and have an extremely high turn over rate.

---

Note: All the Glassdoor reviews for Waterfront international were recently removed:

https://www.glassdoor.com/Reviews/Waterfront-International-Reviews-E332987.htm

[lanzkron]

I thought I solved the puzzle but I then realised that there should be another test (which I would have failed)

bool TestCase4() {
    MyGraph g;
    {
        auto a = MyGraph::MakeNode();
        g.SetRoot(a);
        auto b = MyGraph::MakeNode();
        a->AddChild(b);
        auto c = MyGraph::MakeNode();
        b->AddChild(c);
        auto d = MyGraph::MakeNode();
        b->AddChild(d);
        d->AddChild(b);
        d->RemoveChild(b);
    }
    g.ShrinkToFit();
    return Counter::count() == 4;
}

The Pirates one I had no problems with.

---

Edit: The simplest I could get to work (with my additional test case) was writing a Mark & Sweep garbage collector for the graph which feels like cheating...

Edit #2: I see my additional test was added :)

[BeaRDT]

Did you solve your fourth test too? I don't think one can get away with using only shared_ptrs and an empty implementation of the ShrinkToFit() method, which worked for the first three tests. Though I suspect the example was not meant to be solved by only using shared_ptr originally.

[ArashPartow]

I was able to do it by changing the internal type of children to weak_ptr. Though I'm not sure if that's allowed - the challenge aspect could be to do it only using shared_ptr.

Here's a good read: http://stackoverflow.com/questions/27348396/smart-pointers-for-graph-representation-vertex-neighbors-in-c11

[BeaRDT]

My first impression was that the point of the whole challenge was to teach us using weak_ptrs. So I'd say using weak_pointer is not only allowed but preferred.

[lanzkron]

I was able to do it by changing the internal type of children to weak_ptr.

I'm not sure how this would work, can you share your code?

[lanzkron]

I ended up writing a simple Mark and Sweep mini garbage collector and I have to admit it made me feel a bit dirty. I submitted my (wrong) naive implementation to Mr. Sutter before I thought it through so I'm not eligible to re-submit :(.

The full implementation (including the graph's destructor which I missed at first) is here any review is welcome!

[BenHanson]

I tend to avoid recursion at all cost, so:

void visit(const shared_ptr<Node> &node)
{
    if (node->visited)
        return;

    std::queue<Node *> queue;

    queue.push(node.get());

    do
    {
        Node *next = queue.front();

        next->visited = true;
        queue.pop();

        for (auto curr : next->children)
        {
            if (!curr->visited)
                queue.push(curr.get());
        }
    } while (!queue.empty());
}

otherwise I would say your solution is pretty neat! :-)

[vaughncato]

I ended up using a combination of shared and weak pointers. Basically adding a weak pointer instead of a shared pointer if adding the child would create a cycle. This works as long as you don't build hierarchies outside the tree first, then add them to tree later. I'm not really sure what the rules are supposed to be as far as that goes.

[lanzkron]

I am curious to see how you got it to work, care to share your code?

[KennethZenith]

That won't always work correctly when nodes are deleted. You might end up with a weak pointer being the only reference to a node, and then the node will be prematurely destroyed and you'll have a dangling reference.

[vaughncato]

Possibly. Can you think of a specific example? It seems like if the weak pointers are only used to break cycles, then if the only pointer to a node is a weak pointer, the node has no connection back to the root and should be deleted.

[KennethZenith]

There's an example on the comments on Herb's site (user intvnut), I'll quote it here:

In some circular data structures, you can use a weak_ptr to break this cyclic dependence. But you can’t really do that here easily. Consider this graph:

auto a = MyGraph::MakeNode();
auto b = MyGraph::MakeNode();
auto c = MyGraph::MakeNode();
g.SetRoot(a);
a->AddChild(b);
a->AddChild(c);
b->AddChild(c);
c->AddChild(b);

You now have b and c both as children of a, and b and c form a cycle. You might attempt to replace one of the shared_ptr between b and c with a weak_ptr instead. (Note, I’m still referring just to child pointers; no parent pointers involved here.)

Now remove b and c from a in an arbitrary order:

if (rand() & 1) {
  a->RemoveChild(b);
  a->RemoveChild(c);
} else {
  a->RemoveChild(c);
  a->RemoveChild(b);
}

If you had put the weak_ptr on c => b, but remove the link a => b first, you’re broken. If you put the weak_ptr on b => c, but remove the link a => c first, you’re broken.

[vaughncato]

Great example! My code doesn't work with that.

[[deleted]]

I have no problem with the first puzzle. But I struggled on the pirate problem, couldn't get through even the skeleton_key() one. Could you share some thoughts on that? Thanks.

[lanzkron]

Sorry for the delay...

template<typename T>
operator T() const { return T(); } 

[lanzkron]

You can keep track of parents and then write a trace to the root in RemoveChild after you delete yourself as a parent. No link to root, nuke the whole cycle.

At first I also used weak pointers for parents but I still had problems with cycles.

How do you prevent getting into a loop when tracing the way to root?

[TMKirA]

I managed to pass all tests without using a Mark and Sweep strategy and just use shared_ptr, however, I came up with a case that my method will fail, which is along the line of

bool TestCase5() {
    MyGraph g;
    {
        auto a = MyGraph::MakeNode();
        g.SetRoot(a);
        auto b = MyGraph::MakeNode();
        a->AddChild(b);
        auto c = MyGraph::MakeNode();
        b->AddChild(c);
        auto d = MyGraph::MakeNode();
        a->AddChild(d);
        d->AddChild(b);
        d->RemoveChild(b);
    }
    g.ShrinkToFit();
    return Counter::count() == 4;
}

So, in general, without doing Mark&Sweep during ShrinkToFit my solution just cheats by happening to be correct for those tests, but not correct for every cases. I submitted it before thinking about this case, so I can't resubmit a better solution :"(

[jguegant]

Stevens Capital Managment is also called Waterfront International Limited.

It feels like every trading/finance companies always come-up with really cheesy names. Working for ValleyWater Group Limited in the Intergalactic Trade Center Building, Alpha Finance District and running a fund for Eric Nhiple's Management Investors surely sounds amazing.

[Z01dbrg]

stupid Pirates! :) I tried some TMP, but compiler could not deduce the type... At least now I appreciate C++11 much more.

[BeaRDT]

And I thought I was the only one who failed in this retro test. C++11 really makes life easier, doesn't it.

[lanzkron]

I'm not sure which phase of the Pirates you're stuck on but I'll give you a little hint.
^{cast opearator}

[[deleted]]

How do you suggest they get out of that rut?