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.

Pages: 1 2

4 Responses to “Rhyming Sort”

  1. chaw said

    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:

    (falsely fly freely sorely surely)
    (freely sorely surely falsely fly)
    

  2. matthew said

    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 caunterbury
    
  3. Steve said

    Klong

            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ú"]
    
    
  4. lisper said

    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)))))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: