Algorithmic Thinking with Python part 2 — Decrease and Conquer Strategy

This article is about computational thinking. Before we dive in though, check out this puzzle.

The Ferrying Soldiers Puzzle

A troop of 20 soldiers must cross a river with with no bridge. There are two boys playing in a small by the shore. The boat is only large enough to carry a single soldier or two boys.

How can the soldiers all get across the river, leaving the two boys in the boat on the same side as they started? Work out the minimum number of crossings that the boat must make.

(Medium doesn’t support embedded Python Trinkets, but please go ahead and try the puzzle by clicking on the link, and come back when you’ve had a go):

Trinket: run code anywhere

The Decrease and Conquer Problem Solving Strategy

Decrease and Conquer is a computational problem solving technique which takes a problem and reduces it to a smaller problem which is easier to solve. Sometimes this is confused with Divide and Conquer which is similar, but which breaks up a problem into multiple smaller problems. For comparison, Merge Sort and Quicksort are examples of divide and conquer algorithms.

Classic examples of Decrease and Conquer are:

• Binary Search
• Euclid’s algorithm
• Depth-First Search
• Breadth-First Search
• Insertion Sort and Selection Sort

For example, in Binary Search, the search space is decreased by a factor of 2 at each step, leading to a very efficient algorithm (with a time complexity of O(log n)). In the case of Euclid’s Algorithm for finding the greatest common divisor of two integers, the larger number is divided by the smaller at each step and the algorithm repeats using the smaller number and the remainder of the previous division. For insertion sort, the size of the unsorted section of data is decreased at each step.

There are different categories of amounts that an original problem is decreased by in a Decrease and Conquer algorithm. However for all of them the basic principle holds:

At each step of the algorithm, the problem is reduced to a smaller version of the same problem, until a solution is found (or found not to be possible).

The categories for the amount of decrease are:

Decrease by a constant

This is often by a constant of one.

Examples:

• Insertion sort
• Graph search algorithms: DFS, BFS

Decrease by a constant factor

Most commonly by a factor of two, as in Binary Search

Examples:

• Binary search
• Fake-coin problems
• “Russian peasant multiplication”

Variable size decrease

A classic example here would be the Euclidean Algorithm, where the amount of decrease depends on the values given.

Solution to the Ferrying Soldiers Puzzle

And now for the solution to the Ferrying Soldiers Puzzle.

First, the two boys must row the boat to the other side, after which one of them returns with the boat. Then a single soldier rows the boat to the other side and stays there while the other boy returns the boat. These four trips reduce the problem size by 1 (described by the number of soldiers needing to cross the river). Thus, if this four-trip procedure is repeated a total of 20 times, the problem will be solved after the total of 80 trips. For the general instance of n soldiers, 4n trips will need to be made.

How did you do? Did you get the same result?

The Ferrying Soldiers Puzzle provides a great illustration of the Decrease and Conquer strategy for solving computational problems.

Python Listing for the Ferrying Soldiers Puzzle

For your reference, here is a Python 3 version of the Ferrying Soldiers Puzzle

"""
Ferrying Soldiers Puzzle Python Implementation
Robin Andrews - https://compucademy.net/
"""
import os
import time
NUM_SOLDIERS = 2
def section_break():
    print("*" * 50)
def print_rules():
    pass
def print_state(state, moves_taken):
    os.system("cls" or "clear")
    left_bank, right_bank, bank = state["left_bank"], state["right_bank"], state["bank"]
    print("#### CURRENT STATE OF PUZZLE ####\n")
    print(f"Moves taken: {moves_taken}\n")
    # print(f"{left_bank} | {right_bank}\n")
    print(f"{left_bank['boys']} boys, {left_bank['soldiers']} soldiers | {right_bank['boys']} boys, {right_bank['soldiers']} soldiers\n")
    print(f"Boat is on {bank} bank")
def get_move(state):
    print("\nPuzzle options: \n")
    print("1. Ferry both boys from left to right bank")
    print("2. Ferry both boys from right to left bank")
    print("3. Ferry one boy from left to right bank")
    print("4. Ferry one boy from right to left bank")
    print("5. Ferry a soldier from left to right bank")
    print("6. Ferry a soldier from right to left bank\n")
    choice = 0
    while choice not in [1, 2, 3, 4, 5, 6]:
        try:
            choice = int(input("Choose an action(1-4): "))
        except:
            continue
return choice
def process_move(move, state, moves_taken):
    # We can allow 1 boy, 2 boys or one soldier to cross only
    bank = state["bank"]
    legal_move = False
    # Move both boys from left to right bank
    if move == 1 and bank == "left":
        if state["left_bank"]["boys"] == 2:
            state["left_bank"]["boys"] -= 2
            state["right_bank"]["boys"] += 2
            legal_move = True
            state["bank"] = "right"
    elif move == 2 and bank == "right":
        if state["right_bank"]["boys"] == 2:
            state["right_bank"]["boys"] -= 2
            state["left_bank"]["boys"] += 2
            legal_move = True
            state["bank"] = "left"
    elif move == 3 and bank == "left":
        if state["left_bank"]["boys"] > 0:
            state["left_bank"]["boys"] -= 1
            state["right_bank"]["boys"] += 1
            legal_move = True
            state["bank"] = "right"
    elif move == 4 and bank == "right":
        if state["right_bank"]["boys"] > 0:
            state["right_bank"]["boys"] -= 1
            state["left_bank"]["boys"] += 1
            legal_move = True
            state["bank"] = "left"
    elif move == 5 and bank == "left":
        if state["left_bank"]["soldiers"] > 0:
            state["left_bank"]["soldiers"] -= 1
            state["right_bank"]["soldiers"] += 1
            legal_move = True
            state["bank"] = "right"
    elif move == 6 and bank == "right":
        if state["right_bank"]["soldiers"] > 0:
            state["right_bank"]["soldiers"] -= 1
            state["left_bank"]["soldiers"] += 1
            legal_move = True
            state["bank"] = "left"
if legal_move:
        moves_taken +=1
        return state, moves_taken
    else:
        print("That move is not possible at this time.")
        time.sleep(1)
        return state, moves_taken
def is_win(state):
    return state == {"left_bank": {"boys": 2, "soldiers": 0},
             "right_bank": {"boys": 0, "soldiers": NUM_SOLDIERS},
             "bank": "left"}
def main():
    state = {"left_bank": {"boys": 2, "soldiers": NUM_SOLDIERS},
             "right_bank": {"boys": 0, "soldiers": 0},
             "bank": "left"}
    moves_taken = 0
    while not is_win(state):
        # section_break()
        print_state(state, moves_taken)
        move = get_move(state)
        state, moves_taken = process_move(move, state, moves_taken)  # maybe modify moves_taken in main()
print(f"Well done - you solved the puzzle! You took {moves_taken} moves.")
main()

Happy computing!

Originally published at https://compucademy.net on November 19, 2020.