Sparse Array Demo

Write a program sparse_array_demo.py that demonstrates a dictionary-based implementation of a random walker.

For this problem, a random walker begins in the middle of a 60 wide by 40 tall grid of locations, and takes a series of random steps in the North, South, East, or West direction. The walker takes 5000 steps, and a record is kept at each location of how many times the walker has landed on that spot.

Here's a working version of a "list of lists" program that does just that:

#!/usr/bin/env python3
"""
random_walker.py
Establishes a 60 x 40 array of values and tracks a random walker's
steps for each point on that grid.
"""

import random
import time

def display(grid):
    """Used to display the walker's current progress on screen"""
    print("\033[H\033[2J")          # clears the terminal window
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] != 0:
                print("{0:2d}".format(grid[row][col]),end='')
            else:
                print("{0:2s}".format(""),end='')
        print()
    print()
    time.sleep(0.05)

def main():
    WIDTH = 60
    HEIGHT = 40
    
    # initialize walker at middle of screen
    walker_x = WIDTH // 2
    walker_y = HEIGHT // 2
    
    # initialize grid, a 2-D "list of lists", 40 rows by 60 cols
    grid = []
    for row in range(HEIGHT):
        grid.append([])
        for col in range(WIDTH):
            grid[row].append(0)
    grid[walker_y][walker_x] = 1
    
    # start walking!
    for i in range(5000):
        walker_x = (walker_x + random.randrange(-1, 2)) % WIDTH    # % makes it wrap
        walker_y = (walker_y + random.randrange(-1, 2)) % HEIGHT   # % makes it wrap
        grid[walker_y][walker_x] += 1
        display(grid)   # take this display call out of the loop if you just
                        # want to see the final result


if __name__ == "__main__":
    main()

For this problem, convert the "list of lists" data structure to a dictionary of key-value pairs. Rather than incrementing the value stored in grid[row][col] you'll be creating a dictionary entry for each location on the abstract grid when the walker first arrives. The key for each entry is a tuple representing the row, col for a point in space, and the value is how many steps have been taken there.

grid[ row, col ] = 1

Every time the walker takes a step, we'll either increment that entry if the walker has already been there:

if (row, col) in grid.keys():
    grid[ row, col ] += 1

or if the walker hasn't been there before, we'll create a new entry in the dictionary.

You'll need to rewrite the display() function as well so that a map of the random walker's travel can be printed.

Questions

What is a sparse array?
Is the random walker's 2-D array an example of a sparse array?
What are the advantages of a sparse array over a dictionary?
What are the disadvantages?