Ordered words

Ordered words
You are encouraged to solve this task according to the task description, using any language you may know.

Define an ordered word as a word in which the letters of the word appear in alphabetic order. Examples include 'abbey' and 'dirt'.

The task is to find and display all the ordered words in this dictionary that have the longest word length. (Examples that access the dictionary file locally assume that you have downloaded this file yourself.)

C++

<lang cpp>#include <fstream>

1. include <iostream>
2. include <string>
3. include <algorithm>
4. include <vector>
5. include <iterator>
6. include <functional>

struct OrderByLength :

  public std::binary_function<std::string, std::string , bool> {
  bool operator( )( const std::string &a , const std::string &b ) const {
     if ( a.length( ) != b.length( ) ) 

return a.length( ) > b.length( ) ;

     else 

return a < b ;

  }

};

int main( ) {

  std::ifstream infile( "unixdict.txt" ) ;
  if ( infile ) {
     std::string word , sorted ;
     std::vector<std::string> sortedWords ;
     getline( infile , word ) ;
     while ( infile ) {

sorted = word ; std::sort( sorted.begin( ) , sorted.end( ) ) ; if ( sorted == word ) { sortedWords.push_back( word ) ; } getline( infile , word ) ;

     }
     infile.close( ) ;
     std::partial_sort( sortedWords.begin( ) , sortedWords.begin( ) + 16 ,

sortedWords.end( ) , OrderByLength( ) ) ;

     std::copy( sortedWords.begin( ) , sortedWords.begin( ) + 16 , 

std::ostream_iterator<std::string>( std::cout , " " ) ) ;

     std::cout << '\n' ;
     return 0 ;
  } 
  else {
     std::cout << "Can't find word file!\n" ;
     return 1 ;
  }

}</lang>

Output

abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy knotty

C#

<lang csharp>using System; using System.Linq; using System.Net;

static class Program {

   static void Main(string[] args)
   {
       WebClient client = new WebClient();
       string text = client.DownloadString("http://www.puzzlers.org/pub/wordlists/unixdict.txt");
       string[] words = text.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);

       var query = from w in words
                   where IsOrderedWord(w)
                   group w by w.Length into ows
                   orderby ows.Key descending
                   select ows;

       Console.WriteLine(string.Join(", ", query.First().ToArray()));
   }

   private static bool IsOrderedWord(string w)
   {
       for (int i = 1; i < w.Length; i++)
           if (w[i] < w[i - 1])
               return false;

       return true;
   }

}</lang>

Output:

abbott, accent, accept, access, accost, almost, bellow, billow, biopsy, chilly, choosy, choppy, effort, floppy, glossy, knotty

D

<lang d>import std.stdio;

void main() {

   string[] words; // longest ordered words

   foreach (w; File("unixdict.txt").byLine())
       if (w == w.dup.sort) {
           if (!words.length || w.length == words[0].length)
               words ~= w.idup;
           else if (w.length > words[0].length)
               words = [w.idup];
       }

   writeln(words);

}</lang>

Output:

[abbott, accent, accept, access, accost, almost, bellow, billow, biopsy, chilly, choosy, choppy, effort, floppy, glossy, knotty]

E

Translation of: Python

<lang e>pragma.enable("accumulator")

def words := <http://www.puzzlers.org/pub/wordlists/unixdict.txt>.getText().split("\n") def ordered := accum [] for word ? (word.sort() <=> word) in words { _.with(word) } def maxLen := accum 0 for word in ordered { _.max(word.size()) } def maxOrderedWords := accum [] for word ? (word.size() <=> maxLen) in ordered { _.with(word) } println(" ".rjoin(maxOrderedWords))</lang>

One-pass procedural algorithm which avoids keeping the entire data set in memory:

<lang e>def best := [].diverge() for `@word$\n` ? (word.sort() <=> word) in <http://www.puzzlers.org/pub/wordlists/unixdict.txt> {

 if (best.size() == 0) {
   best.push(word)
 } else if (word.size() > best[0].size()) {
   best(0) := [word] # replace all
 } else if (word.size() <=> best[0].size()) {
   best.push(word)
 }

} println(" ".rjoin(best.snapshot()))</lang>

