Ordered Words

July 14, 2015

Grep and the system dictionary make word games like this easy:

$ grep "^a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$" words | grep "......."

Aegilops is a genus of Eurasian and North American plants in the grass family. Aren’t you glad you know that?

Pages: 1 2

12 Responses to “Ordered Words”

  1. Rutger said


    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

    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

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

  3. FA said

    @Rutger: you forgot to select the longest

  4. Rutger said


    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      => []
        loop ins before TextIO.closeIn ins
    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)
            loop([], xs, ys)
        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)
            loop(List.rev(ns), [], [])
        val merge' = merge lt
        fun ms []  = []
          | ms [x] = [x]
          | ms xs = let
              val (l, r) = split xs
              merge'(ms l, ms r)
        ms xs
    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)
              if firstTwoCharsOrdered(x)
                 andalso isAlphabetical(x)
                 andalso (size word) > (size longest)
              then (loop xs word)
              else (loop xs longest)
        loop dict ""
  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
  10. Soonseop said
    (import (rnrs)
    (define (not-ordered? word wordlen)
      (let loop ((a (string-ref word 0))
    			 (i 1))
    	(if (= i wordlen)
    		(let ((b (string-ref word i)))
    		  (if (char-ci>? a b)
    			  (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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: