11
\$\begingroup\$

Rotonyms 2

A "Rotonym" is a word that ROT13s into another word (in the same language).

For this challenge, we'll use an alternate definition: a "Rotonym" is a word that circular shifts/rotates into another word (in the same language).

For example:

'stable' < 'tables' < 'ablest'
'abort' > 'tabor'
'tada' >> 'data'

The Challenge

Write a program or function that accepts a dictionary/word list and prints or returns a complete list of rotonyms.

  1. Order doesn't matter.
  2. Comparisons should be case-insensitive, so you can assume the input will be passed as a lower-case-only dictionary.
  3. Result should be expressed as single words (not the pairs) and contain no duplicates, so you can assume the input has no duplicates.
  4. This is .

Example

Given

ablest
abort
green
irk
stable
tables
tabor
tata
terra
vex
you

Return

ablest
abort
stable
tables
tabor

A Real Test

Given

a aa aal aalii aam aani aardvark aardwolf aaron aaronic aaronical aaronite aaronitic aaru ab aba ababdeh ababua abac abaca abacate abacay abacinate abacination abaciscus abacist aback abactinal abactinally abaction abactor abaculus abacus abadite abaff abaft abaisance abaiser abaissed abalienate abalienation abalone abama abampere abandon abandonable abandoned abandonedly abandonee abandoner abandonment abanic abantes abaptiston abarambo abaris abarthrosis abarticular abarticulation abas abase abased abasedly abasedness abasement abaser abasgi abash abashed abashedly abashedness abashless abashlessly abashment abasia abasic abask abassin abastardize abatable abate abatement abater abatis abatised abaton abator abattoir abatua abature abave abaxial abaxile abaze abb abba abbacomes abbacy abbadide abbas abbasi abbassi abbasside abbatial abbatical abbess abbey abbeystede abbie abbot abbotcy abbotnullius abbotship abbreviate abbreviately abbreviation abbreviator abbreviatory abbreviature abby abcoulomb abdal abdat abderian abderite abdest abdicable abdicant abdicate abdication abdicative abdicator abdiel abditive abditory abdomen abdominal abdominales abdominalian abdominally abdominoanterior abdominocardiac abdominocentesis abdominocystic abdominogenital abdominohysterectomy abdominohysterotomy abdominoposterior abdominoscope abdominoscopy abdominothoracic abdominous abdominovaginal abdominovesical abduce abducens abducent abduct abduction abductor abe abeam abear abearance abecedarian abecedarium abecedary abed abeigh abel abele abelia abelian abelicea abelite abelmoschus abelmosk abelonian abeltree abencerrages abenteric abepithymia aberdeen aberdevine aberdonian aberia aberrance aberrancy aberrant aberrate aberration aberrational aberrator aberrometer aberroscope aberuncator abet abetment ablest abort abut ach ache acher achete achill achor acor acre acyl ad adad adat add addlings adet ala ama baa bafta balonea batea beta caba cha chilla cora crea da dad dada data each lacy orach rache saddling stable tables tabor tabu tade teache zoquean zoraptera zorgite zoril zorilla zorillinae zorillo zoroastrian zoroastrianism zoroastrism zorotypus zorrillo zorro zosma zoster zostera zosteraceae zosteriform zosteropinae zosterops zouave zounds zowie zoysia zubeneschamali zuccarino zucchetto zucchini zudda zugtierlast zugtierlaster zuisin zuleika zulhijjah zulinde zulkadah zulu zuludom zuluize zumatic zumbooruk zuni zunian zunyite zupanate zutugil zuurveldt zuza zwanziger zwieback zwinglian zwinglianism zwinglianist zwitter zwitterion zwitterionic zyga zygadenine zygadenus zygaena zygaenid zygaenidae zygal zygantra zygantrum zygapophyseal zygapophysis zygion zygite zygnema zygnemaceae zygnemales zygnemataceae zygnemataceous zygnematales zygobranch zygobranchia zygobranchiata zygobranchiate zygocactus zygodactyl zygodactylae zygodactyli zygodactylic zygodactylism zygodactylous zygodont zygolabialis zygoma zygomata zygomatic zygomaticoauricular zygomaticoauricularis zygomaticofacial zygomaticofrontal zygomaticomaxillary zygomaticoorbital zygomaticosphenoid zygomaticotemporal zygomaticum zygomaticus zygomaxillare zygomaxillary zygomorphic zygomorphism zygomorphous zygomycete zygomycetes zygomycetous zygon zygoneure zygophore zygophoric zygophyceae zygophyceous zygophyllaceae zygophyllaceous zygophyllum zygophyte zygopleural zygoptera zygopteraceae zygopteran zygopterid zygopterides zygopteris zygopteron zygopterous zygosaccharomyces zygose zygosis zygosperm zygosphenal zygosphene zygosphere zygosporange zygosporangium zygospore zygosporic zygosporophore zygostyle zygotactic zygotaxis zygote zygotene zygotic zygotoblast zygotoid zygotomere zygous zygozoospore zymase zyme zymic zymin zymite zymogen zymogene zymogenesis zymogenic zymogenous zymoid zymologic zymological zymologist zymology zymolyis zymolysis zymolytic zymome zymometer zymomin zymophore zymophoric zymophosphate zymophyte zymoplastic zymoscope zymosimeter zymosis zymosterol zymosthenic zymotechnic zymotechnical zymotechnics zymotechny zymotic zymotically zymotize zymotoxic zymurgy zyrenian zyrian zyryan zythem zythia zythum zyzomys zyzzogeton

Return

aal aam aba abac abaft abalone abate abet ablest abort abut ach ache acher achete achill achor acor acre acyl ad adad adat add addlings adet ala ama baa bafta balonea batea beta caba cha chilla cora crea da dad dada data each lacy orach rache saddling stable tables tabor tabu tade teache
\$\endgroup\$
  • \$\begingroup\$ can we assume input words are unique? \$\endgroup\$ – ngn May 29 '18 at 19:04
  • \$\begingroup\$ Yes, I think I pre-ran my input through a unique filter when I ran the system dictionary. \$\endgroup\$ – Umbrella May 29 '18 at 19:10
  • \$\begingroup\$ I noticed some answers worked for the example, but not for a full dictionary. I added a larger test set that is a subset of the dictionary large enough to contain words that fail for some answers that pass the trivial example. \$\endgroup\$ – Umbrella May 30 '18 at 14:50
  • \$\begingroup\$ @Umbrella you should comment on any invalid answers to alert the user, so that they can fix/delete their answer \$\endgroup\$ – H.PWiz May 30 '18 at 14:58
  • \$\begingroup\$ abdominovaginal, you got some odd words there. \$\endgroup\$ – Magic Octopus Urn May 31 '18 at 23:18

17 Answers 17

5
\$\begingroup\$

Jelly, 8 bytes

ṙ1$ƬfḊɗƇ

Try it online!

Alternate version, 7 bytes

ṙƬ1fḊʋƇ

Dyadic Ƭ used to do something weird, so this didn't work when the challenge was posted.

Try it online!

How it works

ṙƬ1fḊʋƇ  Main link. Argument: A (array of strings)

     ʋ   Vier; combine the 4 preceding links into a dyadic chain.
      Ƈ  Comb; for each string s in A, call the chain with left argument s and
         right argument A. Keep s iff the chain returned a truthy value.
 Ƭ           'Til; keep calling the link to the left, until the results are no
             longer unique. Return the array of unique results.
ṙ 1          Rotate the previous result (initially s) one unit to the left.
   f         Filter; keep only rotations that belong to A.
             s is a rotonym iff there are at least two rotations of s in A.
    Ḋ        Deque; remove the first string (s) of the result.
             The resulting array is non-empty / truthy iff s is a rotonym.
\$\endgroup\$
  • \$\begingroup\$ Oh new quick characters? Hm gotta learn when to use those now... (same things but 1-byters now so I can use them more than back when they were 2-byters) \$\endgroup\$ – HyperNeutrino May 29 '18 at 16:10
  • \$\begingroup\$ It's equivalent to ṙ1$ÐĿfḊɗÐf. \$\endgroup\$ – Dennis May 29 '18 at 16:13
