Python Sets and a River Crossing Puzzle

Have you heard of the puzzle about the farmer, the wolf, the goat and the cabbage?

You can play it here (click the “run” button to start):

There are many different ways to implement the logic, but here I chose to use Python Sets. My goal here is to teach about Python programming. If you just want to enjoy the puzzle, with some nice graphics, there’s some great versions on here on Trunsum Maths.

Python Sets

A set in Python is defined as “an unordered collection of unique elements”

Sets are a less known but very useful data structure in Python. There are two properties which make them especially helpful for solving certain types of problems.

  • Sets are unordered
  • Sets can not contain duplicate elements.

The second property can lead to a lot of confusion. So let’s be clear about an important point: set declaration is different to the data structure. The declaration can have duplicates but not the structure itself.

So, a set declared by my_set = {1, 2, 2, 5} will be stored and displayed as {1, 2, 5} (potentially with the elements in any order).

This distinction between declaration and representation can lead to exactly opposite answers to the question “can sets contain duplicate elements?” and it really depends on what the person asking actually means. The correct answer is no, assuming they are asking about the actual data structure.

Basic Set Operations in Python

# Create a set using set literal notation
my_set = {1, 3}

# Add an element to a set
my_set.add(2)

# Remove an element from a set
my_set.remove(1)

# find the length of a set
print(len(my_set))

# Create a set from a list
my_set = set(my_list)

Have a go at creating and modifying some sets. Print your sets as you go to check they are displaying what you expect. Also, don’t limit yourself to integer elements – try string and other data types too.

Python Sets Challenge

Once you’ve had a bit of practice with sets, try and solve the following challenge: complete the definition for contains_duplicates() which takes a list as an argument and returns a boolean describing whether the list contains duplicate elements or not.

def contains_duplicates(a_list):
        # Create a set from the argument
        # Then use it to solve the challenge....
        pass

# A couple of tests to check your function is working properly  
my_list = [1,2,2,5,7]  
print(contains_duplicates(my_list)) # True

my_list = [1,2,5,7]  
print(contains_duplicates(my_list)) # False

Python Sets Challenge Solution

Python Version of the Farmer, the Wolf, the Goat and the Cabbage Puzzle

Here’s a listing of the code for the Farmer, the Wolf, the Goat and the Cabbage Puzzle in Python. It is designed to be run in a console, so has a clear method to clear the console to keep things tidy. You may prefer to use the Trinket version, but don’t forget to add brackets to the print statements as Trinket uses Python 2.7.

"""
Wolf, Goat and Cabbage Puzzle in Python
By Robin Andrews - https://compucademy.co.uk/
"""
import os  # Only needed in console version
import time # Only needed in console version

names = {"F": "Farmer",
         "W": "Wolf",
         "G": "Goat",
         "C": "Cabbage"}

forbidden_states = [{"W", "G"}, {"G", "C"}, {"G", "C", "W"}]


def print_story():
    print("""
#### WOLF, GOAT and CABBAGE PROBLEM ####

Once upon a time a farmer went to a market and purchased a wolf, a goat, and a cabbage. On his way home, the farmer came
to the bank of a river and rented a boat. But crossing the river by boat, the farmer could carry only himself and a single
one of his purchases: the wolf, the goat, or the cabbage.

If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage.

The farmer's challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact.
How did he do it?
""")
    input("Press enter to continue.")


def clear():
    # os.system('cls' if os.name == 'nt' else 'clear')  # Console version
    print("*" * 60, "\n")  # IDLE/Trinket version - prints page break instead of clearing screen.


def print_state(state):
    left_bank, right_bank = state
    print("#### CURRENT STATE OF PUZZLE ####")
    print()
    left_bank_display = [names[item] for item in left_bank]
    right_bank_display = [names[item] for item in right_bank]
    print(left_bank_display, "|", right_bank_display if right_bank else "[]")
    print()


def get_move():
    print("Which item do you wish to take across the river?")
    answer = ""
    while answer.upper() not in ["F", "W", "G", "C"]:
        answer = input("Just Farmer (f), Wolf (w), Goat (g) or Cabbage (c)? ")

    return answer.upper()


def process_move(move, state):
    # We need to "think ahead" to see if move is illegal.
    temp_state = [state[0].copy(), state[1].copy()]
    containing_set = 0 if move in state[0] else 1
    if "F" not in state[containing_set]:
        print("Illegal move.")
        print()
        time.sleep(1)
        return state
    if containing_set == 0:
        temp_state[0].difference_update({move, "F"})
        temp_state[1].update([move, "F"])
    elif containing_set == 1:
        temp_state[1].difference_update({move, "F"})
        temp_state[0].update([move, "F"])
    if temp_state[0] not in forbidden_states and temp_state[1] not in forbidden_states:
        state = [temp_state[0].copy(), temp_state[1].copy()]
    else:
        print("Illegal move.")
        print()
        time.sleep(1)
    print()
    return state


def is_win(state):
    return state[1] == {"F", "W", "G", "C"}


def main():
    left_bank = {"F", "W", "G", "C"}
    right_bank = set()
    state = [left_bank, right_bank]
    print_story()
    while not is_win(state):
        clear()
        print_state(state)
        move = get_move()
        state = process_move(move, state)

    print("Well done - you solved the puzzle!")


main()

Happy Computing. Robin Andrews.


Below are products related to this article, some of which may be affiliate links.

Leave a Reply

Your email address will not be published. Required fields are marked *