What's your favourite algorithm?

[WhiteCube]

I'll get the ball rolling.

The Knuth-Morris-Pratt algorithm.

When I was learning assembly language, we had to code a string search. Start at i, try to match, if it fails, start at i+1 and so on.

It never occured to me that it could be improved. Until I found something called a "precomputed string search" in a book. Aka the KMP algorithm.

It made me ask, "Why didn't I think of that?", and "What else am I overlooking?"

 

[WhiteCube]

Here's something that isn't quite an algorithm, more of an approach. I called it Pascal's triangle variation.

In the normal triangle, each node holds the sum of the two nodes above it, on the previous level. Horizontal position is sum, the left branch represents +0 and the right +1.

My idea was to have 3 branches, +0 +1 and +2. The branches crossed each other if I diagrammed it, but that didn't matter.

Then I generalised it, so the number of branches per node, depended on the level.

Then I generalised it some more by making the number of branches depend on a key, stored in every node.

Then the final tweak was having a factor on each branch, so a number is multiplied when it moves down.

There are some recreational math problems that have complicated solutions when using formulas, but can be solved with a simple program using a PTV.

For example, if you have 3 green balls, 8 yellow, 2 blue, 9 red, and 30 white. How many permutations can you make with 10 balls?

Spoiler

5613987

The node key is, number of balls placed.

Level is colour. For example, the second level is yellow, and there are 8+1 branches per node. (0 yellow, 1 yellow, 2,...8)