32
\$\begingroup\$

Objective

From Wikipedia :

A recursive acronym is an acronym that refers to itself in the expression for which it stands.

Your goal is to check if a string is a recursive acronym.

  • The acronym is the first word
  • Words are not case sensitive, separated with a single space.
  • The given string does not contain any punctuation nor apostrophe.
  • Only the first letter of each word can be part of the acronym.

You must also give the function words. For simplicity, every word can be considered as a function word.

Example

f("RPM Package Manager")         =>     { true, [] }
f("Wine is not an emulator")     =>     { true, ["an"] }
f("GNU is not Unix")             =>     { true, ["is"] }
f("Golf is not an acronym")      =>     { false }  
f("X is a valid acronym")        =>     { true, ["is","a","valid","acronym"] }  

You can give a full program or a function.
The input string can be taken from STDIN or as a function argument.
Output result can be true/false, 0/1, yes/no...
The function words list (any format of list is valid) must be given if and only if this is a recursive acronym (even if the list is empty). You do not have to preserve capitalization of the function words.

Winning criteria

This is a , shortest code wins.

\$\endgroup\$
10
  • 4
    \$\begingroup\$ Do we have to preserve capitalization of the function words? \$\endgroup\$ May 26, 2014 at 14:07
  • 1
    \$\begingroup\$ Is it acceptable to have a list of strings accompanying a False value, or no? \$\endgroup\$ May 26, 2014 at 14:24
  • 1
    \$\begingroup\$ Since the word list itself encodes the boolean value by its presence, may we omit the boolean? \$\endgroup\$ May 26, 2014 at 14:56
  • 5
    \$\begingroup\$ Hurd stands for Hird of Unix-Replacing Daemons. Hird stands for Hurd of Interfaces Representing Depth. Why the examples here don't understand that, and claim those aren't recursive acronyms? \$\endgroup\$
    – 0..
    May 26, 2014 at 17:33
  • 3
    \$\begingroup\$ @xfix, wikipedia states that those are mutually recursive acronyms. \$\endgroup\$
    – Michael M.
    May 26, 2014 at 18:05

18 Answers 18

22
\$\begingroup\$

Regex, .NET flavour, 62 bytes

(?i)(?<=^\w(?<c>\w)*)( \k<c>(?<-c>)\w+| (?<w>\w+))*$(?(c)(?!))

You can test it here. If the input is a recursive acronym, this will yield a match, and capturing group w will contain all function words. If it isn't, then there will be no match.

This does preserve capitalisation of the function words (but matches case-insensitively).

Unfortunately, the tester doesn't display the entire stack of a named capturing group, but if you used it anywhere in .NET, the w group would contain all function words in order.

Here is a C# snippet to prove that:

var pattern = @"(?i)(?<=^\w(?<c>\w)*)( \k<c>(?<-c>)\w+| (?<w>\w+))*$(?(c)(?!))";
var input = new string[] {
    "RPM Package Manager",
    "Wine is not an emulator",
    "GNU is not Unix",
    "Golf is not an acronym",
    "X is a valid acronym"
};

var r = new Regex(pattern);
foreach (var str in input)
{
    var m = r.Match(str);
    Console.WriteLine(m.Success);
    for (int i = 0; i < m.Groups["w"].Captures.Count; ++i)
        Console.WriteLine(m.Groups["w"].Captures[i].Value);
}

Here is a quick explanation. I'm using .NET's balancing groups to build a stack of the acronym letters in the named group c, with this snippet

^\w(?<c>\w)*

The trick is that I need the second letter on top of the stack and the last one at the bottom. So I put all of this in a lookbehind that matches the position after the acronym. This helps, because .NET matches lookbehinds from right to left, so it encounters the last letter first.

Once I got that stack, I match the rest of the string word for word. Either the word begins with the letter on top of the acronym stack. In that case I pop that letter from the stack:

 \k<c>(?<-c>)\w+

Otherwise, I match the word anyway and push onto the w stack which will then contain all function words:

 (?<w>\w+)

At the end I make sure I reached the end of the string with $ and also make sure that I've used up all letters from the acronym, by checking that the stack is empty:

(?(c)(?!))

Test it on ideone.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Great regular expression, but the question clearly states "You can give a full program or a function". \$\endgroup\$
    – Toothbrush
    May 26, 2014 at 20:40
  • 4
    \$\begingroup\$ @toothbrush If the OP decides to disqualify my answer based on that, so be it. But I think I could make a point that this is a full program in the language which is .NET's regular expression flavour (not a Turing complete language, and one that is a bit cumbersome to run, but a language nevertheless). In any case, I like the fact that I solved it with a pure-regex approach, and I'd rather have the answer disqualified than destroy that "elegance" (if you will) by making it "just a C#-answer using regex". \$\endgroup\$ May 26, 2014 at 20:45
  • \$\begingroup\$ That's fine with me. I just wanted to point it out in case you missed it. \$\endgroup\$
    – Toothbrush
    May 26, 2014 at 20:51
  • 1
    \$\begingroup\$ I like it. Regexes may not be a Turing-complete programming language, but I think this should count. \$\endgroup\$ May 26, 2014 at 23:49
  • \$\begingroup\$ @PaulDraper In fact, I wouldn't even bet on .NET's regex flavour not being Turing complete... the balancing groups and right-to-left-matched lookbehinds are pretty powerful. And PCRE for instance is known to be Turing complete (that one has recursion, I'm not sure the stacks in .NET are sufficient to emulate arbitrary iteration). \$\endgroup\$ May 26, 2014 at 23:51
11
\$\begingroup\$

Python (158, without regex)

It's not that I don't like regexes. It's that I don't know them.

def f(x):
 s=x.lower().split();w=list(s[0][1:]);s=s[1:];o=[]
 if not w:return 1,s
 [w.pop(0)if i[0]==w[0]else o.append(i)for i in s]
 return(0,)if w else(1,o)

Oh, I also had an ungolfed version:

def acronym(string):
    scentence = string.lower().split()
    word = scentence[0][1:]
    scentence = scentence[1:]
    over = []
    if not word: return 1, scentence
    for item in scentence:
        if item[0] == word[0]:
            word = word[1:]
        else:
            over.append(item)
    if word:
        return 0,
    return 1,over
\$\endgroup\$
7
\$\begingroup\$

GolfScript, 51 50 chars

{32|}%" "/(1>\{.1<2$1<={;1>}{\}if}/{]!}{]`1" "@}if

It probably can be golfed further. Takes input on STDIN. The boolean is 0/1.

Test online


Explanation:

{32|}%      # change everything to lower-case
" "/        # splits the string by spaces
(1>         # takes the first word out and removes the first letter
\           # moves the list of remaining words in front of the acronym word
{           # for every word:
  .1<2$1<=    # compares the first letter of the word with
              # the next unmatched letter of the acronym
  {;1>}       # if they are the same, discard the word and the now-matched letter
  {\}         # otherwise store the word in the stack
  if          # NB. if all letters have been matched, the comparison comes out as false
}/
{]!}        # if there are still unmatched letters, return 0 (`!` non-empty list)
{]`1" "@}   # otherwise, return 1, and display the list of function words
if
\$\endgroup\$
5
\$\begingroup\$

Python 2.7 - 131 126 bytes

def f(s):
 s=s.lower().split();a,f=list(s[0]),[]
 for w in s:f+=0*a.pop(0)if a and w[0]==a[0]else[w]
 return(0,)if a else(1,f)

Makes a list of letters in the first word of the acronym. Then, for each word in the full string, get rid of the first element of that list we made if it is the same as the first letter of that word. Otherwise, add that word to the list of function words. To output, return not a (In python, any list other than the empty list is True-y, and the list is empty if it's a recursive acronym) and the list if not a.

Thanks to @ace for helping me fix an error/save some bytes.

\$\endgroup\$
5
  • \$\begingroup\$ On Python 2.7.3, I get SyntaxError: invalid syntax at the end of the return line. \$\endgroup\$
    – user12205
    May 26, 2014 at 15:11
  • \$\begingroup\$ @ace Huh, I could have sworn it worked when I tested it. I must have changed something and forgot to test again. I'll work on a fix! \$\endgroup\$ May 26, 2014 at 15:14
  • \$\begingroup\$ You can use for w in s:f+=0*a.pop(0)if a and w[0]==a[0]else[w] which is shorter and doesn't rely on tabs. As for the return statement, I found 0if a else(1,f) which is shorter than your original. \$\endgroup\$
    – user12205
    May 26, 2014 at 15:24
  • \$\begingroup\$ Oh and if you use semicolons to put the first two statements in the same line you save one byte of indentation. \$\endgroup\$
    – user12205
    May 26, 2014 at 15:28
  • 1
    \$\begingroup\$ I figured out a way to fix the error, but when I came back here to post it you had golfed it down more in the comments :P \$\endgroup\$ May 26, 2014 at 16:03
3
\$\begingroup\$

Python - 154 characters

First ever code golf attempt. I'm thinking python isn't the best language for it, given all the long keywords. Also, I don't think this function is foolproof. It works for the OP's input, but I'm sure I could think up exceptions.

def f(s):
    w=s.lower().split();r=list(w[0]);return(True,[x for x in w if x[0]not in r])if len(r)==1 or[x for x in[y[0]for y in w]if x in r]==r else False
\$\endgroup\$
1
  • \$\begingroup\$ I count 156 characters (the newline and the tab character both count), but you can get it down to 154 legitimately by removing those two characters since neither are actually required. Welcome to PPCG, btw. :) \$\endgroup\$ May 30, 2014 at 23:52
