4 Replies - 982 Views - Last Post: 15 February 2016 - 04:58 PM Rate Topic: -----

#1 andrewsw  Icon User is online

  • lashings of ginger beer
  • member icon

Reputation: 6338
  • View blog
  • Posts: 25,552
  • Joined: 12-December 12

Word contains vowels in order

Posted 13 February 2016 - 10:14 AM

There was a question a few days ago which I thought was interesting, check if a word contains the vowels "aeiou" in order. (For this task we are ignoring the possibility of 'y' being a vowel.)

English words that use all vowels in alphabetical order

I welcome criticism of my approaches below, your alternative version(s), and, particularly, any discussion of the general problem and performance. (Performance obviously isn't a concern with just a single word to check, which will be of limited length, but performance is still a valid discussion.)



As we consider the question, little issues start to occur to us. What about "a..a..e..", can we ignore the second 'a'? What about "a..e..a..i", is this still in order? To continue, lets consider the answer to be 'yes' in both cases.



My first thought was to use a construct like if x < y < z:, mainly just because it is something that is quite specific to Python, not many languages (that I know) allow such a construct.

It was suggested to use index() in the thread. I switched to find() because index() causes a ValueError if the text isn't found, find() returns -1. Some consider catching this error to be a Pythonic approach. I will use this 'catch it' approach for something like checking if a value is numeric, but I prefer not to if there is an acceptable alternative.
word = "facetious".lower()

if "a" in word:
    if word.find('a') < word.find('e') < word.find('i') < word.find('o') < word.find('u'):
        print("whe'hay!")
    else:
        print("doh")
else:
    print("doh")

I only need to check if 'a' would return the value -1, all other searches will then fall in order, numerically.

The condition is extremely specific but, then again, so is the list of vowels.

It is inefficient to search from the beginning of the word each time. Do you have an alternative that doesn't do this?

Here is the same process (the same algorithm) broken down. We just need to remember the previously found location each time, and break when the checking fails.
word = "facetious".lower()

failed, previous = False, None

for vowel in "aeiou":
    posn = word.find(vowel)
    if posn > -1:
        # vowel is found
        if vowel == 'a':
            previous = posn
        elif posn > previous:
            previous = posn
        else:
            failed = True
            break
    else:
        failed = True
        break

print("good") if not failed else print("bad")

Finally, and the version I'm happiest with, it occurred to me to use a stack of the vowels. Removing each vowel (in order) the word succeeds (has the vowels in order) if the stack is empty.

(I've also commented some parts out that indicate that this could be achieved with either an explicit list or just a string "aeiou".)
word = "facetious".lower()

#vowels = list("aeiou")
vowels = "aeiou"

for x in word:
    if x == vowels[0]:
        #vowels.pop(0)
        vowels = vowels[1:]
        if not vowels:
            break       # empty list, job done
    elif x in vowels:
        # a vowel, but out of order
        break   # vowels remains non-empty

print("good") if not vowels else print("bad")

(I did also consider reversing the string, so that it would be more "stack-like".)

This could be considered inefficient in that it does iterate every letter of the word, although it does break out as soon as the check succeeds or fails. However, compare this to the inefficiency of the first version, which starts each search from the beginning of the word.

Is This A Good Question/Topic? 0
  • +

Replies To: Word contains vowels in order

#2 jon.kiparsky  Icon User is online

  • Screw Trump (before he screws you)
  • member icon


Reputation: 10623
  • View blog
  • Posts: 18,179
  • Joined: 19-March 11

Re: Word contains vowels in order

Posted 14 February 2016 - 08:35 PM

I like the standard lisp-style recursive solution:

>>> word = "facetious"
>>> symbols = "aeiou"
>>> def contains_symbols_in_order(word, symbols):
...   if not symbols:
...     return True
...   loc = word.find(symbols[0])
...   if loc < 0:
...     return False
...   return contains_symbols_in_order(word[loc+1:], symbols[1:])
... 
>>> contains_symbols_in_order(word, symbols)
True


Was This Post Helpful? 1
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6966
  • View blog
  • Posts: 14,572
  • Joined: 16-October 07

Re: Word contains vowels in order

Posted 15 February 2016 - 04:23 AM

A functional way to do this would be to filter then check:
>>> def check(x):
...     vowels = "aeiou"
...     good = ''.join(c for c in x.lower() if c in vowels).find(vowels) != -1
...     print(x, " is good") if good else print(x, " is bad")
... 
>>> check("Bob")
Bob  is bad
>>> check("facetious")
facetious  is good
>>> 



I'm guessing the most efficient would be just to use the find and a loop. e.g.
>>> def check(xs):
...     xs, found = xs.lower(), 0
...     for v in "aeiou":
...         found = xs.find(v, found)
...         if found==-1: break
...     print(xs, "is good") if not found==-1 else print(xs, "is bad")
... 
>>> check("facetious")
facetious is good
>>> check("bob")
bob is bad
>>> 


Was This Post Helpful? 1
  • +
  • -

#4 andrewsw  Icon User is online

  • lashings of ginger beer
  • member icon

Reputation: 6338
  • View blog
  • Posts: 25,552
  • Joined: 12-December 12

Re: Word contains vowels in order

Posted 15 February 2016 - 05:15 AM

Cool.

For baavgai's first solution an alternative to find(vowels) != -1 is to compare the string == vowels. I then thought about a set comprehension so that "faceetious" would be considered a pass. So,
    good = ''.join({c for c in x.lower() if c in vowels}) == vowels

Appreciating that sets are unordered it is wrong of me to expect the order "aeiou"; however, it does seem strange that the returned sequence is "aieuo" (on my computer). Even just set("aeiou") produces {'a', 'i', 'e', 'u', 'o'}.

It is tricky to preserve the order yet drop duplicates. I resorted to
from collections import OrderedDict

    good = ''.join(OrderedDict.fromkeys(''.join(c for c in x.lower() if c in vowels))) == vowels


Ugh, messy.

I should think about it a little further ;)

Added: Actually, I'll forget this. It's moving too far away from the original succinct question.
Was This Post Helpful? 0
  • +
  • -

#5 andrewsw  Icon User is online

  • lashings of ginger beer
  • member icon

Reputation: 6338
  • View blog
  • Posts: 25,552
  • Joined: 12-December 12

Re: Word contains vowels in order

Posted 15 February 2016 - 04:58 PM

I suppose I could add one more (simple) version that explicitly ignores the reappearance of a vowel:
def check2(word):
    vowels = "aeiou"
    accumulate = ""
    for lett in word.lower():
        if lett in vowels and lett not in accumulate:
            accumulate += lett
            if len(accumulate) == len(vowels):
                return accumulate == vowels
    return False

print("Checked 2, good") if check2("faceetious") else print("Checked 2, fail")

This isn't neat (or efficient) but it is probably the clearest.

This post has been edited by andrewsw: 15 February 2016 - 05:12 PM
Reason for edit:: removed magic number

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1