13
\$\begingroup\$

A problem I sometimes encounter is that when writing comments using LaTeX, the comment is too long. Today you will solve this, by writing code which, given a LaTeX math expression, will produce the shortest equivalent expression.

To define equivalent expressions, we will need to specify a (simplified) parser for LaTeX:

Tokenizer

Given an expression, it is first processed by tokenizing it. To tokenize an expression, it is processed from left to right. Most characters are a token by themselves, except whitespaces which are ignored, and \ which has special behavior - if it's followed by a non-letter character, then it and the character become a token. Otherwise, it and all following letters become a token.

For example, \sum_{n \leq r^2} {\frac{v(n)}{n}} + \frac1n \in \{1,2,3\} is tokenized as \sum _ { n \leq r ^ 2 } { \frac { v ( n ) } { n } } + \frac 1 n \in \{ 1 , 2 , 3 \} (with tokens seperated by a space).

Parsing

If the { and } aren't validly matched, this is an invalid LaTeX equation. You can assume this won't be the case in the input. Now, to parse the LaTeX, we will look at the arity of each token. Most tokens have an arity of 0, and we will only have the following exceptions: _, ^, and \sqrt (note: this isn't fully accurate for _ and ^, since they expect a subformula and not an argument, but we'll ignore this for simplicity's sake) have an arity of 1, and \frac has an arity of 2. Each token will bind a number of tokens as its arity, but tokens surrounded by { } are considered a single token for this purpose. For example, the above equation will bind as \sum _({ n \leq r ^ 2 }) { \frac({ v ( n ) }, { n }) } + \frac(1, n) \in \{ 1 , 2 , 3 \}.

Finally, all { and } are removed, so our parsed equation will become \sum _(n \leq r ^ 2) \frac(v ( n ), n) + \frac(1, n) \in \{ 1 , 2 , 3 \}.

We will say two expressions are equivalent if their parsed version is the same.

Input

A valid LaTeX math expression (the braces are matched, and each token has enough tokens to bind to). You may assume it only contains ASCII characters. You can use any reasonable string I/O, but you can't take it pre-parsed. You can assume there are no empty braces, and the only whitespace is a space.

Output

The shortest equivalent LaTeX math expression. You can use any reasonable string I/O (not necessarily the same as the input), but you can't output a parse tree or something similar.

Testcases

\sum_{n \leq r^2} {\frac{v(n)}{n}} + \frac1n \in \{1,2,3\} -> \sum_{n\leq r^2}\frac{v(n)}n+\frac1n\in\{1,2,3\}
\a{b c}d -> \a bcd
\sqrt{b c}d -> \sqrt{bc}d
\sqrt{2 2}d -> \sqrt{22}d
\sqrt{a}d -> \sqrt ad
\sqrt{2}d -> \sqrt2d
\frac{1}{2} -> \frac12
\frac{12}{3} -> \frac{12}3
\frac{2}{n} -> \frac2n
\frac{a}{n} -> \frac an
\frac{a+1}{n} -> \frac{a+1}n
\frac{\frac12}3 -> \frac{\frac12}3
\frac{\sqrt2}3 -> \frac{\sqrt2}3
\frac {1} {23} -> \frac1{23}
\a b -> \a b
^{a b} -> ^{ab}
{ab}_{\log} -> ab_\log
{\sqrt{2}}^2 -> \sqrt2^2
\frac{\frac{\frac{1}{\sqrt{x_{1}}}+1}{\sqrt{x_{2}+1}}+2}{\sqrt{x_{3}+2}}+3 -> \frac{\frac{\frac1{\sqrt{x_1}}+1}{\sqrt{x_2+1}}+2}{\sqrt{x_3+2}}+3
\sqrt{\{} -> \sqrt\{

Note that {ab}_{\log} -> ab_\log, for example, isn't correct in real LaTeX.

This is , so the shortest answer in each language wins. Standard loopholes are disallowed.

\$\endgroup\$
8
  • \$\begingroup\$ Sandbox \$\endgroup\$ Commented Oct 8, 2023 at 4:39
  • \$\begingroup\$ Suggested test case: \frac{1}{23} (currently you have no tests for the second argument to \frac). \$\endgroup\$
    – Neil
    Commented Oct 8, 2023 at 6:52
  • \$\begingroup\$ @Neil thanks, added \$\endgroup\$ Commented Oct 8, 2023 at 7:21
  • \$\begingroup\$ What is expected output for \frac{\frac{\frac{1}{\sqrt{x_{1}}}+1}{\sqrt{x_{2}+1}}+2}{\sqrt{x_{3}+2}}+3 \$\endgroup\$
    – tsh
    Commented Oct 8, 2023 at 7:53
  • \$\begingroup\$ @tsh Added as a testcase \$\endgroup\$ Commented Oct 8, 2023 at 8:00

4 Answers 4

5
\$\begingroup\$

Retina 0.8.2, 202 bytes

M!`\\[A-Za-z]+|\\?.
A`^ 
+`(?<!\\)\{¶(.+)¶}
$1
+`(?<!\\|(?<!\\)[_^]¶|\\sqrt¶|\\frac¶(\{¶(((\{)|(?<-4>})|[^{}])+)¶}(?(4)^)¶|.+¶)?)\{¶(((\{)|(?<-7>})|[^{}])+)¶}(?(7)^)
$5
(\\[A-Za-z]+¶)([A-Za-z])
$1 $2
¶

Try it online! Link includes test cases. Explanation:

M!`\\[A-Za-z]+|\\?.

Tokenise the input.

A`^ 

Delete unquoted spaces.

+`(?<!\\)\{¶(.+)¶}
$1

Remove {}s surrounding a single token.

+`(?<!\\|(?<!\\)[_^]¶|\\sqrt¶|\\frac¶(\{¶(((\{)|(?<-4>})|[^{}])+)¶}(?(4)^)¶|.+¶)?)\{¶(((\{)|(?<-7>})|[^{}])+)¶}(?(7)^)
$5

Remove matched {}s that don't follow \, _, ^, \sqrt, \frac, or aren't the second argument to frac.

(\\[A-Za-z]+¶)([A-Za-z])
$1 $2

If a quoted word is followed by a bare letter, insert a space.

Join everything together.

\$\endgroup\$
3
\$\begingroup\$

Python3, 442 bytes:

lambda s:R(f(re.findall(r'\\\W|\\[a-z]+|\S',s)))
import re
def R(I):
 r=[]
 for i in I:r+=[' '*(r!=[]and r[-1][0]=='\\'and[]!=re.findall('^[a-z]',i))+i]
 return''.join(r)
def f(s,p=0):
 v={'\\sqrt':1,'^':1,'_':1,'\\frac':2}
 if[]==s:return
 if(t:=s.pop(0))in v:k=f(s,1);yield from[t,*[next(k)for _ in range(v[t])]]
 if'{'==t:T=[t,*f(s),'}'];yield R([T[1:-1],T][p and len(T)>3])
 if'}'!=t:
  if t not in v and'{'!=t:yield t
  yield from f(s,p)

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ Your TIO link has def F(s):return instead of F=lambda s:. Additionally, I don't think you have to give a name to the lambda \$\endgroup\$ Commented Oct 10, 2023 at 5:20
  • 1
    \$\begingroup\$ This fails for \sqrt{\{}, but it seems like it can be fixed by replacing '\\\W|\\\[a-z]+|\S' with r'\\\W|\\[a-z]+|\S' \$\endgroup\$ Commented Oct 10, 2023 at 5:24
  • 1
    \$\begingroup\$ @CommandMaster r'\\\[a-z]+|\\.|\S' would probably work. \$\endgroup\$
    – Neil
    Commented Oct 10, 2023 at 7:43
  • \$\begingroup\$ I think *f(s) should be *f(s,p). \$\endgroup\$
    – Neil
    Commented Oct 10, 2023 at 11:52
  • \$\begingroup\$ @Neil Thanks, updated \$\endgroup\$
    – Ajax1234
    Commented Oct 10, 2023 at 12:17
2
\$\begingroup\$

Charcoal, 178 bytes

F⪫_}⪫{_S¿⌕⮌υ\¿⁼ι W⌊υ⊞υω≡ι}«≔⟦⟧θF⌕⮌υ{F∧∨⌊υ⊟υ∧№α↥§§⊞Oθ⊟υ±¹¦⁰⬤§υ±¹⎇μ№α↥λ⁼λ\⊞θ ≔⊟υη¿∧⊖Lθ∨№⪪“7§⪪◧⌊q⦄NYL?⦄”¶§υ±¹⁼\frac§υ±²⊞υ⪫{}⪫⮌θωWθ⊞υ⊟θ⊞υω»⊞υ⁺⎇∨№υω∧№α↥ι⬤§υ±¹⎇λ№α↥κ⁼κ\⊟υωι⊞υ⁺⊟υι✂⌈υ¹±²

Try it online! Link is to verbose version of code. Explanation:

F⪫_}⪫{_S

Wrap the input in _{ and _} as the code will automatically join the tokens back together this way, and then loop over the characters.

¿⌕⮌υ\

If the last character was not a new escape, then:

¿⁼ι 

If the current character is a space, then...

W⌊υ⊞υω

... push an empty string to the predefined empty list if there is not one already, preventing subsequent letters from being joined to a preceding command. Otherwise:

≡ι}«

If current character is a }, then:

≔⟦⟧θ

Start collecting tokens in reverse between the } and the previous {.

F⌕⮌υ{

Loop over the number of tokens.

F∧∨⌊υ⊟υ∧№α↥§§⊞Oθ⊟υ±¹¦⁰⬤§υ±¹⎇μ№α↥λ⁼λ\

Unless the current token is empty, if the current token starts with a letter and the next (previous) token is a command, then...

⊞θ 

Insert a space after pushing the current token.

≔⊟υη

Remove the {.

¿∧⊖Lθ∨№⪪“7§⪪◧⌊q⦄NYL?⦄”¶§υ±¹⁼\frac§υ±²

If there was more than one token and the previous token(s) were ^, _, \sqrt or \frac, then...

⊞υ⪫{}⪫⮌θω

... join the reversed tokens and wrap them in {}s, else...

Wθ⊞υ⊟θ

... push the tokens back. Note that this might also insert extra spaces but there's no point removing them as they would just get reinserted later.

⊞υω

Push an empty string in case the last original token was a command, so that a following letter does not get concatenated to it.

»⊞υ⁺⎇∨№υω∧№α↥ι⬤§υ±¹⎇λ№α↥κ⁼κ\⊟υωι

But if the current character was not a } then if the previous token was a space or current character is a letter and the previous token is a command then append the current character to it otherwise push it to the predefined empty list as a new token.

⊞υ⁺⊟υι

But if the last character was an escape, then append the current character to it.

✂⌈υ¹±²

Output the final result.

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 416 410 394 bytes

a:~"a{"'
t:{,/(((,:';,:)"\\"=*:')t)@'t:(0,&~(-1_0,"\\"=x)|a@x)_x}
kw:"|"\"\\frac |\\sqrt |_|^"
ar:1+~!4
k:{$[1<#x;(,/x)/"{}";*x]}
r:*(,,)/(,()),
f:{*{$[^*y;x;"}"~*y;(,()),x
 "{"~*y;r(x 0;x 1;2_x)
 ~^i:kw?y;r(y;ar[i]#*x;ar[i]_*x;1_x)
 r(y;*x;1_x)]}/[,();|u,'("\\"=*'u:t x)#\:" "]}
g:{r@(!#r)^w@&~a@r@1+w:&^r:{$[`C~@x;x
 |/kw~\:*x;x[0],,/{$[y;x;k@x]}[;2 1~#'(x;x 1)]'o'1_x
 1=#x;o@*x
 ,/o'x]}f@x}

Try it online!

shift/reduce parser (no regexes). Probably plenty of golfing left.
t tokenizes, f parses into an AST and g renders. I couldn't roll rendering into parsing because I couldn't distinguish deep structures which render as a single string from single tokens and failed on the ones mentioned in the problem comments.

\$\endgroup\$
2
  • \$\begingroup\$ Alternative lexer: T:3\"gqig"-97 C:@[3+&256;(" ";"\\";"a"+!26);:;!3] (^*:')_(&~=':+/1(<\~:)\+/1(1=)\0{T[x;y]}\C@s)_s \$\endgroup\$
    – doug
    Commented Oct 11, 2023 at 8:22
  • \$\begingroup\$ those are three lines. I guess I don't know how to do block quotes in comments. \$\endgroup\$
    – doug
    Commented Oct 11, 2023 at 9:40

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.