3
\$\begingroup\$

I've completed the Reddit challenge #383.

Please find a a summary of the challenge and the test cases below:

Reddit Challenge #383 Necklace Matching

challenge:

In this challenge, we should imagine a necklace with many beads. Each bead has a letter engraved onto it. If you push the letters around the string, you can rearrange the letters.

So 'word' can become 'ordw' or 'dwor' and continue that movement until it turns back into the original word:

'word'

'ordw'

'rdwo'

'dwor'

'word'

The challenge is to detect if the original word can turn into the changed word.

For example: 'letters' can turn into 'ttersle' but can't turn into 'terstle' because the two 't' should be stringed > together.

Here is the test cases for the challenge:

(original, changed) => expected response

("nicole", "icolen") => true

("nicole", "lenico") => true

("nicole", "coneli") => false

("aabaaaaabaab", "aabaabaabaaa") => true

("abc", "cba") => false

("xxyyy", "xxxyy") => false

("xyxxz", "xxyxz") => false

("x", "x") => true

("x", "xx") => false

("x", "") => false

("", "") => true

challenge 2:

Some words such as 'mama' can turn into the original word without looping all the way through the necklace.

'mama'

'amam'

'mama'

'amam'

'mama'

In this challenge, you need to count how many times the original word appears when cycling the necklace. This includes the final form of the necklace. so in 'mama', the word is seen twice while 'read' has the word only appear once.

Here is the test cases for this challenge:

(original) => expected response

("abc") => 1

("abcabcabc") => 3

("abcabcabcx") => 1

("aaaaaa") => 6

("a") => 1

("") => 1

challenge 3:

This challenge involves the enable1 word list found here:https://raw.githubusercontent.com/dolph/dictionary/master/enable1.txt

In this challenge, we need to find the words that form other words when cycled through. The results should be one set of four words. The correct result should be: ['estop', 'pesto', 'stope', 'topes']

Code explanation

In my code I created a class called necklace that manages a necklace. In this case, a necklace is a string with a particular order. This class is used to get the results for challenge 1 and 2. Two external functions exists that are used to solve challenge 3 which uses the necklace class to determine if they are the same necklace.

Please find my code below:

'''
    This modules contains code that solves the Reddit exercise #383
'''
class Necklace():
    '''
        Necklace class
        Create a theoretical string necklace which you can manipulate
    '''
    def __init__(self, word):
        '''
            Sets up the necklace using a word. Stores the word as original. Stores all possible positions.
        '''
        self.original = word
        self.cycles_list = self.get_cycle()

    @staticmethod
    def cycle_left(word):
        '''
            move the word one letter to the left. Example: 'word' => 'ordw'
        '''
        return word[1:]+word[0]

    def get_cycle(self):
        '''
            Get every possible combination of the necklace
        '''
        word = self.original
        cycles = [word]
        i = 0
        while i < len(word):
            word = self.cycle_left(word)
            cycles.append(word)
            i = i + 1
        return cycles

    def is_same_necklace(self, changed_word):
        '''
            Check if the changedWord is the same necklace but in a different position
            returns false if it is another combination of words
        '''
        return changed_word in self.cycles_list

    def count_repeats(self):
        '''
            Counts how many times the original position of the necklace is repeated
            when cycling through all possible positions of the necklace
        '''
        count = self.cycles_list.count(self.original)
        if count > 1:
            return count-1
        return count

    def print_cycle(self):
        '''
            Prints all the possible positions the necklace has
        '''
        print(self.cycles_list)

def get_words_from_file(file_name):
    '''
        Reads all the words from  a specific file
    '''
    file = open(file_name, "r")
    return file.read().split("\n")

def find_similar_words():
    '''
        Get all the words from the enable1.txt file and finds
        all words that are the same necklace
        Returns the first set of words that has four combination but are all the same necklace
    '''
    all_words = get_words_from_file("enable1.txt")
    similar = {}
    words_dict = {}
    for word in all_words:
        if len(word) in words_dict:
            words_dict[len(word)].append(word)
        else:
            words_dict[len(word)] = [word]

    for key in words_dict:
        print('Finding all similar words with a length of '+str(key))
        words = words_dict[key]
        for word in words:
            necklace = Necklace(word)
            index = words.index(word)+1
            for word2 in words[index:]:
                if necklace.is_same_necklace(word2):
                    if word in similar:
                        similar[word].append(word2)
                    else:
                        similar[word] = [word2]

    for key in similar:
        if len(similar[key]) >= 3:
            return [key]+similar[key]
    return None

