Activity 07 - The Great City Adventure! 🗺️🚗

CMPSC101 :: Fall 2025 :: Choosing the Best Path and Testing With Python

Assigned: 31 October 2025 Due: 3 November 2025 End of class (Cut off due date and time).

Welcome to Your Mission, Travel Agents!

Congratulations! You've just been hired as junior travel consultants for the world's most exclusive travel agency. Your first assignment? Help a busy client plan the most efficient route through their city to visit all their favorite spots in a single day.

But here's the catch - time is money, and your client wants to minimize their travel time while hitting every location exactly once before returning home. Sound familiar? You're about to tackle one of computer science's most famous puzzles: The Traveling Salesman Problem! 🎯

The Challenge

Your client lives in a bustling city and needs to visit these 5 amazing locations:

• Downtown Library 📚 - Located at coordinates (1, 4)
• Riverside Cafe ☕ - Located at coordinates (3, 1)
• Art Gallery 🎨 - Located at coordinates (5, 3)
• Central Park 🌳 - Located at coordinates (2, 5)
• Tech Store 💻 - Located at coordinates (4, 2)

Their Home 🏠 is at coordinates (0, 0), and they must start and end their journey there.

City Map Visualization 🗺️

Here's what your city looks like on a coordinate grid:

    6 |                                    
      |                                    
    5 |     🌳                           
      |                                    
    4 |  📚                              
      |                                    
    3 |           🎨                      
      |                                    
    2 |        💻                        
      |                                    
    1 |      ☕                          
      |                                    
    0 |🏠                                
      +--+--+--+--+--+--+-- 
        0  1  2  3  4  5  6

Legend:

• 🏠 Home (0, 0)
• 📚 Downtown Library (1, 4)
• ☕ Riverside Cafe (3, 1)
• 🎨 Art Gallery (5, 3)
• 🌳 Central Park (2, 5)
• 💻 Tech Store (4, 2)

Your Mission (Should You Choose to Accept It!)

Part 1: Be a Human Calculator! 🧠

Before touching any code, grab a piece of paper and:

1. Draw a coordinate grid (0-6 on both x and y axes)

2. Plot all the locations including Home at (0,0)

3. Think strategically: What route looks shortest to your eye?

4. Calculate by hand: Pick your best guess route and calculate the total distance using the distance formula:

   distance = √[(x₂-x₁)² + (y₂-y₁)²]
   

5. Record your prediction: Write down your route and total distance!

Part 2: Let Python Do the Heavy Lifting! 💻

Now it's time to see how close your human intuition came to the optimal solution!

Step 1: Update the Code

1. Open src/main.py

2. Replace the existing locations dictionary with your new city locations:

   locations = {
       "Home": (0, 0),
       "Downtown Library": (1, 4),
       "Riverside Cafe": (3, 1),
       "Art Gallery": (5, 3),
       "Central Park": (2, 5),
       "Tech Store": (4, 2)
   }

3. Create your own routes to test! Replace the existing routes with at least 3 different possibilities:

   # Your Route 1 (maybe your hand-calculated guess?)
   route1 = ["Home", "Downtown Library", "Riverside Cafe", 
             "Art Gallery", "Central Park", "Tech Store", "Home"]
   
   # Your Route 2 (try a different strategy!)
   route2 = ["Home", "Tech Store", "Art Gallery", 
             "Riverside Cafe", "Central Park", "Downtown Library", "Home"]
   
   # Your Route 3 (get creative!)
   route3 = ["Home", "Central Park", "Downtown Library", 
             "Tech Store", "Art Gallery", "Riverside Cafe", "Home"]

Step 2: Run and Compare

1. Run your program and see which route wins!
2. Add more routes if you think you can beat the computer's suggestions

What to Think About 🤔

When Planning by Hand:

• Nearest Neighbor Strategy: From each location, what's the closest unvisited spot?
• Visual Clustering: Do some locations form natural groups or clusters?
• Avoid Crossing Paths: Routes that don't cross over themselves are often more efficient
• Geographic Logic: Think like a real person - what makes sense practically?

When Analyzing the Code Results:

• How close was your intuition? Did your hand-calculated route come close to the best computer result?
• Pattern Recognition: What patterns do you notice in the efficient routes?
• Scaling Complexity: With just 5 locations, how many possible routes exist? (Hint: It's (n-1)!/2 for n locations!)

Bonus Challenges 🌟

1. Route Visualization: Can you modify the code to print out the step-by-step journey with distances?
2. Brute Force: How would you test ALL possible routes? (Warning: This gets computationally expensive fast!)
3. Real World: What factors besides distance might matter in real travel planning?

Submission Requirements 📝

Submit:

1. Your hand-drawn map with plotted locations
2. Your hand-calculated best route and total distance
3. Your modified Python code with your custom routes
4. A brief reflection (3-4 sentences) comparing your human intuition vs. the computational results

Fun Facts to Impress Your Friends 🎉

• The Traveling Salesman Problem is NP-hard, meaning there's no known efficient algorithm to solve it perfectly for large numbers of cities!
• For just 10 cities, there are 181,440 possible routes to check
• For 20 cities? Over 60 billion routes! 🤯
• Real-world applications include circuit board drilling, DNA sequencing, and even planning your Netflix binge route through different genres!

Now get out there and show those computers that human intuition can compete with algorithmic precision! Good luck, travel agents! 🚀

---

Remember: The journey of a thousand miles begins with plotting a single coordinate! ✨