3
\$\begingroup\$

ECMAScript 6 (105 bytes):

f=s=>(r=(a=s.toUpperCase(i=1).split(' ')).map((w,c)=>c?a[0][i]==w[0]?(i++,''):w:''),a[0].length==i?1+r:0)

Enter the function in Firefox's browser console, and then just call the function, like this:

f('ABC Black Cats')     // 1,,
f('ABC is Black Cats')  // 1,IS,,
f('ABC Clapping Cats')  // 0
\$\endgroup\$
3
  • \$\begingroup\$ Doesn't quite comply with the rules: The function words list ... must be given if and only if this is a recursive acronym. This will alert them regardless. \$\endgroup\$
    – MT0
    May 27, 2014 at 18:32
  • \$\begingroup\$ @MT0 OK. I didn't notice that requirement. I'll see if I can rewrite it. \$\endgroup\$
    – Toothbrush
    May 27, 2014 at 18:40
  • \$\begingroup\$ @MT0 I've updated the code now. \$\endgroup\$
    – Toothbrush
    May 27, 2014 at 19:34
2
\$\begingroup\$

Haskell - 287 bytes

Not the shortest entry (hey this is Haskell, what did you expect?), but still a lot a fun to write.

import Data.Char
import Data.List
f""w=map((,)False)w
f _[]=[]
f(a:as)(cs@(c:_):w) 
 |toLower a==toLower c=(True,cs):f as w
 |True=(False,cs):f(a:as)w
g s=if(length$filter(fst)d)==length v
  then Just$map(snd)$snd$partition(fst)d 
  else Nothing
 where 
  w=words s
  v=head w
  d=f v w

Tested with

map (g) ["RPM Package Manager","Wine is not an emulator","GNU is not Unix","Golf is not an acronym","X is a valid acronym"]

Expected output

[Just [],Just ["an"],Just ["is"],Nothing,Just ["is","a","valid","acronym"]]

Ungolfed

import Data.Char
import Data.List

f :: String -> [String] -> [(Bool, String)]
f "" w = map ((,) False) w
f _ [] = []
f (a:as) ((c:cs):w) | toLower a == toLower c = (True, c:cs) : f as w
                    | otherwise = (False, c:cs) : f (a:as) w

g :: String -> Maybe [String]
g s = if (length $ filter (fst) d) == (length v)
          then Just $ map (snd) $ snd $ partition (fst) d 
          else Nothing
  where w = words s
        v = head w
        d = f v w
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ECMAScript 6) - 97 Characters

f=x=>(r=(a=x.toLowerCase(i=0).split(' ')).filter(y=>y[0]!=a[0][i]||i-i++),i==a[0].length?[1,r]:0)

Tests:

f("RPM Package Manager")
[1, []]

f("GNU is not Unix")
[1, ["is"]]

f("X is an acronym")
[1, ["is", "an", "acronym"]]

f("Golf is not an acronym")
0

f("Wine is not an emulator")
[1, ["an"]]
\$\endgroup\$
1
\$\begingroup\$

Rebol - 133

f: func[s][w: next take s: split s" "y: collect[foreach n s[either n/1 = w/1[take w][keep n]]]reduce either/only w: empty? w[w y][w]]

Ungolfed:

f: func [s] [
    w: next take s: split s " "
    y: collect [
        foreach n s [
            either n/1 = w/1 [take w][keep n]
        ]
    ]
    reduce either/only w: empty? w [w y][w]
]

Tested with:

foreach t [
    "RPM Package Manager"  "Wine is not an emulator"  
    "GNU is not Unix"      "Golf is not an acronym"  
    "X is a valid acronym"
][probe f t]

Output:

[true []]
[true ["an"]]
[true ["is"]]
[false]
[true ["is" "a" "valid" "acronym"]]
\$\endgroup\$
1
\$\begingroup\$

Julia - 116 bytes

f(w)=(a=split(lowercase(w));L=1;A=a[];while a!=[];a[][1]==A[1]?A=A[2:]:(L=[L,a[]]);a=a[2:];A>""||return [L,a];end;0)

Less Golfed:

f(w)=(
 a=split(lowercase(w))
 L=1
 A=a[]
 while a!=[]
  if a[][1]==A[1]
   A=A[2:]
  else
   L=[L,a[]]
  end
  a=a[2:]
  if !(A>"")
   return [L,a]
  end
 end
0)

The 0 on the end makes it output 0. Otherwise, it outputs an array containing 1 followed by the function words. For example:

julia> f("RPM Package Manager")
1-element Array{Any,1}:
 1

julia> f("Golf is not an acronym")
0

julia> f("GNU is not Unix")
2-element Array{Any,1}:
 1    
  "is"

julia> f("X is a valid acronym")
5-element Array{Any,1}:
 1         
  "is"     
  "a"      
  "valid"  
  "acronym"
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 29 bytes

ḷṇ₁XhY∧X;0zpᵐz{ċ₂ˢ}ᵐZhhᵐcY∧Zt

Try it online!

Outputs the function words through the output variable if the input is a recursive acronym, and fails if it is not.

   X                             X is
ḷ                                the input lowercased
 ṇ₁                              and split on spaces,
    hY                           the first element of which is Y
      ∧                          (which is not X).
       X  z                      X zipped
        ;0                       with zero,
           pᵐ                    with all pairs permuted (creating a choicepoint),
             z                   zipped back,
              {   }ᵐ             and with both resulting lists
               ċ₂ˢ               losing all non-string elements,
                    Z            is Z.
                      hᵐ         The first elements of the elements of
                    Zh           the first element of Z
                        cY       concatenated are Y
                          ∧      (which is not Z).
                           Zt    The last element of Z is the output.

Without having to output the function words (treating this as a pure ), it comes out to just 12 bytes, because ∧Zt can be dropped for -3, Y can be replaced with . for -1, and most importantly ;0zpᵐz{ċ₂ˢ}ᵐZh can be replaced with for a whopping -13: ḷṇ₁Xh.∧X⊇hᵐc

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

Cobra - 187

def f(s as String)
    l=List<of String>(s.split)
    a=l[0]
    l.reverse
    o=0
    for c in a,for w in l.reversed
        if c==w[0]
            l.pop
            o+=1
            break
    x=o==a.length
    print x,if(x,l,'')
\$\endgroup\$
0
\$\begingroup\$

Ruby - 173

