1
Problem-Solving With Algorithms

The act of catching a ball is remarkable. A ball may start so far away that it seems only a speck on the horizon. It may be in the air for only a few short seconds or less. The ball will meet air resistance, wind, and of course, gravity, moving in something like a parabolic arc. And each time a ball is thrown, it is sent with a different force, at a different angle, and in a different environment with different conditions. So how is it that the moment a batter hits a baseball, an outfielder 300 feet away seems to immediately know where to run in order to catch it before it hits the ground?

This question is called the outfielder problem, and it’s still being discussed in scholarly journals today. We’re starting with the outfielder problem because it has two very different solutions: an analytic solution and an algorithmic solution. Comparing these solutions will provide a vivid illustration of what an algorithm is and how it’s different from other approaches to problem-solving. Additionally, the outfielder problem will help us visualize a field that is occasionally abstract—you probably have some experience throwing and catching something, and this experience can help you understand the theory behind your practice.

Before we can really understand how a human knows exactly where a ball will land, it will help to understand how a machine does it. We’ll start by looking at an analytic solution to the outfielder problem. This solution is mathematically precise and easy for computers to execute instantaneously, and some version of it is usually taught in introductory physics classes. It would enable a sufficiently agile robot to play outfield for a baseball team.

However, humans can’t easily run analytic equations in their heads, and certainly not as quickly as computers can. A solution that’s better suited to human brains is an algorithmic solution, which we’ll use to explore what an algorithm is and what its strengths are compared to other problem-solving solutions. Moreover, the algorithmic solution will show us that algorithms are natural to human thought processes and don’t need to be intimidating. The outfielder problem is meant to introduce a new way to solve problems: the algorithmic approach.

The Analytic Approach

To solve this problem analytically, we have to go back a few centuries to an early model of motion.

The Galilean Model

The equations most commonly used to model a ball’s movement date back to Galileo, who centuries ago formulated polynomials that capture acceleration, speed, and distance. If we ignore wind and air resistance and assume the ball starts at ground level, Galileo’s model says that the horizontal position of a thrown ball at time t will be given by the formula

c01eq001

where v1 represents the starting speed of the ball in the x (horizontal) direction. Moreover, the height of a thrown ball (y), according to Galileo, can be calculated at time t as

c01eq002

where v2 represents the starting speed of the ball in the y (vertical) direction, and a represents the constant downward acceleration due to gravity (which will be about –9.81 if we are working in metric units). When we substitute the first equation into the second equation, we find that the height of a thrown ball (y) relates to the horizontal position of the ball (x) as follows:

c01eq003

We can use Galileo’s equations to model a hypothetical ball’s trajectory in Python using the function in Listing 1-1. The specific polynomial in Listing 1-1 is appropriate for a ball whose initial horizontal speed is about 0.99 meters per second, and whose initial vertical speed is about 9.9 meters per second. You can feel free to try other values for v1 and v2 to model any type of throw that interests you.

def ball_trajectory(x):
    location = 10*x - 5*(x**2)
    return(location)

Listing 1-1: A function for calculating the trajectory of a ball

We can plot the function in Listing 1-1 in Python to see what, approximately, a ball’s trajectory should look like (ignoring air resistance and other negligible factors). We’ll import some plotting capabilities from a module called matplotlib in the first line. The matplotlib module is one of many third-party modules we’ll import in code throughout this book. Before you use a third-party module, you’ll have to install it. You can install matplotlib and any other third-party modules by following the instructions at http://automatetheboringstuff.com/2e/appendixa/.

import matplotlib.pyplot as plt
xs = [x/100 for x in list(range(201))]
ys = [ball_trajectory(x) for x in xs]
plt.plot(xs,ys)
plt.title('The Trajectory of a Thrown Ball')
plt.xlabel('Horizontal Position of Ball')
plt.ylabel('Vertical Position of Ball')
plt.axhline(y = 0)
plt.show()

Listing 1-2: Plotting a hypothetical ball trajectory between the moment it is thrown (at x = 0) and when it hits the ground again (at x = 2)

The output (Figure 1-1) is a nice plot that shows the path our hypothetical ball is expected to follow through space. This pretty curved path is similar for every moving projectile that’s influenced by gravity and has been poetically called Gravity’s Rainbow by the novelist Thomas Pynchon.

