Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

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

17 Answers 17

up vote 6 down vote accepted

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
share|improve this answer

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.

share|improve this answer
1  
Great regular expression, but the question clearly states "You can give a full program or a function". –  toothbrush May 26 at 20:40
4  
@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". –  Martin Büttner May 26 at 20:45
    
That's fine with me. I just wanted to point it out in case you missed it. –  toothbrush May 26 at 20:51
1  
I like it. Regexes may not be a Turing-complete programming language, but I think this should count. –  Paul Draper May 26 at 23:49
    
@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). –  Martin Büttner May 26 at 23:51

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
share|improve this answer

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.

share|improve this answer
    
On Python 2.7.3, I get SyntaxError: invalid syntax at the end of the return line. –  ace May 26 at 15:11
    
@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! –  undergroundmonorail May 26 at 15:14
    
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. –  ace May 26 at 15:24
    
Oh and if you use semicolons to put the first two statements in the same line you save one byte of indentation. –  ace May 26 at 15:28
1  
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 –  undergroundmonorail May 26 at 16:03

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
share|improve this answer
    
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. :) –  undergroundmonorail May 30 at 23:52

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
share|improve this answer
    
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. –  MT0 May 27 at 18:32
    
@MT0 OK. I didn't notice that requirement. I'll see if I can rewrite it. –  toothbrush May 27 at 18:40
    
@MT0 I've updated the code now. –  toothbrush May 27 at 19:34

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
share|improve this answer

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"]]
share|improve this answer

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"]]
share|improve this answer

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"
share|improve this answer

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,'')
share|improve this answer

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"]]
share|improve this answer

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);}}}
share|improve this answer
    
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. –  Num Lock May 27 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. –  bitpwner May 28 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" ... –  Num Lock May 30 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|
share|improve this answer

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.

share|improve this answer

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);}
share|improve this answer

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`
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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