World

Is This Some Kind of Code? You Can Solve the …

The verb “puzzle” — to perplex or confuse, bewilder or bemuse — is of unknown origin. “That kind of fits,” said Martin Demaine, an artist in residence at the Massachusetts Institute of Technology. “It’s a puzzle where the word ‘puzzle’ comes from.”

His son, Erik Demaine, an M.I.T. computer scientist, agreed. “It’s a self-describing etymology,” he said.

The father-son duo is most famous for mathematical investigations into paper folding, with “curved-crease sculptures” — swirling loops of pleated paper that resemble intergalactic interchanges. Curved origami dates to late 1920s Bauhaus; a classic specimen starts as a circular piece of paper, which, when folded along concentric circles, automatically twists into a saddle curve. The Demaines’ trio of pieces, “Computational Origami,” was part of the 2008 “Design and the Elastic Mind” exhibit at the Museum of Modern Art in New York and now resides in its permanent collection.

These days, however, the Demaines are more focused on “algorithmic puzzle fonts,” a suite of mathematically inspired typefaces that are also puzzles. The main application is fun. One font, a homage to the mathematician and juggler Ron Graham, who died in 2020, draws its letters from the patterns of motion traced by balls thrown into the air during juggling tricks.

Another font, proposed by the computer scientist Donald Knuth (almost all fonts involve collaborators), has as its distinguishing characteristic that all letters can be “dissected” — cut into pieces and rearranged — into a 6-by-6 square.

In a 2015 paper, “Fun With Fonts: Algorithmic Typography,” the Demaines explained their motivations: “Scientists use fonts every day to express their research through the written word. But what if the font itself communicated (the spirit of) the research? What if the way text is written, and not just the text itself, engages the reader in the science?”

Inspired by theorems or open problems, the fonts — and the messages they compose — can usually be read only after solving the related puzzle or series of puzzles.

Take, for instance, a new font in their collection that debuts today: the Sudoku Font. The inspiration came in the fall of 2019, when Erik Demaine co-taught the course “Fundamentals of Programming” (with the computer scientist Srini Devadas). During one class, Dr. Demaine and his 400 freshmen and sophomores programmed a Sudoku solver — they wrote code that solved a Sudoku puzzle. Dr. Demaine’s father sat in on the lecture that day, and while half-paying attention Mr. Demaine mused about whether it might be possible to make a font based on Sudoku — that is, based on the puzzles whose unique solutions would somehow reveal letters of the alphabet.

After playing around with various possibilities, the Demaines designed a Sudoku puzzle font that works as follows: First, start with one of their Sudoku puzzles and solve it. Next, draw a line connecting the longest path of squares with consecutive numbers (ascending or descending; but only edge-adjacent squares, not diagonal). That line draws the shape of a letter within the grid of the puzzle. A series of Sudokus thus solved can reveal a message, like so:

The entire suite of puzzle fonts is available, with varying degrees of interactivity, on Dr. Demaine’s website. The Demaines hand-designed the letter shapes, but used a computer to generate the letter-embedding Sudoku puzzles.

“It was hard to design letters that still enabled the puzzle to be solvable, and without adding additional stray connections to the longest path,” Dr. Demaine said. “This was quite a difficult font to design, both for the human and the computer.”

The Demaines began this puzzle-font experiganza around the turn of the century with a dissection puzzle — a puzzle whereby one shape, or polygon, is sliced up and reassembled into other geometric shapes. Their motivation was a problem posed in 1964 by Harry Lindgren, a British-Australian engineer and amateur mathematician: Can every letter of the alphabet be dissected into pieces that rearrange to form a square?

In 2003, building on previous work, the Demaines proved that, yes, indeed it was possible, and they published the result. (Typically, a puzzle font comes with a corresponding research paper.) This first foray was a puzzle only in the sense that the Demaines were perplexed for a while about how to design the font. And they made the challenge more puzzling by adding an extra criterion: They wanted not merely a dissection font, but a “hinged dissection” — a special kind of dissection whereby the pieces are connected (hinged) at their vertexes, forming a closed chain that rearranges, in this case not only into the desired square but also into every other letter of the alphabet.

They succeeded in their quest by deploying the mathematics of “polyforms,” shapes made from multiple copies of a polygon, such as a triangle. More precisely, they used a polyform with the improbable name “polyabolo” (popularized by Martin Gardner, who was a mathematics columnist for Scientific American). A polyabolo is made from congruent right isosceles triangles. A square can be cut into two right isosceles triangles; and those two triangles can in turn be cut into four right isosceles triangles, and those four triangles into eight, and those eight into 16, 16 into 32, 32 into 64, 64 into 128, and so forth.

By this method, the Demaines created their Hinged-Dissection Font. Every letter of the alphabet is dissected into 32 triangles (rendering it a “32-abolo”) that can be rearranged into a 4-by-4 square, or any other letter. But achieving the desired hinged dissection — a connected chain of triangles that can morph from one letter into any other — required that each letter be dissected into 128 triangular pieces (making it a “128-abolo”).

Reflecting on this exercise in an email, the Demaines said: “The fun for us was combining art and math together, aiming for good design (recognizable as letters and looking consistent across the alphabet) within hard mathematical constraints (fixed area and working with polyabolo shapes).”

Twenty years on, those humble beginnings have sprouted into a fabulous fun house of fonts, with artistic media as varied as rods of glass, string art and coins.

Consider the Tiling Font: Each letter “tiles the plane,” meaning, as the Demaines explain, “that infinitely many copies of that one shape can fill two dimensions without leaving any gaps between the tiles.” Perfect for a bathroom renovation.

With the Conveyer Belt Font, each letter is formed by the closed loop of a conveyor belt that curves around strategically placed wheels. (The font name is intentionally spelled “conveyer” rather than “conveyor,” as the font “conveys” letters and words.)

The Conveyer Belt Font was prompted by a still-unsolved problem posed in 2001 by the Spanish mathematician Manuel Abellanas: If there are several two-dimensional and nonoverlapping wheels, or disks, of equal size, can they all be wrapped (connected) with a taut conveyor belt, such that the belt touches all the wheels but doesn’t intersect itself?

The Demaines tried to solve this problem and got stuck. They distracted themselves by designing the font. “That’s always been an important part of our philosophy,” Mr. Demaine said. “If we get stuck on a problem, we like to find an artistic way to represent it.”

The Demaines also find that puzzles are a nice way to initiate newcomers into the fun of formal mathematics. The Checkers Font (in which the letters are formed from paths of jumping moves) came into being when Spencer Congero, a computer science graduate student at the University of California, San Diego, got in touch with the idea. The Spiral Galaxies Font (based on the Japanese pencil-and-paper puzzle of the same name; unique solutions to puzzles form letters) was a collaboration with Walker Anderson, then a student at Central Bucks West High School in Doylestown, Pa., and a member of the USA World Puzzle Championship team.

The puzzle font was Mr. Anderson’s gateway to mathematical research; now he’s an undergrad studying math at M.I.T. For the Demaines, these sorts of collaborations are cause for celebration: One more person successfully “corrupted” into the world of theoretical computer science.

Given their reputation with origami, the Demaines have naturally created a few fonts riffing on the nuances of folding, including the Origami Maze Font, the Simple Fold & Cut Font, the Fold & Punch Font and an Impossible Folding Font.

The Demaines also decided, for a change, to create a minimalistic font requiring only a single fold.

Lest that simplicity make the unsolved font too simple to read, they added a restriction: The letters must be illegible before folding. Most of their typefaces, in fact, are based around similar constraints. The Demaines like to make the task hard but not preposterously so; they don’t want too much freedom or flexibility, since the allure is in the challenge, but they do want the task to be attainable.

With these parameters, they devised the One-Fold Silhouette Font. The silhouette element borrows from a 1900-era “Rabbit Silhouette Puzzle,” in which five cards with cutouts of various animals stack up to produce the silhouette of a rabbit. The One-Fold Silhouette Font works in a similar way. Imagine a transparent sheet, with black markings:

The central vertical crease invites you to fold the sheet in half (from right to left, as if you were turning the page of a book).

And surprise, the text is revealed!

With the Strip-Folding Font, a sequence of letters is folded from a long strip of paper — the constraint here was that every letter had to be foldable using only horizontal, vertical and diagonal folds.

Last fall, the Demaines published their Tetris Font, which is a continuation of their studies into the computational complexity of the iconic falling-block video game. (In 2002 Erik Demaine was conferred the title of “Tetris Master” by the Harvard Tetris Society, in honor of his “intellectual contribution to the art of Tetris,” for a foundational paper, “Tetris Is Hard, Even to Approximate.” )

The upshot of the new result is this: They have proved, in playing the offline version of Tetris (wherein the player has full information in advance about the identity and order of pieces that will drop) that the game is “NP-complete” — meaning that no efficient solution algorithm exists, even with as few as eight columns or four rows. And more practically, as Dr. Demaine described on his website, NP-completeness means “it’s computationally intractable to figure out whether you can survive, or clear the board, given an initial board configuration and a sequence of n pieces to come.”

Initially, the creative constraint for this font was that each letter be constructed as a stacking of one copy of all seven Tetris shapes. Then the Demaines realized it would be neat to animate the font, with letters dropping into formation like pieces in the game — so that each piece placed also had to be supported by the previous pieces, with no extreme overhangs, thus obeying “Tetris physics.” This necessitated a bit of redesign, sometimes with the help of a computer tool (“BurrTools”) that assembled desired shapes from basic unit pieces.

“When us humans got stuck finding a good solution, we’d put some of the shapes we’d been trying into BurrTools, and it would help guide our search,” Dr. Demaine said. “Q” and “M” were among the last letters to fall into place.

Finally, try to fathom Everything Font, also just released today into the wild. It was inspired by those eye charts with “Es” on every line. In the mathematical font context, the letter “E” is what’s called a “canonical form” — every letter of the alphabet can be folded into an “E,” and “E” in turn can be folded into every letter. Which means, ultimately, that every letter can fold into every other letter. (A natural canonical form for protein chains, which fold into various shapes, is the helix.)

So, had this article been written in Everything Font — with each letter bearing a crease pattern (folding instructions) for another letter — there would be another article encoded herein.


Source

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button