CODEWITHSUNDEEP
python
user3422146
user3422146

Reputation: 57

Python - Determine if a word is in this language or not

I'm having trouble solving this homework question. If anyone can just give me any tips or something to start off with, that would be great! Thanks in advance!

Bob and Joe decide to create a new language. The words in their language only consist of the letters A, B, and C. The first words they invent are AB and C. Then they decide that all the other words are of the form AuB or vCw where u, v and w are all previously invented words. (Note that v and w might be the same word.) Write a function in_language that consumes a string s and produces True if s is in the language and False otherwise.

Examples:

in_language('C') => True
in_language('AB') => True
in_language('ACB') => True
in_language('ABCAB') => True
in_language('ACBCABCAB') => True

in_language('') => False (empty string with length 0)
in_language('A') => False
in_language('A^BD%AB') => False
in_language('BCA') => False
in_language('ACBACB') => False

Upvotes: 3

Views: 220

Answers (1)

Samy Arous
Samy Arous

Reputation: 6814

This is a simple recursion algorithm:

  1. if a word is empty, return False
  2. if a word is AB or C return True
  3. if a word begins with A and ends with B, return True if the inner part is a valid word (recursion)
  4. Else for each letter C in the word, return True if the left part and right part are both a valid word (recursion)
  5. if none of the above is true, return false

Here's an implementation as asked by SwankyLegg

def in_language(word):
    if word in ('AB', 'C'):
        return True
    if len(word) < 3: #The only valid words with 2 or less letters are AB and C
        return False
    if word[0] == 'A' and word[-1] == 'B' and in_language(word[1:-1]):
        return True
    else:
        for i, letter in enumerate(word):
            if letter == 'C' and in_language(word[:i]) and in_language(word[i+1:]):
                return True
    return False

Upvotes: 4

Related Questions