Could be better...

 f=->s{a=[];o={};s=s.split;r=true;s[0].each_char{|c|s.each{|w| w[0]=~/#{c}/i?(o[c]=1;a<<w if o[c]):(o[c]=0 if !o[c])}};r,a=false,s if o.values&[0]==[0];!r ?[r]:[r,(s-(a&a))]}

Calling the func :

p f.call('RPM Package Manager')
p f.call('Wine is not an emulator')
p f.call("GNU is not Unix")
p f.call("Golf is not an acronym")
p f.call("X is a valid acronym")

Output :

[true, []]
[true, ["an"]]
[true, ["is"]]
[false]
[true, ["is", "a", "valid", "acronym"]]
\$\endgroup\$
0
\$\begingroup\$

Java - 195

Unfortunately, Java does not have built in tuple support.

So, this is a class that stores the boolean in 'b' and the function word list in 'x'.

Here, the function is the constructor of the class.

static class R{boolean b;String[]x;R(String s){String v=" ",i="(?i)",f=s.split(v)[0],r=i+f.replaceAll("(?<=.)",".* ");if(b=(s+=v).matches(r))x=(s.replaceAll(i+"\\b["+f+"]\\S* ","")+v).split(v);}}

Test

public class RecursiveAcronyms {
public static void main(String args[]) {
    String[] tests = {
            "RPM Package Manager",
            "Wine is not an emulator",
            "GNU is not Unix",
            "Golf is not an acronym",
            "X is a valid acronym"
        };
    for (String test:tests) {
        R r = new R(test);
        System.out.print(r.b);
        if (r.b) for (String s:r.x) System.out.print(" "+s);
        System.out.print("\n");
    }
}
static class R{boolean b;String[]x;R(String s){String v=" ",i="(?i)",f=s.split(v)[0],r=i+f.replaceAll("(?<=.)",".* ");if(b=(s+=v).matches(r))x=(s.replaceAll(i+"\\b["+f+"]\\S* ","")+v).split(v);}}}
\$\endgroup\$
3
  • \$\begingroup\$ C# has tuples but I came up with this while working on my solution: just return string[]: null simply means false, empty means true and n elements means true with n function words. \$\endgroup\$
    – Num Lock
    May 27, 2014 at 15:13
  • \$\begingroup\$ I would like to do that too. However OP specifies that the boolean must be provided regardless. See the reply to Jan Dvorak's comment. \$\endgroup\$
    – Vectorized
    May 28, 2014 at 9:47
  • \$\begingroup\$ I don't care about the comments as I can't seem to spot a resulted edit in the original post. And even if i did, it clearly just says to "specify the boolean". And even in the answer itself it says "Output result can be true/false, 0/1, yes/no...+" which I might just extend at the ellipsis by "*null/not null" ... \$\endgroup\$
    – Num Lock
    May 30, 2014 at 8:37
0
\$\begingroup\$

Awk - 145

awk -v RS=' ' '{c=tolower($0)};NR==1{w=c};{t=substr(c,1,1)!=substr(w,NR-s,1);if(t){f=f" "c;s++};a=a||t};END{print a&&(s>NR-length(w))?"N":"Y|"f}'

Test:

$ cat gcp.sh
#!/bin/sh
f() {
echo "$1:"
echo "$1"|awk -v RS=' ' '{c=tolower($0)};NR==1{w=c};{t=substr(c,1,1)!=substr(w,NR-s,1);if(t){f=f" "c;s++};a=a||t};END{print a&&(s>NR-length(w))?"N":"Y|"f}'
}
f "RPM Package Manager"
f "Wine is not an emulator"
f "Wine is not an appropriate emulator"
f "GNU is not Unix"
f "Golf is not an acronym"
f "Go is not an acronym"
f "Go is a valid acronym OK"
f "X is a valid acronym"
f "YAML Ain't Markup Language"

$ ./gcp.sh
RPM Package Manager:
Y|
Wine is not an emulator:
Y| an
Wine is not an appropriate emulator:
Y| an appropriate
GNU is not Unix:
Y| is
Golf is not an acronym:
N
Go is not an acronym:
N
Go is a valid acronym OK:
Y| is a valid acronym
X is a valid acronym:
Y| is a valid acronym

YAML Ain't Markup Language:
Y|
\$\endgroup\$
0
\$\begingroup\$

Coffeescript - 144

z=(a)->g=" ";b=a.split g;c=b[0];d=[];(d.push(e);g++)for e,f in b when e[0].toLowerCase()!=c[f-g].toLowerCase();if(g+c.length==f)then{1,d}else{0}

Call it with, for instance: z "GNU is not Unix"

The compiled JS:

var z;
z = function(a) {
  var b, c, d, e, f, g, _i, _len;
  g = " ";
  b = a.split(g);
  c = b[0];
  d = [];
  for (f = _i = 0, _len = b.length; _i < _len; f = ++_i) {
    e = b[f];
    if (e[0].toLowerCase() !== c[f - g].toLowerCase()) {
      d.push(e);
      g++;
    }
  }
  if (g + c.length === f) {
    return {
      1: 1,
      d: d
    };
  } else {
    return {
      0: 0
    };
  }
};

It splits the string into words and then loops through each word. If the first character of the word doesn't match the next in the acronym, the word is stored. A counter (g) is used to track how many words have been skipped. If the number of skipped words plus the length of the acronym matches the length of the phrase, it matched, so return 1 and the skipped words. If not, it was not valid, so return 0.

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

C# - 234

Tuple<bool,string[]> f(string w) {var l=w.ToLower().Split(' ');var o=new List<string>();int n=0;var a=l[0];foreach(var t in l){if(n>=a.Length||a[n]!=t[0])o.Add(t);else n++;}var r=n>=a.Length;return Tuple.Create(r,r?o.ToArray():null);}
\$\endgroup\$
0
\$\begingroup\$

Python (108)

l=raw_input().lower().split()
a=l[0]
e=[]
for w in l:d=w[0]!=a[0];a=a[1-d:];e+=[w]*d  
b=a==''
print b,b*`e`
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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