Assignment 0: Searching and Python

B551 Assignment 0: Searching and Python
This assignment will give you practice with posing AI problems as search and an opportunity to dust off
your coding skills. Because it’s important for everyone to get up-to-speed on Python, for this
particular assignment you must work individually. Future assignments will allow you to work in
groups. Please read the instructions below carefully; we cannot accept any submissions that do not follow
the instructions given here. Most importantly: please start early, and ask questions on Q&A Community
or in office hours.
If you don’t know Python, never fear – this is your chance to learn! But you’ll have to spend some significant
amount of out of class time to do it. Students in past years have recommended the Python CodeAcademy
website, http://www.codeacademy.com/learn/python, and Google’s Python Class, https://developers.
google.com/edu/python/. There are also a wide variety of tutorials available online. If you’re already
proficient in one particular language, you might look for tutorials with names like “How to code in Python:
A guide for C# programmers,” “Python for Java programmers,” etc. Feel free to share any particularly
good or bad resources on Slack and/or Q&A Community. The instructors are also happy to help during
office hours. If you are struggling, please come and get help! We can’t help if you don’t ask.
Guidelines for this and future assignments
Coding requirements. For fairness and efficiency, we use a semi-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. Please be forewarned that
Python 2 is still quite popular, despite being obsolete, so many examples and tutorials you see online
may be written in Python 2. There are many minor changes between the two versions (see https:
//docs.python.org/3/whatsnew/3.0.html), but two come up particularly often. First, in Python 3,
print is a function, so its arguments must be surrounded by parentheses. Second, in Python 3, dividing
one integer by another integer performs floating point division, instead of integer division.
2. Your code must obey the input and output specifications given below. Because our grading
program is automatic (and is not powered by advanced AI!), it will not understand your code’s input
and output unless you carefully follow the specifications given below. For example, your code should
not require keyboard input (i.e., someone actually typing keys once your program is running) unless
we specifically indicate it below.
3. You may import standard Python modules for routines not related to AI, such as basic
sorting algorithms and data structures like queues, as long as they are already installed on the SICE
Linux servers. However, using additional modules is typically not required; we’ll usually tell you if we
feel a module would be helpful.
4. Make sure to use the program file name we specify. For example, for part 1, please call your
program submission route pichu.py, as we specify below. Submitting your program with a different
name, or submitting multiple versions of your code, will cause our autograder to fail and you to lose
points.
5. Please avoid using global (public) variables in your programs as they may cause your program
to behave unexpectedly when run by our grading program. A global variable is one that is defined
outside of any function. If you need to access the same variable in multiple functions, use return
statments and function arguments instead of global variables.
1
6. You should test your code on silo.sice.indiana.edu. We will test your code on this system, so
this is the only way to guarantee that your program will work correctly when we run it. You may (and
probably should!) do your actual day-to-day development work on your laptop, but it is important
that you periodically check that your code operates correctly on our servers, as minor differences in
Python versions, available modules, etc. may cause your code to work differently — and may seriously
affect your grade.
To help you test, we have included an automated testing program in your github repo. We also use this
testing program for autograding. Ensuring that your code works well with the testing program will help
make sure we grade your code correctly. The program requires you to make a one-time installation.
To install, type:
pip install pytest-timeout
Once installed you do not need to repeat this step in the future. To test your code, type:
python3 -m pytest -v
This will automatically run your programs on two 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.
Submissions. You’ll submit your code via GitHub. We strongly recommend using GitHub as you work
on the assignment, pushing your code to the cloud frequently. Among other advantages, this: (1) makes it
easier to collaborate on a shared project in later assignments, when you are working in groups, (2) prevents
losing your code from a hard disk crash, accidental deletion, etc., (3) makes it possible for the AIs to look
at your code if you need help, (4) makes it possible to retrieve previous versions of your code, which can
be crucial for successful debugging, and (5) helps document your contribution to team projects (since Git
records who wrote which code). If you have not used GitHub before, instructions for getting started with git
are available on Canvas and there are many online tutorials. Being well versed with git commands of add,
commit, push and pull will be useful for all upcoming assignments in this class.
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. For each assignment, we’ll require a short written report that summarizes your programming
solutions and that answers specific questions that we pose. Please put the report in the Readme.md file in
your Github repository. For each programming problem, your report should include a brief overview of how
your solution works, including any problems you faced, any assumptions, simplifications, or design decisions
you made, any parts of your solution that you feel are particularly innovative, etc. These comments are your
opportunity for us to better understand your code and the amount of work that you did in writing it; they are
especially important if your code does not work as well as you would like, since it is a chance to document how
much energy and thought you put into your solution. For example, if you tried several different approaches
before finding one that worked, feel free to describe this process so that we can appreciate the work that you
did that might not otherwise be reflected in your final solution.
Academic integrity. We take academic integrity very seriously. To maintain fairness to all students in
the class and integrity of our grading system, we will prosecute any academic integrity violations that we
discover. Before beginning this assignment, make sure you are familiar with the Academic Integrity policy
of the course, as stated in the Syllabus, and ask us about any doubts or questions you may have. To briefly
summarize, you may discuss the assignment with other people at a high level, e.g. discussing general strategies
to solve the problem, talking about Python syntax and features, etc. You may also consult printed and/or
online references, including books, tutorials, etc., but you must cite these materials (e.g. in source code
comments). We expect that you’ll write your own code and not copy anything from anyone else, including
online resources. However, if you do copy something (e.g., a small bit of code that you think is particularly
2
clever), you have to make it explicitly clear which parts were copied and which parts were your own. You can
do this by putting a very detailed comment in your code, marking the line above which the copying began,
and the line below which the copying ended, and a reference to the source. Any code that is not marked in
this way must be your own, which you personally designed and wrote. You may not share written answers
or code with any other students, nor may you possess code written by another student, either in whole or in
part, regardless of format.
Part 1: Navigation
As those of you in the online section learned in Module 1, a certain autonomous agent likes to fly around the
house and interrupt video recordings at the most inopportune moments (Figure 1). Suppose that a house
consists of a grid of N × M cells, represented like this:
....XXX
.XXX...
....X..
.X.X...
.X.X.X.
pX...X@
Figure 1: The autonomous
agent, after a bath.
As you can see, the map consists of N lines (in this case, 6) and M columns
(in this case, 7). Each cell of the house is marked with one of four symbols: p
represents the agent’s current location, X represents a wall through which the
agent cannot pass, . represents open space over which the agent can fly, and @
represents your location (presumably with video recording in progress).
Your goal is to write a program that finds the shortest path between the agent
and you. The agent can move one square at a time in any of the four principal
compass directions, and the program should find the shortest distance between
the two points and then output a string of letters (L, R, D, and U for left, right,
down, and up) indicating that solution. Your program should take a single
command line argument, which is the name of the file containing the map file.
For example:
[<>djcran@silo ~] python3 route_pichu.sh map1.txt
Shhhh... quiet while I navigate!
Here’s the solution I found:
16 UUURRDDDRRUURRDD
You can assume that there is always exactly one p and one @ in the map file. If there is no solution, your
program should display path length -1 and not display a path.
To help get you started, we have provided some initial code that is already available in your GitHub repo.
Here’s what to do to complete the program.
1. We’ve already created a GitHub repository for you for this assignment. You can see the name of your
repository 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 youruserid-a0, (If you do not see cs-b551-fa2021 or a repository with
your userid, it probably means that did not log into GitHub to create your account during the A Few
Action Items activity during week 1 of class, so we were not able to add you to a team. Post a private
message on Q&A Community so that we can create your repo manually.)
3
To get started, from the SICE Linux machines, clone the github repository:
git clone git@github.iu.edu:cs-b551-fa2021/your-repo-name
If that doesn’t work, instead try:
git clone https://github.iu.edu/cs-b551-fa2021/your-repo-name
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.)
2. Now you should see a program called route pichu.py. We have also provided two sample map files,
map1.txt and map2.txt. You can run our program like this:
python3 route_pichu.py map1.txt
Unfortunately, the program does not work very well; it will probably enter an infinite loop and you’ll
have to press CONTROL-C to kill it. Nevertheless, the code is a good starting point, so familiarize
yourself with it. Figure out the precise search abstraction that the program is using and include it in
your report. In other words, what is the set of valid states, the successor function, the cost function,
the goal state definition, and the initial state?
3. Why does the program often fail to find a solution? Implement a fix to make the code work better,
and explain what you did in the report.
4. Complete the program so that it finds and displays the correct solution. Check the starter code
comments for specifications on the search() function, because our autograder (and the pytest command
above in Coding Requirements) calls it directly.
Part 2: Hide-and-seek
Suppose that instead of a single agent as in Part 1, you have adopted k agents. The problem is that these
agents do not like one another, which means that they have to be positioned such that no two agents can
see one another. Write a program called arrange_pichus.py that takes the filename of a map in the same
format as Part 1 as well as a single parameter specifying the number k of agents that you have. You can
assume k ≥ 1. Assume two agents can see each other if they are on either the same row, column, or diagonal
of the map, and there are no walls between them. An agent can only be positioned on empty squares (marked
with .). It’s okay if agents see you, and you obscure the view between agents, as if you were a wall. Your
program should output a new version of the map, but with the agents’ locations marked with p. Note that
exactly one p will already be fixed in the input map file. If there is no solution, your program should just
display False. Here’s an example on the same sample output on the same map as in Part 1:
[<>djcran@silo ~] python3 arrange_pichus.py map1.txt 5
....XXX
.XXXp..
.p..X..
.X.X...
.X.X.Xp
pX.p.X@
We’ve again given you some code to get started with, but it’s not fully working; the configurations it finds
often allow agents to see one another, and it can be quite slow. Fix the code so that it works, and then try
to make it run as quickly as possible. In your report, explain the search abstraction you’ve used – what is
the state space, initial state, goal state, successor function, and cost function?
Make sure to test your program on maps other than the one we’ve given, including ones of different sizes and
shapes. Check the starter code comments for specifications on the solve() function, because our autograder
(and the pytest command above in Coding Requirements) calls it directly.
4
What to turn in
Turn in the two programs on GitHub (remember to add, commit, push) — we’ll grade whatever version
you’ve put there as of 11:59PM on the due date. Also remember to put your report in the Readme.md
file. To make sure that the latest version of your work has been accepted by GitHub, you can log into the
github.iu.edu website and browse the code online.
5