Maximising the Number of Friendship Bracelets for the Taylor Swift Concert

◀

By: Alfie Chadwick Date: February 7, 2024 Flower

▶

With Taylor Swift coming to Melbourne next week, my house has started its prep for the concert. An important part of that preparation is making friendship bracelets to trade at the concert. So we headed down to Spotlight and grabbed ourselves a couple of bags of beads to make the bracelets. However, when we opened them up, we found that the distribution of letters was all over the place. We had a heap of useless Zs while also having almost no vowels. Instead of driving back to Spotlight, I decided to see if I could make enough friendship bracelets from the letters we already had, while also being a bit clever about which songs we were going to make friendship bracelets for.

The beads after I spent 15 minutes organinsing them

First Try

I set out to make an algorithm to determine the best set of song titles we could use. I want to assign each song title a cost, and then make the song with the lowest cost the bracelets. I can keep doing this until I can’t make any more bracelets. To determine the cost of a song title, I just summed the costs of its letters. The cost of the letters was the number of occurrences it had in the list of songs divided by the number of beads I had remaining for that letter.

from collections import defaultdict
import re

def count_chars_in_list(list_of_strings):
    char_counts = defaultdict(int)
    
    for string in list_of_strings:
        for char in string:
            char_counts[char] += 1
    
    return dict(char_counts)


def bracelets(song_list, bead_dict):

    # W and M is interchangeable
    cleaned_dict = {
        re.sub(r'\W+', '', i.lower()).replace("w","m"): i 
        for i in song_list
    }

    # dict of letter usage totals
    letter_popularity = count_chars_in_list(cleaned_dict.keys())

    # will run until a break is called
    while True:
        cost_dict = {}
        # Determine the cost of all the songs
        for song in cleaned_dict.keys():
            song_cost = 0
            flag = False
            for char in song: 
                # Assign the cost by adding up beads value
                if char in bead_dict:
                    # If no beads for that letter are left then that word cant be formed
                    if bead_dict[char] == 0:
                        flag = True
                        break
                    else:
                        song_cost += letter_popularity[char]/bead_dict[char]
            if not flag:
                cost_dict[song] = song_cost

        # Finish loop if no more songs can be made
        if len(cost_dict) ==0:
            break
        # Find the cheapest song
        cost_dict_sorted = list(dict(sorted(cost_dict.items(), key=lambda item: item[1])).keys())
        cheapeast_song = cost_dict_sorted[0]
        print(cleaned_dict[cheapeast_song])
        # Remove the cheapest songs beads from the bead counts
        for char in cheapeast_song:
            bead_dict[char] -= 1
bracelets(song_list.copy(), bead_dict.copy())

ivy
ivy
ivy
ivy
ivy
ivy
ivy
ivy
ivy
Run
Slut
ME
Slut
ivy
ME
Run
hoax
Slut
ME
hoax
Glitch
Run
ivy
ME
hoax
Glitch
hoax
ME
Glitch
Karma

This was pretty good, but let’s remove the repeated songs because I don’t want to have 10 bracelets with Ivy on them. We can do this by adding del cleaned_dict[cheapest_song] to the end of the loop.

def bracelets(song_list, bead_dict):
    cleaned_dict = {re.sub(r'\W+', '', i.lower()).replace("w","m"): i for i in song_list}
    letter_popularity = count_chars_in_list(cleaned_dict.keys())

    while True:
        cost_dict = {}
        for song in cleaned_dict.keys():
            song_cost = 0
            flag = False
            for char in song: 
                # Assign the cost by adding up beads value
                if char in bead_dict:
                    if bead_dict[char] == 0:
                        flag = True
                        break
                    else:
                        song_cost += letter_popularity[char]/bead_dict[char]
            if not flag:
                cost_dict[song] = song_cost
        if len(cost_dict) ==0:
            break
        cost_dict_sorted = list(dict(sorted(cost_dict.items(), key=lambda item: item[1])).keys())
        cheapeast_song = cost_dict_sorted[0]
        print(cleaned_dict[cheapeast_song])
        for char in cheapeast_song:
            bead_dict[char] -= 1
        del cleaned_dict[cheapeast_song]


bracelets(song_list.copy(), bead_dict.copy())

ivy
Run
Slut
ME
Glitch
hoax
Mine
willow
Paris
august
Midnights
Red
Mean
Ours
Daylight
Invisible
London Boy

Getting Picky

I presented this list to my housemates only to get the response, ‘I hate ME!’ So, I did some cleaning to remove some of the so-called ‘banned songs’. It also turns out that I’m not allowed to listen to “London Boy” anymore since the guy it is about is canceled or something? Not sure, but now we have a new list that doesn’t include the songs we don’t want.

bannded_songs = [
"Invisible",
"London Boy",
"ME",
'hoax',
'run'
]

bracelets([song for song in song_list if song not in bannded_songs], bead_dict.copy())

ivy
Run
Slut
Glitch
willow
Mine
Paris
august
Mean
Ours
Midnights
Clean
Style
gold rush
Daylight
Long Live

A Final Go

I tried showing this list, which received a better reception, but there were still a couple of non-negotiable songs that needed to be included. We also decided that the Qs and the Os look close enough to be interchangeable, so I changed the way we generate the cleaned dict to reflect that.

def bracelets(song_list, bead_dict):
    cleaned_dict = {re.sub(r'\W+', '', i.lower()).replace("w","m").replace("q",'o'): i for i in song_list}
    letter_popularity = count_chars_in_list(cleaned_dict.keys())

    while True:
        cost_dict = {}
        for song in cleaned_dict.keys():
            song_cost = 0
            flag = False
            for char in song: 
                # Assign the cost by adding up beads value
                if char in bead_dict:
                    if bead_dict[char] == 0:
                        flag = True
                        break
                    else:
                        song_cost += letter_popularity[char]/bead_dict[char]
            if not flag:
                cost_dict[song] = song_cost
        if len(cost_dict) ==0:
            break
        cost_dict_sorted = list(dict(sorted(cost_dict.items(), key=lambda item: item[1])).keys())
        cheapeast_song = cost_dict_sorted[0]
        print(cleaned_dict[cheapeast_song])
        for char in cheapeast_song:
            bead_dict[char] -= 1
        del cleaned_dict[cheapeast_song]

# Move all the Q beads to O
bead_dict['o'] += bead_dict['q']
del bead_dict['q']

required_songs = ['Delicate', 'Lover']
    
for song in required_songs:
    print(song)
    for char in re.sub(r'\W+', '', song.lower()).replace("w","m").replace("q",'o'):
        bead_dict[char] -= 1

bracelets([song for song in song_list if song not in bannded_songs and song not in required_songs], bead_dict.copy())

Delicate
Lover
ivy
willow
Run
Slut
Glitch
Ours
Bad Blood
august
Mine
Paris
Midnights
Long Live
Last Kiss

And there’s a final list of 14 bracelets we can make with our current beads. Would it have been faster to drive back to Spotlight to buy more beads? Probably, but this was more fun.