if __name__ == "__main__":
    #challenge 1 test cases
    print("Challenge 1 Test Cases Results:")
    NECKLACE = Necklace("nicole")
    print(NECKLACE.is_same_necklace("icolen"))
    print(NECKLACE.is_same_necklace("lenico"))
    print(NECKLACE.is_same_necklace("coneli"))
    print(Necklace("aabaaaaabaab").is_same_necklace("aabaabaabaaa"))
    print(Necklace("abc").is_same_necklace("cba"))
    print(Necklace("xxyyy").is_same_necklace("xxxyy"))
    print(Necklace("xyxxz").is_same_necklace("xxyxz"))
    print(Necklace("x").is_same_necklace("x"))
    print(Necklace("x").is_same_necklace("xx"))
    print(Necklace("x").is_same_necklace(""))
    print(Necklace("").is_same_necklace(""))

    #challenge 2 test cases
    print("Challenge 2 Test Cases Results:")
    print(Necklace("abc").count_repeats())
    print(Necklace("abcabcabc").count_repeats())
    print(Necklace("abcabcabcx").count_repeats())
    print(Necklace("aaaaaa").count_repeats())
    print(Necklace("a").count_repeats())
    print(Necklace("").count_repeats())

    #challenge 3 result
    print("Challenge 3 is starting:")
    result = find_similar_words()
    print("Challenge 3 Test Cases Results:")
    print(result)

Things that could be done to improve code quality

  1. Storing the cycles (self.cycles) Not sure if it should have been stored or retrieved when needed. I changed it to store the cycles so it could speed up challenge three however I'm not sure it makes much of a difference.

  2. count_repeats function I tried to use self.cycle.counts however for results with no combination, it came out as '0' instead of '1' however I don't know if there was a better way

  3. find_similar_words function I tried to optimise it as best as I can however it still seems really slow. A lot of redditors put restriction on the word length (>=5) however it should include a search on all words.

