CSCI 1133, Spring 2022

Lab Exercise 09

Associative Data Structures

This week, we continue our exploration of container classes in Python.  Python dictionaries are mutable structures that provide a powerful association mechanism using key : value pairs.   The Python dictionary structure provides a simple, efficient mechanism that can be used to               implement a number of tasks such as frequency counting.

Warm-up

1).  Word Frequency

The following function is designed to take in a file name and return a dictionary containing each word in the file as a key, and the number of times that word occurs as a value (we’re considering a “word” here to be any consecutive sequence of characters surrounded by whitespace: don’t       worry about things like punctuation or numbers for this problem).  However, due to several         runtime and logic errors, it fails to do that.  Fix the errors so that the function works correctly.      You’re not required to handle the case that the file doesn’t exist.

def word_freq(fname):

fp = open(fname)

for line in fp:

counts = {}

words = line.split()

for word in words:

counts[word] = 1

fp.close()

return counts

Example: Suppose you saved the following file as sample.txt:

here are some words

this line has more words

words are words on this line

>>> word_freq('sample.txt')

{'here': 1, 'are': 2, 'some': 1, 'words': 4, 'this': 2, 'line': 2,

'has': 1, 'more': 1, 'on': 1}

Stretch

Remember that while it’s a good idea to have one person primarily responsible for typing (the driver) and the other reviewing each line of code and making suggestions (the navigator) you  must switch roles after every problem.

1).  Morse Code

Write a Python program that will allow a user to type in a message and convert it into Morse    code. Your program must use a dictionary to represent and implement the code.  The letters in Morse code are encoded as follows (since the encoding will use spaces between each letter, an actual space in the message gets encoded as special character / not normally present in Morse

code) :

You may copy and paste the dictionary below.

morse_dictionary={'A': '.-', 'B': '-...', 'C': '-.-.',

'D': '-..', 'E': '.', 'F': '..-.', 'G': '--.', 'H': '....',

'I': '..', 'J': '.---', 'K': '-.-', 'L': '.-..', 'M': '--',

'N': '-.', 'O': '---', 'P': '.--.', 'Q': '--.-', 'R': '.-.',

'S': '...', 'T': '-', 'U': '..-', 'V': '...-', 'W': '.--',

'X': '-..-', 'Y': '-.--', 'Z': '--..', ' ': '/'}

Example:

Enter a message: My TAs are amazing

-- -.-- / - .- ... / .- .-. . / .- -- .- --.. .. -. --.

Notice that the message is not case-sensitive. You can assume that no characters other than the  options specified above will be input. You may want to make a function for this, but you’re not required to do so.

Workout

Suppose we’re interested in the cost of flying from one location to another. We can represent the cost of air travel by drawing lines representing flights between two cities, with the cost ofthat      flight as a label for each line.  Those ofyou who have taken a course on Discrete Math may         recognize this structure as a graph. Notice that it is not always the case that the cheapest way to  get from one city to another is with a direct flight: for example, to get from Chicago to Dallas, it  costs $105 for a direct flight, but $56 + $44 = $100 if we fly through Las Vegas on the way.

One way we can represent this graph is as a dictionary of dictionaries: the outer dictionary has     keys containing all of the possible origin points, and each value is a dictionary containing all        possible destinations from that origin as keys, and the cost ofthe corresponding flight as a value. For example, the above graph would be represented as:

costs = {'Philadelphia':{'Chicago':227, 'Dallas':289},

'Chicago':{'Philadelphia':227, 'Dallas':105, 'Las Vegas':56},

'Dallas':{'Philadelphia':289, 'Houston':173, 'Chicago':105,

'Las Vegas':44, 'San Diego':303},

'Houston':{'Dallas':173},

'Las Vegas':{'Chicago':56, 'Dallas':44, 'San Diego':74,

'Los Angeles':44, 'San Francisco':56},

'Los Angeles':{'Las Vegas':44, 'San Diego':157,

'San Francisco':111},

'San Diego':{'Las Vegas':44, 'Los Angeles':157, 'Dallas':303},

'San Francisco':{'Las Vegas':56, 'Los Angeles':111}}

1).  Chicago to Dallas

In order to compare the different possible ways to get from Chicago to Dallas, we’d need to      access the elements in the nested dictionary.  Below shows the wrong way to compute the total cost ofgoing from Chicago to Dallas through Las Vegas:

total = costs['Chicago'['Las Vegas']] + costs['Las Vegas'['Dallas']] Correct the errors in the statement above. You should get 100 as your value for total.

2).  One Stop Maximum

Write a function cheapest(costs, origin, destination) that takes in a costs dictionary as shown above, an origin city, and a destination city, and returns the cheapest price to get from    the origin to the destination. You can assume that there will be at most one intermediate stop        along the way.  For example, to get from Chicago to Dallas, you have to consider the following    three options:

Chicago -> Dallas ($105)

