VP 22: Lists and Dictionaries (15 pts + 10 extra)

What You Need

Any Python 3 environment, such as Google Colab.

Purpose

To practice lists and dictionaries.

Google Colab

This is the new way to get a Python environment in the cloud, including an AI to help write your code.

In a browser, go to

https://colab.research.google.com/
If you see a blue "Sign In" button at the top right, click it and log into a Google account.

From the menu, click File, "New notebook".

One-Dimensional Lists

Execute this code: 
a = [1, 3, 7, 2, 9, 2]
print("a:", a, type(a))
print("a[0]:", a[0], type(a[0]))
a.sort()
print("After sort, a:", a, type(a))

a.append(99)
a[0] = 100
for i in a:
  print(i, end=" ")
As shown below, note these facts:

Two-Dimensional Lists

You can make a list of lists.

Execute this code: 

a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9]

d = [a, b, c]

print("d:", d, type(d))
print("d[0]:", d[0], type(d[0]))
print("d[0][1]:", d[0][1], type(d[0][1]))
As shown below, note these facts:

Dictionaries

Execute this code: 
a = {1:"apple", 2:"baker", 3:"cat"}
print("a:", a, type(a))
print("a[1]", a[1], type(a[1]))

a[1] = "Alligator"
print("a:", a, type(a))
As shown below, note that dictionaries are mutable:

Searching a List

Execute this code to see how long it takes to search an unordered list: 
import time

passwords = ["123456","password","12345678","qwerty","123456789","12345","1234",
  "111111","1234567","dragon","123123","baseball","abc123","football","monkey",
  "letmein","696969","shadow","master","666666","qwertyuiop","123321","mustang",
  "1234567890","michael","654321","pussy","superman","1qaz2wsx","7777777","fuckyou",
  "121212","000000","qazwsx","123qwe","killer","trustno1","jordan","jennifer",
  "zxcvbnm","asdfgh","hunter","buster","soccer","harley","batman","andrew",
  "tigger","sunshine","iloveyou"]

print("Searching", len(passwords), "passwords")

guess = ""
while (guess != "quit"):
  guess = input("Guess a password: ")
  t0 = time.time()
  if guess in passwords:
    dt = time.time() - t0
    print("Password found in", round(dt, 6), "seconds.")
  else:
    dt = time.time() - t0
    print("Password not found; the search took", round(dt, 6), "seconds.")
Run the program, and enter these guesses, one at a time: 

123456
iloveyou
qqq
quit
As shown below, all these searches are fast, taking only a few microseconds.

Flag VP 22.1: 1000 passwords (5 pts)

This code loads the 1000 passwords from a list on my server: 
!wget https://samsclass.info/COMSC132/proj/10-million-password-list-top-1000.txt
with open('10-million-password-list-top-1000.txt', 'r') as f:
  lines = f.readlines()
passwords = []
for i in range(1000):
  passwords.append(lines[i].strip())

print("There are", len(passwords), "passwords")
print("First:", passwords[0], "Last:", passwords[-1])
Modify the code above to search that list of 1000 passwords.

As shown below, the failed searches take much longer.

The flag is covered by a green rectangle in the image below.

Flag VP 22.2: 1 million passwords (10 pts)

Load the passwords from this file on my server, in the same folder:

10-million-password-list-top-1000000.txt

Perform the same sort of searches. They are much slower.

The flag is covered by a green rectangle in the image below.

Flag VP 22.3: Binary Search (10 pts)

Sort the list. Then code a binary search, which halves the remaining list on each comparison.

Every search is now very fast, as shown below.

The flag is covered by a green rectangle in the image below.

Posted: 8-25-24
Video added 10-9-24