Ordered Vowels

January 31, 2017

Today’s exercise is to write a program that finds all the words in a dictionary in which all the vowels in the word appear in ascending order. It is not necessary that all five vowels appear in the word, and vowels may be doubled. For instance, afoot passes because the three vowels, a, o and o appear in non-decreasing order.

An easy way to solve this problem uses regular expressions:

$ grep '^[^aeiou]*a*[^aeiou]*e*[^aeiou]*i*[^aeiou]*o*[^aeiou]*u*[^aeiou]*$' /etc/dict/words

Since that is so easy, you must write a program that does not use regular expressions.

Your task is to write a program that finds words with ordered vowels. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

5 Responses to “Ordered Vowels”

  1. maximeeuziere said

    Your regex doesn’t seem to handle doubled vowels separated by non-vowels, like, ALBATROS

    so something like that may be more accurate: ‘^([^aeiou]*a)*([^aeiou]*e)*([^aeiou]*i)*([^aeiou]*o)*([^aeiou]u*)*[^aeiou]*$’

    also, in some languages “y” is also a vowel. (not in english?)

  2. Paul said

    In Python.

    from glob import glob
    
    VOWELS = "aeiou"
    WORDLISTFILES = glob('D:/Data/Development/spell/en/english.?')
    WORDLIST = (w.strip().lower() for f in WORDLISTFILES for w in open(f))
    
    def check(word):
        vowels = [c for c in word if c in VOWELS]
        return sorted(vowels) == vowels
    
    print(list(word for word in WORDLIST if check(word)))
    
  3. Jussi Piitulainen said

    A finite-state automaton then, for the Finnish set of vowel characters.

    (define-syntax at
      (syntax-rules ()
        ((at state ((c0 c1 ...) next) ...)
         (define (state rest)
           (or (null? rest)
               (case (car rest)
                 ((c0 c1 ...) (next (cdr rest)))
                 ...
                 (else (state (cdr rest)))))))))
    
    (at a* ((#\e) e*) ((#\i) i*) ((#\o) o*) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at e* ((#\a) no) ((#\i) i*) ((#\o) o*) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at i* ((#\a #\e) no) ((#\o) o*) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at o* ((#\a #\e #\i) no) ((#\u) u*) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at u* ((#\a #\e #\i #\o) no) ((#\y) y*) ((#\ä) ä*) ((#\ö) ö*))
    (at y* ((#\a #\e #\i #\o #\u) no) ((#\ä) ä*) ((#\ö) ö*))
    (at ä* ((#\a #\e #\i #\o #\u #\y) no) ((#\ö) ö*))
    (at ö* ((#\a #\e #\i #\o #\u #\y #\ä) no))
    (define (no rest) #f)
    
    (define (ow<= s) (a* (string->list s)))
    
    ;; Guile stuff
    (use-modules (ice-9 rdelim))
    (set-port-encoding! (current-input-port) "UTF-8")
    (set-port-encoding! (current-output-port) "UTF-8")
    
    (do ((line (read-line) (read-line)))
        ((eof-object? line))
      (if (ow<= (string-downcase line)) (begin (write line) (newline))))
    

    Testing with a 1916 translation of Homer’s Odysseus from Project Gutenberg,
    recall looks about right:

    $ tr -s ' \n\r' '\n' < Documents/pg52108.txt | guile ow.scm | awk 'rand() < .001'
    "taas"
    "yhä"
    "maito."
    "Yö"
    "lahden"
    "hän"
    "vastassani"
    "Kenenkään"
    "ja"
    "ei"
    "eikä"
    "eikö"
    "\"Jalo"
    "ja"
    "\"Tämäpä"
    "mitä"
    "must"
    
  4. Zack said

    An implementation in Julia, from scratch (i.e. no external libraries whatsoever). Using the complete scrabble dictionary (~173K words), it took a little over a second to work out all the words with ascending vowels and store them in a string array. I also added an auxiliary function to retrieve the dictionary words from the text file I’ve put them in. Here is the source code:

    function GetWordsFromDictionary{T <: AbstractString}(fn::T = "D:\\data\\words.txt")
    f = open(fn)
    words = split(readall(f), ",")
    close(f)
    return words
    end

    function ascending(v::Array{Char, 1})
    n = length(v)

    for i = 2:n
    if v[i] < v[i-1]; return false; end
    end

    return true
    end

    function AllVowels{T 0]
    vowels = Array(Char, n)

    for i = 1:n
    vowels[i] = word[ind[i]]
    end

    return vowels
    end

    function vao{T <: AbstractString}(words::Array{T, 1}) # this is the main function
    n = length(words)
    ind = falses(n)

    for i = 1:n
    ind[i] = ascending(AllVowels(words[i]))
    end

    return words[ind]
    end

    Probably not the most elegant solution, but I prefer to keep the code in a modular format so that I can reuse parts of it in other scripts (something quite common in functional languages).

  5. Globules said

    Here’s a Haskell version. You supply an ascending list of vowels as a command-line argument. The function hasOrderedSubsequence works for any type that supports equality, not just characters. I’ve included the output of two runs: one with English vowels (I don’t count ‘y’) on the Mac dictionary, another with Finnish vowels (taken from Jussi’s program) on the same translation of Homer’s Odyssey.

    import Data.Char (toLower)
    import Data.List (elemIndex)
    import Data.List.Ordered (isSorted)
    import Data.Maybe (mapMaybe)
    import System.Environment (getArgs)
    
    -- hasOrderedSubsequence ords xs is True if all elements of xs, that occur in
    -- ords, appear in the same order as in ords.  Otherwise, the value is False.
    hasOrderedSubsequence :: Eq a => [a] -> [a] -> Bool
    hasOrderedSubsequence ords = isSorted . mapMaybe (`elemIndex` ords)
    
    main :: IO ()
    main = do
      let lower = map toLower
      vowels <- concatMap lower <$> getArgs
      interact (unlines . filter (hasOrderedSubsequence vowels . lower) . words)
    
    $ ./ordvowels "aeiou" < /usr/share/dict/words | awk 'rand() < 0.0003'
    anemony
    araban
    bossdom
    brandering
    Canton
    che
    epinicion
    French
    grapelet
    hatmaking
    hough
    lapsing
    miswish
    needments
    racism
    syringitis
    talabon
    toyon
    wrathily
    $ ./ordvowels "aeiouyäö" < ~/Downloads/pg52108.txt | awk 'rand() < 0.001'
    taas
    yhä
    maito.
    Yö
    lahden
    hän
    vastassani
    Kenenkään
    ja
    ei
    eikä
    eikö
    "Jalo
    ja
    "Tämäpä
    mitä
    must
    $ 
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: