Rhyming Sort
December 8, 2020
Here is our solution:
(define (reverse-word str) (list->string (reverse (string->list str)))) (define (rhyming-lt? a b) (string<? (reverse-word a) (reverse-word b))) (define (rhyming-sort words) (sort rhyming-lt? words))
And that’s it, three one-liners that are nearly as simple as the Unix pipeline:
> (rhyming-sort '("falsely" "fly" "freely" "sorely" "surely"))
("freely" "sorely" "surely" "falsely" "fly")
You can run the program at https://ideone.com/4dNypS.
Here is a “one-liner” using standard R7RS Scheme and a couple of well
known helpers that seems very close in spirit to the Unix pipeline
solution. In comparing it to the solution by @programmingpraxis, one
difference is that this one makes only Theta(n) string-reversals
instead of Theta(n log n). Based on some very quick tests on larger
inputs (e.g., /usr/share/dict/words on Debian GNU/Linux), the
difference can be quite significant (10x).
(import (scheme base) (scheme write) (only (srfi 13) string-reverse) (only (srfi 132) list-sort)) (define sample '("falsely" "fly" "freely" "sorely" "surely")) (define (rhyming-sort strs) (map string-reverse (list-sort string<? (map string-reverse strs)))) (display sample) (newline) (display (rhyming-sort sample)) (newline)Output:
We might as well use some actual poetry for our test data, so here is some Chaucer. After sanitizing the text, reverse all words, sort with appropriate collation (to get, for example, ‘vertú’ in the right place – Unicode combining characters might be a problem), and reverse again before final output:
import locale s = """ Whan that Aprille with his shoures soote, The droghte of March hath perced to the roote, And bathed every veyne in swich licóur Of which vertú engendred is the flour; Whan Zephirus eek with his swete breeth Inspired hath in every holt and heeth The tendre croppes, and the yonge sonne Hath in the Ram his halfe cours y-ronne, And smale foweles maken melodye, That slepen al the nyght with open ye, So priketh hem Natúre in hir corages, Thanne longen folk to goon on pilgrimages, And palmeres for to seken straunge strondes, To ferne halwes, kowthe in sondry londes; And specially, from every shires ende Of Engelond, to Caunterbury they wende, The hooly blisful martir for to seke, That hem hath holpen whan that they were seeke. """ locale.setlocale(locale.LC_COLLATE,'en_GB.UTF-8') words = set(w.rstrip(';,.')[-1::-1] for w in s.lower().split()) print(" ".join(s[-1::-1] for s in sorted(words, key=locale.strxfrm))) # perced bathed engendred inspired and engelond ende wende halfe yonge # straunge the kowthe seeke seke smale aprille thanne y-ronne sonne # ferne veyne tendre were natúre swete droghte roote soote ye melodye # of which swich march hath heeth breeth priketh with eek folk al # blisful ram hem from whan longen maken seken slepen holpen open in # on goon so to hir martir for licóur flour londes strondes # pilgrimages corages foweles croppes palmeres shires shoures halwes # is his cours zephirus that nyght holt vertú they specially hooly # sondry every caunterburyKlong
str::["falsely" "fly" "freely" "sorely" "surely"] ["falsely" "fly" "freely" "sorely" "surely"] {|x}'str2@<str2::{|x}'?str ["freely" "sorely" "surely" "falsely" "fly"]Adopting Chaucer’s sample text (Thanks, @matthew), I get the following:
str ["whan" "that" "aprille" "with" "his" "shoures" "soote" "the" "droghte" "of" "march" "hath" "perced" "to" "the" "roote" "and" "bathed" "every" "veyne" "in" "swich" "licóur" "of" "which" "ertú" "engendred" "is" "the" "flour" "whan" "zephirus" "eek" "with" "his" "swete" "breeth" "inspired" "hath" "in" "every" "holt" "and" "heeth" "the" "tendre" "croppes" "and" "the" "yonge" "sonne" "hath" "in" "the" "ram" "his" "halfe" "cours" "y-ronne" "and" "smale" "foweles" "maken" "melodye" "that" "slepen" "al" "the" "nyght" "with" "open" "ye" "So" "priketh" "hem" "natúre" "in" "hir" "corages" "thanne" "longen" "folk" "to" "goon" "on" "pilgrimages" "and" "palmeres" "for" "to" "seken" "straunge" "strondes" "to" "ferne" "halwes" "kowthe" "in" "sondry" "londes" "and" "specially" "from" "every" "shires" "ende" "of" "engelond" "to" "caunterbury" "they" "wende" "the" "hooly" "blisful" "martir" "for" "to" "seke" "that" "hem" "hath" "holpen" "whan" "that" "they" "were" "seeke"] {|x}'str2@<str2::{|x}'?str ["perced" "bathed" "engendred" "inspired" "and" "engelond" "ende" "wende" "halfe" "yonge" "straunge" "the" "kowthe" "seeke" "seke" "smale" "aprille" "thanne" "y-ronne" "sonne" "ferne" "veyne" "tendre" "were" "natúre" "swete" "droghte" "roote" "soote" "ye" "melodye" "of" "which" "swich" "march" "hath" "heeth" "breeth" "priketh" "with" "eek" "folk" "al" "blisful" "ram" "hem" "from" "whan" "longen" "maken" "seken" "slepen" "holpen" "open" "in" "on" "goon" "So" "to" "hir" "martir" "for" "flour" "licóur" "londes" "strondes" "pilgrimages" "corages" "foweles" "croppes" "palmeres" "shires" "shoures" "halwes" "is" "his" "cours" "zephirus" "that" "nyght" "holt" "they" "specially" "hooly" "sondry" "every" "caunterbury" "ertú"]A common lisp solution.
(defun read-file-into-list (file-path) "return an ordered list of strings of each line in file-path" (with-open-file (in file-path) (loop for line = (read-line in nil) while line collect line))) (defun rhyming-sort (data-list) (sort data-list #'(λ (s u) (string-lessp (reverse s) (reverse u)))))