# Recursive acronyms

## 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.

• Do we have to preserve capitalization of the function words? May 26 '14 at 14:07
• Is it acceptable to have a list of strings accompanying a False value, or no? May 26 '14 at 14:24
• Since the word list itself encodes the boolean value by its presence, may we omit the boolean? May 26 '14 at 14:56
• 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? May 26 '14 at 17:33
• @xfix, wikipedia states that those are mutually recursive acronyms. May 26 '14 at 18:05

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


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


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  # 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"]]  # 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"]]  # 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"  # 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 # 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,'')  # 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"]]  ## 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);}}}  • 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. May 27 '14 at 15:13 • 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. May 28 '14 at 9:47 • 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" ... May 30 '14 at 8:37 # 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|


# 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.

# 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);}


# 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