Not all balls will follow this exact path, but this is one possible path that a ball could follow. The ball starts at 0, and it goes up and then down exactly like we are used to seeing balls go up and down, from the left of our field of view to the right.

figure_1-1

Figure 1-1: The trajectory of a hypothetical thrown ball

The Solve-for-x Strategy

Now that we have an equation for the ball’s position, we can solve that equation for anything that interests us: where the ball will reach its highest point, for example, or where it will get to ground level again, which is the one thing that an outfielder needs to know in order to catch it. Students in physics classes all over the world are taught how to find these solutions, and if we wanted to teach a robot to play outfield, it would be very natural to teach the robot these equations as well. The method for solving for the ball’s final location is as simple as taking the ball_trajectory() function we started with and setting it equal to 0:

c01eq004

Then, we can solve this for x, using the quadratic formula taught to teenagers everywhere:

c01eq005

In this case, we find that x = 0 and x = 2 are the solutions. The first solution, x = 0, is where the ball started, where it was thrown by the pitcher or hit by the batter. The second solution, x = 2, is where the ball returns to the ground again after its flight.

The strategy we just used is a relatively simple one. Let’s call it the solve-for-x strategy. We write down an equation that describes a situation, and then solve that equation for the variable we’re interested in. The solve-for-x strategy is extremely common in the hard sciences, at both the high school and college levels. Students are asked to solve for: a ball’s expected destination, the ideal level of economic production, the proportion of a chemical that should be used in an experiment, or any number of other things.

The solve-for-x strategy is extremely powerful. If, for example, an army observed an enemy force fire a projectile weapon (say, a missile), they could quickly plug Galileo’s equation into their calculators and nearly instantaneously find where the missile was expected to land, and evade it or intercept it accordingly. It could be done for free on a consumer-level laptop running Python. If a robot were playing outfield in a baseball game, it could do the same to catch a ball without breaking a sweat.

The solve-for-x strategy is easy in this case because we already know the equation that needs to be solved and the method to solve it. We owe the equation for a thrown ball to Galileo, as mentioned. We owe the quadratic formula to the great Muhammad ibn Musa al-Khwarizmi, who was the first to specify a fully general solution of the quadratic equation.

Al-Khwarizmi was a ninth-century polymath who contributed to astronomy, cartography, and trigonometry, besides giving us the word algebra and the method it refers to. He’s one of the important figures who has enabled us to take the journey of this book. Since we live after giants like Galileo and al-Khwarizmi, we don’t need to suffer through the difficult part of deriving their equations—we just have to memorize them and use them appropriately.

The Inner Physicist

Using Galileo’s and al-Khwarizmi’s equations and a solve-for-x strategy, a sophisticated machine can catch a ball or intercept a missile. But it seems reasonable to assume that most baseball players don’t start writing out equations as soon as they see a ball go into the air. Reliable observers have reported that professional baseball spring training programs consist of a great deal of time running around and playing, and considerably less time gathered around a whiteboard deriving the Navier-Stokes equations. Solving the mystery of where a ball will land doesn’t provide a clear-cut answer to the outfielder problem—that is, how a human can instinctively know where a ball will land without plugging it into a computer program.

Or maybe it does. The glibbest possible solution to the outfielder problem is to assert that if computers are solving Galilean quadratics to determine where balls will land, then so are humans. We’ll call this solution the inner physicist theory. According to this theory, the “wetware” of our brains is able to set up and solve quadratic equations, or else draw plots and extrapolate their lines, all far beneath the level of our consciousness. Each of us, in other words, has an “inner physicist” deep in our brains who can calculate exact solutions to difficult math problems in seconds and deliver the solutions to our muscles, which can then find their way to the ball, bringing our bodies and mitts along. Our subconscious might be able to do this even if we’ve never taken a physics class or solved for x.

The inner physicist theory is not without its proponents. Notably, the well-known mathematician Keith Devlin published a book in 2006 called The Math Instinct: Why You’re a Mathematical Genius (Along with Lobsters, Birds, Cats, and Dogs). The book’s cover shows a dog jumping to catch a Frisbee, with arrows tracing the respective trajectory vectors of the Frisbee and the dog, implying that the dog is able to perform the intricate calculations that would be required to make those vectors meet.

The manifest ability of dogs to catch Frisbees and humans to catch baseballs seems to be a point in favor of the inner physicist theory. The subconscious is a mysterious and powerful thing, whose depths we have yet to fully plumb. So why couldn’t it solve some high school–level equations now and then? More pressingly, the inner physicist theory is difficult to refute because it’s hard to think of alternatives to it: if dogs can’t solve partial differential equations to catch Frisbees, then how do they catch them anyway? They take great leaps into the air and catch erratically moving Frisbees in their jaws like it’s nothing. If they aren’t solving some physics problem in their brains, then how else could they (and we) possibly know how to precisely intercept a ball?

As recently as 1967, no one had a good answer. That year, the engineer Vannevar Bush wrote a book in which he described the scientific features of baseball as he understood them, and he was unable to provide any explanation for how outfielders know where to run to catch fly balls. Luckily for us, the physicist Seville Chapman read Bush’s book and was inspired to propose a theory of his own the very next year.

The Algorithmic Approach

Chapman, true scientist that he was, was not satisfied with a mystical and unverified trust in the human subconscious, and he wanted a more concrete explanation for outfielders’ powers. This is what he discovered.

Thinking with Your Neck

Chapman began to tackle the outfielder problem by noting the information available to someone catching a ball. Though it’s difficult for humans to estimate an exact velocity or the trajectory of a parabolic arc, he thought we would have an easier time observing angles. If someone throws or hits a ball from the ground and the ground is flat and even, then the outfielder will see the ball start at close to eye level. Imagine an angle formed by two lines: the ground, and the line between the outfielder’s eyes and the ball. The moment the ball is hit by the batter, this angle will be (roughly) 0 degrees. After the ball has been in flight for a brief moment, it will be higher than the ground, so the angle between the ground and the outfielder’s line of sight with the ball will have increased. Even if the outfielder has not studied geometry, they will have a “feel” for this angle—for example, by feeling how far back they have to tilt their neck to see the ball.

If we suppose that the outfielder is standing where the ball will eventually land, at x = 2, we can get a sense of the way the angle of the outfielder’s line of sight with the ball increases by plotting a line of sight from early in the ball’s trajectory. The following line of code creates a line segment for the plot we drew in Listing 1-2, and it is meant to be run in the same Python session. This line segment represents the line between the outfielder’s eyes and the ball after the ball has traveled 0.1 meters horizontally.

xs2 = [0.1,2]
ys2 = [ball_trajectory(0.1),0]

We can plot this line of sight along with other lines of sight to see how the angle continues to increase over the course of the ball’s trajectory. The following lines of code add more line segments to the same plot we drew in Listing 1-2. These line segments represent the line between the outfielder’s eyes and the ball at two more points in the ball’s journey: the points when the ball has traveled 0.1, 0.2, and 0.3 meters horizontally. After creating all of these line segments, we will plot them all together.

xs3 = [0.2,2]
ys3 = [ball_trajectory(0.2),0]
xs4 = [0.3,2]
ys4 = [ball_trajectory(0.3),0]
plt.title('The Trajectory of a Thrown Ball - with Lines of Sight')
plt.xlabel('Horizontal Position of Ball')
plt.ylabel('Vertical Position of Ball')
plt.plot(xs,ys,xs2,ys2,xs3,ys3,xs4,ys4)
plt.show()

The resulting plot shows several lines of sight that form continuously increasing angles with the ground (Figure 1-2).

figure_1-2

Figure 1-2: The trajectory of a hypothetical thrown ball, with line segments representing the outfielder looking at the ball as it travels

As the ball progresses through its flight, the angle of the outfielder’s line of sight continues to increase, and the outfielder has to keep tipping their head back until they make the catch. Let’s call the angle between the ground and the outfielder’s line of sight with the ball theta. We assume that the outfielder is standing at the ball’s eventual destination (x = 2). Recall from high school geometry class that the tangent of an angle in a right triangle is the ratio of the length of the side that’s opposite the angle and the length of the side that’s adjacent to the angle (and is not the hypotenuse). In this case, the tangent of theta is the ratio of the height of the ball to its horizontal distance from the outfielder. We can plot the sides whose ratio constitutes the tangent with the following Python code:

xs5 = [0.3,0.3]
ys5 = [0,ball_trajectory(0.3)]
xs6 = [0.3,2]
ys6 = [0,0]
plt.title('The Trajectory of a Thrown Ball - Tangent Calculation')
plt.xlabel('Horizontal Position of Ball')
plt.ylabel('Vertical Position of Ball')
plt.plot(xs,ys,xs4,ys4,xs5,ys5,xs6,ys6)
plt.text(0.31,ball_trajectory(0.3)/2,'A',fontsize = 16)
plt.text((0.3 + 2)/2,0.05,'B',fontsize = 16)
plt.show()

The resulting plot is shown in Figure 1-3.

figure_1-3

Figure 1-3: The trajectory of a hypothetical thrown ball, with a line segment representing the outfielder looking at the ball as it travels, and line segments A and B showing the lengths whose ratio constitutes the tangent we are interested in

We calculate the tangent by taking the ratio of the length of the side labeled A and the length of the side labeled B. The equation for the height A will be 10x – 5x2, while the equation for the length of B will be 2 – x. So the following equation implicitly describes the ball’s angle theta at each moment of its flight:

c01eq006

The overall situation is complex: a ball is hit far away and quickly shoots through a parabolic curve whose end is hard to immediately estimate. But in this complex situation, Chapman has found this simple relationship: that when the outfielder is standing in the right location, the tangent of theta grows at a simple, constant rate. The kernel of Chapman’s breakthrough is that the tangent of theta, the ball’s angle with the ground, grows linearly over time. Since Chapman found that simple relationship in the weeds of the outfielder problem, he was able to develop an elegant algorithmic solution to it.

His solution depends on the fact that if something—in this case, the tangent of theta—grows at a constant rate, it has zero acceleration. So if you are standing exactly where a ball is headed, you’ll observe an angle whose tangent experiences zero acceleration. By contrast, if you are standing too close to the ball’s initial position, you’ll observe positive acceleration. If you are standing too far from the ball’s initial position, you’ll observe negative acceleration. (You are encouraged to verify the messy calculus behind these truths if you so desire.) This means that an outfielder can know where they need to go by feeling how steadily they have to tilt back their head as they look at the ball rising—thinking, so to speak, with their neck.

Applying Chapman’s Algorithm

Robots don’t necessarily have necks, and so a method for “thinking with one’s neck” may not be helpful for a robot outfielder. Remember that they can solve quadratic equations directly and instantaneously to find where to go to catch a ball, without worrying about the acceleration of the tangent of theta. But for humans, Chapman’s neck-thinking method could be extremely useful. In order to get to the ball’s eventual destination, a human outfielder could follow this relatively simple process:

  1. Observe the acceleration of the tangent of the angle between the ground and your line of sight with the ball.
  2. If the acceleration is positive, step backward.
  3. If the acceleration is negative, step forward.
  4. Repeat steps 1–3 until the ball is directly in front of your face.
  5. Catch it.

One serious objection to Chapman’s five-step method is that outfielders following this process seem to have to calculate the tangents of angles on the fly, meaning we’re replacing an inner physicist theory with an “inner geometer theory” in which baseball players can instantaneously, and subconsciously, take tangents.

One potential resolution to this objection is that for many angles, tan(theta) is approximately equal to theta, so rather than observing the acceleration of a tangent, outfielders can merely observe the acceleration of an angle. If the acceleration of an angle can be estimated by the felt acceleration of the neck joints that crick as the neck moves back to observe the ball, and if an angle is a reasonable approximation for its tangent, then we don’t need to assume any great subconscious mathematical or geometrical powers on the part of outfielders—only the physical skill of being accurately attuned to subtle sensory inputs.

By making an acceleration estimate the only difficult part of the process, we have obtained a potential solution to the outfielder problem that has much more psychological plausibility than the inner physicist’s theory of subconsciously extrapolated parabolas. Of course, the psychological appeal of the solution doesn’t mean that it can be used only by humans. A robot outfielder could also be programmed to follow Chapman’s five-step process, and it might even perform better at catching the ball if it did so, because, for example, Chapman’s process enables those who use it to dynamically respond to changes due to wind or bounces.

Besides psychological plausibility, there’s one more crucial feature that the five-step process implied by Chapman’s insight possesses: it doesn’t rely on a solve-for-x strategy or any explicit equation at all. Instead, it proposes successive iterations of easy observations and small, gradual steps to reach a well-defined goal. In other words, the process that we have inferred from Chapman’s theory is an algorithm.

