Lauren Ipsum: A Story About Computer Science and Other Improbable Things

by Carlos Bueno

  On a map with N towns, there are (N – 1)! ÷ 2 cycles. As Tinker said, x! is shorthand for (x × (x – 1) × . . . × 2 × 1), so for a map with six towns, you’d have

  (6 – 1)! ÷ 2 = 5! ÷ 2 = (5 × 4 × 3 × 2 × 1) ÷ 2 = 60 cycles!

  Finding a cycle is fairly easy because there are so many possibilities; finding a short one is the hard part! See also Wandering Salesman (Chapter 0; Wandering salesman).

  Fair Coin

  A Fair Coin is a coin that has an equal chance of landing with heads or tails facing up when you flip it. Real coins (like Laurie’s quarters), however, aren’t always perfectly balanced in weight, so in our world, there is no such thing as a perfectly fair coin. But for most coins, the odds of landing with either side up are close enough to fifty-fifty that we have no problem using a coin flip to choose between two options.

  Even so, for important things like physics simulations, or choosing who gets to ride in the front seat, flip twice to guarantee absolute fairness. See also A Fair Flip (Chapter 11; Chapter 11: A Fair Exchange).

  Circle

  When Laurie used the turtle robot to make a circle, she discovered that filling in one for how-big? made a much bigger circle than she expected. What number should you plug into MOTH-CIRCLE in order to draw a circle two inches in diameter?

  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 (how-big?).

  Improbable vs. Impossible

  No matter which subject you study, there will always be problems that just don’t have a solution. We say that those problems are impossible to solve. Some problems, on the other hand, can be solved, but only under highly unlikely conditions. Those are improbable.

  Chapter 7: Read Me

  Cryptography

  Thank goodness Xor was able to decode Colonel Trapp’s secret message! People have been encoding information into ciphers for others to decode since ancient times, and today, that science is called cryptography. Computers are great at creating and cracking secret codes, but you can do it, too!

  One quick way to encode a message is by using a substitution cipher, which is when you replace each letter in your message with something else. For example, you could map each letter to a number:

  A

  B

  C

  D

  E

  F

  G

  H

  I

  J

  K

  L

  M

  N

  O

  P

  Q

  R

  S

  T

  U

  V

  W

  X

  Y

  Z

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

  10

  11

  12

  13

  14

  15

  16

  17

  18

  19

  20

  21

  22

  23

  24

  25

  Following these rules, “Hello!” would become “7 4 11 11 14!” But you can replace those letters with anything you want: different numbers, other letters, or even symbols you create yourself. Make your own secret message and see if your friends can crack it. Or, share your cipher with your friends so you can send each other secret messages that no one else can read!

  Chapter 8: More Than One Way to Do It

  Hugh Rustic

  If there are millions of possible ways to solve a difficult problem, searching for the best solution just isn’t practical. When that happens, scientists use heuristics to find an answer that is, as Hugh Rustic might say, “good enough.”

  Heuristic algorithms are based on experience—on things that we know will work—but they aren’t guaranteed to be the best possible solutions. For example, Hugh Rustic’s ants find many different paths on the map at random, and by following the scent trails of other ants. Scent trails eventually dry up if no new ants follow them. The shorter a path is, the more ants follow it, which makes the scent stronger. Over time, shorter paths become more popular and longer ones fade away. Based on what Laurie saw the ants do, she knows the path is short, even if it may not be the shortest, so she can use that as a heuristic to get home more quickly.

  Something to think about: Is Hugh Rustic’s ant map through Userland the shortest possible path, or is it only a short-enough path? Can you do better? Try it!

  Chapter 9: Don’t Repeat Yourself

  Axiom

  Much as Xor said, an axiom is a rule or principle that you can’t prove, but that everyone accepts as true because it just makes sense. Mathematicians, scientists, and anyone who wants to prove anything might start their argument with an axiom.

  For example, the idea that part of a thing is always smaller than the entire thing is an axiom. If you cut a slice out of a pie, there’s no way that slice can be bigger than the whole pie. The same rule applies to numbers: if you take 2 away from 5, you’re left holding a 2 and a 3, and neither is more than 5.

  Chapter 10: A Well-Timed Entrance

  Timing Attack

  Jane Hecate checks each letter of Laurie’s password guesses one by one until there is a mismatch with the correct password. The more letters Laurie gets correct in a row, the longer it takes for Jane to find a mismatch, which tells Laurie how close her guess is to being right.

  Computer scientists call this a timing attack because the guesser watches the amount of time it takes to check each incorrect try and makes new guesses based on that. Many people who should know better make Jane’s mistake and leak information about the secret they are keeping.

  Chapter 11: A Fair Exchange

  A Fair Flip

  As Trent Escrow explains to Laurie, you can guarantee a fifty-fifty chance of flipping heads or tails on an unbalanced coin—if you flip it twice. If you get Heads-Tails, then Heads is your answer. If you get Tails-Heads, then Tails is your answer. At least half of the time, you’ll probably flip Heads-Heads or Tails-Tails; in those cases, just start over. On average, you’ll need at least three coin flips to get a Fair flip. Try it! See also Fair Coin (Chapter 6; Hamiltonian Cycle).

  Chapter 12: An Improbable Twist

  Attempted Mythology

  . . . is not actually a crime in any jurisdiction, and that’s a good thing! Otherwise, no one would be allowed to write any stories, and myths are just stories that have been passed down to us through many generations. Some myths try to explain how the world works, and some are just for fun. Use your imagination, and maybe someday, you’ll write a story that becomes part of a future mythology.

  The Doppelganger

  The Doppelganger’s tale is based on a classic question in philosophy: If you replace all of the parts of a boat, do you still have the same boat? Winsome doesn’t think so. She claims she stole the Doppelganger from its owner piece by piece and left him with a copy! But what do you think? If you reassemble the old parts, which boat is the original? What if you replaced only half of the parts?

  Chapter 13: The Game of Life

  Gliders

  Conway’s Game of Life is a simulation of how a population of creatures might change over time. Computer scientists (and plenty of other scientists) use the Game of Life to study patterns based on simple rules. You can try it out yourself with a pencil and paper! First, grab some graph paper or draw a grid like this:

  Now fill in some squares in the grid. Here’s one example:

  After you’ve filled in some squares, you just have to follow a few simple rules to play the game and change your pattern:

  If a filled-in square has more than three filled-in neighbors, then