Chicago -> Las Vegas -> Dallas ($56 + $44 = $100)

Chicago -> Philadelphia -> Dallas  ($227 + $289 = $516)

But you don’t have to consider something like Chicago -> Las Vegas -> San Diego -> Dallas,     since that’s more than one intermediate stop.  Ifthere is no possible path from the origin to the    destination within one intermediate stop, return infinity (you can use float('inf') to get this value in Python).

Hints:

●   You’ll need to loop through each potential intermediate stop (that is, every key in the inner dictionary associated with the origin), and then look into the inner dictionary     associated with the intermediate stop to see if there’s a flight from there to the            destination.

●   This problem is tricky: talk over how you’d solve it manually first with your partner     before starting to code, and be sure to put print statements in your loops so you can see what’s going on.

Examples (assumes that you have the costs dictionary from earlier defined in the global scope) >>> cheapest(costs, 'San Francisco', 'Philadelphia')

inf

>>> cheapest(costs, 'Chicago', 'Dallas')

100

>>> cheapest(costs, 'Las Vegas', 'Los Angeles')

44

>>> cheapest(costs, 'Philadelphia', 'Las Vegas')

283

Challenge

1).  Playing Cards

Many games involve the use of "playing cards" drawn from a deck of 52 individual cards.  Each card in the deck has a unique combination of value (or rank) and suit.  The rank of each card is   taken from the set: { 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace } and the suit is one of: {    Clubs, Spades, Diamonds, Hearts }.

Construct a function named rank_suit_count(cards) that will take a list of strings               representing a collection of playing cards (a "hand" perhaps), and returns a list of two Python   dictionaries with the frequency count of each unique card rank and suit (respectively) in the list of cards.  See below for examples.

Your dictionary should not include ranks and suits not present in the list.  Individual cards are represented by a 2-character string.  The first character represents the card rank:

'2' - '9' ==>  2 - 9

'T' 'J'  'Q' 'K'

'A'

==>  10

==>  Jack

==>  Queen

==>  King

==> Ace

and the second character represents the suit:

'C' 'S' 'D'

'H'

==>  Clubs

==>  Spades

==>  Diamonds

==>  Hearts

For example, a hand with the ace of spades, the ace of diamonds, the 2 of clubs, the 10 of hearts and the 10 of spades would be represented as:

[ 'AS', 'AD', '2C', 'TH', 'TS' ]

And the result of rank_suit_count() on this list of cards would look like this:

>>> rank_suit_count(['AS','AD','2C','TH','TS'])

[{'A':2, '2':1, 'T':2}, {'S':2, 'D':1, 'C':1, 'H':1}]

Here is another example with the eight, nine, ten, jack, and queen of diamonds, utilizing tuple  assignment to separate out the result into the rank and suit dictionaries:

>>> rank, suit

>>> rank

{'8':1, '9':1,

>>> suit

{'D':5}

= rank_suit_count(['8D','9D','TD','JD','QD'])

'T':1, 'J':1, 'Q':1}

If you have completed part 1 of the challenge, you can get checked off and leave early, or stay and try to complete part 2.

2).  Poker Hands

Most variants of the card game Poker are played by ranking the various types of hands that can occur with 5 cards:

straight flush: all cards in rank sequence, same suit  (e.g.,  ['8D', '9D', 'TD', 'JD', 'QD']) four-of-a-kind: 4 cards of the same rank                    (e.g.,  ['5C', '5S', '5D', '5H', '9C'])   full-house:  3 cards of one rank and 2 of another       (e.g.,  ['6H', '6S', '6C', 'QD', 'QH'])

flush :  all cards of same suit, not in sequence           (e.g.,  ['3H', '6H', 'TH', 'JH', 'AH'])

straight:  all cards in rank sequence, not same suit    (e.g.,  ['2S', '3D', '4H', '5H', '6S']) three-of-a-kind:  3 cards of the same rank                 (e.g.,  ['2C', '2H', '2D', '7S', '3D'])

two pair:  2 pairs of matching rank cards                   (e.g.,  ['AH', 'AD', 'QS', 'QH', '2C'])

one pair:  1 pair of matching rank cards                     (e.g.,  ['8S', '8C', '9D', '3S', 'TH'])  high-card: no matching rank cards                             (e.g.,  ['4H', '7D', 'KS', 'AS', '9C'])

You can see more examples of this here: https://en.wikipedia.org/wiki/List_of_poker_hands

The value of any particular poker hand is inversely proportional to its probability of occurrence when 5 cards are dealt randomly from a 52-card deck.  The highest ranked poker hand is a         ‘straight flush’, and the lowest ranked is a ‘high-card’.  If more than one ofthe above hand        categories applies to a given hand, the highest one is always chosen (so ['8D', '9D', 'TD', 'JD',     'QD'] is counted as a straight flush, even though it could also count as a flush, a straight, or a     high-card).