## 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)])
```

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)

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 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
```
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: […]