Project 2:
Problem Formulation in Python

CSE 190C, University of Washington, Early Fall Start 2020


 

Overview

This project should be done in partnerships of two. You should first form a partnership with another member of the class. Then arrange to meet online and/or communicate by email at certain times to coordinate progress on this project.

There are two parts to this project. In Part A, you and your partner will work together to create a problem formulation for the puzzle called "The Farmer, the Fox, the Chicken, and the Grain." In Part B, you and your partner will create the formulation of another problem.

Part A

In this part, you and your partner will create a formulation for the "The Farmer, the Fox, the Chicken, and the Grain" puzzle. This puzzle is similar to the Missionaries and Cannibals problem in the sense that the player has to help get everything across a river where there is a boat. However, the rules are slightly different. A farmer, a fox, a chicken, and a bag of grain are on the left bank of a river. There is a boat there, too. The player has to figure out how to get everybody across. Each move involves the farmer rowing the boat across the river either alone or with one of the animals or grain. The constraints are as follows: The fox must not be left alone with the chicken, or else the chicken gets eaten. The chicken must not be left alone with the grain, or the grain gets eaten.

Work with your partner to create a working formulation of this problem. It should at least work with the Text SOLUZION client. To use this tool, first try it out with Missionaries.py as follows: Make sure both of these files are in the same folder on your computer: Text_SOLUZION_Client.py and Missionaries.py. Then decide whether you will use the "command-line" method or the IDLE method to run the program.

  1. Command-Line Method: In a Linux or Unix style environment (like Darwin on Macs, or Cygwin on PCs), change directory into the folder containing your two Python files, and then execute this: 
    % python3 Text_SOLUZION_Client.py Missionaries
  2. IDLE Method: Open Text_SOLUZION_Client.py in IDLE (in its own buffer, not the Shell). Then choose Run Module from the Run menu. You should then be able to interact with the Missionaries and Cannibals puzzle in the shell window.

When you are ready to try out your FarmerFox.py example, you'll again either use the Command-Line Method or the IDLE Method. If you use the Command-Line Method, type that command line starting with python3 as above, except replace "Missionaries" with "FarmerFox".

If you use the IDLE Method, edit the line in Text_SOLUZION_Client.py where it does import Missionaries and change it to 

import FarmerFox

Then when you select Run Module from the Run menu, it should run your FarmerFox.py formulation instead of Missionaries.py.

Optionally, you can also make your FarmerFox.py formulation work with the Tk SOLUZION client, which supports a graphical state display. The best way to go about this is (a) develop a complete understanding of the Missionaries.py problem formulation, as well as its visualization code, and (b) make sure you understand the rules for the Farmer, Fox, Chicken and Grain puzzle. Then either start a new file from scratch called FarmerFox.py or make a copy of Missionaries.py and start editing that as your FarmerFox.py. If you are using the Tk_SOLUZION_Client, you'll also need the following file to be in the same folder as your FarmerFox.py file: show_state_array.py.

This puzzle is relatively easy to formulate and get working, and so doing this is a good step to perform prior to starting Part B of this project. Some guidelines for creating the visualization file are provided How-to-Pose-for-TkS.txt. here

Part B

Then in Part B, you will then choose a particular problem from a list of suggested problems. However, you may suggest an alternative problem and get clearance from the instructor to base your work around that problem.

Purposes

There are two main purposes for doing this project. First is to get more practice with the Python language, and whatever IDE or editor you may be using with Python. The second purpose is to develop some feeling for the process of "operationalizing" a problem -- creating something that a user (a solver) can actually operate and do something with, using a computer.

Choosing a Problem

This project focuses more on the coding phase of problem formulation rather than pre-formulation or posing. Consequently, you should choose a fairly well-defined problem or define something yourself that is simple. Here is a list of suggestions.

  1. Instant Insanity. This is the 4-cube puzzle that requires arranging a given set of colored cubes into a tower such that on each of the four sides of the tower, there is one face of each of the four colors.
  2. Rubik's Cube. This is well-known. It's not the easiest puzzle to formulate, but some teams may wish to try it.
  3. "Single-player Tic-Tac-Toe". This is not a standard puzzle or game, but you can make up the rules. One approach would be to have the single player play X's and O's in alternating turns, except that the objective is to maximize a score by creating patterns, rather than simply getting three in a row. For example, each occurrence of the pattern XOX in any direction might be worth 5 points, and each occurrence of a 2x2 block of Os might be worth 10 points, etc.
  4. A simple linear equation solving problem. Each state will be a formula such as "3 + 7 - 2*x = 0". The operators might be "subtract 3 from both sides", or "divide both sides by 2", etc. Rather than having operators for every possible value, limit the values to potentially relevant ones or ones that depend on the formula: "subtract the first constant from both sides." Etc.

Formulation of the Problem

Develop a formulation that can be operated using the Text_SOLUZION_Client.py program. You can debug your state representation and your operators here, in a relatively efficient manner. In this first stage of development, you should not have any state visualization. The solver will only get to see a textual representation of the current state.

Then create a version that uses the graphical state-visualization capabilities of Tk_SOLUZION_Client.py (and which will involve show_state_array.py).

Description File and Turn-in

Create a file P2-Description.pdf that answers the following questions. (1) What is the problem you have formulated in Part B? If this is not a well-known problem, explain what the problem is and any rules you have made up. (2) What is your state representation and why? (3) What operators do you provide? Did you face a choice when you designed your operators, and if so, what is another possibility that you considered? Why did you go with the choice you made? (4) Did you provide a visualization in your formulation? Briefly, how does that work? (5) Describe how you and your partner(s) divided up the work of the project. Make sure that both partners' full names are included in the report. (Note that both of your names should also be included as authors, within the METADATA portion of the problem-formulation template file.) (6) Describe any particular challenges you had with this project.

Submit your solutions files for both Part A and Part B and your P2-Description.pdf file via Canvas. Due on Friday, September 4 at 5:00 PM. In each partnership, there should be a submission by only one of the partners, and that submission should be made by the partner whose last name comes first in an alphabetical ordering of last names. For example of Judy Kirsch is partnered with Zoe Anderson, all the files for this project should be submitted by Zoe, and not Judy, because Zoe's last name, Anderson, comes before Judy's last name, Kirsch, in an alphabetical ordering.

Files needed: 

A1: Your problem formulation file for Part A, named FarmerFox.py.
A2: (Optional) your visualization file for Part A, named FarmerFox_array_VIS_FOR_TK.py.

B1: Your problem formulation file for Part B, named appropriately.
B2: Your visualization file for Part B, named appropriately.

D: P2-Description.pdf

So each partnership will be turning in at least 4 files and possibly 5 files. (Do not turn in show_state_array.py; you should NOT have made any modifications to that file.)