Lauren Ipsum: A Story About Computer Science and Other Improbable Things Read Online Free PDF Page B

wander around the room. Xor was staring at a moth that was flying in lazy
loops around a lightbulb. His skin was slowly fading from red to yellow and back to red. The moth
went around and around. It was hypnotic. Around and around and around and . . .
    Oh! If the moth doesn’t have to go to the center of the lightbulb to fly
around it in a circle, then why does the turtle need to go back to the center to draw
one?
    Laurie reached 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.
    Make a MOTH-CIRCLE ( one ).
    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.” Laurie 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 and 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, and you have 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