Factor

This example is incorrect. Please fix the code and remove this message. Details: The output is not shown.

<lang factor>USING: fry grouping io io.encodings.utf8 io.files kernel math math.order sequences unicode.case ; IN: ordered-words

CONSTANT: dict-file "vocab:ordered-words/unixdict.txt"

word-list ( -- seq )

   dict-file utf8 file-lines ;

ordered-word? ( word -- ? )

   >lower 2 <clumps> [ first2 <= ] all? ;

filter-longest-words ( seq -- seq' )

   dup [ length ] [ max ] map-reduce
   '[ length _ = ] filter ;

main ( -- )

   word-list [ ordered-word? ] filter
   filter-longest-words [ print ] each ;</lang>

Fortran

<lang fortran> !***************************************************************************************

module ordered_module

!***************************************************************************************

implicit none 

!the dictionary file: integer,parameter :: file_unit = 1000 character(len=*),parameter :: filename = 'unixdict.txt'

!maximum number of characters in a word: integer,parameter :: max_chars = 50

type word character(len=max_chars) :: str !the word from the dictionary integer :: n = 0 !length of this word logical :: ordered = .false. !if it is an ordered word end type word

!the dictionary structure: type(word),dimension(:),allocatable :: dict

contains !***************************************************************************************

!****************************************************************************** function count_lines_in_file(fid) result(n_lines) !****************************************************************************** implicit none

integer  :: n_lines integer,intent(in)  :: fid character(len=1)  :: tmp integer  :: i integer  :: ios

!the file is assumed to be open already.

rewind(fid) !rewind to beginning of the file

n_lines = 0 do !read each line until the end of the file. read(fid,'(A1)',iostat=ios) tmp if (ios < 0) exit !End of file n_lines = n_lines + 1 !row counter end do

rewind(fid) !rewind to beginning of the file

!****************************************************************************** end function count_lines_in_file !******************************************************************************

!****************************************************************************** pure elemental function ordered_word(word) result(yn) !****************************************************************************** ! turns true if word is an ordered word, false if it is not. !******************************************************************************

implicit none character(len=*),intent(in) :: word logical :: yn

integer :: i

yn = .true. do i=1,len_trim(word)-1 if (ichar(word(i+1:i+1))<ichar(word(i:i))) then yn = .false. exit end if end do

!****************************************************************************** end function ordered_word !******************************************************************************

!***************************************************************************************

end module ordered_module

!***************************************************************************************

!****************************************************

program main

!****************************************************

use ordered_module
implicit none

integer :: i,n,n_max

!open the dictionary and read in all the words: open(unit=file_unit,file=filename) !open the file n = count_lines_in_file(file_unit) !count lines in the file allocate(dict(n)) !allocate dictionary structure do i=1,n  ! read(file_unit,'(A)') dict(i)%str !each line is a word in the dictionary dict(i)%n = len_trim(dict(i)%str) !save word length end do close(file_unit) !close the file

!use elemental procedure to get ordered words: dict%ordered = ordered_word(dict%str)

!max length of an ordered word: n_max = maxval(dict%n, mask=dict%ordered)

!write the output: do i=1,n if (dict(i)%ordered .and. dict(i)%n==n_max) write(*,'(A,A)',advance='NO') trim(dict(i)%str),' ' end do write(*,*)

!****************************************************

end program main

!**************************************************** </lang>

Output

abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy knotty  

Haskell

<lang haskell> -- Words are read from the standard input. We keep in memory only the current -- set of longest, ordered words. -- -- Limitation: the locale's collation order is not take into consideration.

isOrdered wws@(_:ws) = and $ zipWith (<=) wws ws

keepLongest _ acc [] = acc keepLongest max acc (w:ws) =

 let len = length w in 
 case compare len max of
   LT -> keepLongest max acc ws
   EQ -> keepLongest max (w:acc) ws
   GT -> keepLongest len [w] ws

longestOrderedWords = reverse . keepLongest 0 [] . filter isOrdered

main = do

 str <- getContents
 let ws = longestOrderedWords $ words str
 mapM_ putStrLn ws

</lang>

J

<lang j> require'web/gethttp'

  dict=: gethttp'http://www.puzzlers.org/pub/wordlists/unixdict.txt'
  oWords=: (#~ ] = /:~L:0) <;._2 dict-.CR
  ;:inv (#~ (= >./)@:(#@>))oWords

abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy knotty</lang>

Recap:

1. fetch dictionary (dict)
2. break into words, one per line (<;._2 dict-.CR)
3. find ordered words (oWords)
4. select the longest ordered words ((#~ (= >./)@:(#@>))oWords)
5. format for display (using ;:inv)

JavaScript

Using node.js:

<lang javascript>var fs = require('fs'), print = require('sys').print; fs.readFile('./unixdict.txt', 'ascii', function (err, data) {

   var is_ordered = function(word){return word.split().sort().join() === word;},
       ordered_words = data.split('\n').filter(is_ordered).sort(function(a, b){return a.length - b.length}).reverse(),
       longest = [], curr = len = ordered_words[0].length, lcv = 0;
   while (curr === len){
       longest.push(ordered_words[lcv]);
       curr = ordered_words[++lcv].length;
   };
   print(longest.sort().join(', ') + '\n');

});</lang>

Lua

<lang lua>fp = io.open( "dictionary.txt" )

maxlen = 0 list = {}

for w in fp:lines() do

   ordered = true
   for l = 2, string.len(w) do

if string.byte( w, l-1 ) > string.byte( w, l ) then ordered = false

 	    break

end

   end
   if ordered then

if string.len(w) > maxlen then list = {} list[1] = w maxlen = string.len(w) elseif string.len(w) == maxlen then list[#list+1] = w end

   end

end

for _, w in pairs(list) do

   print( w )

end

fp:close()</lang>

OCaml

<lang ocaml>let input_line_opt ic =

 try Some(input_line ic)
 with End_of_file -> None

(* load each line in a list *) let read_lines ic =

 let rec aux acc =
   match input_line_opt ic with
   | Some line -> aux (line :: acc)
   | None -> (List.rev acc)
 in
 aux []

let char_list_of_string str =

 let lst = ref [] in
 String.iter (fun c -> lst := c :: !lst) str;
 (List.rev !lst)

let is_ordered word =

 let rec aux = function
   | c1::c2::tl ->
       if (Pervasives.compare c1 c2) <= 0
       then aux (c2::tl)
       else false
   | c::[] -> true
   | [] -> true  (* should only occur with an empty string *)
 in
 aux (char_list_of_string word)

let longest_words words =

 let res, _ =
   List.fold_left
     (fun (lst, n) word ->
       let len = String.length word in
       let comp = Pervasives.compare len n in
       match lst, comp with
       | lst, 0 -> ((word::lst), n)  (* len = n *)
       | lst, -1 -> (lst, n)         (* len < n *)
       | _, 1 -> ((word::[]), len)   (* len > n *)
       | _ -> assert false
     )
     ([""], 0) words
 in
 (List.rev res)

let () =

 let ic = open_in "unixdict.txt" in
 let words = read_lines ic in
 let lower_words = List.rev_map String.lowercase words in
 let ordered_words =
   List.fold_left
     (fun acc w ->
       if is_ordered w
       then w::acc
       else acc)
     [] lower_words in
 let longest_ordered_words = longest_words ordered_words in
 List.iter print_endline longest_ordered_words</lang>

$ ocaml ordered_words.ml 
abbott
accent
accept
access
accost
almost
bellow
billow
biopsy
chilly
choosy
choppy
effort
floppy
glossy
knotty

Perl

<lang Perl>#!/usr/bin/perl use strict; use warnings;

open(FH, "<", "unixdict.txt") or die "Can't open file!\n"; my @words; while (<FH>) {

  chomp;
  push @{$words[length]}, $_ if $_ eq join("", sort split(//));

} close FH; print "@{$words[-1]}\n"; </lang> Output:

abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy knotty

Perl 6

<lang Perl 6>my @words; my $maxlen = 0; for slurp("unixdict.txt").lines {

   if .chars >= $maxlen and [le] .comb {
       if .chars > $maxlen {
           @words = ();
           $maxlen = .chars;
       }
       push @words, $_;
   }

} say ~@words;</lang> Output:

abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy knotty

PicoLisp

<lang PicoLisp>(in "unixdict.txt"

  (mapc prinl
     (maxi '((L) (length (car L)))
        (by length group
           (filter '((S) (apply <= S))
              (make (while (line) (link @))) ) ) ) ) )</lang>

Output:

abbott
accent
accept
access
accost
almost
bellow
billow
biopsy
chilly
choosy
choppy
effort
floppy
glossy
knotty

PureBasic

<lang PureBasic>Procedure.s sortLetters(*word.Character, wordLength) ;returns a string with the letters of a word sorted

 Protected Dim letters.c(wordLength)
 Protected *letAdr = @letters()
 
 CopyMemoryString(*word, @*letAdr)
 SortArray(letters(), #PB_Sort_Ascending, 0, wordLength - 1)
 ProcedureReturn PeekS(@letters(), wordLength)

EndProcedure

Structure orderedWord

 word.s
 length.i

EndStructure

Define filename.s = "unixdict.txt", fileNum = 0, word.s

If OpenConsole()

 NewList orderedWords.orderedWord()
 If ReadFile(fileNum, filename)
   While Not Eof(fileNum)
     word = ReadString(fileNum)
     If word = sortLetters(@word, Len(word))
       AddElement(orderedWords())
       orderedWords()\word = word
       orderedWords()\length = Len(word)
     EndIf
   Wend
 EndIf

 SortStructuredList(orderedWords(), #PB_Sort_Ascending, OffsetOf(orderedWord\word), #PB_Sort_String)
 SortStructuredList(orderedWords(), #PB_Sort_Descending, OffsetOf(orderedWord\length), #PB_Sort_integer)
 Define maxLength
 FirstElement(orderedWords())
 maxLength = orderedWords()\length
 ForEach orderedWords()
   If orderedWords()\length = maxLength
     Print(orderedWords()\word + "  ")
   EndIf
 Next 
  
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang> Sample output:

abbott  accent  accept  access  accost  almost  bellow  billow  biopsy  chilly
choosy  choppy  effort  floppy  glossy  knotty

Python

<lang python>import urllib.request

url = 'http://www.puzzlers.org/pub/wordlists/unixdict.txt' words = urllib.request.urlopen(url).read().decode("utf-8").split() ordered = [word for word in words if word==.join(sorted(word))] maxlen = len(max(ordered, key=len)) maxorderedwords = [word for word in ordered if len(word) == maxlen] print(' '.join(maxorderedwords))</lang>

Alternate Solution <lang python>import urllib.request

mx, url = 0, 'http://www.puzzlers.org/pub/wordlists/unixdict.txt'

for word in urllib.request.urlopen(url).read().decode("utf-8").split():

   lenword = len(word)
   if lenword >= mx and word==.join(sorted(word)):
       if lenword > mx:
           words, mx = [], lenword
       words.append(word)

print(' '.join(words))</lang>

Sample Output

abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy knotty

Ruby

<lang ruby> require 'open-uri' ordered_words = open('http://www.puzzlers.org/pub/wordlists/unixdict.txt', 'r').select do |word|

 word.chomp!
 word.split(  ).sort.join == word

end

grouped = ordered_words.group_by{ |word| word.size } puts grouped[grouped.keys.max] </lang>

Tcl

<lang tcl>package require http

1. Pick the ordered words (of maximal length) from a list

proc chooseOrderedWords list {

   set len 0
   foreach word $list {

# Condition to determine whether a word is ordered; are its characters # in sorted order? if {$word eq [join [lsort [split $word ""]] ""]} { if {[string length $word] > $len} { set len [string length $word] set orderedOfMaxLen {} } if {[string length $word] == $len} { lappend orderedOfMaxLen $word } }

   }
   return $orderedOfMaxLen

}

1. Get the dictionary and print the ordered words from it

set t [http::geturl "http://www.puzzlers.org/pub/wordlists/unixdict.txt"] puts [chooseOrderedWords [http::data $t]] http::cleanup $t</lang> Output:

abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy knotty