it dies. Make it blank.

  If a filled-in square has only one or zero filled-in neighbors, it dies. Make it blank.

  If a filled-in square has two or three filled-in neighbors, it survives! Leave it colored in.

  If a blank square has three filled-in neighbors, it comes to life! Color it in.

  Follow these rules to color in a new grid. Our sample grid would turn out like this after one round:

  These patterns come in many types. Gliders move around. Blinkers turn on and off, like traffic lights. Some patterns even create other patterns as they go. This particular grid pattern repeats:

  Chapter 14: In the Abstract

  Five Whys

  When scientists want to get to the root cause of a confusing problem, they’ll ask Why questions until they find out exactly Where their experiment went Wrong. But you don’t have to leave that kind of thinking to the scientists.

  Play Five Whys the next time you need to figure out the solution to a problem of your own. There are a lot of mental games you can try to help you avoid or learn from mistakes. Another good rule is “Never worry alone.” Grab a friend if you’re puzzled—when you work together, you can solve any problem!

  Chapter 15: Cleverness When It Counts

  Following the Byzantine Process

  The word Byzantine can describe any extremely long and complicated process. Fortunately, Laurie was able to get all of the signatures she needed by helping the three generals, and she actually solved each of their very different problems similarly.

  Laurie’s algorithm for moving the wolf, the goat, and the mandelbroccoli uses a counting argument. The idea behind a counting argument is that you can solve some problems by ignoring unimportant differences between things and counting only how many there are. For example:

  Everyone wants to use General Euripides’s books all at once. But reader or writer, only one person can use any given book at a time.

  General Darius was so concerned with getting the mandel-broccoli, the wolf, and the goat across the stream that he didn’t think of counting backward—of bringing the goat across multiple times. But mandelbroccoli or wolf, as long as you don’t leave the goat alone with it, everything works out.

  Sometimes it’s the opposite: you have to count the same thing different ways to see if they add up. General Case stopped counting posts after he hit 100 feet of fence; he wasn’t thinking about holding up the last length! Count the gaps between the posts and you get 10. Count the posts, and you get 11.

  When Tinker tells Laurie to count paths that are mirror images of other paths (like BCD and DCB) as one, he is also using a counting argument. This rule cuts the number of paths through Userland in half. But even cutting the number in half doesn’t help much with the Traveling Salesman problem: a Very Big Number divided by a small number is still a Very Big Number!

  Mandelbroccoli

  Mandelbroccoli does exist in our world, and it’s the weirdest-looking vegetable I know. At the market, it’s called Romanesco, and it looks a lot like a fractal. Fractals are patterns that start with one shape and repeat it infinitely, smaller and smaller, according to a set of rules.

  For example, draw an equilateral triangle (a triangle with three sides that are all the same length) inside another equilateral triangle. Make sure each point from the second triangle touches the middle of a side from the first! This should create four smaller, but identical, triangles inside the original.

  Now, draw an equilateral triangle inside each of those, following the same rules, and repeat until you can’t fit any more triangles. You should have something like the fractal pattern shown here. See also Infinity (Chapter 4; Infinity).

  “Sierpinski triangle evolution.” Licensed under public domain via Wikimedia Commons.

  Chapter 16: A Change of Plan

  Bruto Fuerza

  This lighthouse keeper thinks the answer to every problem is more power and brute force. Even if he builds a lighthouse twice as tall, twice as wide, and twice as thick as the one that failed, the new one will still fall over eventually because he’s following the same plan.

  Yet in his own way, Bruto is right when he decides to build a pyramid instead. Pyramids are much sturdier, and if you pile on enough bricks, you could eventually make a pyramid tall enough to be a lighthouse. But Bruto’s plan has enormous costs: he needs a lot more bricks, a lot more land to build on, and a lot more time to build.

  Some programmers approach problems this way, too, but putting all your resources into a brute-force attempt isn’t always a sensible answer. When your algorithm collapses, don’t just pile on more bricks! Change your point of view, as Laurie did with the generals on the Island of Byzantium, and you’ll find a more effective solution. See also Five Whys (Chapter 14; Chapter 14: In the Abstract).

  Chapter 17: Chasing Elegants

  Elegants

  They don’t really exist, but don’t you wish they did?

  Fresnel

  The Fresnel whom Laurie meets on Elegant Island is named after a real scientist named Augustin-Jean Fresnel, who invented a way of focusing big lighthouse lights with only a little bit of glass. He knew that lenses didn’t have to be large and thick to focus a beam of light, so instead of one huge piece of glass, the Fresnel lens is an arrangement of small pieces of glass at different angles. Lighthouses still use this type of lens today.

  Decomposing

  Decomposing starts with a big idea and breaks it into smaller, easier-to-understand pieces. When you know how to solve each smaller piece, you can combine those ideas to solve a bigger problem. One good way to take an idea apart is to describe it without using its name, just as Laurie did when she said you could also call a turtle a “Green Round animal with a Shell.”

  Even simple ideas, like the numbers 3 and 4, can be decomposed into simpler ideas. Start with 0 and then add 1. Then add 1 again, and so on:

  0 = 0

  1 = 0 + 1

  2 = 0 + 1 + 1

  3 = 0 + 1 + 1 + 1

  If you really wanted to, you could just use 0 and 1 and ditch all of the other numbers. I don’t recommend it—you’ll use up a lot of paper!—but it’s a perfectly valid way to do math. For example, let’s break an addition problem down into nothing but 0s and 1s:

  2 + 2 = 4

  would become

  (0 + 1 + 1) + (0 + 1 + 1) = (0 + 1 + 1 + 1 + 1)

  Relating

  When you relate two ideas, you put them side by side and compare them, like Fresnel’s balloon and a lighthouse. With numbers, you use the less-than sign (<) to show that the number on the left is smaller than the one on the right. You use the equal sign (=) to show that the value on the left is equal to the value on the right.

  2 < 3

  2 × 3 = 6

  You can relate things besides numbers, though that means some relations are less precise. Fresnel’s balloon isn’t exactly a lighthouse, but it’s like a lighthouse. We expect a lighthouse to have a way for people to climb up high, somewhere to stand when they get there, and a big light that faraway ships can see. Fresnel’s balloon technically has all of those things:

  Fresnel’s balloon is-like-a lighthouse.

  (elevator, balloon, light) is-like-a (staircase, tower, light).

  Chapter 18: Many Hands Make Light Work

  Network

  Winsome created the Lighthouse Network to let people in Userland send messages faster. In computer science, a network is a group of computers that are connected to one another so that they can share information. Those computers could be connected through wires or even the air!

  Baudot

  In 1870, Émile Baudot invented a code that represented letters with different groups of 1s and 0s. This code was meant to let people share messages using electricity: if you have a switch, the power can either be on (1) or off (0). Naturally, Baudot named this code after himself. See Bach’s Laws of Eponymy (Chapter 2; Bach’s First Law of Eponymy).

  We don’t use the Baudot code very often in the real world, but Ping, Fresnel, an
d the other members of Winsome’s Lighthouse Network use it to send messages with their lights, which can also be on (FLASH) or off (FLOOSH).

  Here’s the Baudot code and the letter each number stands for, so you can make your own Lighthouse Network. Grab some friends and some flashlights, and send each other messages!

  Letter

  Baudot code

  Letter

  Baudot code