Outsmart the boffins at New Scientist (string rotation)

Question

The brainiacs at New Scientist tweeted this morning that "The word STABLE has the neat property that you can cycle the first letter to the end to make a new word: TABLES. And you can do it again to make ABLEST." (https://twitter.com/newscientist/status/1379751396271124480)

This is of course correct. It is not, however, unique. Let us demonstrate that we can use computational force to match their linguistic cleverness.

You are to write a program that generates two sets of outputs based on the dictionary words revealed when rotating the letters of another dictionary word. Using the dictionary at https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words,

1. find all the dictionary words with more than two characters for which every possible rotation yields another dictionary word. Show only one example of each rotation set (so, for example, show only one of "car", "arc", and "rca").
2. find the words for which the largest number of valid rotations exist. You should find multiple words that tie with the same number of valid rotations. As above, show only one member of each set.

Additional rules:

• You can assume that the dictionary has been downloaded outside your code, and can be passed to your code as input or in a variable.

• If you need to process the word list to put it in a format more natural for your programming language (a list for example), you may exclude this code from your byte count. However this process should not remove any words; any bytes associated with, for example, removing two-letter and one-letter words from the dictionary must be included in your byte total.

• Anything in the words list counts as a word, even if we know it's really an acronym, or contains punctuation marks, or is not English (e.g. "AOL" or "Abdul's"). Treat all characters as letters.

• Treat all letters as identically cased (so "India" and "india" are the same, and "eAt" is a valid word).

• No shortcuts based on already knowing the answer, or knowing the maximum number of rotations. Your code needs to actually solve for that.

Using these rules and some ungolfed Wolfram Language, I found four completely rotateable words and 15 words tied at the level of maximum rotateability. This is a code golf challenge, and I imagine it won't be hard to do it more concisely than I did. I plan to call out any particularly creative solutions as well, regardless of length.

--

Intended output (assuming I coded it correctly)

completely rotatable words: aol, arc, asp, eat (each of these words can be presented with the letters in any rotation)

maximum rotatable words: all of the words above, plus ablest, alan, ales, anal, ankh, aver, emit, ernst, errant, evan, evil (each of this latter group also has two valid rotations)

Answer 1

Python 3.10, 166 bytes

Based on Manish Kundu's answer. The assignment expression in the set comprehension would need parentheses in version 3.8.

def f(a,m=0):
 a={*map(str.lower,a)};b=c=[]
 while a:w,*_=a;k={w:=w[1:]+j for j in w}&a;p=len(k);a-=k;c+=[w]*(p==len(w)>2);b=b*(p<=m)+[w][p<m:];m=max(m,p)
 return b,c

Local output:

>>> f(words)
(['lesa', 'ernst', 'mite', 'hank', 'ablest', 'car', 'ola', 'spa', 'rave', 'alan', 'vile', 'vane', 'aral', 'eat', 'errant'], ['car', 'ola', 'spa', 'eat'])

With a recursive lambda this gets down to 165 bytes, but it crashes for the full word list:

f=lambda a,m=0,b=[],c=[]:(a:={*map(str.lower,a)})and(w:=min(a))and f(a-(k:={w:=w[1:]+j for j in w}&a),max(m,p:=len(k)),b*(p<=m)+[w][p<m:],c+[w]*(p==len(w)>2))or(b,c)

Answer 2

Python 3, 269 266 bytes

def f(a,m=0,b=[],c=[]):
 a=[k.lower()for k in a]
 while a:
  w,k,u=a[0],[],1
  for i in range(len(w)):
   x=w[i:]+w[:i]
   u,k=x in a and(u,k+[x])or(0,k)
  p=len(k)
  for j in{*k}:a.remove(j)
  if u and len(w)>2:c+=[w]
  if p==m:b+=[w]
  if p>m:m,b=p,[w]
 return b,c

Try it online!

Takes a list of words as input. First convert all words to lowercase, then for each word check all it's rotations and if they are valid, remove them from the list. Outputs two lists containing maximum rotatable words and completely rotatable words respectively.

Needless to say this is not optimal at all and takes several minutes to execute for the provided input.

Output I got for the given dictionary: (['aol', 'alan', 'alar', 'ernst', 'evan', 'hank', 'lesa', 'levi', 'rca', 'terran', 'vera', 'ablest', 'asp', 'ate', 'emit'], ['aol', 'rca', 'asp', 'ate'])

-3 bytes thanks to pxeger

Answer 3

Java, 369 bytes

d->{var o=new HashSet<String>();Set a[]={new HashSet(),new HashSet()};for(var s:d)o.add(s.toLowerCase());int l=0;for(var s:o){int v=1,i=0,b=s.length(),g=0,h=0;for(;++i<b;){var c=s.substring(i)+s.substring(0,i);if(a[0].contains(c))++g;if(a[1].contains(c))++h;if(o.contains(c))++v;}if(v==b&b>2&g<1)a[0].add(s);if(h<1&v>=l){if(v>l)a[1].clear();l=v;a[1].add(s);}}return a;}

Full program:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.URL;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
 
public class Main {
    public static void main(String[] args) throws IOException {
        Function<Set<String>,Set[]> f=
        d->{var o=new HashSet<String>();Set a[]={new HashSet(),new HashSet()};for(var s:d)o.add(s.toLowerCase());int l=0;for(var s:o){int v=1,i=0,b=s.length(),g=0,h=0;for(;++i<b;){var c=s.substring(i)+s.substring(0,i);if(a[0].contains(c))++g;if(a[1].contains(c))++h;if(o.contains(c))++v;}if(v==b&b>2&g<1)a[0].add(s);if(h<1&v>=l){if(v>l)a[1].clear();l=v;a[1].add(s);}}return a;}
        ;
        Set<String> dictionary = new BufferedReader(
                    new InputStreamReader(
                        new URL("https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words").openStream()
                    )).lines().collect(Collectors.toSet());
        System.out.println(Arrays.toString(f.apply(dictionary)));
    }
}

Answer 4

R, 182 191 bytes

Edit: +9 bytes to fix bug after discovering that some entries are present twice (with different capitalization) in the dictionary

function(d,e=tolower(d),x=unique(e),`?`=nchar,s=substring,S=sapply,z=S(e,function(w){y=x%in%S(1:?w,function(n,w)paste0(s(w,n+1),s(w,1,n)),w);x<<-x[!y];sum(y)}))list(d[z>2&z==?e],d[z==max(z)])

Try it online!

Function "outsmart_the_boffins" with input parameter d=dictionary in the form of a vector of words. TIO link includes a mini-dictionary that encompasses at least some of the intended output words.

Outputs a list of completely-rotatable words, and then maximum-rotatable words.

Ungolfed code

outsmart_the_boffins=
function(d){
    e=tolower(d)                # first convert dictionary to lower case (e),
    x=unique(e)                 # make a copy of unique elements (x);
    r=function(n,w)             # define function r=rotates letters of word w by r steps
      paste0(substring(w,n+1),  #   by paste-ing the second half
        substring(w,1,n))       #   in front of the first half;
    z=sapply(e,function(w){     # now calculate z=valid rotations for each word w in e:
        y=x %in% sapply(1:nchar(w),r,w);
                                #   define y as the positions of matches in x to all rotations of w, 
        x<<-x[!y];              #   delete them all from x (so we don't find the other members of the set later),
        sum(y)                  #   and return the number of them;
    })
list(d[z>2 & z==nchar(e)],      # finally, output the words with >2 characters whose valid rotations equals their length,
  d[z==max(z)])                 # and those whose valid rotations is equal to the maximum found.

Run on the full dictionary (took a few minutes):

> outsmart_the_boffins(scan(file="words.txt",what="abc"))
Read 99171 items
[[1]]
[1] "AOL" "RCA" "asp" "ate"

[[2]]
 [1] "AOL"    "Alan"   "Alar"   "Ernst"  "Evan"   "Hank"   "Lesa"   "Levi"  
 [9] "RCA"    "Terran" "Vera"   "ablest" "asp"    "ate"    "emit"  

Answer 5

JavaScript (ES6),  211  203 bytes

Expects an array of words.

a=>[(a=[...new Set(a.map(w=>w.toUpperCase(m=g=(w,W=k=w)=>(W=W.slice(1)+W[0])==w?k:g(w,W,k=W<k?W:k))))]).filter(w=>g[w]^(n=w.length)|n<3?0:m>n?1:m=n,a.map(w=>g[g(w)]=-~g[k])),a.filter(w=>g[g(w)]=g[k]==m)]

Try it online!

Output on the full dictionary

[
  [ 'AOL', 'ARC', 'ASP', 'ATE' ],
  [
    'AOL',    'ALAN', 'ALAR',
    'ERNST',  'EVAN', 'HANK',
    'LESA',   'LEVI', 'RCA',
    'TERRAN', 'VERA', 'ABLEST',
    'ASP',    'ATE',  'EMIT'
  ]
]
timer: 329.15ms

Commented

Helper function

The helper function g turns a word into a normalized rotation form, i.e. the first one in lexicographical order. The result is also saved in k.

m = g = (                      // m = maximum 'rotatability'
  w,                           // w = input word
  W =                          // W = current rotation of w
  k = w                        // k = first rotation in lexicographical order
) =>                           //
  (W = W.slice(1) + W[0])      // rotate W by one position
  == w ?                       // if W is equal to w:
    k                          //   stop and return k
  :                            // else:
    g(                         //   do a recursive call:
      w,                       //     pass w unchanged
      W,                       //     pass the updated W
      k = W < k ? W : k        //     update k to min(W, k)
    )                          //   end of recursive call

Main function

a => [                         // a[] = list of words
  ( a =                        // convert a[] to:
    [...new Set(               //   the list of unique words in a[] ...
      a.map(w =>               //
        w.toUpperCase(...)     //   ... in upper case
      )                        //   (NB: m and g are actually defined here)
    )]                         //
  )                            // end of conversion
  .filter(w =>                 // for each word w in a[]:
    g[w] ^ (n = w.length) |    //   if the length of w is not equal to the number of
    n < 3 ? 0                  //   rotations or is less than 3: discard this entry
          : m > n ? 1 : m = n, //   otherwise, update m to max(m, n) and keep this entry
    a.map(w =>                 //   for each word w in a[]:
      g[g(w)] = -~g[k]         //     increment g[k], where k = normalized rotation of w
    )                          //   end of map()
  ),                           // end of filter()
  a.filter(w =>                // for each word w in a[]:
    g[g(w)] = g[k] == m        //   keep the words that have m rotations
                               //   and update g[k] in such a way that each word can
                               //   appear only once
  )                            // end of filter
]                              //