4
\$\begingroup\$

APL (Dyalog), 20 bytes

Requires ⎕io←0

⊂∩¨(,/(1↓∘∪⍳∘≢⌽¨⊂)¨)

Try it online!

(1↓∘∪⍳∘≢⌽¨⊂)¨ gets the unique rotations (excluding the string itself) of each string in the dictionary

takes the length of a vector

⍳∘≢ creates the range from 0 up to the length

rotates a vector some number of times, e.g 2⌽'abort' -> 'ortab'

⍳∘≢⌽¨⊂ will then give all the rotations of a vector

removes the duplicates

1↓ removes the first element (the original string)

,/ flattens all the rotations into one list

⊂∩¨ takes the intersection of the dictionary with the rotations

\$\endgroup\$
  • \$\begingroup\$ your result comes out enclosed, but I guess that should be okay, and @Adám can steal your ⊂∩¨ trick (or vice versa) for a further -1 \$\endgroup\$ – ngn May 29 '18 at 20:31
4
\$\begingroup\$

APL (Dyalog Unicode), 25 23 22 17 16 bytesSBCS

Borrows ideas from ngn's ngn/k solution. And then -6 thanks to him. Also -1 by returning an enclosed list as like H.PWiz.

Anonymous tacit prefix function.

⊂∩¨1,.↓(∪≢,/,⍨)¨

Try it online!

( apply the following tacit function to each word:

,⍨ concatenate the word to itself

≢,/ all word-length sub-strings (i.e. all rotations)

 unique elements of those rotations (to prevent words like tata for appearing twice)

1,.↓ the concatenation of the drop-firsts (the original words) of each list

⊂∩¨ intersection of the the content of that and the entire original word list


Old solution

-2 thanks to ngn.

Anonymous prefix lambda.

{⍵/⍨2≤+/⍵∊⍨↑(∪≢,/,⍨)¨⍵}

Try it online!

{} function where is the word list:

( apply the following tacit function to each word:

  ,⍨ concatenate the word to itself

  ≢,/ all word-length sub-strings (i.e. all rotations)

   unique elements of those rotations (to prevent words like tata for appearing twice)

 mix the list of lists into a single matrix (pads with all-space strings)

⍵∊⍨ indicate which elements of the matrix are members of the original list

+/ sum the rows (counts occurrences of each of the original words)

2≤ indicate which have duplicates (i.e. occur other than when rotated back to original)

⍵/⍨ use that to filter the original list

\$\endgroup\$
  • \$\begingroup\$ {∪⌽∘⍵¨⍳≢⍵} -> (∪≢,/,⍨); your use of is clever \$\endgroup\$ – ngn May 29 '18 at 18:32
  • \$\begingroup\$ @ngn Thanks. I learned the trick from Morten. \$\endgroup\$ – Adám May 29 '18 at 19:15
  • \$\begingroup\$ those trains make my brain hurt... it's simpler as a dfn: {⍵∩⊃,/1↓¨(∪≢,/,⍨)¨⍵} \$\endgroup\$ – ngn May 29 '18 at 20:13
  • \$\begingroup\$ @ngn That's what I have although made into a train and without the trick for rotations \$\endgroup\$ – H.PWiz May 29 '18 at 20:18
  • 1
    \$\begingroup\$ sorry, one last change of mind: ⊢∩∘⊃1,.↓(∪≢,/,⍨)¨ \$\endgroup\$ – ngn May 29 '18 at 20:19
4
\$\begingroup\$

Brachylog, 26 bytes

g;?z{tWl⟧₆∋I;W↺₍R;W≠&h∋R}ˢ

Try it online!

g;?z                          % Zip the whole input with each word in it respectively
    {                   }ˢ    % Apply this predicate to each pair in the zip
                              %   and select the successful values
     tW                       % Let the current word be W
       l⟧₆∋I                  % There exists a number I from 1 to length(W)-1
            ;W↺₍R             % And R is the result of circularly shifting the 
                              %   current word I times 
                 ;W≠          % And R is not the current word itself (needed for words like "tata")
                    &h∋R      % And R is one of the input dictionary words
                              % (R is implicitly the output of the predicate, and 
                              %  successful R values are collected and output by the ˢ)
\$\endgroup\$
3
\$\begingroup\$

Python 2, 73 69 67 bytes

lambda d:[w for w in d if{w[i:]+w[:i]for i in range(len(w))}-{w}&d]

Try it online!

Takes a set of words (lowercase), and returns a list of rotonyms.


Saved

  • -2 bytes, thanks to ovs
\$\endgroup\$
  • \$\begingroup\$ 67 bytes \$\endgroup\$ – ovs May 29 '18 at 15:13
3
\$\begingroup\$

K (ngn/k), 23 bytes

{x^x^,/1_'(,/|0 1_)\'x}

Try it online!

{ } is a function with argument x

0 1_ cuts a string at indices 0 and 1, e.g. "abcd" -> (,"a";"bcd")

| reverses the two slices: ("bcd";,"a")

,/ joins them: "bcda"

(,/|0 1_)\ returns all rotations of a string

(,/|0 1_)\'x are the rotations of each string in x

1_' drops the first "rotation" of each, i.e. each trivial identity rotation

,/ join

x^y is the list x without elements of the list y

x^x^y is the intersection of x and y

\$\endgroup\$
  • \$\begingroup\$ Clever. I was able to use the intersection part to save another byte. \$\endgroup\$ – Adám May 29 '18 at 19:55
2
\$\begingroup\$

05AB1E, 14 bytes

εDvDÀ})ÙåO<Ā}Ï

