Anagrams

An anagram is a word spelled by rearranging the letters of another word. The “other word” may or may not be a real word; if it is not, we say the letters have been jumbled or scrambled. Note that some “other words” yield more than one anagram. The letters TPSO, for example, can be rearranged to spell OPTS, POST, POTS, SPOT, STOP, and TOPS.

The obvious way to extract an anagram from a jumbled string of letters is to arrange the letters in all possible ways, checking each arrangement against a lexicon (ie, a list of valid words). This brute-force approach can quickly get out of hand, however. The number of ways that three unique letters can be arranged is only 3 times 2 times 1, or 6; but the number of ways that 9 unique letters can be arranged is 362,880. So we need a better way.

The not-so-obvious way to extract an anagram from a jumbled string is to first convert the lexicon into a dictionary where each entry in the dictionary is a sorted word, and the “definition” is the original, unscrambled word. These are the Plain English type definitions we need to describe that:

A dictionary is a thing with some entries.
An entry is a thing with a sorted string and a string.

Our Plain English development system includes a lexicon of the 64,000 most commonly used English words in the form of a text file, one word per line, so we can use that to make our dictionary. These are the Plain English routines that do that:

To create a dictionary:
Allocate memory for the dictionary.
Put “z:\g4g articles\anagrams\lexicon.txt” into a path.
Read the path into a buffer.
Slap a rider on the buffer.
Loop.
Get a string from the buffer given the rider.
If the string is blank, break.
Trim the string.
Sort the string into a sorted string.
Add an entry to the dictionary using the sorted string and the string.
Repeat.

To add an entry to a dictionary given a sorted string and a string:
Allocate memory for the entry.
Put the string into the entry’s string.
Put the sorted string into the entry’s sorted string.
Append the entry to the dictionary’s entries.

A random sample of entries from our “anagram dictionary” looks like this:

aeprrs parser
aeprrss parsers
aeprrss sparser
aeprrssstu superstars
aeprrsstu superstar
aeprrssy sprayers
aeprrstu raptures
aeprrsy prayers
aeprrsy sprayer
aeprrtu rapture

Note that some of the sorted words (like aeprrss) have more than one “definition” (like parsers and sparser).

Now we can find all the anagrams for a given string simply by sorting the input string and searching for matches in the dictionary. Here are the Plain English routines that do that:

To run:
Start up.
Create the dictionary.
Loop.
Write “Enter a scrambled word: ” on the console without advancing.
Read a string from the console. If the escape key is down, break.
Unscramble the string.
Repeat.
Write “Done…” on the console.
Destroy the dictionary.
Shut down.

To unscramble a string:
Trim the string.
Lowercase the string.
Sort the string into a sorted string.
Loop.
Get an entry from the dictionary’s entries.
If the entry is nil, break.
If the entry’s sorted string is not the sorted string, repeat.
Write the entry’s string on the console.
Repeat.

A typical run looks like this:

It takes a second or two to create the dictionary, but that only has to be done once, and it can be saved for later use. The unscrambling part is aaeinnnossttu. Whoops! Sorry. I meant to say, “instantaneous.”

A Jigsaw Puzzle

This is a fun little program that cuts a picture into pieces, splatters them around the screen, then lets the user put them back together by pushing them around with the mouse. Here are the Plain English type definitions:

A puzzle is a thing with a box, a picture and some pieces.
A piece is a thing with a box and a picture.

And here is the main routine:

To run:
Start up.
Create a puzzle from “c:\g4g articles\jigsaw\maga.jpg”.
Display the puzzle.
Show the arrow cursor.
Loop.
Deque an event.
If the event is nil, break.
If the event’s kind is “key down”, break.
If the event’s kind is not “left click”, repeat.
Track the mouse on the puzzle.
Repeat.
Destroy the puzzle.
Shut down.

These are the Plain English routines that create a puzzle:

To create a puzzle from a path:
Allocate memory for the puzzle.
Make the puzzle’s box 8 inches by 8 inches.
Center the puzzle’s box in the screen’s box.
Fetch the puzzle’s picture from the path.
Resize the puzzle’s picture to 8 inches by 8 inches.
Center the puzzle’s picture in the puzzle’s box.
Cut the puzzle into pieces.
Splatter the puzzle’s pieces.

To cut a puzzle into pieces:
Draw the puzzle’s picture.
Put the puzzle’s left-top into a spot.
Loop.
Allocate memory for a piece. Append the piece to the puzzle’s pieces.
Put the spot and the spot plus 2 inches into the piece’s box.
Extract the piece’s picture using the piece’s box.
Add 2 inches to the spot’s left.
If the spot’s left is less than the puzzle’s right, repeat.
Put the puzzle’s left into the spot’s left.
Add 2 inches to the spot’s top.
If the spot’s top is the puzzle’s bottom, break.
Repeat.

To splatter some pieces:
Make a box 1 inch smaller than the screen’s box.
Loop.
Get a piece from the pieces.
If the piece is nil, break.
Pick a spot anywhere in the box.
Round the spot to the nearest multiple of 1/4 inch.

Center the piece’s box on the spot.
Center the piece’s picture on the spot.
Repeat.

This is how we draw a puzzle’s pieces on the screen:

To display a puzzle:
Clear the screen without refreshing.
Loop.
Get a piece from the puzzle’s pieces.
If the piece is nil, break.
Draw the piece’s picture.
Repeat.
Refresh the screen.

And this is typical of how the splattered pieces of a puzzle look:

These are the routines we use to track the user’s mouse movements:

To track the mouse on a puzzle:
Find a piece of the puzzle given the mouse’s spot.
If the piece is nil, exit.
Loop.
If the mouse’s left button is up, exit.
Put the mouse’s spot into a spot.
Round the spot to the nearest multiple of 1/4 inch.
Center the piece’s box on the spot.
Center the piece’s picture on the spot.
Display the puzzle.
Repeat.

To find a piece of a puzzle given a spot:
Get the piece from the puzzle’s pieces (backwards).
If the piece is nil, exit.
If the spot is not in the piece’s box, repeat.

Note that we “snap” the pieces to a 1/4-inch grid so they’ll fit together easily. Note also that we search for pieces in the opposite order they are drawn (ie, backwards) so that the front-most piece gets selected first.

This is what the pieces of our sample puzzle look like once they’ve been properly arranged:

It’s a painting I did a while back. I called it “Make America GREEN Again.”

The Travelling Salesman

Our goal in this exercise is to find a reasonably short route through an arbitrary number of cities splattered, randomly, on a map (or in this case, on the screen). We begin with just two Plain English type definitions:

A city is a thing with a number, a spot and a visited flag.
A nearest neighbor is a city.

Then we create a list of five cities at random locations on the screen using this routine:

To create some cities:
Put 5 into a number.
Make a box 1 inch smaller than the screen’s box.
Loop.
Pick a spot anywhere in the box.
Allocate memory for a city.
Put the spot into the city’s spot.
Append the city to the cities.
Subtract 1 from the number. If the number is 0, break.
Repeat.
Put 1 into the cities’ first’s number.

The starting city is at the top of the list and is marked with the number “1”. When we draw those cities on the screen they look like this:

Then we arrange those cities into a reasonable sequence for the travelling salesman. We do this using the Nearest Neighbor algorithm. It doesn’t guarantee the shortest possible path, but it is very simple and very fast and produces a reasonably short path through the cities. Great engineering seeks a balance between competing objectives.

This is the Plain English routine that implements the Nearest Neighbor algorithm:

To arrange some cities for a travelling salesman (nearest neighbor algorithm):
Get a city from the cities.
If the city is nil, break.
Set the city’s visited flag.
Find a nearest neighbor to the city in the cities.
If the nearest neighbor is nil, break.
Remove the nearest neighbor from the cities.
Insert the nearest neighbor into the cities after the city.
Repeat.
Number the cities.
Draw the cities.

Finding the nearest neighbor of a city requires calculating the distance between the current city and all of the other cities, which is accomplished using this routine:

To find a nearest neighbor to a current city in some cities:
Void the nearest neighbor.
Put the largest number into a shortest distance.
Loop.
Get a city from the cities.
If the city is nil, break.
If the city is the current city, repeat.
If the city’s visited flag is set, repeat.
Get a distance between the city and the current city.
If the distance is not less than the shortest distance, repeat.
Put the distance into the shortest distance.
Put the city into the nearest neighbor.
Repeat.

