Ordered words: Difference between revisions
No edit summary |
No edit summary |
||
Line 413: | Line 413: | ||
my @alphawords ; |
my @alphawords ; |
||
while ( my $word = $fh.get( ) ) { |
while ( my $word = $fh.get( ) ) { |
||
say $word ; |
|||
@alphawords.push( $word ) if $word eq $word.split( "" ).sort.join( "" ) ; |
@alphawords.push( $word ) if $word eq $word.split( "" ).sort.join( "" ) ; |
||
} |
} |
Revision as of 11:02, 27 November 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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.
C++
Note: This example is using a different dictionary than that mentioned in the task description. <lang c++>#include <fstream>
- include <iostream>
- include <string>
- include <algorithm>
- include <vector>
- include <iterator>
- 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( ) + 15 ,
sortedWords.end( ) , OrderByLength( ) ) ;
std::copy( sortedWords.begin( ) , sortedWords.begin( ) + 15 ,
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
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
<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>
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:
- fetch dictionary (
dict
) - break into words, one per line (
<;._2 dict-.CR
) - find ordered words (
oWords
) - select the longest ordered words (
(#~ (= >./)@:(#@>))oWords
) - 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 -w use strict ; use warnings ;
open ( FH , "<" , "unixdict.txt" ) or die "Can't open file!\n" ; my @alphawords ; while ( my $word = <FH> ) {
chomp $word ; push ( @alphawords , $word ) if $word eq join( "" , sort split( // , $word ) ) ;
} close FH ; my @sortedwords = sort { length $b <=> length $a || $a cmp $b } @alphawords ; foreach my $i ( 0..14 ) {
print "$sortedwords[ $i ] " ;
} print "\n" ;</lang> Output:
abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy
Perl 6
<lang Perl 6>my $fh = open( "unixdict.txt" , :r ) or die "Can't open file!" ; my @alphawords ; while ( my $word = $fh.get( ) ) {
@alphawords.push( $word ) if $word eq $word.split( "" ).sort.join( "" ) ;
} $fh.close ; my @sortedwords = @alphawords.sort( { $^b.chars <=> $^a.chars || $^a leg $^b } ) ; for 0..14 -> $i {
print "@sortedwords[ $i ] " ;
} say ;</lang> Output:
abbott accent accept access accost almost bellow billow biopsy chilly choosy choppy effort floppy glossy
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
- 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
}
- 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