Description

Guidelines for this assignment
Coding requirements. For fairness and efficiency, we use an automatic program to grade your submissions. This means you must write your code carefully so that our program can run your code and understand its output properly. In particular:
1. You must code this assignment in Python 3, not Python 2.
2. Make sure to use the program file name we specify.
3. Use the skeleton code we provide, and follow the instructions in the skeleton code (e.g., to not change the parameters of some functions.
5. IMPORTANT: In addition to testing your programs on your own, test your code on silo.sice.indiana.edu using test scripts that are provided in the Github repo. To run these test scripts on your code, type: python3 -m pytest -v
This will automatically run your programs on some sample test cases, and indicate whether your programs passed or failed. These test cases are just samples; we will run this on more cases while grading, so make sure to test your code thoroughly.
Coding style and documentation. We will not explicitly grade based on coding style, but it’s important that you write your code in a way that we can easily understand it. Please use descriptive variable and function names, and use comments when needed to help us understand code that is not obvious.
Report. Please put a report describing your assignment in the Readme.md file in your Github repository.
For each problem, please include: (1) a description of how you formulated the search problem, including precisely defining the state space, the successor function, the edge weights, the goal state, and (if applicable) the heuristic function(s) you designed, including an argument for why they are admissible; (2) a brief description of how your search algorithm works; (3) and discussion of any problems you faced, any assumptions, simplifications, and/or design decisions you made. These comments are especially important if your code does not work as well as you would like, since it is a chance to document the energy and thought you put into your solution. For example, if you tried several different heuristic functions before finding one that worked, feel free to describe this in the report so that we appreciate the work that you did.
Part 0: Getting started
To get started, clone the github repository:
git clone git@github.iu.edu:cs-b551-fa2021/your-repo-name-a1 If that doesn’t work, instead try:
git clone https://github.iu.edu/cs-b551-fa2021/your-repo-name-a1
where your-repo-name is the one you found on the GitHub website above. (If neither command works, you probably need to set up IU GitHub ssh keys. See Canvas for help.)
For example, here is a sequence of three moves on such a puzzle:
1 2 3 4 5 →L3 1 2 3 4 5
6 7 8 9 10 6 7 8 9 10
11 12 13 14 15 12 13 14 15 11
16 17 18 19 20 16 17 18 19 20
21 22 23 24 25 21 22 23 24 25
1 2 23 4 5 Occ → 2 23 4 5 10
6 7 3 9 10 1 7 3 9 11
12 13 8 15 11 6 13 8 15 20
16 17 14 19 20 12 17 14 19 25
21 22 18 24 25 16 21 22 18 24
→D3
2 23 4 5 10
1 13 7 3 11
6 17 8 9 20
12 14 19 15 25
16 21 22 18 24
→Ic
The goal of the puzzle is to find a short sequence of moves that restores the canonical configuration (on the left above) given an initial board configuration. We’ve provided skeleton code to get you started. You can run the skeleton code on the command line:
python3 solver2021.py [input-board-filename]
where input-board-filename is a text file containing a board configuration (we have provided an example). You’ll need to complete the function called solve(), which should return a list of valid moves. The moves should be encoded as strings in the following way:
• For sliding rows, R (right) or L (left), followed by the row number indicating the row to move left or right. The row numbers range from 1-5.
• For sliding columns, U (up) or D (down), followed by the column number indicating the column to move up or down. The column numbers range from 1-5.
• For rotations, I (inner) or O (outer), followed by whether the rotation is clockwise (c) or counterclockwise (cc).
For example, the above diagram performs the moves L3 (slide row 3 left), D3 (slide column 3 down), Occ (outer counterclockwise), and Ic (inner clockwise).
The initial code does not work correctly. Using this code as a starting point, implement a fast version, using A* search with a suitable heuristic function that guarantees finding a solution in as few moves as possible. Try to make your code as fast as possible even for difficult boards, although it is not necessarily possible to quickly solve all puzzles. For example, board1.txt can be solved in 11 moves. You will need to be creative with your heuristic function in order to find this solution in less than 15 minutes.
In your report, answer the following questions:
1. In this problem, what is the branching factor of the search tree?
2. If the solution can be reached in 7 moves, about how many states would we need to explore before we found it if we used BFS instead of A* search? A rough answer is fine.
In addition to doing your own testing, it is important that you test your program on silo.sice.indiana.edu using our test script to ensure that we will be able to run it and grade it accurately.
Part 2: Road trip!
It’s not too early to start planning a post-pandemic road trip! If you stop and think about it, finding the shortest driving route between two distant places — say, one on the east coast and one on the west coast of the U.S. — is extremely complicated. There are over 4 million miles of roads in the U.S. alone, and trying all possible paths between two places would be nearly impossible. So how can mapping software like Google Maps find routes nearly instantly? The answer is A* search!
We’ve prepared a dataset of major highway segments of the United States (and parts of southern Canada and northern Mexico), including highway names, distances, and speed limits; you can visualize this as a graph with nodes as towns and highway segments as edges. We’ve also prepared a dataset of cities and towns with corresponding latitude-longitude positions. Your job is to find good driving directions between pairs of cities given by the user.
The skeleton code can be run on the command line like this:
python3 ./route.py [start-city] [end-city] [cost-function] where:
• start-city and end-city are the cities we need a route between.
• cost-function is one of:
– segments tries to find a route with the fewest number of road segments (i.e. edges of the graph).
– distance tries to find a route with the shortest total distance.
– time finds the fastest route, assuming one drives the speed limit.
– delivery finds the fastest route, in expectation, for a certain delivery driver. Whenever this driver drives on a road with a speed limit ≥ 50 mph, there is a chance that a package will fall out of their truck and be destroyed. They will have to drive to the end of that road, turn around, return to the start city to get a replacement, then drive all the way back to where they were (they won’t make the same mistake the second time they drive on that road).
Consequently, this mistake will add an extra 2·(troad +ttrip) hours to their trip, where ttrip is the time it took to get from the start city to the beginning of the road, and troad is the time it takes to drive the length of the road segment.
For a road of length ` miles, the probability p of this mistake happening is equal to tanh if the speed limit is ≥ 50 mph, and 0 otherwise. This means that, in expectation, it will take troad + p · 2(troad + ttrip) hours to drive on this road.
For example:
python3 ./route.py Bloomington,_Indiana Indianapolis,_Indiana segments
You’ll need to complete the get route() function, which returns the best route according to the specified cost function, as well as the number of segments, number of miles, number of hours for a car driver, and expected number of hours for the delivery driver. See skeleton code for details.
Like any real-world dataset, our road network has mistakes and inconsistencies; in the example above, for example, the third city visited is a highway intersection instead of the name of a town. Some of these “towns” will not have latitude-longitude coordinates in the cities dataset; you should design your code to still work well in the face of these problems.
In addition to doing your own testing, it is important that you test your program on silo.sice.indiana.edu using our test script to ensure that we will be able to run it and grade it accurately.
Extra credit. Implement an additional cost-function: statetour should find the shortest route from the start city to the end city, but that passes through at least one city in each of the 48 contiguous U.S. states.
Part 3: Choosing teams
1. What is your IU email username?
2. Please choose one of the options below and follow the instructions.
(a) You would like to work alone. In this case, just enter your userid in the box and nothing else.
(b) You would like to work in a group of 2 or 3 people and already have teammates in mind. In this case, enter all of your userids (including your own!) in the box below, in a format like userid1-userid2 for a team of 2, or userid1-userid2-userid3 for a team of 3.
(c) You would like to work in a group of 2 or 3 people but do not have any particular teammates in mind. In this case, please enter your user ID followed by one “zzz” per missing teammate (e.g.
djcran-zzz where djcran is your user ID to request a team of 2, or djcran-zzz-zzz for a team of 3).
(d) You would like to work in a group of 3 people and have some teammates in mind but not all. Enter all of your ids, with zzz’s to mark missing teammates (e.g. if I only have one teammate (vkvats) in mind so far, I’d enter djcran-vkvats-zzz).
3. If there are any people you DO NOT want to work with, please enter their userids here (separated by commas, e.g. userid1,userid2,userid3).
• It will take 5 minutes to grade each assignment, so total grading time is 5 times the number of teams.
djcran djcran-vkvats-nthakurd sahmaini sahmaini sahmaini _ sulagaop sulagaop-xxx-xxx _ fanjun fanjun-xxx nthakurd nthakurd nthakurd djcran,fanjun vkvats vkvats-sahmaini _ where the underscore character ( ) indicates an empty value.
We have provided skeleton code to get you started, which can be run like:
python3 ./assign.py [input-file]
[“djcran-vkvats-nthakurd”, “sahmaini”, “sulagaop-fanjun”]
which has a cost of 34, computed by the sum of: 1. There are three groups’ assignments to grade (3×5 = 15 minutes) 2. Three people (sulagaop, nthakurd, and vkvats) didn’t get the requested number of teammates (3 × 2 = 6 minutes) 3. One person (nthakurd) had to work with someone they requested not to work with (djcran) (10 minutes) 4. One person (vkvats) didn’t get to work with a person they requested (sahmaini) (0.05 × 60 = 3 minutes)
In addition to doing your own testing, it is important that you test your program on silo.sice.indiana.edu using our test script to ensure that we will be able to run it and grade it accurately.
What to turn in
Tip: These three problems are very different, but they can all be posed as search problems. This means that if you design your code well, you can reuse or share a lot of it across the three problems, instead of having to write each one from scratch.