The one about frequency

Weekly Challenge 247

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Secret Santa

Task

Secret Santa is a Christmas tradition in which members of a group are randomly assigned a person to whom they give a gift.

You are given a list of names. Write a script that tries to team persons from different families.

My solution

This one is a lot harder than it seems. Either that or I've massively over engineered my solution. So a few things before I get started:

• Because we don't have anything better to go on, I'm going to assume 'families' are defined by a persons surname.
• I'm also making an assumption that the family name is everything after the last space. In a lot of cultures, the family name occurs first, or is not used at all.
• In New Zealand, Secret Santa is circular (i.e A » B » C » D » E » A). In the given example this is not the case (three pairs give to each other). However, I believe the best solution can be found if we follow the circular model. It's also better so you don't give to the person you get from.

This code is quite detailed, so I'll try and break it down as best I can.

The first thing I do is create a dict (hash in Perl) called family_members. This has a surname as the key and a list (arrayref in Perl) of family members. The get_surname function simply returns everything after the last space (or the whole name if there is no space)

family_members = {}
for p in people:
    surname = get_surname(p)
    if surname not in family_members:
        family_members[surname] = []
    family_members[surname].append(p)

I then have a function called get_person. This takes the family members dict from above, and an optional value of surname not to use. I then sort the dict by the number of people in each family, largest first. It does not matter the order of families with the same number of people in it.

If

1. the exclude value is set, and
2. the first surname is to be excluded, and
3. there is more than one family, and
4. that family still has someone that hasn't received a present

I will chose the second family name in the list. Otherwise, I will return the first family name.

def get_person(family_members, exclude=None):
    sorted_surname = sorted(
        family_members,
        key=lambda i: len(family_members[i]),
        reverse=True
    )

    if exclude and sorted_surname[0] == exclude and len(sorted_surname) > 1 \
            and len(family_members[sorted_surname[1]]) > 0:
        return sorted_surname[1]

    return sorted_surname[0]

The next step is to get the first person to give a present. This is the result of calling the above function. The person is removed from the family_members dict. This is the first value in the chain list, which will record the chain of people (first person gives to second, 2nd person to 3rd, etc)

current_surname = get_person(family_members)
first_person = family_members[current_surname].pop()
chain = [first_person]

I then work through the remaining people calling the get_person function to determine the next person to give a present to. Each call will remove a person from the family_member dict.

for _ in range(len(people)-1):
    next_surname = get_person(family_members, current_surname)
    chain.append(family_members[next_surname].pop())

    # Repeat for the next person
    current_surname = next_surname

Finally, I add the first person to the end of the chain list to represent that the last person gives a gift to the first person, and display the results.

chain.append(chain[0])

for i in range(len(people)):
    print(f'{chain[i]} -> {chain[i+1]}')

And there you have it. The Perl code uses the same logic as the Python code.

Examples

$ ./ch-1.py 'Mr. Wall' 'Mrs. Wall' 'Mr. Anwar' 'Mrs. Anwar' 'Mr. Conway' 'Mr. Cross'
Mrs. Wall -> Mrs. Anwar
Mrs. Anwar -> Mr. Wall
Mr. Wall -> Mr. Anwar
Mr. Anwar -> Mr. Conway
Mr. Conway -> Mr. Cross
Mr. Cross -> Mrs. Wall

$ ./ch-1.py 'Mr. Wall' 'Mrs. Wall' 'Mr. Anwar'
Mrs. Wall -> Mr. Anwar
Mr. Anwar -> Mr. Wall
Mr. Wall -> Mrs. Wall

Task 2: Most Frequent Letter Pair

Task

You are given a string S of lower case letters 'a'..'z'.

Write a script that finds the pair of consecutive letters in S that appears most frequently. If there is more than one such pair, chose the one that is the lexicographically first.

My solution

This is definitely the easier of the two challenges, which is unusual. For this I start with three variables. The variables alphabet has the letters a to z. The solution variable has the current solution (two consecutive letters), while occurrences has the number of times that the pair occurs.

Then its a matter of looping through each pair, and count the occurrences of that string in s. If it is more than the current occurrences value, I update the two values.

for i in range(25):
    letters = alphabet[i:i+2]
    count = s.count(letters)

    if count > occurrences:
        occurrences = count
        solution = letters

The Perl code is a transliteration of Python code.

Examples

$ ./ch-2.py abcdbca
bc

$ ./ch-2.py cdeabeabfcdfabgcd
ab

$ ./ch-2.py acegik
No consecutive letters found!