# Bifurcated text

Given a string of ASCII letters (upper and/or lower case), output the raw MathJax required to display that string bifurcating at each character, into superscripts and subscripts. For example, the inputs cat and horse would result in outputs which MathJax renders as the following, respectively:

Note that only one input is required to be taken - these two are listed side by side simply to save vertical space.

# Markup meaning

• _ indicates a subscript.
• ^ indicates a superscript.
• Braces are required around superscripted or subscripted substrings that contain further superscripting or subscripting in order to prevent them all being at the same level.

# Test cases

Test cases are in the format input : output. The first test case shows the empty string as input should result in the empty string as output.

"" : ""
"a" : "a"
"me" : "m_e^e"
"cat" : "c_{a_t^t}^{a_t^t}"
"frog" : "f_{r_{o_g^g}^{o_g^g}}^{r_{o_g^g}^{o_g^g}}"
"horse" : "h_{o_{r_{s_e^e}^{s_e^e}}^{r_{s_e^e}^{s_e^e}}}^{o_{r_{s_e^e}^{s_e^e}}^{r_{s_e^e}^{s_e^e}}}"
"bifurcate" : "b_{i_{f_{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}^{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}}^{f_{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}^{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}}}^{i_{f_{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}^{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}}^{f_{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}^{u_{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}^{r_{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}^{c_{a_{t_e^e}^{t_e^e}}^{a_{t_e^e}^{t_e^e}}}}}}}"


You can see how these are rendered by pasting the output into mathurl.com.

# No redundant braces

MathJax will happily render markup that has redundant braces. For example, the following will all look identical when rendered: a, {a}, {}{a}, {{{{a}}}}.

However, valid output for this challenge has no redundant braces. Note in particular that single characters in the output are not surrounded by braces.

# Order

The order of subscript and superscript is unimportant. The following are equivalent and will be indistinguishable when rendered (and are all equally valid outputs):

c_{a_t^t}^{a_t^t}
c_{a^t_t}^{a_t^t}
c_{a_t^t}^{a^t_t}
c_{a^t_t}^{a^t_t}
c^{a_t^t}_{a_t^t}
c^{a^t_t}_{a_t^t}
c^{a_t^t}_{a^t_t}
c^{a^t_t}_{a^t_t}


# Scoring

For each language, the winner is the shortest code in bytes.

Too many notifications? Type </sub> to unsubscript

• Too many notifications? Type </sub> to unsubscript huh who said I want to unsubscript or something? It was a test to see if I read the whole post right? – Erik the Outgolfer Aug 9 '17 at 15:39
• @EriktheOutgolfer no it was just a very bad joke. – trichoplax Aug 9 '17 at 15:49
• Can we just output the compiled pdf result instead? I would like to write a pure Latex answer. – Post Rock Garf Hunter Aug 9 '17 at 17:24
• @WheatWizard that sounds like a different challenge. It wouldn't be valid as an answer here. – trichoplax Aug 9 '17 at 21:14

# Python, 95908692 82 bytes

10 bytes saved thanks to @ConnerJohnston

f=lambda s:s and s[0]+(s[1:]and'_{0}^{0}'.format(s[2:]and'{'+f(s[1:])+'}'or s[1]))


Try it online!

• Wow, that is some crazy recursion. – Mr. Xcoder Aug 9 '17 at 15:13
• Some string formatting for 81 bytes (not sure how to TIO link in comments yet): f=lambda s:s and s[0]+'_{0}^{0}'.format(s[2:]and'{'+f(s[1:])+'}'or s[1:]and s[1]) – Conner Johnston Aug 9 '17 at 20:01
• @ConnerJohnston thanks! you can put tio links with [text](link), but that's really spoiling ;) – Uriel Aug 9 '17 at 20:37
• 79 bytes; and I assume you do not want to use the anonymous function trick, would save 2 bytes though. – Jonathan Frech Sep 7 '17 at 19:55

# Mathematica, 728477 76 bytes

a_±b__:={"{",a,"_",±b,"^",±b,"}"};±(a_:""):={"",a,""};""<>Most@Rest@±##&@@#&


Uses CP-1252 (Windows) encoding. Takes a list of characters as input.

## Explanation

a_±b__:=


Define the function ±, with 2 or more arguments. Label the first argument a, and second and on b.

{"{",a,"_",±b,"^",±b,"}"}


Create a List equivalent to "{a_±b^±b}" (±b is evaluated again, recursively).

±(a_:""):= ...


Define the function ±, with 1 or 0 arguments. Label the first argumenta, if it exists, and assign "" to a otherwise.

{"",a,""}


Create a List equivalent to "a", padded with empty Strings.

""<>Most@Rest@±##&@@#&


A pure function that applies ± to the input, drops first and last element, and converts List to String.

## CJam (35 bytes)

MqW%{"^{ }_{ }"{AW$,)3e<#<},S/@*+}/  This is a full program. Online demo. 3 bytes work around a bug in the interpreter (see below). ### Dissection M e# Start building from the empty string qW%{ e# For each character in the reversed input "^{ }_{ }" e# Take a template { e# If the accumulator is of length n, remove all characters whose A e# codepoints are greater than pow(10, W$,)3e<  e#                                   min(n+1, 3))
#<       e#   When the accumulator is the empty string, that's all of them.
},         e#   When the accumulator is one character, that's {}
e#   When the accumulator is any longer, it's none of them.
S/@*       e#   Substitute the accumulator for the spaces.
+          e#   Append to the new character.
}/


Note that the min(n+1, 3) is to work around a bug in the interpreter: there must be some pattern in the powers of 10 that '} is smaller than, but it's not obvious.

• Doesn't appear to work for the empty string (first test case). – trichoplax Aug 9 '17 at 21:49
• @trichoplax, that was due to a subtle difference between GolfScript and CJam which occasionally catches me out. Now fixed at the cost of only one byte by making the code far cleverer than it previously was. – Peter Taylor Aug 9 '17 at 23:15
• Works perfectly now. Great explanation. – trichoplax Aug 9 '17 at 23:28
• @PeterTaylor (At least in the online demo) It does not work for words with more than four letters. – dessert Aug 10 '17 at 7:30
• @dessert, that is very weird, and definitely deserves a bug report against the interpreter. I have added a workaround at a cost of 3 bytes. – Peter Taylor Aug 10 '17 at 8:00

## JavaScript (ES6), 57 55 bytes

f=([c,...s])=>s+s?c+_${p=s[1]?{${f(s)}}:s}^+p:c||''


Θ(len(s)) complexity! According to @PeterTaylor, this is actually Θ(2^len(s)), which is still the best possible...

• Doesn't appear to work for the empty string (first test case). – trichoplax Aug 9 '17 at 21:47
• @trichoplax Should be fixed now. – ETHproductions Aug 9 '17 at 23:27
• Works perfectly now. – trichoplax Aug 9 '17 at 23:31
• What is n in your O(n)? I presume it's the length of the output, but unless you state that it is interpreted by default to be the length of the input, and since the length of the output is exponential in the length of the input it's impossible to implement in polynomial time. – Peter Taylor Aug 10 '17 at 7:14
• @PeterTaylor I had figured that since the algorithm only takes len(input) steps, that the complexity is len(input)... if that isn't correct I'll just remove it from the post since I don't know how to calculate it, unless you know what the correct complexity is. – ETHproductions Aug 10 '17 at 11:47

f[x,y]=x:'_':y:'^':y:[]
f(x:y@(_:_))=x:"_{"++f y++"}^{"++f y++"}"
f x=x


Try it online!

If we just had to output valid code the following would work for 44 bytes:

f[a]=[a]
f(a:b)=a:"_{"++f b++"}^{"++f b++"}"


Try it online!

# SOGL V0.12, 21 bytes

±K;{╔+;lH?"{ŗ}”}1 ^Ο+


Try it Here!

Explanation:

±                      reverse the string
K                     take off the first letter - will slowly convert to the output
;                    get the rest of the string ontop
{                   iterate over the rest of the characters
╔+                   append "_" to it
;                  get the output string ontop
lH?     }         if it's length - 1 [isn't 0]
"{ŗ}”            push the string "{ŗ}" where ŗ is replaced by the output string
1 ^Ο     wrap "^" around with the output string
+    prepend to it the current character + "_"


# Perl 5, 54 + 1 (-p) = 55 bytes

s/\{(.)\}/$1/g while s/([a-z])([a-z]+)/$1_{$2}^{$2}/ig


Try it online!

How?

The substitution in the while condition breaks occurrences of multiple letters in the first letter, followed by the rest in braces like this:

abc -> a_{bc}^{bc}


The while loop executes the substitution until no more multi-letter sequences remain. The substitution inside the loop removes braces from around single letters.