Try it online!

Explanation

ε           }    # apply to each word in the input
 Dv  }           # for each letter in the word
   DÀ            # copy the previous word and rotate it left
      )Ù         # wrap the rotations in a list and remove duplicates
        å        # check each rotation for presence in the input
         O       # sum presences
          <Ā     # decrement the sum and truthify it (check if 1 or greater)
             Ï   # filter, keep words in input that are true in the resulting list
\$\endgroup\$
2
\$\begingroup\$

PynTree, 44 bytes

§y:f#x0€[x/|Ḟz&⁻xzėzḞw+#x`wLx#x`0wRLxy]y#\x1

Try it online!

This turned out to reveal a major flaw in the way PynTree constructs list comprehensions because it uses functions to assign variables so that assignment can go in expressions, but then the conditions end up not having the value of the variable until after it has been evaluated and the main block has been evaluated. This appears to be easily fixable but I did not notice this earlier and so this answer is hideously long.

Actually even if I fixed that I think it still might be terribly long.

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 65 bytes

{@^a.grep:{@a∋any(($/=[.comb]).rotate,*.rotate...^*eq$/).join}}

Try it

Expanded:

{  # bare block lambda with placeholder parameter @a

  @^a     # declare and use placeholder parameter
  .grep:  # find the values that match
  {

    @a
    ∋            # Set contains operator

    any(         # create a junction of the following

      # generate a sequence
      (
        $/ =     # store into $/ (no declaration needed for this variable)
        [        # turn into an array instead of a one-time sequence
          .comb  # the input split into characters
        ]
      ).rotate,  # start the sequence on the first rotation

      *.rotate   # use this to generate the rest of the values in the sequence

      ...^       # keep generating values until: (and throw out last value)

      * eq $/    # one of them matches the cached array of the input

    ).join       # for each array in the junction join the strings (no spaces)
  }
}
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 105 99 bytes

f=l=>l.filter(w=>[...Array(k=w.length)].map((x,i)=>(w+w).substr(i,k)).some(r=>l.includes(r)&&r!=w))

Ungolfed:

f = list =>
  list.filter( word =>
    // create a list of all rotonyms for the current word
    [ ...Array( len = word.length ) ]
      .map( (x,i) => 
         ( word+word ).substr(i, len)
      )
    // check if any of the rotonyms is in the initial dictionary/wordlist
     .some( rotonym =>
        list.includes( rotonym )
    // and is not the word itself
        && rotonym != word
     )

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! I'm not versed in JavaScript, but be sure to check out the JavaScript Tips thread to see if there's anything that applies here. \$\endgroup\$ – AdmBorkBork Jun 1 '18 at 13:06
  • \$\begingroup\$ Thanks for the hint. I read the answers both for JS and ES6 but it seems I applied all relevant tips for this already. At least the ones that were obvious to me. \$\endgroup\$ – bubens Jun 1 '18 at 20:02
1
\$\begingroup\$

Retina 0.8.2, 71 62 bytes

^(\w)(\w*)
$2$1!¶$&
%+)s`^(.+)(!.*¶\1)$
$2
O`
!`\b(.+)(?=¶\1!)

Try it online! Explanation:

%+)

Repeat for each word.

^(\w)(\w*)
$2$1!¶$&

Prepend the next rotation of the word with a trailing !.

s`^(.+)(!.*¶\1)$
$2

But if that's the original word, then delete it again.

O`

Sort the words.

!`\b(.+)(?=¶\1!)

Find the duplicates.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 66 55 70 bytes

lambda d:{w for w in d for v in d if v not in w not in v in w*2in v*3}

Try it online!

11 bytes thx to Dennis to use chained x in y in z approach.

Takes a set of words d; returns a set of Rotonyms.

\$\endgroup\$
  • \$\begingroup\$ The check is too weak; {ab, abab} would pass it. \$\endgroup\$ – xnor May 29 '18 at 22:02
  • \$\begingroup\$ @xnor: Dang those edge conditions! A quick fix... \$\endgroup\$ – Chas Brown May 30 '18 at 2:45
1
\$\begingroup\$

C# (.NET Core), 100 94 bytes

x=>x.Where(y=>y.Select((z,i)=>x.Where(c=>c!=y).Contains(y.Remove(0,i)+y.Remove(i))).Any(b=>b))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 17 bytes

Extremely slow, but works. TIO times out, but I confirmed it works by manually lowering the number of iterations in the language source.

f@_XéZ ÀX©UøXéZ}a
f@                // Filter the input array by
  _            }a // generating up to 1e8 rotations of each string
   XéZ ÀX         // and checking if the rotation is different than the original,
         ©UøXéZ   // yet still exists in the input array.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Why so many iterations? I initially did iterations for string length, but through testing realized ten left rotations per word was enough to find all cases in the MacOS dict file. \$\endgroup\$ – Umbrella Jun 1 '18 at 14:35
  • \$\begingroup\$ @Umbrella Because it's short to write. The question is code golf, not fastest code. \$\endgroup\$ – Nit Jun 3 '18 at 12:23
  • \$\begingroup\$ I see. I'm unfamiliar with Japt, so it wasn't apparent to me that iterating less would take more characters. \$\endgroup\$ – Umbrella Jun 4 '18 at 19:47
0
\$\begingroup\$

Javascript, 129 Chars

f=a=>{n={};r=w=>w.slice(1,w.length)+w[0];a.map(w=>{m=r(w);while(m!=w){if(-~a.indexOf(m))n[m]=1;m=r(m);}});return Object.keys(n);}

Ungolfed

f=a=>{
    n={};
    r=w=>w.slice(1,w.length)+w[0];
    a.map(w=>{
        m=r(w);
        while(m!=w){
            if(-~a.indexOf(m))n[m]=1;
            m=r(m);
        }
    });
    return Object.keys(n);
}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Java (JDK 10), 144 bytes

l->{for(var s:l){var r=s;for(int i=s.length();i-->1;){r=r.substring(1)+r.charAt(0);if(!r.equals(s)&l.contains(r)){System.out.println(s);i=0;}}}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 66 bytes

s=>s.filter(t=>s.some(u=>(t+t).match(u)&&t!=u&t.length==u.length))

Try it online!

boring answer

\$\endgroup\$
  • \$\begingroup\$ This does not work correctly. Test it against the larger test set I added. \$\endgroup\$ – Umbrella Jun 1 '18 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.