Lab10: The Dime-and-Penny Switcheroo Solution

1. Introduction

In this assignment, we use graph traversal to solve an interesting problem from the book "Perplexing Puzzles and Tantalizing Teasers" by Martin Gardner. 

 

 

2. Objectives

The purpose of this assignment is to give you experience e in:

•    Understanding the BFS graph traversal

•    How to use BFS to solve some real world problems.

•    Understanding when to use BFS and when to use DFS.

 

Note: Before you start, if you are not familiar with graph and graph traversal algorithms, it is

recommended you review the corresponding class notes.  

 

3. Background

 

3.1. The Dime-and-Penny Switcheroo

This problem is from book "Perplexing Puzzles and Tantalizing Teasers" by Martin Gardner. This

problem is the 9th problem in the book.

 

The following page displays the cover of the book, and the illustration and description of this problem

from the book.

We will solve this problem using graph traversal. We consider the positions of the 4 coins as one state, which is regarded as a vertex in the graph we try to construct. We use a 5-tuple to represent a state of the coins. For example, the state shown in the previous page is represented as (1, 1, 0, 10, 10). We use 0 to denote that the space at the position is empty.

 

Therefore, the starting vertex is (1, 1, 0, 10, 10) and the end vertex is (10, 10, 0, 1, 1). We need to use BFS to traverse from the starting vertex to the end vertex. We need to use BFS because we want to find the shortest path between these two vertices.

 

 

Before we can traverse this graph, we first need to construct the graph. We first obtain all the vertices for the graph.  We get all the permutations of the 4 coins and an empty space and add all these states as vertices of the graph.

 

We then construct all the edges of the graph. We construct the edges for this graph as follows. We do a nested loop for vertex u and v, and decider whether (u, v) is an edge of the graph. If so, we add this edge to the set of the edges.

 

Once the graph is constructed, we then do the BFS traversal and print out the solution.

 

 

4. Assignment

In the skeleton zip file, you will find a skeleton for your .py file named coins.py. All you need to do is to complete the skeleton code based on the instructions and submit it to the Mimir system. 

 

There are two places you need to fill in your code.

 

4.1. isneighbor(v1, v2)

 

 

Here we need to determine whether vertex v1 and v2 are neighbors based on the rules of two

types of allowed moves. Note the method needs to return a Boolean value.

 

 

 

 

4.1. showresult(self, u, v)

 

 

This method does the BFS starting from vertex u. We use BFS in this case because we’re

interested in finding the shortest path – BFS visits vertices in order of distance so BFS can be

used for the shortest path problem. We check whether the end vertex v is in the BFS tree. If so,

we print out all the vertices traverse. Below is a screenshot of my results. 

 

5. Submit your work to Mimir

Submit your code to Mimir after you complete your code. Mimir will automatically check the output of your code and grade your submission. You can submit your code to Mimir up to 30 times to refresh your existing score before the submission deadline. 

 

 

7. Getting help

Start your project early, because you will probably not be able to get timely help in the last few

hours before the assignment is due.

•    Go to the office hours of instructors and TAs.

o Prof. Wei Wei: Mon. 2:30 - 3:15pm, Wed. 2:30 - 3:15pm, Thurs. 2:30 - 3:15pm, Fri. 2:30 - 3:15pm @ITE258

o Jenny Blessing: Fri. 12pm - 2pm @ITE140

o Param Bidja: Tues. 2pm - 3pm @ITE140

o Yamuna Rajan: Tues. 11am - 12pm, Wed. 9:30am – 10:30am @ITE140

o Zigeng Wang: Mon. 3pm - 4pm @ITE140

•    Post your questions on Piazza. TAs and many of your classmates may answer your

questions. 

•    Search the answer of your unknown questions on the Internet. Many questions asked by

you might have been asked and answered many times online already.