Charmed!

Collator Repo on GitHub

Third time’s a charm, they say. New idea feels very good. Woot! It is!

I’m not sure where this structure and algorithm came from: I’m just quite sure that it’s going to be really fine. The idea goes like this:

• A Python dictionary keeps its keys in order of arrival;
• After each production of the output sequence, any names at or beyond the length of the dictionary at that moment will be new;
• So we will prime the dictionary to “Unrun”, keep track of the high water mark, add at will, and then iterate the keys and create Result instances.

I plan to set this new class up as a Context Manager, using with to drive it. We’ll build this in the current repo. Begin with a test.

class TestDictCollator:
    def test_exists(self):
        DictCollator()

That passes with a trivial class. Now with:

    def test_context_manager(self):
        c = DictCollator()
        with c as d:
            pass

That fails, of course:

def test_context_manager():
        c = DictCollator()
>       with c as d:
E       TypeError: 'DictCollator' object does not support the context manager protocol

We respond accordingly:

class DictCollator:
    def __enter__(self):
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        pass

Green. Let’s commit, I have a good feeling about all this. Commit: initial DictCollator.

Let’s test add:

    def test_add_a_few(self):
        dc = DictCollator()
        with dc as collator:
            dc.add('TestFoo', "Pass")
            dc.add('TestBar', "Fail")

That will drive out some code. I have no assertion, though, and I’d like to do this by the book. Doggone it, this is a lot but I’m going to ask for a report.

    def test_add_two_and_report(self):
        dc = DictCollator()
        with dc as collator:
            dc.add('TestFoo', "Pass")
            dc.add('TestBar', "Fail")
            results = dc.results()
            assert len(results) == 2

I won’t make any assumptions here about what we get back. That will keep the step smaller. We still need to add a bit:

class DictCollator:
    def __init__(self):
        self.collator = dict()

    def __enter__(self):
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        pass

    def add(self, name, outcome):
        self.collator[name] = outcome

    def results(self):
        return self.collator.keys()

Now let’s return Result instances with a constant is_new:

    def test_add_two_and_report(self):
        dc = DictCollator()
        with dc as collator:
            dc.add('TestFoo', "Pass")
            dc.add('TestBar', "Fail")
            results = dc.results()
            assert len(results) == 2
            self.check(results,
               0, 'TestFoo', 'Pass', True)
            self.check(results,
               1, 'TestBar', 'Fail', True)

I’m using the same check as in the other tests, copied over to this test class. Make it work:

    def results(self):
        result = []
        for name, outcome in self.collator.items():
            result.append(Result(name, outcome, True))
        return result

I prefer to write list answers out longhand when I first create them, but now we’ll do a comprehension. The other version of Collator returns generators. I think here we’ll just do a list.

Nearly there. There are two features left to do: we need to deal with is_new, and we need to return Unrun for tests not run. We’ll do is_new next:

    def test_old_and_new(self):
        dc = DictCollator()
        with dc as collator:
            dc.add('TestFoo', "Fail")
        with dc as collator:
            dc.add('TestBar', "Pass")
            dc.add('TestFoo', "Fail")
            results = dc.results()
        self.check(results,0, 'TestFoo', 'Fail', False)
        self.check(results,1, 'TestBar', 'Pass', True)

My cunning plan for this is to keep a high-water mark, in enter, and use it in results, like this:

    def results(self):
        return [Result(name, outcome, i>=self.high_water)
            for i, (name, outcome) in enumerate(self.collator.items())]

Test passes. I missed a commit or two. Bad Ron, no biscuit! Commit: DictCollator working.

That was a bit overstated. I should have said is_new working. We need more thing; “Unrun”.

    def test_unrun(self):
        dc = DictCollator()
        with dc as collator:
            dc.add('TestFoo', "Fail")
        with dc as collator:
            dc.add('TestBar', "Pass")
            results = dc.results()
        self.check(results,0, 'TestFoo', 'Unrun', False)
        self.check(results,1, 'TestBar', 'Pass', True)

And here’s the sweet spot:

    def __enter__(self):
        self.high_water = len(self.collator)
        for key in self.collator:
            self.collator[key] = 'Unrun'
        return self

Upon enter, we simply initialize all our dictionary’s current values to ‘Unrun’, and any that are in fact run will override that outcome. We assume they are all unrun, and we learn otherwise when they are run.

We are green. Commit: DictCollator supports Unrun and is_new like a charm!

We’re Done

This is all there is to it:

class DictCollator:
    def __init__(self):
        self.collator = dict()
        self.high_water = 0

    def __enter__(self):
        self.high_water = len(self.collator)
        for key in self.collator:
            self.collator[key] = 'Unrun'
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        pass

    def add(self, name, outcome):
        self.collator[name] = outcome

    def results(self):
        return [Result(name, outcome, i>=self.high_water)
            for i, (name, outcome) in enumerate(self.collator.items())]

We could write more tests, and probably should. Not that I’m not confident: If anything, I’m too confident.