Since we Osmosians don’t believe in transcendental functions (like sine and cosine), we calculate the Minkowski distance between the cities using this simple and speedy routine:

To get a distance between a spot and another spot (minkowski):
Put the spot’s x minus the other spot’s x into a number.
De-sign the number.
Put the spot’s y minus the other spot’s y into another number.
De-sign the other number.
Put the number plus the other number into the distance.

Once the cities are arranged in a proper sequence, we can redraw the map like this:

And that’s about all there is to it. But before we go, let’s see what it does with 99 cities (the biggest number that will fit inside a city circle on the map). I eliminated the intermediate lines and the distance numbers for this test to keep the screen from getting too cluttered:

Less than a second to run, and a pretty good path. I also tried it with 1,000 cities (and smaller city markers, the starting city marked in red). It still took less than a second…

…but you can see it got lost a couple of times. But who knows? Maybe our salesman likes a long, quiet drive now and then, to collect his thoughts or listen to the radio.

Fibonacci Fables

The Fibonacci Sequence is a sequence of numbers where each number equals the sum of the two preceding numbers. Except, of course, for the second number in the series, because it only has one number preceding it. So we cheat a little at the start, putting two ones there to get the thing going.

This is a Plain English program that lists all the Fibonacci Numbers less than 1000:

To run:
Start up.
Put 1 into a first number. Write the first on the console.
Put 1 into a second number. Write the second on the console.
Loop.
Add the first to the second giving a third number.
If the third is greater than 1000, break.
Write the third on the console.
Put the second into the first.
Put the third into the second.
Repeat.
Wait for the escape key.
Shut down.

These are the numbers we get when we run that:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

Now here’s a little program that does something interesting with the first few of those numbers:

To run:
Start up.
Clear the screen with the tan color.
Start in the middle of the screen facing south.
Move 1-3/4 inches right and 1 inch down.
Draw some fibonacci squares starting with 1/4 inch.
Refresh the screen.
Wait for the escape key.
Shut down.

To draw some fibonacci squares starting with a length:
Use the brown pen.
Put the length into a first length. Draw a fibonacci square using the first length.
Put the length into a second length. Draw the fibonacci square using the second length.
Loop.
Add the first length to the second length giving a third length.
Draw the fibonacci square using the third length.
If the third length is greater than 4 inches, break.
Put the second length into the first length.
Put the third length into the second length.
Repeat.

To draw a fibonacci square given a length:
Stroke the length. Turn left.
Stroke the length. Turn left.
Stroke the length. Turn left.
Stroke the length. Turn left.
Move the length. Turn left. Move the length.

The result on the screen looks like this:

You can see that once we get rolling, each square mates with the two squares that came before it.

And with just two more routines, we can lay a Fibonacci Spiral on top of those Fibonacci Squares. Here are the additional routines:

To draw a fibonacci spiral starting with a length:
Use the fat black pen.
Put the length into a first length.
Draw a quarter circle the first length times 2 wide (backwards).
Put the length into a second length.
Draw the quarter circle the second length times 2 wide (backwards).
Loop.
Add the first length to the second length giving a third length.
Draw the quarter circle the third length times 2 wide (backwards).
If the third length is greater than 4 inches, break.
Put the second length into the first length.
Put the third length into the second length.
Repeat.

To draw a quarter circle a width wide (backwards):
Put the width times 355/113 divided by 96 into a segment length.
Loop.
Turn left 1/96 of the way.
Stroke the segment length.
Add 1 to a count.
If the count is 24, exit.
Repeat.

When we run that, the nifty result we get looks like this:

You probably noticed that I had to use an approximation for pi (355/113) because Plain English is a whole-number-only language. I wasn’t entirely happy with that, so I got into our built-in wysiwyg page editor to see if I could get to a Fibonacci Spiral without using pi, or an approximation of pi, at all. I started by drawing the Fibonacci Squares, by hand:

It was easy because our editor has a handy snap-to-grid feature. Then I colored that “grid” light blue and drew a simple polygon on top of it in black:

Finally, I smoothed that polygon three times. Et voila! An almost-Fibonacci Spiral:

Our all-integer smoothing technique is described in another article I’ve posted on this blog.

I admit the two spirals aren’t exactly the same, but then neither are all the supposed Fibonacci Spirals in the real world. It is nearly (if not entirely) impossible, for example, to fit a Fibonacci Spiral to a real-life Nautilus shell. Check it out. Look closely at all those overlaid images on Google and you’ll see that the supposed correspondence is just one more mathemagical myth; a Fibonacci Fable, we might say.

But I don’t want to leave this article on a negative note, so let’s have a little fun with a simpler kind of spiral that is drawn with this routine:

To draw a spiral starting with some twips;
To draw a spiral given a size:
Privatize the size.
Loop.
Draw a half circle given the size.
Divide the size by 2.
Add 1 to a count. If the count is 5, break.
Repeat.

But let’s not just draw one; let’s draw lot’s of ’em:

To run:
Start up.
Clear the screen with the tan color.
Start in the middle of the screen facing north.
Move 2 inches left and 1 inch down.
Loop.
Use the brown pen. Use the fat pen.
Draw a spiral starting with 6 inches.
Turn 1/10 of the way around.
Add 1 to a count. If the count is 5, break.
Repeat.
Refresh the screen.
Wait for the escape key.
Shut down.

Here’s the result:

As Israel Kamakawiwo’ole used to sing, “What a Wonderful World!” It’s cool that we have the privilege, as Johannes Kepler put it, “of thinking God’s thoughts after Him.” Credit where credit is due. I suspect that when we finally figure out exactly what makes a Nautilus shell what it is, we’ll find it’s more like an algorithm than an equation.

Sierpinski & Koch

Two of the most famous fractals are the Sierpinski Triangle and the Koch Snowflake.

A Sierpinski Triangle in Plain English

This is a Plain English description of how to draw a Sierpinski Triangle:

To draw a Sierpinski Triangle starting with a size:
If the size is less than 1/8 inch, exit.
Draw another Sierpinski Triangle starting with the size divided by 2.
Draw a line using the size for the length.
Refresh the screen.
Turn right 1/3 of the way around.
Add 1 to a count. If the count is 3, break.
Repeat.

If we call the above routine from this top-level routine…

To run:
Start up.
Clear the screen with the tan color. Use the dark brown pen.
Start 4 inches to the left and 3-1/2 inches down from the screen’s center.
Turn right 1/12 of the way around.
Draw a Sierpinski Triangle starting with 8 inches.
Wait for the escape key.
Shut down.

…this is what we get on the screen:

Triangles within triangles within triangles. Nifty.

A Koch Snowflake in Plain English

Now these are the Plain English routines we need to draw a Koch Snowflake:

To draw a Koch Snowflake given a size and a depth:
Loop.
Draw a Koch Curve with 3 inches and the depth.
Refresh the screen.
Turn left 1/3 of the way around.
Add 1 to a count. If the count is 3, break.
Repeat.

To draw a Koch Curve given a size and a depth:
If the depth is 0, draw a line using the size for the length; exit.
Put the size divided by 3 into a new size.
Draw the Koch Curve given the new size and the depth minus 1.
Turn right 1/6 of the way.
Draw a second Koch Curve given the new size and the depth minus 1.
Turn left 2/6 of the way.
Draw a third Koch Curve given the new size and the depth minus 1.
Turn right 1/6 of the way.
Draw a fourth Koch Curve given the new size and the depth minus 1.

If we position ourselves properly on the screen and call the first routine above four times, increasing the depth by one each time, we get this on the screen:

1. At the top-left, we see that our snowflake, at depth zero, is just a simple triangle.

2. At the top-right, one level deeper, we see that each of the sides of the triangle has been divided into three parts, the middle part being replaced with a “peak”.

3. Continuing clockwise around the screen, at the bottom-right, we see that at the next level down, each of the sides of preceding figure is again divided into thirds, with the middle third being replaced by a peak of the appropriate size.

4. Finally, at the bottom-left, yet another level down, we see the finished snowflake. I say “finished” even though we could go deeper and deeper if our screen had the resolution to display it clearly.

A Koch Triangle in Plain English

Something curious happens if, when we’re drawing a Koch Snowflake, we turn right instead of left at each of the original vertices (the revised routine is shown below, with the modified word in all uppercase letters).

To draw a Koch Snowflake given a size and a depth:
Loop.
Draw a Koch Curve with 3 inches and the depth.
Refresh the screen.
Turn RIGHT 1/3 of the way around.
Add 1 to a count. If the count is 3, break.
Repeat.

The result is an “inside-out” snowflake, or what I call, a Koch Triangle:

Comparing the top-right figure with the finished bottom-left figure, perhaps a better name would be “The Mitsubishi Logo on Steroids.”

Another curious thing happens when we tile some Koch Snowflakes; we get the flakes and the triangle together. Here’s the main routine…

To run:
Start up.
Clear the screen with the tan color. Use the dark brown pen.
Turn right 7/12 of the way around. Move up 1/2 inch.
Loop.
Draw a Koch Snowflake given 4 inches and 3.
Turn right 1/3 of the way around.
Add 1 to a count. If the count is 3, break.
Repeat.
Wait for the escape key.
Shut down.

…and here’s the result:

We can get other interesting results if we base our snowflakes on, say, a hexagon rather than a triangle. Here’s a main routine that does that (by turning 1/6 instead of 1/3 of the way around), with some tiling as well:

To run:
Start up.
Clear the screen with the tan color. Use the dark brown pen.
Turn right 7/12 of the way around.
Loop.
Draw a Koch Snowflake given 3 inches and 3.
Turn right 1/6 of the way around.
Add 1 to a count. If the count is 6, break.
Repeat.
Wait for the escape key.
Shut down.

And here’s what the screen looks like when we run that:

Well, I could go on all day with this kind of thing, but I’m sure you get the idea. More fun and interesting programs written entirely in Plain English.

Random Numbers

When a programmer asks for a a series of random numbers, he typically doesn’t want truly random numbers. What he generally wants is numbers that are evenly distributed over a given range, supplied in an unexpected sequence.

Plain English’s random number generator is a hybrid of English and Intel x86 machine code (for speed). It uses a “seed” that is initialized to the system’s tickcount when a program starts running. The seed can be set by the programmer to a specific value if he wants the same sequence of numbers to be generated with each run. This is the routine:

To pick a random number between a min number and a max number:
Put the seed’s whereabouts into eax.
Intel $8BC8. \ mov ecx,eax \ calculate zero based max
Intel $8B8510000000. \ mov eax,[ebp+16]
Intel $8B00. \ mov eax,[eax] \ dereference
Intel $8B9D0C000000. \ mov ebx,[ebp+12]
Intel $2B03. \ sub eax,[ebx]
Intel $40. \ inc eax \ adjust randseed
Intel $691105840808. \ imul edx,[ecx],134775813
Intel $42. \ inc edx
Intel $8911. \ mov [ecx],edx
Intel $F7E2. \ mul edx
Intel $0313. \ add edx,[ebx] the min
Intel $8B9D08000000. \ mov ebx,[ebp+08] 
Intel $8913. \ mov [ebx],edx
Put the random number into the context’s number.

Everything following a backslash to the end of the line is a comment. Comments appear in a different color than “code” in our editor so they can be easily ignored. (The colors in this article are reversed.) The algorithm is essentially the same as the linear congruential generatorthat was used in Borland’s Turbo Pascal.

Now here is a program that illustrates exactly how uniform a distribution that routine generates:

To run:
Start up.
Clear the screen using the tan color.
Make a box 2 inches by 2 inches.
Center the box on the screen. Move the box left 5 inches.
Fill and label the box with random spots stopping at 100.
Move the box right 2-1/2 inches.
Fill and label the box with random spots stopping at 1000.
Move the box right 2-1/2 inches.
Fill and label the box with random spots stopping at 10000.
Move the box right 2-1/2 inches.
Fill and label the box with random spots stopping at 100000.
Move the box right 2-1/2 inches.
Fill and label the box with random spots stopping at 1000000.
Refresh the screen.
Wait for the escape key.
Shut down.

