Recursive Data Structures

5. Isomorphic data structures

When we have what ought to be an elegant algorithm, but the interface between the algorithm and the data structure ends up being as complicated as the rest of the algorithm put together, we can always ask ourselves, "What data structure would make this algorithm stupidly simple?"

The answer can often be found by imagining a data structure that looks like the algorithm's basic form. If we follow that heuristic, our data structure would be recursive, rather than ‘flat.' Since we do all kinds of work sorting out which squares form the four regions of a bigger square, our data structure would describe a square as being composed of four region squares.

Such a data structure already exists, it's called a quadtree. Squares are represented as four regions, each of which is a smaller square or a cell. A simple implementation is a "Plain Old JavaScript Object" (or "POJO") with properties for each of the regions. If the property contains a string, it's cell. If it contains another POJO, it's a quadtree.

A square that looks like this:

⚪️⚫️⚪️⚪️
 ⚪️⚪️⚫️⚪️
 ⚫️⚫️⚫️⚪️
 ⚪️⚪️⚪️⚪️

Is composed of four regions, the ul ("upper left"), ur ("upper right"),  lr ("lower right"), and ll ("lower left"), something like this:

ul | ur
 ---+---
 ll | lr

Thus, for example, the ul is:

⚪️⚫️
 ⚪️⚪️

And the ur is:

⚪️⚪️
 ⚫️⚪️

And so forth. Each of those regions is itself composed of four regions. Thus, the ul of the ul is  ⚪️, and the ur of the  ul is ⚫️.

The quadtree could be expressed in JavaScript like this:

const quadTree = {
  ul: { ul: '⚪️', ur: '⚫️', lr: '⚪️', ll: '⚪️' },
  ur: { ul: '⚪️', ur: '⚪️', lr: '⚪️', ll: '⚫️' },
  lr: { ul: '⚫️', ur: '⚪️', lr: '⚪️', ll: '⚪️' },
  ll: { ul: '⚫️', ur: '⚫️', lr: '⚪️', ll: '⚪️' }
};

Now to our algorithm. Rotating a quadtree is simpler than rotating an array of arrays. First, our test for indivisibility is now whether something is a string or not:

const isString = (something) => typeof something === 'string';

The value of an indivisible cell remain the same, itself.

Our divide function is simple: quadtrees are already divided in the manner we require, we just have to turn them into an array of regions:

const quadTreeToRegions = (qt) =>
  [qt.ul, qt.ur, qt.lr, qt.ll];

And finally, our combine function reassembles the rotated regions into a POJO, rotating them in the process:

const regionsToRotatedQuadTree = ([ur, lr, ll, ul]) =>
  ({ ul, ur, lr, ll });

And here's our function for rotating a quadtree:

const rotateQuadTree = multirec({
  indivisible : isString,
  value : itself,
  divide: quadTreeToRegions,
  combine: regionsToRotatedQuadTree
});

Let's put it to the test:

rotateQuadTree(quadTree)
  //=>
    ({
       ul: { ll: "⚪️", lr: "⚫️", ul: "⚪️", ur: "⚫️" },
       ur: { ll: "⚪️", lr: "⚫️", ul: "⚪️", ur: "⚪️" },
       lr: { ll: "⚪️", lr: "⚪️", ul: "⚫️", ur: "⚪️" },
       ll: { ll: "⚪️", lr: "⚪️", ul: "⚪️", ur: "⚫️" }
     })

If we reassemble the square by hand, it's what we expect:

⚪️⚫️⚪️⚪️
 ⚪️⚫️⚪️⚫️
 ⚪️⚫️⚫️⚪️
 ⚪️⚪️⚪️⚪️