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
alloquy
beefily
begorry
belloot
billowy
deglory
egilops

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

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
12 Comments »

12 Responses to “Ordered Words”

  1. Rutger said
    July 14, 2015 at 10:27 AM

    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
    July 14, 2015 at 11:07 AM

    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
    July 14, 2015 at 11:09 AM

    @Rutger: you forgot to select the longest

  4. Rutger said
    July 14, 2015 at 11:36 AM

    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
    July 14, 2015 at 2:51 PM

    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
    July 14, 2015 at 5:36 PM 
    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
    July 14, 2015 at 6:32 PM

    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
    July 16, 2015 at 11:09 AM

    Some solutions in (Guile) Scheme.

  9. Globules said
    July 20, 2015 at 1:07 AM

    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
  11. Soonseop said
    July 29, 2015 at 5:32 AM 
    (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”)

  12. Ordered words Problem | cbrachyrhynchos said
    September 13, 2015 at 5:31 PM

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

Leave a comment