NaBloPoMo #13

A first draft recursive function to solve a problem I found on codewars. I am happy with the recursion, but I’m finding that it struggles when the initial row is up to 100,000 characters long. I think that means there’s a secret to working this out – or, at least, a more efficient way than just brute-forcing it. Comments welcome!

Problem Description

A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.

My code

class Triangle:
    def __init__(self):
        self.colours = {'R', 'G', 'B'}

    def triangle(self, row):
        if len(row) == 1:
            return row[0]
            new_row = []
            for i in range(len(row) - 1):
                parent_colours = set(row[i:i + 2])
            return self.triangle(new_row)

    def child_colour(self, parent_colours: set) -> str:
        if len(parent_colours) == 1:
            return parent_colours.pop()
            return self.colours.difference(parent_colours).pop()

So: this class has two methods, triangle and child_colour. triangle calls itself until it reaches its exit condition. The exit condition comes when we’ve only got one letter in row – that is to say, we’re down to the bottom level of the triangle.

If we’re not at that point yet, the method works out what the next row would be and passes it to a new instance of the same method.

Before very long, it’s triangles all the way down – until at last one reaches the exit condition. At this point I imagine all the methods snapping back together in exactly the way Terry Pratchett described the Cabinet of Curiosity. A cabinet where the first shelf contains another shelf that shoots off at a right angle, and that shelf branches another, and another, and another – until the answer is found. Then the first shelf draws back, and then the second, and then the third which somehow passes through the sixth and ninth because human brains can’t even see the eighth colour of the rainbow.

And then, at last, in the only drawer in the cabinet, is the answer you were looking for.

Look, he does it much better than I do. This is really just a recommendation to read Making Money. Ignore the code entirely.

November is National Blog Posting Month, or NaBloPoMo. I’ll be endeavouring to write one blog post per day in the month of November 2019 – some short and sweet, others long and boring.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s