\$\endgroup\$
2
\$\begingroup\$
  • Your docstrings are not compliant, they should use """ not '''. You currently have discouraged unless multiline string literals.
  • If you are inheriting from nothing (), then you can just remove the brackets and make your code cleaner.
  • The Necklace class is largely over complicated.
  • The Necklace class is even more redundant when you do self.cycles_list = self.get_cycle().
    This also signals to me that the Necklace is actually performing two jobs, and not the one i would intuitively think.
  • It's un-Pythonic to use while loops when you can easily use a for i in range loop.
  • You can change self.get_cycle() to a simple list comprehension and merge cycle_left into it.
  • To handle the solution_1("", "") is True test case, we can default the range to 1 if the length is 0.
  • is_same_necklace is a really poor name, even more so that a simple in is more readable and better understood. You can allow a class to utilize this operator by defining the __contains__ dunder method.
  • You can simplify the logic of count_repeats by removing the last value.
  • Your tests would better be described as pytest tests.

So far this would get:

def necklace_cycle(beads):
    return [
        beads[i:] + beads[:i]
        for i in range(len(beads) or 1)
    ]


def solution_1(original, changed):
    return changed in necklace_cycle(original)


def solution_2(original):
    return necklace_cycle(original).count(original)


def test_solution_1():
    for original, changed, expected in [
        ("nicole", "icolen", True),
        ("nicole", "lenico", True),
        ("nicole", "coneli", False),
        ("aabaaaaabaab", "aabaabaabaaa", True),
        ("abc", "cba", False),
        ("xxyyy", "xxxyy", False),
        ("xyxxz", "xxyxz", False),
        ("x", "x", True),
        ("x", "xx", False),
        ("x", "", False),
        ("", "", True),
    ]:
        assert solution_1(original, changed) is expected


def test_solution_2():
    for original, expected in [
        ("abc", 1),
        ("abcabcabc", 3),
        ("abcabcabcx", 1),
        ("aaaaaa", 6),
        ("a", 1),
        ("", 1),
    ]:
        assert solution_2(original) == expected
  • You should always wrap open in a with. This is so the file is closed correctly. Currently you're not closing the file, which can lead to problems.
  • You can just use file.read_lines() and strip the newlines.
  • You can use setdefault to set a dictionaries key to a list and then append to that list.

    for word in all_words:
        words_dict.setdefault(len(word), []).append(word)
    
  • Personally I would move this grouping code into its own function. This will allow us to use it twice if we need to.

  • You can use for key, words in words_dict.items(): rather than:

    for key in words_dict:
        words = words_dict[key]
    
  • If you remove the print then you can use for words in words_dict.values(): instead.

  • You can use for index, word in enumerate(words, start=1): rather than:

    for word in words:
        index = words.index(word)+1
    

    Note: These are technically different operations if there are duplicates in words. However enumerate is the solution that you want to use.

  • You can update the similar to be appended to using dict.setdefault.

  • I would change the default to [word] rather than [].
def get_words(file_name):
    with open(file_name) as f:
        return map(str.rstrip, f.readlines())


def grouper(values, transformation):
    output = {}
    for value in values:
        output.setdefault(transformation(value), []).append(value)
    return output


def find_similar_words(words):
    similar = {}
    for grouped_words in grouper(words, len).values():
        for index, word in enumerate(grouped_words, start=1):
            necklace = necklace_cycle(word)
            for word2 in grouped_words[index:]:
                if word2 in necklace:
                    similar.setdefault(word, [word]).append(word2)
    return similar.values()


def solution_3():
    four_words = (
        words
        for words in find_similar_words(get_words("enable1.txt"))
        if len(words) >= 4
    )
    return next(four_words, None)


def test_solution_3():
    assert solution_3() == ["estop", "pesto", "stope", "topes"]

It's much easier to read, and also runs in 5:20 rather than 10:30. This includes the time it takes to run all tests. But since the other tests take 0.05s I'm fine with this. Now we can focus on improving performance.

Anagrams

You should group by anagrams. This is because you're currently checking if four and cats are similar. And I think them not sharing a single character in common might just indicate that they are not.

To do this you can just sort the value and group by that. This makes your \$O(n^2)\$ code perform better because \$n\$ is now much smaller than it was before. This is because \$a^2 + b^2 <= (a + b)^2\$ when a and b are natural numbers - which is what we're working with.

def by_anagram(word):
    return tuple(sorted(word))


def find_similar_words(words):
    similar = {}
    for grouped_words in grouper(words, by_anagram).values():
        ...

This runs in 1.04s rather than 5:20.

Sets

You can further improve the performance and readability of the code by using sets. We know that the updated find_similar_words should return the intersection of the necklace and the grouped words. Since you are already returning duplicates this means we can just use set.intersection. The performance increase from this is likely due to the fact that we're returning early, and so don't consume the entire of the grouper.

def find_similar_words(words):
    for words_ in grouper(words, by_anagram).values():
        words_ = set(words_)
        for word in words_:
            yield words_ & set(necklace_cycle(word))

This runs in 0.62s rather than 1.04s.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ can you explain why if the necklace class is overcomplicated and does two jobs? Isn't a class suppose to be used in multiple ways? Also the while loop was originally a for loop however pylint kicked up a fuss as the 'x' wasn't being used, do i still change it to a for loop? \$\endgroup\$ – Meerfall the dewott Mar 12 at 17:07
  • 1
    \$\begingroup\$ @Meerfallthedewott No a class is meant to have one job and one job only. Yours was building and interacting, very poorly, with a 'necklace'. It was over complicated because of this. Additionally why use a class when three really dumb functions is all you need. Have you read the above code, I use a for loop, and pylint won't complain. \$\endgroup\$ – Peilonrayz Mar 12 at 17:11
  • \$\begingroup\$ I've read your code a bit deeply now, it makes a lot of sense. \$\endgroup\$ – Meerfall the dewott Mar 12 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.