Maximising the Number of Friendship Bracelets for the Taylor Swift Concert

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.

## 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.

# 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

## Delicate
## Lover

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

## 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.