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.
Programming Praxis 
Python.
Added capitals, no requirement there. Otherwise add s.lower() in comparisons.
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)
@Rutger: you forgot to select the longest
Longest:
print sorted([word for word in [‘abc’, ‘cba’, ‘billowy’, ‘deglory’, ‘egilops’, ‘aZ’, ‘Za’] if sorted(word) == list(word)], key=len, reverse=True)[0]
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)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))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 "" endSome solutions in (Guile) Scheme.
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_ putStrLnUsing as input the dictionary on a Mac:
Solution in R7RS Scheme with SRFI 95.
https://notabug.org/PangolinTurtle/praxis-solutions/raw/master/2015-07-14.scm
scheme@(guile-user)> (ordered-words “/usr/share/dict/words”)
$31 = 7
$32 = (“egilops” “billowy” “begorry” “beefily” “alloquy” “Adelops”)
[…] My racket solution to the Ordered Words Problem on Programming Praxis: […]