Lauren Ipsum: A Tinker's Trade

Chapter 6

When they were safely inside the town walls, the little lizard popped his head out of Laurie’s pocket.
A story about computer science
and other improbable things.

“See what I mean? Let’s hope they don’t figure out what you did to get in here,” Xor said. “So, why are we here?”

“We’re looking for information. Maybe we can find a map or something.”

“Oh,” said Xor. “I was hoping you were going to say food. Why don’t we try this place?”

In front of them was a storefront with a very fancy sign painted on the window:

“Al-go-rith-ms. That sounds like a kind of fruit.”

“Are you always hungry, Xor?”

“Time flies like an arrow, and fruit flies like a banana. Let’s see if there’s a fruit fly problem I can help them solve.”

A bell jingled as she opened the door. “Hello, hello!” the shopkeeper said. “And welcome to my shop. I’m Tinker, and you are looking for a finely crafted algorithm, am I right?”

Laurie looked at the items listed on the chalkboard, but they didn’t make any sense.

“I’m not sure. What is an algorithm? Can you eat it?”

“What? No, it’s just a fancy way of saying ‘how to do something’. But ‘Algorithm’ looks more impressive on the sign,” said Tinker.

Xor turned orange with disappointment.

“How to do something.” repeated Laurie. “In that case, I want to find a sensible way to visit every town.”

“That sounds like an interesting problem. What have you been doing so far?”

Laurie told him about her adventure in the Red-Black Forest and her visit with Eponymous Bach.

“A Hamiltonian path, eh?” said Tinker. “That’s a tough one. I hate to say it, because he sounds like a nice person, but the Wandering Salesman might take a long, long time to finish his tour of all the towns.”

“Oh, no! But why?”

“If you always go to the nearest town you haven’t visited yet, you might miss a town that’s just a little farther away. Then you go to another town that’s closer to you but still farther from the one you missed, and so on. You can end up criss-crossing the whole country to get to the last few towns.”

“That sounds exhausting,” said Laurie. The Wandering Salesman wasn’t so sensible after all! “So how do I find the shortest path?”

“I’ll have a look at what I have in stock. But it might be expensive.”

“I don’t have much money with me,” Laurie said. She took a few quarters from her bag and showed them to Tinker.

He looked at them with surprise. “‘Quarter Dollar.’ Is this money where you come from?”

“Of course it’s money! That’s seventy-five cents.” she said.

“Cents? We use Fair Coins here.”

“What’s a Fair Coin?”

“Well, they are a bit bigger than these ‘Quarter Dollars’ of yours, but they are not nearly as pretty! You can tell genuine Fair Coins because they always flip heads or tails, fifty-fifty.”

“But you can flip quarters fifty-fifty too!”

“That may be true, but I can’t just take your word for it, can I? Here, all Fair Coins must be certified Fair.”

Laurie was crestfallen.

“Don’t look so sad! I do want to help you,” said Tinker. “Maybe we can do a trade. It so happens I’m in the market for a particular algorithm.”

“But I don’t have any algorithms, either.” said Laurie.

“That’s not a problem,” said Tinker. “You can compose new ones any time you want, with a little bit of thinking.”

“I can? How?”

“Well, everyone develops their own style. You can put little ideas together to make big ideas. Or you put two ideas side-by-side and compare them. Or you start with big ideas and take them apart.”

“You mean like Eponymous does?”

“Yes, just like her. She’s a great Composer.”

Laurie had never thought that she could do things like that herself. But Tinker seemed to think it was normal.

“So what do I do?”

“The algorithm I’m looking for is how to draw a circle, Tinker said. “It’s a tough one, so you’ll have to use your imagination. I’ve asked all the adults and even Ponens and Tollens already, but all they do is mutter about X squared plus Y squared and never get anywhere.”

“Take a look at this.” He handed her a windup toy animal. It had a Shell, and was Round and Green. “This turtle can do three things: it can move forward or backward, it can turn, and it can draw a little dot on the paper.”

“Hey, that’s pretty neat!”

“Yes, but the thing is, it doesn’t know how to do anything else. That’s where the algorithm comes in.” Tinker took out a piece of paper and wrote what looked like a little poem:

Go forward one inch,
make a mark,
repeat five times.

Then he wound up the turtle and placed it on the poem. It went zzzrbt bzzaap whuzzzsh, and so on. Then it drew a line of dots, just like the poem said:

“You see?” Tinker said. “If you put little ideas together, you can make bigger ones,” Tinker said. “And you can compose those ideas into even bigger and bigger ones.”

“How do you do that?” asked Laurie.

“By giving them a name. You can use the name like a handle. Here, let’s call the first idea LINE. Then you can put four lines together to make a square:”

LINE:
Go forward one inch,
make a mark,
repeat five times.

SQUARE:
Make a LINE,
make a right turn,
repeat four times.

Make a SQUARE.

The little turtle zzzrbted and whuzzzshed and bzzaaped, etc, then it drew this:

Laurie was amazed. It was like magic, but every step made sense.

“So, knowing what the turtle can do, can you teach it how to draw a circle?” Tinker said.

“I don’t know,” Laurie said, “but I want to try!”

“That’s good enough for me. Here, you can work at my desk. There is plenty of paper and compasses and things like that.”

Laurie sat down at Tinker’s desk. She doodled with the compass and played with the turtle for a while, trying to remember what she knew about circles.

A circle is round. No, not just round, perfectly round. You put the pin in the center, and the pencil spins round. To make a bigger one you open the compass; to make a smaller one you close the compass. If you change the width of the compass when it’s spinning, it doesn’t make a circle...

Suddenly an idea, or maybe a memory, popped into her head: A circle is all of the points that are exactly the same distance from the center. Hmm... what if you

Go forward one inch,
make a mark,
go back one inch,
turn right a tiny bit,
then repeat!

She wound up the little turtle again and placed it on her poem. It buzzed and burbled for a moment, then drew this:

“It’s working!” she said. “Hey, it’s not stopping.” The turtle was drawing over dots it had already drawn.

“I think it’s because you told it to repeat, but not how many times,” said Tinker.

“Well, it should stop when the circle is done,” Laurie said.

“It doesn’t really understand circles,” Tinker said. “It’s just a toy turtle, remember? You have to teach it.”

Laurie thought a little more, then rewrote her poem:

CIRCLE:
Go forward one inch,
make a mark,
go back one inch,
turn right one degree,
repeat three hundred sixty times.

Then she realized that she could make circles any size she wanted. It was just like opening the compass wider:

TWO-CIRCLE:
Go forward two inches,
make a mark,
go back two inches,
turn right one degree,
repeat three hundred sixty times.

“This is interesting. You’re working really hard!” Tinker scratched his head. “But as it is, it’s no good.”

“Why?”

“People want to make lots of different circles,” he said. “I’ll have to keep a lot of algorithms of different sizes, just in case someone wants three-and-nine-thirteenths inches or four-and-three quarters.”

“Well, what if you tell the turtle how big to make the circle?” she said. “Maybe like this:”

ANY-CIRCLE (how-big?):
Go forward how-big inches,
make a mark,
go back how-big inches,
turn right one degree,
repeat three hundred sixty times.

“And then,” she said, “instead of ONE-CIRCLE or TWO-CIRCLE you can say ANY-CIRCLE(one), or two, or even one-and-eleventy-sevenths!”

“Good idea, Laurie. That’s a lot simpler.” said Tinker. “I was worried you were going to fill my shop with circles!”

“You know, the turtle is drawing really slowly. Not like when it was doing the square,” she said.

It was true. The turtle would crawl all the way to the edge of the circle, then make a mark, then crawl all the way back to the center, three hundred sixty times. With small circles it wasn’t too bad, but big circles took a lot longer.

“Hmm.” Tinker said. “It spends a lot more time running back and forth than it does making marks. Do you think you can reduce the running time?”

It makes sense, but it isn’t sensible. She thought & doodled and doodled & thought, but Laurie couldn’t figure out how to make it more sensible. The turtle has to go back to the center, right? How else could it know where the edge of the circle was?

Laurie let her eyes wander around the room. Xor was staring at a moth that was flying in lazy loops around a light bulb. His skin was slowly fading from red to yellow and back to red. The moth went round and round. It was hypnotic. Round and round and round and...