Let’s at least write a three phase more complicated one.

    def test_three_phases(self):
        dc = DictCollator()
        with dc:
            dc.add('TestFoo', "Pass")
            dc.add('TestBar', "Pass")
            dc.add('TestBaz', "Fail")
            results = dc.results()
        assert [r.name for r in results] == ['TestFoo', 'TestBar', 'TestBaz']
        assert [r.outcome for r in results] == ['Pass', 'Pass', 'Fail']
        assert [r.is_new for r in results] == [True, True, True]

        with dc:
            dc.add('TestFoo', "Fail")
            dc.add('Test2New', 'Pass')
            results = dc.results()
        assert [r.name for r in results] == ['TestFoo', 'TestBar', 'TestBaz', 'Test2New']
        assert [r.outcome for r in results] == ['Fail', 'Unrun', 'Unrun', 'Pass']
        assert [r.is_new for r in results] == [False, False, False, True]

        with dc:
            dc.add('TestBar', 'Fail')
            dc.add('Test3New', 'Pass')
            results = dc.results()
        assert [r.name for r in results] == ['TestFoo', 'TestBar', 'TestBaz', 'Test2New', 'Test3New']
        assert [r.outcome for r in results] == ['Unrun', 'Fail', 'Unrun', 'Unrun', 'Pass']
        assert [r.is_new for r in results] == [False, False, False, False, True]

I devised a new assertion scheme that I prefer. Easier to type and easier to get the right answers put in.

I claim this works. Commit: three phase test added. Let’s sum up. This will take a while, there’s a lot to think about.

Reflection

First of all, let’s get this out of the way: I am really happy with this solution and the overall process to get it. But I cannot explain how I did it. I have solved the problem three times now, not counting any false starts, and not counting any ideas that I thought about and rejected. And sometime between yesterday’s article and this morning at 0400, this idea came to me.

I had most of it when I went to bed. There are these key ideas involved:

1. Python dictionaries return keys in the order added. Therefore, if we iterate the keys, we’ll have the report order.
2. If we remember the next index available in the dictionary, any indices at or above that index will be new and below will be old.
3. If we save the outcome in the dictionary, as we’ve been doing anyway, we’ll have all we need for the results.
4. We can reinitialize all the entries to Unrun and then the next batch will override just the ones that were run.

At 4 AM I woke up and wanted to verify what I was sure about, that setting a key a second time did not reorder the dictionary. That is critical to this idea working. I got up, tested that, and went back to bed.

And you’ve seen the rest. We went in this order:

1. Test-drive the trivial class.
2. Test-drive with.
3. Test adding two runs and getting two unchecked items back.
4. Extend that test to check that we got expected Result instances. This one drove out the loop in results, and we refactored it to a comprehension, as one does.
5. Test two phases, old vs new, with all tests run (no ‘Unrun’ returns needed). This drove out the high water mark.
6. test ‘Unrun’, driving out the initialization of the dictionary to have all ‘Unrun’ entries.

Assessment

This went very smoothly, and I think this implementation is quite solid. It is one class, twenty lines long. Five methods. The longest method, __enter__, is only five lines long, including its def line and return self.

My previous solution, the second that I did, which I liked fairly well, was two classes, each about 30 or 35 lines long. One of those classes uses an auxiliary class, AgedName, that is just a simple dataclass. That solution separates sequencing, keeping the names in order and listing them, from keeping the outcomes and creating the result.

All of that behavior is included in the twenty lines written this morning. Today’s program is 1/4 the size of the previous one.

My initial solution, which came with a terrible process that felt like grotesque hackery to me, was also about 80 lines after substantial refactoring, with four classes, Collator and NameKeeper being the main ones.

I would have to study the first and second to make a decent comparison of the code. I did the second primarily because I felt I had not been working well. I was OK with the outcome but I felt I had gotten there by brute strength, not by using sensible practices and taking appropriately small steps. I think the first two are similar in that they separate out the concerns of keeping the test order and the test outcomes, using two fairly large classes of around 40 lines each. In this solution, it’s all handled by a dictionary and an integer.

Today’s, I did because I was certain that it was a far better idea.

What does this tell us?

GeePaw wanted to see what those of us working on this did with what he calls a Data Structures and Algorithms question. I did it, to be helpful, but mostly because it seemed like an interesting problem, with just enough complexity to make a fun puzzle.

My initial designs both separate keeping the names in order and managing the outcomes. I think it’s fair to say that the separation keeps order and newness separate, as both solutions keep two containers, one for known names and one for unknown. The current solution just remembers however many it had last time and knows that any items above that count are new.

The initial two solutions create the ‘Unrun’ status dynamically, upon finding that there is no expected entry in the outcomes dictionary, therefore the test was not run. Today’s solution initializes all the outcomes to ‘Unrun ‘, and tests that are added override that value, leaving un-run tests marked ‘Unrun’. Simple, elegant, just makes sense.

Technical Debt?

Is this a kind of “technical debt” situation? As Ward initially described it, it kind of is. I saw, on day five, a solution to the problem that was simpler. The solution collapsed down into a smaller, simpler one.

How did I do this?

I have no idea how I did it. I just kept playing with the problem, in code, in little sketches that didn’t amount to much, and in my head. And this one came to me.

Can this be improved?

I’ve not done type hinting this morning. Other than that, I don’t see anything I would do. Perhaps tomorrow I’ll see something. Perhaps the team will have ideas next Tuesday night. We’ll see.

If anyone comes up with a nicer solution than this one, I will be absolutely delighted to see it. It will surely be a marvel. I will also be a bit surprised.

A final thought

I wish I had a way of organizing my DS&A thinking so that I could lay it out to you in a short article. I do not have that ability at this time. I just turn the problem over in my mind, looking for places to cleave it into smaller problems. I look at it and pluck out ideas, like “hey, anything actually added is new”.

I take it apart, put it together, trying to find pieces that make sense together or separately.

And I do it again, and again, and again. Maybe that’s the lesson: Next time better.

See you … next time! I’m almost sure we’ll go back to Forth.