Solved-Project 11- Solution

The Water Jugs Problem

We’ve previously talked about this problem in Lecture 2:

“You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a tap that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?”. (cf. ​Rich & Knight, 1991​)

In general, we could have more than two jugs of some other pre-specified volumes (For example, see ​this Wikipedia entry​for a version with 3 jugs). We will use the configuration file to specify the particular instance of the puzzle. It has the following format:

Line 1 is a keyword (​jugs​) that tells you this is the water jug problem

Line 2 is a tuple specifying the capacities of the jugs; e.g., (3, 4)

Line 3 is the initial state; e.g., (0, 0)

Line 4 is the goal state; e.g., (0, 2)

You may assume that we ​will not​stress test with bad inputs like negative capacities or impossible states, and we’ll keep to just two or three jugs.

The Path-Planning Problem

For this problem, we will read in a graph representation of a roadmap, where cities are nodes and roads between them are undirected edges with costs. We want to find a path from the starting city to the destination city with the lowest cost. Here is the format of the input configuration file:

Line 1 is a keyword (​cities​) that tells you that this is the path-planning problem. Line 2 is a list of the names and locations of the cities; e.g., [(“Arlington”,1,1),(”Berkshire”,2,3),(”Chelmsford”,1, 5)]

Line 3 is the name of the starting city

Line 4 is the name of the destination city

Each of the following lines specifies a connection between two cities and the cost of taking that route; e.g.,: (“Arlington”, “Chelmsford”, 4) specifies that it costs 4 units to go from Arlington to Chelmsford or vice versa (after one action).

You may assume that we ​will not​stress test with bad inputs like roads with negative or zero cost. We may try a large graph with this problem, however.

Timeline

• Begin by implementing the uninformed search strategies (​bfs​, ​dfs​, ​iddfs, ​and ​unicost) for the two specified puzzle problems.

• Next, implement the informed search algorithms (​greedy, astar, ​and ​idastar​) for the two specified puzzles. What would be a reasonable heuristic for each problem?

• Remote commit what you’ve got by 9/18 (Tuesday) night. At this point, you should have completed the uninformed search strategies and gotten started on the informed strategies. You may still modify any part of the code you want during the second week;

• we will not grade this first-week version for correctness, but we will check to see your early implementation decisions.

• I will specify the 3rd puzzle on 9/20 (Wednesday). You will then have a week to complete the assignment and do a final commit by 11:59pm 9/26 (Wednesday).

What to commit

• A transcript of running your program on the sample input file (on Linux or Mac Terminal or Cygwin on Windows, use the command “script” which will save your session into a text file. For DOS Prompt, you may have to find some workarounds (See: ​[1]​, ​[2]​)).

• Your Python source code.

• A README file that addresses the following:

• • the version of Python you used

• • List any additional resources, references, or web pages you’ve consulted.

• • List any person with whom you’ve discussed the assignment and describe the nature of your discussions.

• • Describe any component that is not working in your program

Grading Guideline