Ordered Words

July 14, 2015

An ordered word is one in which the letters in the word appear in alphabetic order; for instance, dirt and knotty are ordered words, praxis is not.

Your task is to write a program to find the longest ordered word in a dictionary. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

12 Responses to “Ordered Words”

  1. Rutger said

    Python.

    print([word for word in ['abc', 'cba', 'billowy', 'deglory', 'egilops', 'aZ', 'Za'] if sorted(word) == list(word)])
    

    Added capitals, no requirement there. Otherwise add s.lower() in comparisons.

  2. FA said

    Scala:
    val words = List(“abc”,”cba”, “billowy”, “deglory”, “egilops”, “aZ”, “Za”)
    val orderedWords = words.filter(x=>x.toLowerCase==x.toLowerCase.sorted)
    val longest= orderedWords.map(x => x.size).max
    orderedWords.filter(x=>x.size==longest)

    //> res0: List[String] = List(billowy, deglory, egilops)

  3. FA said

    @Rutger: you forgot to select the longest

  4. Rutger said

    Longest:

    print sorted([word for word in [‘abc’, ‘cba’, ‘billowy’, ‘deglory’, ‘egilops’, ‘aZ’, ‘Za’] if sorted(word) == list(word)], key=len, reverse=True)[0]

  5. Paul said

    Two more solutions in Python. The first is using a trie. Generatting the trie costs much time, but finding the word is superfast.

    def longest_ordered(trie):
        """walk the trie and find the longest ordered word"""
        maxlength, maxword = 0, None
        Q = [(trie[letter], 1, letter) for letter in trie]
        while Q:
            trie, length, word = Q.pop()
            for letter in trie:
                if letter != _end:
                    if letter >= word[-1]:
                        Q.append((trie[letter], length + 1, word + letter))
                elif length > maxlength:
                    maxlength, maxword = length, word
        return maxword
    
    trie = make_trie(*(w.strip().lower() for w in open(fname).readlines()))
    result = longest_ordered(trie)
    
    result = max((w for w in (w.strip().lower() for w in open(fname).readlines())
               if list(w) == sorted(w)), key=len)
    
  6. Mike said
    def isordered(w):
        return all(c1 <= c2 for c1, c2 in zip(w, w[1:]))
    
    with open('/python34/12dicts/5desk.txt', 'rt') as f:
        words = (line.strip().lower() for line in f)
        ordered_words = filter(isordered, words)
        print(max(ordered_words, key=len))
    
  7. mcmillhj said

    According to my sample program, the longest such word in my /usr/share/dict/words file is “Babbitt”.

    fun readFile infile = let
        val ins = TextIO.openIn infile
        fun loop ins =
            case TextIO.inputLine ins of
                SOME line => (List.filter
                                  (fn c => (ord c) <> 10) (explode line)) :: loop ins
             |  NONE      => []
    in
        loop ins before TextIO.closeIn ins
    end
    
    fun mergesort lt xs = let
        fun merge lt (xs, ys) = let
            fun loop(out, [], []) = List.rev out
              | loop(out, x::xs, []) = loop (x::out, xs, [])
              | loop(out, [], y::ys) = loop (y::out, [], ys)
              | loop(out, left as x::xs, right as y::ys) =
                if lt (x, y) then loop (x::out, xs, right)
                else loop (y::out, left, ys)
        in
            loop([], xs, ys)
        end
        fun split ns = let
            fun loop([], xs, ys) = (xs, ys)
              | loop(x::y::zs, xs, ys) = loop(zs, x::xs, y::ys)
              | loop(x::[], xs, ys) = loop([], x::xs, ys)
        in
            loop(List.rev(ns), [], [])
        end
                           
        val merge' = merge lt
        fun ms []  = []
          | ms [x] = [x]
          | ms xs = let
              val (l, r) = split xs
          in
              merge'(ms l, ms r)
          end
    in
        ms xs
    end
                              
    val dict = readFile("/usr/share/dict/words")
    val alphasort = mergesort (Char.<)
    fun isAlphabetical [] = false
      | isAlphabetical xs = (implode (alphasort xs)) = (implode xs)
    fun firstTwoCharsOrdered [] = false
      | firstTwoCharsOrdered (x::[]) = true
      | firstTwoCharsOrdered (x::y::xs) = Char.<= (x, y)
                                                   
    fun longestOrderedWord (dict : char list list) = let
        fun loop [] longest = longest
          | loop (x::xs) longest = let
              val word = (implode x)
          in
              if firstTwoCharsOrdered(x)
                 andalso isAlphabetical(x)
                 andalso (size word) > (size longest)
              then (loop xs word)
              else (loop xs longest)
          end
    
    in
        loop dict ""
    end
    
  8. r. clayton said

    Some solutions in (Guile) Scheme.

  9. Globules said

    A Haskell version. In order to avoid having to retain all the ordered words in
    memory (as would always be the case when sorting by length) I use maxsBy
    to keep only the longest ordered words seen so far. Of course, if all the ordered
    words have the same length we still lose…

    import Data.Char (toLower)
    import Data.List (foldl')
    import Data.Ord (comparing)
    
    -- True iff the list is empty or the elements are in non-decreasing order.
    isOrdered :: Ord a => [a] -> Bool
    isOrdered xs = and $ zipWith (<=) xs (tail xs)
    
    -- Like maximumBy, but giving all maximum elements.
    maxsBy :: (a -> a -> Ordering) -> [a] -> [a]
    maxsBy _    []    = []
    maxsBy cmp (a:as) = snd $ foldl' step (a, [a]) as
      where step (y, ys) x = case cmp x y of
              LT -> (y,   ys)
              EQ -> (x, x:ys)
              GT -> (x,  [x])
    
    -- Longest ordered words.
    lows :: [String] -> [String]
    lows = maxsBy (comparing length) . filter (isOrdered . map toLower)
    
    -- Read from stdin a list of whitespace separated words; write to stdout the
    -- list of longest ordered words.  Ignore case.
    main :: IO ()
    main = fmap (lows . words) getContents >>= mapM_ putStrLn
    

    Using as input the dictionary on a Mac:

    $ ./ordwords < /usr/share/dict/words
    egilops
    billowy
    begorry
    beefily
    alloquy
    Adelops
    
  10. Soonseop said
    (import (rnrs)
    		(prelude))
    
    (define (not-ordered? word wordlen)
      (let loop ((a (string-ref word 0))
    			 (i 1))
    	(if (= i wordlen)
    		#f
    		(let ((b (string-ref word i)))
    		  (if (char-ci>? a b)
    			  #t
    			  (loop b (1+ i)))))))
    
    (define (ordered-words path)
      (call-with-input-file path
    	(lambda (port)
    	  (let loop ((maxlen 0)
    				 (words '())
    				 (word (get-line port)))
    		(if (eof-object? word)
    			(values maxlen words)
    			(let ((wordlen (string-length word)))
    			  (cond ((or (< wordlen maxlen) (not-ordered? word wordlen))
    					 (loop maxlen words (get-line port)))
    					((> wordlen maxlen)
    					 (loop wordlen `(,word) (get-line port)))
    					(else ;; (= wordlen maxlen)
    					 (loop maxlen (cons word words) (get-line port))))))))))
    

    scheme@(guile-user)> (ordered-words “/usr/share/dict/words”)
    $31 = 7
    $32 = (“egilops” “billowy” “begorry” “beefily” “alloquy” “Adelops”)

  11. […] My racket solution to the Ordered Words Problem on Programming Praxis: […]

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: