Prune and Search

In this lesson, we will learn about the prune and search techniques. Prune refers to the act of removing or eliminating unnecessary or irrelevant paths, and this term is often used in the context of search algorithms. In short, pruning refers to the process of discarding certain branches or paths in the search to improve efficiency and make the search more efficient.

We have two problems below for which we need to find efficient solutions. We will employ the prune and search techniques to solve them. So let’s begin!

Beans challenge

A pot contains $75$ white beans and $150$ black ones. Next to the pot is a large pile of black beans.

A cook removes the beans from the pot, one at a time, according to the following rule: he removes two beans from the pot at random.

• If at least one of the beans is black, he places it on the bean pile and drops the other bean, no matter what color, back into the pot.
• On the other hand, if both beans are white, he discards both of them and picks one black bean from the pile and drops it in the pot.

By taking a close look at each step of this procedure. We’ll notice that the pot has one less bean in it each time! Finally, there will only be one bean left. What color is it?

Directions to look at the challenge

There could be three scenarios while picking beans:

1. One black and one white bean
2. Two black beans
3. Two white beans

For the first two scenarios, $1$ black bean is being moved from jar to pile. But in the last case, when both beans are white, they get discarded and $1$ black bean from the pile gets added to the jar.

Solution

As the cook only removes white beans when it is in pair, he will eventually remove $74/75$ white beans from the pot leaving behind unknown $N$ black beans in a pot.

All the black beans will be removed from the pot one by one. For example, if the cook picks two black beans, he removes one from the pot. If he picks one black bean and one white bean, he removes the black one from the pot. In either case, he removes all of the black beans and the remaining beans will be white as white beans could only be removed in pairs and there is an odd number of white beans in the pot.

$100-$story building challenge

You are given two balls made of clay and a 100-story building. The balls can be either fragile or strong, which means that they may break if dropped from the first floor or may not even break if dropped from the 100th floor. Both balls are the same.

You need to figure out the highest floor of that 100-story building from where you can drop either ball without breaking it.

Directions to look at the challenge

First, try solving the problem with one ball. We can’t use binary search for this problem because if we drop a ball from the 50th floor and it breaks, we’ve lost our chance. So, for one ball, we can only solve that by dropping the ball from the 1st floor, then from the 2nd, and so on. But in that case, there will be a lot of steps to solve this problem. For example, for $N$ floors, $N-1$ tries would be needed.

Now let’s try with two balls. With two balls, we can first drop one ball from the 50th floor, and if it breaks, we can use the same solution that we used above using one ball (dropping the second ball from 1st to the 49th floor). However, if the first ball doesn’t break on the 50th floor, we can again drop it from the 75th floor. If it breaks, we can drop the second ball from the 51–100th floor.

Remember: If it’s the worst-case scenario and the floor where the ball breaks is the 100th floor, our first approach would require 99 steps but the latter approach will find the answer in half steps.

Solution

Approach 1

Here’s a possible solution to find the answer in less than $20$ steps for all possible scenarios.

We’ll take one of the given balls and drop it from the $10^{th}$ floor at first. If the ball does not break there, we’ll drop the ball from the $20^{th}$ floor, then $30^{th}$, and so on. If the ball breaks at any $K^{th}$ floor, we’ll step down nine floors and start dropping the ball from $K - 9^{th}$ floor and approach the $K^{th}$ floor step by step. This technique will help us find the highest floor of that building from where the ball does not break at a maximum of $19$ steps.

Approach 2

For the above solution, one can observe that if the clay ball breaks on the first try, the number of possibilities is only $10$, and if it breaks on the second try, the number of possibilities is only $11$, and this number of possibilities increases as we go forward and the worst case is if the ball breaks closer to the last range from $81-90$ or $91-100$.

What can we do so that as we go up the order of range, the number of possibilities remains the same? The idea is that instead of dropping it with a gap of 10, we start from a position of $x$, and on the next, we drop the ball with the gap of $x-1$, $x-2$, and so on up to $2$ and then $1$. This way, if the ball breaks on the first try, the total number of possibilities is $x$, and if it breaks on the second try, the total number of possibilities is again $x$. Hence, it becomes the following expression:

$$The \space total\space tries\space accumulation \space of \space ranges = x+(x-1)+(x-2)+...+3+2+1 = 100$$

To solve for $x$ (where the equation represents an arithmetic series), we can do the following:

$$\frac{x}{2}\times(x+1) = 100$$

$$x^2 + x -200 = 0$$

$$x = 13.65$$

Hence, we used the prune and search technique to solve the above problem using only $14$ tries by following this algorithm, first by dropping the ball from $14$, then $27$, then $39$, then $50$, and so on.

Note: The prune and search technique is one of the most fundamental strategies in computer science. We can use it to design an algorithm in which the pruning process yields a reduced search space geometrically.