Unordered collections

These problems can be solved with collections in which the order of items doesn’t matter.

Dictionaries

A dictionary is an unordered collection of key-value pairs with unique keys. Dictionaries are useful to map one collection of items to another. Dictionaries allow quick access to a value by key when implemented with hash tables.

Python has a built-in dictionary type. If the keys are integers from a known range, a list may suffice, with the indices being the keys.

1. Relocation (8 LOC): Keep track of companies relocating to a different number on the same street and determine the distance (number of doors) between any two companies.

2. Preludes (15 LOC): Print the alternate name for a musical key, e.g. Gb major -> F# major. The problem description explains all you need to know.

3. Linden Mayor System (9 LOC): A simple simulation of a computational biology system, the L-system. The problem description explains all you need to know. Needs string processing.

4. Metaprogramming (24 LOC): An interpreter for simple integer comparisons. Requires some string processing.

5. False Sense of Security (26 LOC): Decrypt a given text, using Morse code. The problem description explains all you need to know.

Sets

A set is an unordered collection of unique items, i.e. without duplicates. Sets are useful if we need:

• efficient removal and addition of items;
• the items that two or more sets have in common;
• the items that are in one set but not the other.

Python has a built-in set type. If the set has only integers, a list of Booleans may suffice.

1. Booking a Room (5 LOC): Given the capacity of a hotel and the already booked rooms, find an available room.

2. Free Food (6 LOC): Given several ranges of days, how many days are there in total?

3. Quick Brown Fox (8 LOC): Find all English letters that don’t occur in the given text.

4. CD (7 LOC): See the Input and Output section for details.

5. Jolly Jumpers (17 LOC): Given a sequence of integers, do the differences between consecutive integers cover all numbers from 1 to n?

Bags

A bag (or multiset) is an unordered collection with duplicates. Bags are useful when you need to count the frequency of each item. Python’s class collections.Counter provides a bag data type, implemented with a hash table.

1. Hardwood Species (6 LOC): Compute the percentage of each tree species in a forest. Requires sorting.

2. Recount (6 LOC): Check if one candidate has more votes than all the other ones.

3. Peragrams (10 LOC): What is the least number of characters we must remove from a given string to obtain an anagram (i.e. a rearrangement) of a palindrome (a string that is the same forwards and backwards)? No string processing required.

4. Mastering Mastermind (14 LOC): Given the secret code and a guess in a game of Mastermind, report how many letters of the guess are in the correct place and how many are in the wrong place.

5. Zipf’s Law (28 LOC): Find in a text all words that occur exactly a given number of times. Requires string processing.