Oh.

She grabbed for a fresh piece of paper before the idea got away. Don’t let a new thing out of your sight without a name.

MOTH-CIRCLE (how-big?):
Go forward how-big inches,
make a mark,
turn right one degree,
repeat three hundred sixty times.

The turtle went bzzaap and zzzrbt and whuzzzsh and then it started to draw. It moved one inch, made a dot, then turned a tiny bit, then moved one inch, then made another dot...

“Whoops. It’s making a huge circle! Let me try a small number.” She didn’t have a small number handy, so she borrowed one she had heard from Tortoise: one thirty-second of an inch.

“That’s better.” Laurie said.

“Let me see,” Tinker said. “Wow, look at the little guy run!”

“That was fun,” said Laurie. “I didn’t know you could just make up new ways to do things.”

“Of course you can. Often you aren’t the first to think of something, but if it works, who cares? Now, for my end of the trade.”

“Did you find the shortest path?” Laurie asked.

“Not exactly. The bad news is that what you are trying to do is impossible.”

“It’s impossible?”

“Well, highly improbable. There are many different ways to visit all the towns. It seems like you could write an algorithm for the turtle to try each one and find the shortest, right?”

“Sure, why not?” said Laurie.

“There are twenty-one towns in Userland. How many paths do you think there are?” Tinker said.

“I don’t know,” said Laurie. “A hundred?”

“Way more.”

“Um, a million?” Laurie said.

“More like a million million times that!” said Tinker.

“But how can that be?”

“Let’s say there are only three towns: A, B, and C,” Tinker said. “You are already standing in A, so you have to worry only about B and C. How many ways can you go?”

“Well,” she said, “I could go from B to C, or go to C then B. That’s two.”

“That’s right! But BC is the same as CB, just backward. Every path has a mirror image, so with three towns there is really only one possible path that visits them all. What if there were four towns, A, B, C, and D?”

Laurie counted on her fingers. “I could go BCD, or BDC, or CBD, or CDB, or DCB, or... DBC. Six! No, three.”

“That’s three times as many. Add another town, twelve times as many,” Tinker said. “Add a sixth town and there are sixty different paths through all of them. With seven towns there are three hundred sixty paths. As you add more towns, the number of paths gets very big!”

3 Towns: 2  ÷  2 = 1
4 Towns: 2  ×  3  ÷  2 = 3
5 Towns: 2  ×  3  ×  4  ÷  2 = 12
6 Towns: 2  ×  3  ×  4  ×  5  ÷  2 = 60
7 Towns: 2  ×  3  ×  4  ×  5  ×  6  ÷  2 = 360
8 Towns: 2  ×  3  ×  4  ×  5  ×  6  ×  7  ÷  2 = 2,520
9 Towns: 2  ×  3  ×  4  ×  5  ×  6  ×  7  ×  8  ÷  2 = 20,160

“For twenty-one towns you have to multiply one times two times three times four, all the way up to twenty. It makes a HUGENORMOUS number!”

2  ×  3  ×  4  ×  5  ×  6  ×  7  ×  8  ×  9  ×  10  ×  11  ×  12  ×  13  ×  14  ×  15  ×  16  ×  17  ×  18  ×  19  ×  20  ÷  2 = 1,216,451,004,088,320,000

“!” said Laurie.

“Indeed!” Tinker said. “All of that ‘one times two times three’ stuff takes too long to write. So you can use the exclamation point as a shorthand.”

20!  ÷  2 = 1,216,451,004,088,320,000

“But that’s...” Laurie said, counting the commas, “over one million million million paths!”

“One of those umpty-million paths is the shortest,” Tinker said. “I don’t know of any way to find it quickly.”

“I’ll be old before we check them all! Isn’t there a better way?”

“Ah, that’s the good news!” Tinker said. “I only deal in Exact answers. But there is a brilliant Composer who lives in Permute, named Hugh Rustic. He deals in Good Enough answers. I send him all of my hardest cases. I’ll write an IOU that you can take to him.”

Like what you read? Lauren Ipsum is a children's story about computer science. Buy a copy and help us translate it into Spanish, Portuguese, and other languages.