Visualize a Recursive Acronym

Question

Background

Famously, the acronym GNU stands for GNU's Not Unix. ¹

It's recursive because, after expanding it once, it still contains the acronym GNU, and so must be exanded again:

(GNU's Not Unix)'s Not Unix

And so on, ad infinitum. Visualizing this, we get a kind of Droste effect:

┌────────────────────────────────────────────┬───────────┐
│┌──────────────────────────────┬───────────┐│'s Not Unix│
││┌────────────────┬───────────┐│'s Not Unix││           │
│││┌──────────────┐│'s Not Unix││           ││           │
││││GNU's Not Unix││           ││           ││           │
│││└──────────────┘│           ││           ││           │
││└────────────────┴───────────┘│           ││           │
│└──────────────────────────────┴───────────┘│           │
└────────────────────────────────────────────┴───────────┘

Recursive acronyms need not recurse on the first word, or only once. For example:

YOPY: Your Own Personal YOPY
PIPER: PIPER Is PIPER Expanded Recursively

Visualized:

Challenge

Input

You will be given two inputs:

A string whose space-delimited words form a recursive acronym. That is, if you form a string from the first letter of each word, that string is guaranteed to be either:
- One of the words of the input string (it may occur more than once).
- A prefix of one or more of those words (e.g. GNU is a prefix of GNU's)
- The casing will match exactly
A non-negative integer -- the number of times to recursively expand. Given 0, you'll return the input unaltered (or "framed" once, in its entirety). Given 1, you'll expand once. Etc.

Output

The output is the input string with all instances of the acronym visually expanded, recursively, the specified number of times.

You must use some visual effect to "frame" the nesting -- at minimum, distinct start and end delimiters like parentheses. Ascii boxing of some sort, as in the examples above, is also fine. As would be outputting an actual image that showed the nesting.

I'm flexible as long as the nesting is in fact visualized.

For clarity, parenthesized output would like this:

(((GNU's Not Unix)'s Not Unix)'s Not Unix)'s Not Unix

You are guaranteed that parentheses will never be part of acronym. Other than alphanumeric characters, the acronym will only contain apostrophes, commas, quotes, question marks and exclamation points, and those will only occur as valid punctuation (e.g., a question mark will not appear at the beginning of a word).

This is code golf, fewest bytes wins, no loopholes.

Test Cases

This assumes you're using a parentheses visualization.

Format for test cases:

Input string (the acronym)
Input integer (recursion)
Expected Output

GNU's Not Unix
0
GNU's Not Unix

GNU's Not Unix
2
((GNU's Not Unix)'s Not Unix)'s Not Unix

YOPY Own Personal YOPY
1
(YOPY Own Personal YOPY) Own Personal (YOPY Own Personal YOPY)

YOPY Own Personal YOPY
2

((YOPY Own Personal YOPY) Own Personal (YOPY Own Personal YOPY)) Own Personal ((YOPY Own Personal YOPY) Own Personal (YOPY Own Personal YOPY))

YourYOPY Own Personal YOPY
2

YourYOPY Own Personal (YourYOPY Own Personal (YourYOPY Own Personal YOPY))

Next level: visualize mutually recursive acronyms. Eg. “Hurd” → “Hird of Unix-Replacing Daemons” / “Hird” → “Hurd of Interfaces Representing Depth”. — manatwork, Feb 19 '20 at 12:04
@Anush That's absolutely acceptable, even encouraged. Just not required. — Jonah, Feb 19 '20 at 15:53
I don't see why we handle YourYOPY Own Personal YOPY as if the YOPY in YourYOPY is not the acronym - the caps seem to imply it should be :/ — Jonathan Allan, Feb 19 '20 at 18:29

Razetime · Accepted Answer · 2021-04-09 15:06:08Z

Stax, 11 bytes

û╟;±å↕êg╥σç

Run and debug it

Regex is pretty nice.

Explanation

D.\bxjMh+x:{R X → input
D             do the following n times, with the first input on stack
 .\b          push "\b" (word boundary)
    xj        split X on spaces
      M       transpose
       h      take first row to get abbreviation
        +     add that to the boundary
         x:{  push X, embedded in braces
            R replace matches of the created regex with "(X)"

Adám · Accepted Answer · 2020-02-19 07:27:55Z

7

APL (Dyalog Extended), 33 32 bytes

-1 byte thanks to Bubbler.

Anonymous infix lambda. Takes count as left argument and string as right argument.

{('\b',⊃¨⍵⊆⍨≠⍵)⎕R(1⌽')(',⍵)⍣⍺⊢⍵}

Try it online!

{…} "dfn"; number is ⍺ and text is ⍵:

⊢⍵ on the text:

⍣⍺ repeat given number of times

(…)⎕R(…) PCRE Replace:

')(',⍵ the text prefixed by ")("

1⌽ cyclically rotated one step left (puts ")" at end)

… with:

≠⍵ The mask of non-spaces in the text

⍵⊆⍨ characters runs in the text corresponding to runs of 1s in that

⊃¨ first character of each

'\b', prepend PCRE for word boundary

edited Feb 19 '20 at 7:27

answered Feb 19 '20 at 6:58

Adám

24.5k2 gold badges105 silver badges266 bronze badges

\$\begingroup\$ I like that rotation trick for the parens \$\endgroup\$ – Jonah Feb 19 '20 at 7:20
\$\begingroup\$ Unfolding (≠⊆⊢)⍵ into ⍵⊆⍨≠⍵ saves a byte. Actually I was about to post the same thing as a full program, which has the same byte count. \$\endgroup\$ – Bubbler Feb 19 '20 at 7:24

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

JavaScript (ES9), 88 85 82 bytes

Takes input as (string)(n).

s=>g=n=>n?s.replace(eval(`/\\b${s.match(/(?<=^| )./g).join``}/g`),`(${g(n-1)})`):s

Try it online!

Commented

s =>                       // s = string
  g = n =>                 // g is a recursive function taking the counter n
    n ?                    // if n is not equal to 0:
      s.replace(           //   replace in s:
        eval(              //     each word matching:
          `/\\b${          //       a word boundary followed by
            s.match(       //       the acronym which consists of
              /(?<=^| )./g //         the letters that are preceded by
                           //         either a space or nothing at all
            ).join``       //       joined together
          }/g`             //
        ),                 //     with:
        `(${               //     the result of
          g(n - 1)         //       a recursive call
        })`                //     surrounded with parentheses
      )                    //   end of replace()
    :                      // else:
      s                    //   end of recursion: just return s

\$\begingroup\$ What level of JavaScript is this??? \$\endgroup\$ – Peter Feb 23 '20 at 15:45 — Peter, Feb 23 '20 at 15:45

Grimmy · Accepted Answer · 2020-02-19 16:43:25Z

05AB1E, 27 25 22 bytes

ðìÐ#€нJðìs" (ÿ )"Iи.:¦

Try it online!

To make sure we only match the acronym at the beginning of a word, we match an extra leading space. This results in extra spaces in the output, which is allowed.

ðì                      # prepend a space to the input
  Ð                     # triplicate
   #€нJ                 # acronymize (split on spaces, head of each, join)
       ðì               # prepend a space to the acronym
         s              # swap
          " (ÿ )"       # surround with parentheses
                 Iи     # repeat the following second-input times:
                   .:   #  replace the acronym with the parenthesized string
                     ¦  # remove the leading space

LegionMammal978 · Accepted Answer · 2020-10-18 02:11:02Z

Husk, 20 bytes

!→⁰Ṡ¡§¤σΘom←w`J"()"Θ

Try it online! Takes the number followed by the string. Outputs with parentheses, prefixing each expansion with a space.

Explanation

!→⁰Ṡ¡§¤σΘom←w`J"()"Θ  (Let X and Y denote the arguments.)
                   Θ  Take Y prefixed with a space; denote this Y'.
!→⁰                   Take element X + 1 of
   Ṡ¡                  the infinite list created by iterating this function on Y':
       σ                Take the argument and substitute
          m←              the string containing the first character of
   Ṡ §      w              each space-separated word of Y',
      ¤ Θ                prefixed with a space, with
   Ṡ §       `J           the characters of Y' placed between
               "()"        '(' and ')',
      ¤ Θ                prefixed with a space.

nwellnhof · Accepted Answer · 2020-02-19 14:56:04Z

Perl 6, 48 bytes

{($^s,{S:g/$([~] $s~~m:g/<<./)/($s)/}...*)[$^x]}

Try it online!

Explanation

{                                              }  # Anonymous block
 (   ,                               ...*)  # Construct infinite sequence
  $^s                                       # starting with input string.
      {                             }  # Compute next item by
       S:g/                   /    /   # globally replacing
           $(                )         # interpolated
                 $s~~m:g/<<./          # first letters of each word
             [~]                       # joined (the acronym)
                               ($s)    # with input string in parens
                                          [$^x]  # Take nth item

Surculose Sputum · Accepted Answer · 2020-02-19 19:45:24Z

2

Python 3, 104 96 bytes

-7 bytes thanks to @DeathIncarnate, and another -1 byte thanks to @wastl

import re
f=lambda s,n:n and re.sub('\\b'+''.join(c[0]for c in s.split()),f'({s})',f(s,n-1))or s

Try it online!

Explanation:

re.sub(
  '\\b'+''.join(c[0]for c in s.split()), # match all acronyms that starts on a word boundary
  '('+s+')',                             # replace with the original string in parenthesis
  f(s,n-1)                               # on the result of the (n-1)th recursion
)

This is the acronym expanded n times.

return n and recursive_case or base_case

This returns base_case if n is 0, and recursive_case otherwise. This works because in Python, 0 is Falsy and non-empty string is Truthy.

If n is 0, n and recursive_case short circuits to False, then False or base_case is evaluated which returns base_case.
If n is not 0, n and recursive_case evaluates to recursive_case which is Truthy, so recursive_case or base_case is short-circuited to recursive_case.

edited Feb 19 '20 at 19:45

answered Feb 19 '20 at 19:08

Surculose Sputum

7,6951 gold badge8 silver badges39 bronze badges

\$\begingroup\$ Obvious saving is to make this a lambda 97 bytes Try it online! \$\endgroup\$ – DeathIncarnate Feb 19 '20 at 19:23
\$\begingroup\$ And using f-strings, there's another byte to be saved: Try it online! \$\endgroup\$ – wastl Feb 19 '20 at 19:30
\$\begingroup\$ My understanding of the rules is that 2 bytes can be saved by swapping the lines and moving the f= to the header. Is that correct? \$\endgroup\$ – Seb Feb 20 '20 at 16:33
2

\$\begingroup\$ @Seb Not if it's a recursive function, and in a language that doesn't support anonymous, recursive function calls. For example, Python. \$\endgroup\$ – mypetlion Feb 20 '20 at 19:59
\$\begingroup\$ @mypetlion Makes sense. Thanks for explaining! \$\endgroup\$ – Seb Feb 20 '20 at 20:12

Add a comment |

Xcali · Accepted Answer · 2020-02-20 14:40:52Z

2

Perl 5 `-apl`, 49 43 bytes

/./,$p.=$&for@F;for$a(1..<>){s/\b$p/(@F)/g}

Try it online!

edited Feb 20 '20 at 14:40

answered Feb 19 '20 at 17:19

Xcali

11.7k2 gold badges9 silver badges32 bronze badges

Add a comment |

Neil · Accepted Answer · 2020-02-19 15:42:26Z

Retina, 48 bytes

~(`$
 ¶($%`)
(.).*? (?=.*¶)
$1
^(.+)¶
1A`¶$1+`\b

Try it online! Takes the expansion count and acronym string on separate lines. Explanation:

~(`

After performing the script, interpret the result as a new script to be evaluated on the original input.

$
 ¶($%`)

Append a space to the string, and append a copy of the string wrapped in ()s on a new line.

(.).*? (?=.*¶)
$1

Turn the string into the acronym.

^(.+)¶
1A`¶$1+`\b

Replace the count with a Retina repeat instruction, and also prefix an instruction to delete the count from the original input.

For example, the result of evaluating the inner script on the input 2 GNU's Not Unix is

1A`
2+`\bGNU
(GNU's Not Unix)

This deletes the count from the original input, and then performs the acronym expansion twice.

wastl · Accepted Answer · 2020-02-19 18:52:19Z

1

sed 4.2.2, 180 bytes

h
s/(.)[^ ]* */\1/g
G
s/$/\n/
G
h
N
s/.*\n//
tx
:l
s/^(.*)\n(.*)\b\1(.*)\n(.*)\n(.*)/\1\n\2\n(\5)\3\4\n\5/
tl
s/\n(.*)\n(.*)\n/\n\1\2\n\n/
x
tx
:x
s/.//
x
tl
s/.*\n(.*)\n.*\n.*/\1/

Try it online!

Well, finding one part of input in another part of input is not that simple in sed. Input is on two lines: first line is the acronym string; second line is number of expansions in unary.

answered Feb 19 '20 at 18:52

wastl

3,80311 silver badges33 bronze badges

\$\begingroup\$ You should be able to include \ns in the capturing groups of your two longest substitutions to save some bytes in the respective replacements \$\endgroup\$ – user41805 Mar 5 '20 at 18:27
\$\begingroup\$ You can simplify the last substitution using the P command, and shave more bytes by using the -n flag. Also this is sed 4.2.2, so you can use empty labels. All together, you should save 22 bytes \$\endgroup\$ – user41805 Mar 5 '20 at 18:34

Add a comment |

Chas Brown · Accepted Answer · 2020-02-20 02:07:35Z

1

Python 2, 93 bytes

f=lambda s,n:n and re.sub('\\b'+''.join(zip(*s.split())[0]),'('+s+')',f(s,n-1))or s
import re

Try it online!

Python 2, 78 bytes

f=lambda s,n:n and f(s,n-1).replace(''.join(zip(*s.split())[0]),'('+s+')')or s

Try it online!

Except I didn't see the YourYOPY example when I put this together...

edited Feb 20 '20 at 2:07

answered Feb 20 '20 at 1:35

Chas Brown

9,4891 gold badge10 silver badges38 bronze badges

Add a comment |

wasif · Accepted Answer · 2021-04-08 07:58:32Z

1

PowerShell, 106 bytes

function f($a,$n){$s="\b"+(($a.split(" ")|%{$_[0]})-join'')+"\b"
$o=$a;1..$n|%{$a=$a-replace$s,"($o)"};$a}

Try it online!

answered Apr 8 at 7:58

wasif

8,1831 gold badge12 silver badges41 bronze badges

Add a comment |

mazzy · Accepted Answer · 2021-04-08 08:50:26Z

1

PowerShell, 84 71 bytes

Inspired by Wasif

param($n,$a)$o=$a
1..$n*!!$n|%{$a=$a-creplace'\b[A-Z]{2,}\b',"($o)"}
$a

Try it online!

edited Apr 8 at 8:50

answered Apr 8 at 8:43

mazzy

6,3582 gold badges8 silver badges22 bronze badges

Add a comment |

Noodle9 · Accepted Answer · 2020-02-20 12:30:35Z

0

Python 3, ^{123 106} 118 bytes

Rolled back to my initial post.
Chas Brown kindly pointed out I was going down a rabbit hole.
Added 17 bytes to fix word boundary bug.

import re
def f(a,n):
 o=a
 for i in[1]*n:a=re.sub(r'\b'+''.join([i[0]for i in o.split()])+r'\b',f"({o})",a)
 return a

Try it online!

edited Feb 20 '20 at 12:30

answered Feb 19 '20 at 18:32

Noodle9

15k2 gold badges15 silver badges37 bronze badges

\$\begingroup\$ Clever, but I think this fails for GIGA Is GIGA Again. \$\endgroup\$ – Chas Brown Feb 20 '20 at 1:33
\$\begingroup\$ @ChasBrown Oh no! I thought we were only to expand the first instance. T_T \$\endgroup\$ – Noodle9 Feb 20 '20 at 8:46

Add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Visualize a Recursive Acronym

Background

Challenge

Input

Output

Test Cases

14 Answers 14

Stax, 11 bytes

Explanation

APL (Dyalog Extended), 33 32 bytes

JavaScript (ES9), 88 85 82 bytes

Commented

05AB1E, 27 25 22 bytes

Husk, 20 bytes

Explanation

Perl 6, 48 bytes

Explanation

Python 3, 104 96 bytes

Perl 5 `-apl`, 49 43 bytes

Retina, 48 bytes

sed 4.2.2, 180 bytes

Python 2, 93 bytes

Python 2, 78 bytes

PowerShell, 106 bytes

PowerShell, 84 71 bytes

Python 3, ^{123 106} 118 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf string balanced-string recursion text-processing or ask your own question.

Hot Network Questions

Visualize a Recursive Acronym

Background

Challenge

Input

Output

Test Cases

14 Answers 14

Stax, 11 bytes

Explanation

APL (Dyalog Extended), 33 32 bytes

JavaScript (ES9), 88 85 82 bytes

Commented

05AB1E, 27 25 22 bytes

Husk, 20 bytes

Explanation

Perl 6, 48 bytes

Explanation

Python 3, 104 96 bytes

Perl 5 -apl, 49 43 bytes

Retina, 48 bytes

sed 4.2.2, 180 bytes

Python 2, 93 bytes

Python 2, 78 bytes

PowerShell, 106 bytes

PowerShell, 84 71 bytes

Python 3, 123 106 118 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf string balanced-string recursion text-processing or ask your own question.

Related

Hot Network Questions

Perl 5 `-apl`, 49 43 bytes

Python 3, ^{123 106} 118 bytes