CSCI-B-551-Assignment 1 Solved

Part 0: Getting started
For this project, we are assigning you to a team. You can find your assigned teammate(s) by logging into IU Github, at http://github.iu.edu/. In the upper left hand corner of the screen, you should see a pull-down menu. Select cs-b551-fa2021. Then in the box below, you should see a repository called userid1-a1, userid1-userid2-a1, or userid1-userid2-userid3-a1, where the other user ID(s) correspond to your teammate(s). Now that you know their userid(s), you can write them an email at userid@iu.edu.

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.)

Part 1: The 2021 Puzzle
Consider the 2021 puzzle, which is a lot like the 15-puzzle we talked about in class, but: (1) it has 25 tiles, so there are no empty spots on the board (2) instead of moving a single tile into an open space, a move in this puzzle consists of either (a) sliding an entire row of tiles left or right one space, with the left- or right-most tile ‘wrapping around’ to the other side of the board, (b) sliding an entire column of tiles up or down one space, with the top- or bottom-most tile ‘wrapping around’ to the other side of the board, (c) rotating the outer ‘ring’ of tiles either clockwise or counterclockwise, or (d) rotating the inner ring either clockwise or counterclockwise.

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.[1] 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.


Part 3: Choosing teams

In a certain Computer Science course, students are assigned to groups according to preferences that they specify. Each student is sent an electronic survey and asked to give answers to three questions:

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).

Unfortunately — and as we already discovered while assigning teams for Assignment 1 — the student preferences may not be compatible with each other: student A may request working with student B, but B may request not to work with A, for example. Students are going to complain, so the course staff decides to minimize their own work. They estimate that:

•    It will take 5 minutes to grade each assignment, so total grading time is 5 times the number of teams.

•    Each student who requested a specific group size and was assigned to a different group size will send a complaint email to an instructor, and it will take the instructor 2 minutes to read this email.

•    If a student is not assigned to someone they requested, there is a 5% probability that the two students will still share code, and if this happens it will take 60 minutes for the instructor to walk through the Academic Integrity Policy with them. If a student requested to work with multiple people, then this will happen independently for each person they were not assigned to. If both students requested each other, there will be two meetings.

•    Each student who is assigned to someone they requested not to work with (in question 3 above) complains to the Dean, who meets with the instructor for 10 minutes. If a student is assigned to a group with multiple people they did not want to work with, a separate meeting will be needed for each.

The total time spent by the course staff is equal to the sum of these four components. You can assume that each student fills out the survey exactly once, and fills it out according to the instructions. Your goal is to write a program to find an assignment of students to teams that minimizes the total amount of work the staff needs to do, subject to the constraint that no team may have more than 3 students. Your program should take as input a text file that contains each student’s response to these questions on a single line, separated by spaces. For example, a sample file might look like:

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]

Your job is to complete the solver() function. The function should return the final groups (each named according to the students in the group, separated by hyphens), and the total cost (time spent by instructors in minutes). For example, one assignment for the above file could be:

["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)

Hint: It may not always be possible to find the actual best solution in a reasonable amount of time, and “reasonable amount of time” may differ from one problem to the next. Our grading program will eventually exit your program if it takes too long. Your program is thus allowed to generate multiple solutions, which may be useful if your approach can quickly produce an estimate of the solution, and then as it performs more computation, finds better and betters solutions. You’ll call yield() each time you have found an answer — see skeleton code for details.

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.