• Nice, I was wondering how long it would take for a regex answer to show up – Nnnes Aug 9 '17 at 17:49

# Ruby, 7673726867 57 bytes

Use of lambda saving 4 bytes thanks to Tutleman

f=->s{(r=s[1..-1])[0]?s[0]+?_+[r[1]??{+f[r]+?}:r]*2*?^:s}


Try it online!

Ungolfed:

def f(s)
r = s[1..-1]
if r.size > 0
if r.size > 1
x = "{" + f(r) + "}"
else
x = r
end
return s[0] + "_" + [x, x].join("^")
else
return s
end
end

• Instead of a function, use an anonymous lambda (e.g. ->s{...}), which saves 7 bytes. Then, you can save 2 more bytes by replacing "#{s[0]}_ with s[0]+"_. You can save one further byte by doing inline assignment of '{}' to a variable the first time you use it. – Tutleman Aug 9 '17 at 15:36
• @Tutleman It's recursive (t=f s[1..-1]), so I don't think an anonymous function will work, and I already rearranged the beginning of the string, but I can use the inline assignment. – Nnnes Aug 9 '17 at 15:41
• D'oh! Whoops - I can't believe I missed that. Anyway, it's still shorter to use a (named) lambda: f=->s{...} saves 4 bytes, even accounting for the extra [] you need when making the recursive call. – Tutleman Aug 9 '17 at 15:47
• @Tutleman Oh yeah, changed it. Now if I can come up something better than that .tr mess... – Nnnes Aug 9 '17 at 15:56

# Python 2, 84 bytes

def b(s):q=s and(s[2:]and'{%s}'or'%s')%b(s[1:]);return s[1:]and s[0]+'^%s_'%q+q or s


Try it online!

# Pyth, 47 bytes

Ljk[hb|&ttbs[\_\{ytb"}^{"ytb\})&tbs[\_htb\^htb;


Try it online!

This is pretty much a straight port of @Uriel's Python answer. Going to golf it down in a bit.

# PHP, 121 bytes

function b($s){return$s[0].($s[1]?'_'.($s[2]?'{'.($b=b(substr($s,1))).'}^{'.$b.'}':"$s[1]^$s[1]"):'');}echo b($argv[1]);


The function itself is 104 bytes and shows a PHP Notice.

# Retina, 43 bytes

(.)(.)1¶$2 +(.)¶(.*) ¶{$1_$2^$2}
¶{|}$ Try it online! Link includes test cases. Explanation: (.)(.)$
$1¶$2


Get the ball rolling by slicing off the last character. (But if it's the only character, them leave it alone.)

+(.)¶(.*)
¶{$1_$2^$2}  Move the ¶ character back one step at a time, each time taking the previous result and making it a subscript and superscript of the next character. ¶{|}$


Remove the now redundant ¶ and the outer {}s.

# Java (OpenJDK 8), 121 bytes

s->{int l=s.length;String r=--l<0?"":""+s[l];for(;l-->0;)r="{"+s[l]+"_"+r+"^"+r+"}";return r.replaceAll("^\\{|\\}$","");}  Try it online! # Javascript, 73 Bytes s=>[...s].reduceRight((m,c)=>${c}_{${m}}^{${m}}).replace(/{(.)}/g,'$1')  ## Explanation s=> // take the input string [...s] // split the string into an array .reduceRight( // reduce the array in reverse order (m,c)=>${c}_{${m}}^{${m}}  // storing the result of each iteration in the memo m
)                                // and returning m at the end
.replace(/{(.)}/g,'$1') // replace redundant {}  Because there is no specified initial value of m, reduceRight takes the last element of s as the initial value, and begins iterating at index s.length-2. const f=s=>[...s].reduceRight((m,c)=>${c}_{${m}}^{${m}}).replace(/{(.)}/g,'$1'); const input = document.querySelector('#input'); const output = document.querySelector('#output'); output.textContent = f(input.value); input.addEventListener('keyup', e => output.textContent = f(input.value)); Enter text to bifurcate: <input type="text" id="input" value="cat" /> <br /> <span id="output"></span> • s=>[...s].reduceRight((m,c)=>{${c}_${m}^${m}}).slice(1,-1) is only 60 bytes. – Neil Aug 9 '17 at 21:20
• Doesn't appear to work for the empty string (first test case). – trichoplax Aug 9 '17 at 21:46