To fill and label a box with random spots stopping at a number:
Privatize the number.
Draw the box with the brown pen.
Loop.
Pick a spot anywhere in the box.
Draw the spot with the brown pen.
If a counter is past the number, break.
Repeat.
Write the number under the box.
Refresh the screen.

To pick a spot anywhere in a box:
Pick the spot’s x between the box’s left and the box’s right.
Pick the spot’s y between the box’s top and the box’s bottom.

And here is what we get when we run it:

You can see that the distribution is reasonably uniform in each case. Plain English uses a 96 pixel-per-inch resolution, so a 2-inch square contains 36,864 spots. It takes many more iterations than that to completely fill the box, however, because the random number generator sometimes returns a number more than once. It returns fewer duplicates, of course, when the range (the size of the box, in this case) is larger. Just 10,000,000 iterations, for example, was enough to almost completely fill my entire, 1,310,720-pixel screen.

Plain English Programming — Jackson Pollock’s Alphabet Soup

Jackson Pollock was an “artist” who “painted” by pouring paint on a canvas on the floor. This is close-up portion of one of his most famous works, aptly entitled, “Number 8”:

When I’m not programming, I’m often painting. But it turns out that I’m constitutionally incapable of “painting” using Pollock’s technique simply because I think too much about what I’m trying to paint. This, for example, is what came out when I attempted to apply his technique while thinking about him at work in his studio:

So I thought, maybe I can write a Plain English program to approximate Pollock’s unique style. I just need an easy way to simulate the drippy calligraphic strokes that the “master” used to use. And the moment the word “calligraphic” popped into my head, I thought, “Of course! All I really need is one of those fancy, scripty fonts to work with. A quick search of dafonts.com quickly yielded “Jellyka Saint-Andrew’s Queen,” exactly the kind of font I had in mind. It was free, but I sent a donation to the author since the font served me so well. And because people should get paid for their work.

This is what the uppercase letters and squiggly braces look like on a page in Plain English’s built-in page editor:

And this is the Plain English program I wrote to make use of that font:

To run:
Start up.
Clear the screen.
Make a box 6 inches by 6 inches. Center the box on the screen. Mask outside the box.
Loop.
Pick a letter from “{ABCDEFGHIJKLMNOPQRSTUVWXYZ}”.
Pick a spot within 1/2 inch of the box.
Pick a pollock color.
Pick a size between 1/16 inch and 2 inches.
Put “Jellyka, Saint-Andrew’s Queen” and the size into a font.
Draw the letter at the spot with the pollock color and the font (varying the thickness).
If a counter is past 2000, break.
If the counter is evenly divisible by 100, Rotate the canvas.
Repeat.
Refresh the screen.
Wait for the escape key.
Shut down.

In short, the program just draws random letters at random spots in colors typical of Pollock’s Number 8 painting, over and over and over, rotating the canvas every 100 letters (to simulate Jackson walking around his canvas on the floor).

The subroutine that chooses a “pollock color” looks like this:

To pick a pollock color:
If you feel like it, exit.
Pick a number between 1 and 100.
If the number is less than 35, put the darkest yellow color into the pollock color; exit.
If the number is less than 50, put the black color into the pollock color; exit.
If the number is less than 80, put the lightest orange color into the pollock color; exit.
If the number is less than 85, put the light red color into the pollock color; exit.
If the number is less than 94, put the light orange color into the pollock color; exit.
If the number is less than 95, put the lightest yellow color into the pollock color; exit.
Put the white color into the pollock color.

“If you feel like it” means 50% of the time, which in this case leaves the color as it was for another round.

The subroutine that varies the thickness of the letters looks like this:

To draw a letter at a spot with a pollock color and a font (varying the thickness):
Draw the letter at the spot
with the pollock color and the font.

If you feel like it, move the spot 1 pixel right
and 1 pixel down; repeat.

Add 1 to a count. If the count is less than 3, repeat.

As you can see, we sometimes move the spot right and down and redraw the letter to make it a little thicker. Sometimes more than once.

This is what shows up on the screen after the first two dozen letters are drawn:

And this is what the finished work looks like:

Et voila! Not exactly an original Pollock, but definitely in the ballpark. Fun to write, fun to run.