22 set 2020

Brainstorming With Factoring

In the last post I described how I sometimes describe a problem with a matrix, and then look at the matrix transpose to see if it gives me new ideas. Another technique I use is to look for a factoring.

In algebra, factoring transforms a polynomial like 5x² + 8x - 21 into (x + 3)·(5x - 7). To solve 5x² + 8x - 21 = 0, we can first factor into (x + 3)·(5x - 7) = 0. Then we say that x + 3 = 0 or 5x - 7 = 0. Factoring turns a problem into several easier problems.

x 3
5x 5x² 15x
-7 -7x -21

Let's look at an example: I have six classes, File, EncryptedFile, GzipFile, EncryptedGzipFile, BzipFile, EncryptedBzipFile. I can factor these into a matrix:

Uncompressed Gzip Bzip
Unencrypted File Gzip(File) Bzip(File)
Encrypted Encrypt(File) Encrypt(Gzip(File)) Encrypt(Bzip(File))

Using the Decorator pattern (or mixins), I've turned six different types of files into four components: plain, gzip, bzip, encrypt. This doesn't seem like much savings, but if I add more variations, the savings will add up. Factoring turns O(M*N) components into O(M+N) components.

Another example comes up when people ask me things like "how do you write linear interpolation in C#?" There are a lot of potential tutorials I could write:

C++ Python Java C# Javascript Rust Idris
Interpolation
Neighbors
Pathfinding
Distances
River maps
Isometric
Voronoi
Transforms

If there are M topics and N languages, I could write M*N tutorials. However, that's a lot of work. Instead, I write a tutorial about interpolation, someone else writes a tutorial about C#, and then the reader combines knowledge of C# with knowledge about interpolation to write the C# version of interpolation.

Like transpose, factoring only helps sometimes, but when it applies, it can be quite useful.