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?