Solving Problems with Algorithms

The word algorithm came from the name of the great al-Khwarizmi, mentioned earlier. It’s not an easy word to define, not least because its accepted definition has changed over time. Stated simply, an algorithm is just a set of instructions that produce a well-defined outcome. This is a broad definition; as we saw in the Introduction, tax forms and recipes for parfaits could rightly be considered algorithms.

Chapman’s ball-catching process, or Chapman’s algorithm as we may want to call it, is arguably even more algorithm-like than a recipe for a parfait, because it contains a looping structure in which small steps are taken repeatedly until a definite condition is reached. This is a common algorithmic structure you’ll see throughout this book.

Chapman proposed an algorithmic solution to the outfielder problem because a solve-for-x solution was not plausible (outfielders often don’t know the relevant equations). In general, algorithms are most useful when the solve-for-x strategy fails. Sometimes we don’t know the right equations to use, but more often there is no equation that could fully describe a situation, the equation is impossible to solve, or we face time or space constraints. Algorithms exist at the edge of what is possible, and every time an algorithm is created or improved, we push the frontier of efficiency and knowledge out a little further.

Today, there is a common perception that algorithms are difficult, esoteric, mysterious, and strictly mathematical and that they require years of study to understand. The way our education system is structured today, we begin teaching children the solve-for-x strategy as early as possible, and we explicitly teach algorithms only at the college or graduate school levels, if at all. For many students, it takes years to master the solve-for-x strategy, and it always feels unnatural to them. People who have had this experience may assume that algorithms will feel just as unnatural, and will also be more difficult to understand because they are more “advanced.”

However, the lesson I take from Chapman’s algorithm is that we have gotten it all exactly backward. During recess, students learn and perfect their performance of dozens of algorithms, for catching, throwing, kicking, running, and moving. There are probably also much more complex algorithms, which have not been fully delineated, that govern the operation of the social world of recess: the talking, status seeking, gossiping, alliance formation, and friendship cultivation. When we end recess time and start math class, we take students out of a world of algorithm exploration and push them to learn an unnatural and mechanistic process of solving for x, a process that is not a natural part of human development and is not even the most powerful method for solving analytical problems. Only if students progress to advanced math and computer science do they return to the natural world of algorithms and the powerful processes that they were unconsciously and joyfully mastering at recess.

This book is meant to be an intellectual recess for the curious—a recess in the sense that a young student means it: the beginning of all important activity, the end of all drudgery, and the continuation of cheerful exploration with friends. If you have any feeling of trepidation about algorithms, remind yourself that we humans are naturally algorithmic, and if you can catch a ball or bake a cake, you can master an algorithm.

In the remainder of this book, we explore many different algorithms. Some will sort lists or calculate numbers. Others will enable natural language processing and artificial intelligence. I encourage you to bear in mind that algorithms don’t grow on trees. Each algorithm, before it became mainstream and was packaged for general consumption in this book, was discovered or created by someone like Chapman, who woke up one day in a world in which his algorithm didn’t exist and went to sleep at the end of that day in a world in which it did. I encourage you to try to get in the mindset of these heroic discoverers. That is, I encourage you to approach an algorithm not only as a tool to be used but also as a formidable problem that was solved. The world of algorithms is not yet close to being fully mapped—many remain to be discovered and perfected, and I earnestly hope that you can be a part of that discovery process.

Summary

In this chapter, you saw two approaches to solving a problem: the analytic one and the algorithmic one. By solving the outfield problem two ways, we explored the differences between these approaches, ultimately arriving at Chapman’s algorithm. Chapman found a simple pattern in a complex situation (the constant acceleration of the tangent of theta) and used it to develop the idea of an iterative, looping process that requires only one simple input (the feeling of acceleration in a craning neck) and leads to a definite goal (catching a ball). When you seek to develop and use algorithms in your own work, you can try to emulate Chapman’s example.

In the next chapter, we look at some examples of algorithms in history. These examples should deepen your appreciation of algorithms, including what they are and how they work. We’ll talk about algorithms from ancient Egypt, ancient Greece, and Imperial Japan. Every new algorithm you learn can be an addition to the “toolbox” of algorithms that you can rely on when you eventually advance to the point at which you can design and perfect your own.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.236.64.8