09-23

Upcoming

  • Next week: Object oriented programming in Python.
  • Tomorrow: Quiz on Python.
  • Soon: searching and backtracking
  • Week 6: graph theory.

Skill of the day

Python’s f-strings give a quick and easy way to create a string. Example:

predator = 'snake'
prey = 'mouse'
print(f'The {predator} ate the {prey}.')

Read Chapter 7. Input and Output in the Python Tutorial.

Maze Explanation

The squares in a maze are numbered 0, 1, 2 …, N. In the maze below, there is a path from zero to eight: 0 - 3 - 6 - 7 - 8. The square 5 does not directly connect to 2 or 8, only to 4.

0 -- 1 -- 2
|    |
3    4 -- 5
|
6 -- 7 -- 8

We will actually represent the maze in text by giving the number of a a vertex followed by all of the vertices with higher numbers that it connects to.

9
0 1 3
1 2 4
2 
3 6
4 5
5 
6 7
7 8
8

Internally, the computer should represent the maze as a dictionary whose keys are integers (the number of the square) and whose values are lists (all of the squares reachable from the key square).

The complete dictionary representing the maze above looks like this:

{ 0: [1,3], 
  1: [0,2,4], 
  2: [1], 
  3: [0,6],
  4: [1,5],
  5: [4],
  6: [3,7],
  7: [6,8],
  8: [7] }

Maze Functions

  1. (readMaze) Input a file containing all of the lines in the maze file (in the format above) and output the maze dictionary.
  2. (strMaze) Input a maze dictionary and output a string containing the lines of the maze file.
  3. (beautifulMaze) Bonus. Input a maze dictionary for a square maze and output a string containing the maze as shown in the first character-drawn maze above.

Problem Solving

USACO 2019 February Bronze 3 (measuring traffic).