# Starring MathJax

Twinkle, Twinkle, little star...

Having enjoyed @Humn's recent MathJax puzzles (MathJax exposed and MathJax re-flex), I decided to contribute some of my own.

This one is a classic $\rm\TeX$ exercise, but since MathJax doesn't implement counter registers, numeric operations, or looping and if-then control structures, it takes a bit more ingenuity than in actual $\rm\TeX$.

Goal: find the minimal replacement for (replace this line) in the following MathJax code

$$\require{begingroup}\begingroup (replace this line) \stars{57} \endgroup$$


so that the output is 57 asterisks in the \texttt{} font (and nothing else):

$$\texttt{*********************************************************}$$

The Catch? Your code should produce the proper number of stars no matter what non-negative integer is given in place of 57 (including 0).

When counting the length of your solution, control sequences count as 1 character, as do macro parameters #1 (and ## if needed, and even ##1 if used in a nested macro definition), and pairs of braces ({ with a paired } count as one). So \stars and \s each count as 1. All other non-space characters count as 1, but please do use spaces and line breaks for clarity.

Example: \def \x #1:#2\x {#1#1\stop} has a character count of 10.

To make this easier, I've made a code snippet that counts the tokens for you. (Unfortunately, there are no code snippets on this site, so I had to use the SE sandbox for it.) Run the snippet, then past your MathJax code into the resulting text area and press "Count tokens".

Do not use any additional \require{...} macros, or defeat the final call to \endgroup. Admittedly, the audience for this puzzle is small. Please share any answer that even almost works. A solution is known, and will be posted after a suitable period, if no other solution is offered.

In displaying formatted code in a spoiler, feel free to omit $‍$, which doesn’t play well in that combination (or copy-and-paste the pair above, which have an invisible character between them, allowing the spoiler to display properly).

NOTE ☆ Before posting an answer, be sure to test it on a freshly loaded browser page ☆ Might also need to reload the page while editing, as inadvertent indiscretions in one edit can pervert MathJax results during later edits ☆

• Mmmmm beanz – Jonathan Allan Jul 19 '16 at 0:07
• Too soon for the solution, Davide C, especially as you knew it at post time. You solved the first 2 in record time for something this tough. Could even wait a couple more days before hinting unless someone asks. My initial comment gives a chance to ward off false leads, though, if your solution doesn't use numbers in templates. (I haven't really gotten started yet, keep finding more twists in |Medusa|. A spaces-cheating version uses just 51 chars. Legitimate version is at 56.) I'm pleasantly surprised by the interest in these. Really enjoy the title and intro of this one too, by the way. – humn Jul 20 '16 at 11:03
• OK, thanks for the info; this is my first foray into the puzzling site, so I'm not familiar with the process, and I appreciate the help. I'll hold off for a while, then. In response to your first comment, my solution does not use a macro like yours to decompose the number, though I don't want to dissuade you from following your own approach. – Davide Cervone Jul 20 '16 at 11:24
• I thought you might still be working on the re-flex puzzle instead, as you have made lots of progress there. I am also pleased with the interest in them. I have three more puzzles prepared for when this one is solved. – Davide Cervone Jul 20 '16 at 11:26
• Here's the kind of thing I'm trying out: $\require{begingroup}\begingroup\large \def \parseOne #11#2\endOne{ #1\text{\one}#2 1\endOne } \def \parseTwo #12#2\endTwo{ #1\text{\two}#2 2\endTwo } \def \show #1\hide#2\stop{#1} \parseOne\parseTwo\parseOne\show 3.14159265\hide 2\endTwo 1\endOne \stop \endgroup$ is produced by:  \def \parseOne #11#2\endOne{ #1\text{\one}#2 1\endOne } \def \parseTwo #12#2\endTwo{ #1\text{\two}#2 2\endTwo } \def \show #1\hide#2\stop{#1} \parseOne\parseTwo\parseOne\show 3.14159265\hide 2\endTwo 1\endOne \stop  – humn Jul 20 '16 at 15:03

Overhauled solutionjust $\, \texttt{\stars{}} \:$ and $\, \texttt{\N} \:$ while borrowing $\, \texttt{\endgroup} \:$ as a delimiter

$\small \texttt{\stars{57}}$ — solution with 47 code tokens, as $\small\texttt{\stars{}}$ and one dynamic macro — base 10: $$\require{begingroup}\begingroup \def \stars #1#2 #3\endgroup{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3 \stars ##4#2 #3##6\endgroup} \N 9 8 7 6 5 4 3 2 1 0 #2 % \texttt * #3 #3#3#3#3 #1 #1 } \stars{57} \endgroup$$

$\small \texttt{\starsTwo{111001}}$ — 34 code tokens — base 2: $$\require{begingroup}\begingroup \def \starsTwo #1#2 #3\endgroup{ \def \N ##1#1##2 ##3 ##4 ##5 ##6 { ##3 \starsTwo ##5#2 #3##4\endgroup } \N 1 \texttt* 0 #2 % #3 #1 #1 } \starsTwo{111001} \endgroup$$

$\small \texttt{\starsEight{71}}$ — 40 ½ code tokens — base 8: $$\require{begingroup}\begingroup \def \starsEight #1#2 #3\endgroup{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 { ##4 \starsEight ##2#2 #3##5\endgroup} \N 7 6 5 4 3 2 1 0 \texttt * {} #2 % #3 #1 #1 } \starsEight{71} \endgroup$$

Base 8’s ½ token is a nonfunctional $\small\texttt{{}}$ that allows an otherwise blank line to reach MathJax’s interpreter. Along this approach, base 8 is might be optimally efficient in that every larger base seems to require adding non-digit tokens to base 2's minimum.

Once again, squeezing out code tokens has burdened execution, and added scads of spaces as well, as a mere $\small\texttt{\stars{87}}$ exceeds MathJax’s default safety limits and the call to $\small\texttt{\N}$ uses 113 spaces. (Notice the scroll bar below the code.)

.                               - - - WRUNG OUT \stars{} - - - -
$$\require{begingroup}\begingroup \def\stars#1#2 #3\endgroup{ \def\N##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3\stars##4#2 #3##6\endgroup} \N9 8 7 6 5 4 3 2 1 0 #2 % \texttt * #3 #3#3#3#3 #1 #1 } \stars{57} \endgroup$$
.
.                               - - - AIRED OUT \stars{} - - -
$$\require{begingroup}\begingroup % \def \stars #1#2 #3\endgroup{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3 \stars ##4#2 #3##6\endgroup} \N 9 8 7 6 5 4 3 2 1 0 #2 % \texttt * #3 #3#3#3#3 #1 #1 } % \stars{57} \endgroup$$
.
. leading digit's current value   #1
.             subsequent digits   #2
.     accumulated ***...* stars   #3
.                     % if done   ##3   (usually empty)
. leading digit's next value(s)   ##4   decrement  or  (two values:) \texttt *  or  empty
.               add stars to #3   ##6   \texttt *  or  #3 (double)  or  #3#3#3#3 (quintuple)
.                                 ##7   (leftovers)


The code for base 2, $\small\texttt{\starsTwo{}}$, is relatively tidy while the code for base 8, $\small\texttt{\starsEight{}}$, is compact in its own vertical way. (Notice the scroll bar along the right side.)

.                                 - - - \starsTwo{} - - -
$$\require{begingroup}\begingroup % \def \starsTwo #1#2 #3\endgroup{ \def \N ##1#1##2 ##3 ##4 ##5 ##6 { ##3 \starsTwo ##5#2 #3##4\endgroup } \N 1 \texttt* 0 #2 % #3 #1 #1 } \starsTwo{111001} \endgroup$$
.
.
. leading digit's current value   #1
.             subsequent digits   #2
.     accumulated ***...* stars   #3
.              \S for next call   ##3   (empty when done)
.    leading digit's next value   ##4   decrement  or  \texttt  or  *  or  empty
.               add stars to #3   ##5   \texttt*  or  \texttt *  or  #3 (double)
.                                 ##6   (leftovers)
.
.
.                                 - - - \starsEight{} - - -
$$\require{begingroup}\begingroup % \def \starsEight #1#2 #3\endgroup{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 { ##4 \starsEight ##2#2 #3##5\endgroup} \N 7 6 5 4 3 2 1 0 \texttt * {} #2 % #3 #1 #1 } \starsEight{71} \endgroup$$


Yes, that’s $\small\texttt{\endgroup}$ being borrowed as a terminal delimiter so that $\small\texttt{\stars{}}$ can accumulate $\small\texttt{***...*}$ stars into an initially-empty parameter after the line break. This does not defeat $\small\texttt{\endgroup}$ because it is rewritten each time, on the line that remains active when $\small\texttt{%}$ comments out the recursive call to $\small\texttt{\stars{}}$. In the following trace, $\small\texttt{\t}$ represents $\small\texttt{\texttt}$ while $\large \raise-.3ex{\unicode{8629}}$ represents the line break.

$\require{begingroup}\begingroup \def \Eol {{ \large \kern2mu \raise-.3ex{\unicode{8629}} \kern1mu }} \def \t #1{{ \normalsize \texttt{#1} \large \strut }} % \def \stars #1#2 #3\end{ \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { \texttt {##3 \stars ##4#2} \Eol \tiny \texttt {#3##6} \, \scriptsize\texttt{\endgroup} \\[-1ex] ##3 \stars ##4#2 #3##6\end} \N 9 8 7 6 5 4 3 2 1 0 #2 % \t * #3 #3#3#3#3 #1 #1 } % \small \begin{array}{l} \texttt{ \stars {23}} \Eol \scriptsize\texttt{\endgroup} \\[-1ex] \stars{23} \end{array} \endgroup$

The present approach is built on Davide Cervone’s algorithm that accumulates stars by appending each leading digit’s number of stars and, if more digits follow, multiplying that total by $\small 10$ and recursively calling $\small\texttt{\stars{}}$. Leading digits are treated like states of a state machine with branch points at the digits$\scriptsize \raise.2ex/$states $\small\texttt{0}$ and $\small\texttt{*}$. Here are the steps in rendering $\small\texttt{\stars{2301}}$.

$$\require{begingroup}\begingroup \small \def \S #1{ \textsf {#1} } \def \T #1{{ \small \texttt {#1} }} \def \U #1{{ \scriptsize \K\!\texttt{#1}\K }} \def \P #1{{ \scriptsize ( \kern1mu\raise-.1ex{\texttt{#1}}\kern1mu ) }} \def \K { \kern-.5em } \def \Zip {{ \tiny \raise.6ex - }} \def \L { \\[ .4ex] } \def \M { \\[-.7ex] } \def \Timess {{ \small \raise .1ex \times \kern 1mu }} \def \Times {{ \small \raise .1ex \times }} \def \Pluss {{ \scriptsize\raise .1ex + \kern 2mu }} \def \Plus {{ \scriptsize\raise.1ex + \kern1mu }} \kern-.5em \begin{array}{rcccc} &\rlap {\kern .85em \S {Original algorithm}} \\ & \rlap{ \kern .7em \S{Direct and efficient}} \\[.5ex] & & & & \\[-.7ex] &\K\S{Leading}\K&\S{Further}&\K\S{Previous}\K& \\[-.7ex] \S{Step}& \S{digit} & \S{digits}& \S{total} & \S{Operation} \\[-.5ex] & \P{#1} & \P{#2} & \P{#3} & \P{\N...} \\[1ex] & & & & \L \sf a.~ &\tt 2 &\tt 3 0 1 & \Zip & \Pluss 2 \M\L \sf b.~ &\tt 2 &\tt 3 0 1 &\tt 2 & \Times 10 \M\M\L \sf c.~ &\tt 3 &\tt 0 1 &\tt 20 & \Pluss 3 \M\M\L \sf d.~ &\tt 3 &\tt 0 1 &\tt 23 & \Times 10 \M\M\L \sf e.~ &\tt 0 &\tt 1 &\tt 230 & \Times 10 \M\M\L \sf f.~ &\tt 1 &\tt \Zip &\tt 2300 & \Pluss 1 \L \sf g.~ &\tt 1 &\tt \Zip &\tt 2301 & \S{done} \end {array} \kern4em \begin{array}{rcccc} &\rlap {\kern .9em \S {Solution's algorithm}} \\ & \rlap{ \kern-1.5em \S{Small steps, inefficient, less code}} \\[.5ex] &\K\S{State /}\K& & & \\[-.7ex] &\K\S{leading}\K&\S{Further}&\K\S{Previous}\K& \\[-.7ex] \S{Step}& \S{digit} & \S{digits}& \S{total} & \S{Operation} \\[-.5ex] & \P{#1} & \P{#2} & \P{#3} & \P{\N...} \\[1ex] 1.~~ &\K \T{{2301}}\K& \Zip & \Zip & \raise.6ex*\S{unwrap}\,\L 2.~~ &\tt 2 &\tt 3 0 1 & \Zip & \Plus 1 \M 3.~~ &\tt 1 &\tt 3 0 1 &\tt 1 & \Plus 1 \L 4.~~ &\tt 0 &\tt 3 0 1 &\tt 2 & \Zip \M 5.~~ & \!\U{\texttt} &\tt 3 0 1 &\tt 2 & \Timess 2 \M 6.~~ &\tt * &\tt 3 0 1 &\tt 4 & \Timess 5 \L 7.~~ &\tt 3 &\tt 0 1 &\tt 20 & \Plus 1 \M 9.~~ &\tt 2 &\tt 0 1 &\tt 21 & \Plus 1 \M 10.~~ &\tt 1 &\tt 0 1 &\tt 22 & \Plus 1 \L 11.~~ &\tt 0 &\tt 0 1 &\tt 23 & \Zip \M 12.~~ & \!\U{\texttt} &\tt 0 1 &\tt 23 & \Timess 2 \M 13.~~ &\tt * &\tt 0 1 &\tt 46 & \Timess 5 \L 14.~~ &\tt 0 &\tt 1 &\tt 230 & \Zip \M 15.~~ & \!\U{\texttt} &\tt 1 &\tt 230 & \Timess 2 \M 16.~~ &\tt * &\tt 1 &\tt 460 & \Timess 5 \L 17.~~ &\tt 1 & \Zip &\tt 2300 & \Plus 1 \L 18.~~ &\tt 0 & \Zip &\tt 2301 & \S{done} \end{array}\endgroup$$

$\small\raise.6ex* \sf unwrap$ in step $\small 1$ means that $\small\texttt{{2301}}$, delivered as a lone “digit” from the initial call $\small\texttt{\stars{2301}}$, becomes an ad hoc state that refeeds $\small\texttt{2301}$ to $\small\texttt{\stars}$ as an unwrapped sequence of digits.

$\small\texttt{\texttt}$ and $\small\texttt{*}$ in steps $\small 5, 6, 12, 13, 15$ and $\small 16$ represent the use of those tokens as states — pseudo-digits below $\small\tt 0$ — when they are not needed as text for incremental stars.

The bottom line’s call to $\small\texttt{\N}$ is effectively a state-transition case$\scriptsize \raise.2ex/$switch regime that determines what to do with each current leading digit, what to use as the next leading digit, and whether to reiterate or halt.

.     space after possible % = c   nnn = 3 spaces after next digit
.    3 spaces after skip = fff |   |           ssssss = 6 spaces after skip
.      space after digit = d | |   |             |           aa = 2 spaces after added stars
.                          | | |   |             |            |
.                         _dfffc_nnn          ssssss_________aa                                      zzzzzzzzzzzzzzzzzzzz
.   \N  9     8  .  .  .  2     1     0   #2 %      \texttt *             #3      #3#3#3#3  #1     #1                               }
.                         :     :                   :       :
.                         :     :                   :       :
.   Any positive digit ...:.....:......             :       :
.   gets replaced by            :     :             :       :
.   1 less and adds             _dfffc_nnn    ssssss_________aa                                      zzzzzzzzzzzzzzzzzzzz
.   \text *  to the             1     0   #2 %      \texttt *             #3      #3#3#3#3  #1     #1                               }
.   cumulative stars                                :       :
.   in #3...........................................:.......:
.
.   When no further digits              _dfff_cnnn           ssssssaa                                zzzzzzzzzzzzzzzzzzzz
.   remain, % is prepended,             0    %      \texttt *             #3      #3#3#3#3  #1     #1                               }
.   halting \stars iteration ................:                     :
.   and adding nothing to #3.......................................:
.                               ............
.   When further digits remain, :         ::
.   they split the space before %,    _d ---> fffc___________nnnssssssaa                             zzzzzzzzzzzzzzzzzzzz
.   causing fff to bypass %.          0   #2 %      \texttt *             #3      #3#3#3#3  #1     #1                               }
.                                                 :         :
.   0 is replaced as the leading .................:.........:
.   digit by both \texttt and *
.   at the same time, saving                        _______d_fffcnnnssssss__aa                       zzzzzzzzzzzzzzzzzzzz
.   space even if not code.                         \texttt *             #3      #3#3#3#3  #1     #1                               }
.                                                                         ::
.   \texttt and * add 1 or 4 .............................................::..............
.   copies of #3 to itself,                                                       :      :
.   multiplying its cumulative                              _dfffcnnn       ssssss________aa         zzzzzzzzzzzzzzzzzzzz
.   stars by 2 or 5.                                        *             #3      #3#3#3#3  #1     #1                               }
.
.   Initially, all digits are .......................................................................
.   encapsulated in #1 as a                                                                 :       :
.   single leading digit, so this                                                           __dfffc__nnnssssssaazzzzzzzzzzzzzzzzzzzz
.   refeeds them unwrapped to \stars.                                                       #1     #1                               }


### A more sophisticated matrix-oriented solution with only one more code token

Without using $\small\texttt{\endgroup}$ as a delimiter, a 48 code-token alternate solution uses a macro with an auxiliary parameter for multiplying more efficiently than the 47 token solution.

$$\require{begingroup}\begingroup \def \stars #1{ \S #1 } \def \S #1#2 #3 #4 { \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3 \S ##4#2 #3##6 } \N 9 8 7 6 5 4 3 2 1 0 #2 % \texttt * #3#4 #3 } \stars{57} \endgroup$$

Here the call to $\small\texttt{\N}$ uses 4 fewer tokens, because $~ \small\texttt{#1 #1} ~$ is not needed to unwrap the initial number and because multiplication uses $~ \small\texttt{#3#4 #3} ~$ instead of $~ \small\texttt{#3 #3#3#3#3} \,$. (Again, scroll right.)

$$\require{begingroup}\begingroup % \def \stars #1{ \S #1 } \def \S #1#2 #3 #4 { \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3 \S ##4#2 #3##6 } \N 9 8 7 6 5 4 3 2 1 0 #2 % \texttt * #3#4 #3 } % \stars{57} \endgroup$$
.
.   leading digit's current value   #1
.               subsequent digits   #2
.       accumulated ***...* stars   #3
. temporary copy of ***...* stars   #4    (usually empty)
.                       % if done   ##3   (usually empty)
.   leading digit's next value(s)   ##4   decrement  or  (two values:) \texttt*  or  empty
.        add stars to #3 (and #4)   ##6   \texttt*  or  #3#4 #3 (sqrt 5)  or  #3 (double)
.                                   ##7   (leftovers)


In the following trace, $\small\texttt{\t}$ represents $\small\texttt{\texttt}$ while $\large \raise-.4ex{\unicode{8629}}$ represents a line break and $\small \, \Rule{ .5pt}{.6ex}{0ex} \kern -.3pt \Rule{2.3em}{.5pt}{0ex} \kern-.3pt \Rule{.5pt}{.6ex}{0ex} \,$ represents the 6 spaces between $\small\texttt{#3}$ and $\small\texttt{#4}$.

$\require{begingroup}\begingroup \def \Eol {{ \large \kern1mu \raise-.4ex{\unicode{8629}} \kern2mu }} \def \t #1{{ \normalsize \texttt{#1} \strut }} % \def \stars #1{ \S #1 } % \def \S #1#2 #3 #4 { \rlap { \small \texttt {\S #1#2} \, \Eol {\tiny \texttt{#3}} \, \Rule{ .5pt}{.6ex}{0ex} \kern -.3pt \Rule{2.3em}{.5pt}{0ex} \kern-.3pt \Rule{.5pt}{.6ex}{0ex} \, {\tiny \texttt{#4}} } \\[-1ex] \def \N ##1#1 ##2 ##3 ##4 ##5 ##6 ##7 { ##3 \S ##4#2 #3##6 } \N 9 8 7 6 5 4 3 2 1 0 #2 % \t * #3#4 #3 } % \small \begin{array}{l} \texttt{\stars {23}} \\[-.5ex] \stars{23} \end{array} \endgroup$

This alternate approach performs $\small 10$-fold multiplication by approximating $\small \surd 5$ with a matrix and by treating cumulative stars as a vector  $\small [ \, \texttt{#3 #4} \, ] \,$ that is almost always just  $\small [ \, \texttt{#3 -} ~ ] \,$. The $\small ~ \texttt{#3#4 #3} ~$ in $\small \texttt{\N}$ economically serves as two different matrices when appended, as a whole or in part, to $\small \, \texttt{#3} \,$.

$$\small \begin{array}{lll} \texttt{#3} ~~~{\sf \&}~~~ \texttt{#3#4 #3} & \to ~~~ [ \, \texttt{#3#3#4 #3} \, ] & = ~~~ [ \, \texttt{#3 -} ~ ] ~ \displaystyle \bigg[ \, { 2 ~~ 1 \atop 1 ~~ 0 } \, \bigg] ~~~\sim ~~~ [ \, \texttt{#3 -} ~ ] \kern1mu \cdot \kern2mu \surd 5 \\[.5ex] \texttt{#3} ~~~{\sf \&}~~~ \texttt{#3} & \to ~~~ [ \, \texttt{#3#3 -} ~ ] & = ~~~ [ \, \texttt{#3 -} ~ ] ~ \displaystyle \bigg[ \, { 2 ~~ 0 \atop 0 ~~ 0 } \, \bigg] ~~~ = ~~~ [ \, \texttt{#3 -} ~ ] \kern1mu \cdot \kern2mu 2 \end{array}$$

The first matrix, derived from $\small ~ \texttt{#3#4 #3} \kern1mu$, is multiplied twice. Then the second, derived from $\small \, \texttt{#3} \,$.

$$\small [ \, \texttt{#3 -} ~ ] \kern 1mu \cdot \kern 2mu ( \kern-2mu \surd 5 )^2 \kern-1mu \cdot \kern1mu 2 ~~~\sim ~~~ [ \, \texttt{#3 -} ~ ] ~ \bigg[ \, { 2 ~~ 1 \atop 1 ~~ 0 } \, \bigg] \raise2.5ex{\scriptsize 2} ~ \bigg[ \, { 2 ~~ 0 \atop 0 ~~ 0 } \, \bigg] ~~~ = ~~~ [ \, 10 \cdot \texttt{#3 -} ~ ]$$

Layout of this matrix-oriented alternative’s progression through $\small\texttt{\N}$:

.     space after possible % = c   nnn = 3 spaces after next digit
.    3 spaces after skip = fff |   |           ssssss = 6 spaces after skip
.      space after digit = d | |   |             |           aaaaaaa = 7 spaces after added stars
.                          | | |   |             |              |
.                          | | |   |             |              |
.                         _dfffc_nnn          ssssss_________aaaaaaa                  zzzzzzz
.   \N  9     8  .  .  .  2     1     0   #2 %      \texttt *             #3#4      #3              }
.
.   appends  \texttt *  to      _dfffc_nnn    ssssss_________aaaaaaa                  zzzzzzz
.   cumulative stars in #3      1     0   #2 %      \texttt *             #3#4      #3              }
.
.   halt when #2 contains               _dfff_cnnn           ssssssaaaaaaa            zzzzzzz
.   no further digits                   0    %      \texttt *             #3#4      #3              }
.
.   triggers multiplication           _d ---> fffc___________nnnssssss________________aaaaaaazzzzzzz
.   of  #3 #4  by ~sqrt(5)            0   #2 %      \texttt *             #3#4      #3              }
.
.
.   Leading digit \texttt triggers                  _______d fffcnnnssssss____________aaaaaaazzzzzzz
.   multiplication by ~sqrt(5)                      \texttt *             #3#4      #3              }
.
.
.   Leading digit * triggers                                _dfffcnnn         ssssss__aaaaaaazzzzzzz
.   multiplication by 2                                     *             #3#4      #3              }


### Previous Solution, progress along the way

While this solution weighs in at 124  108  75 replacement tokens that include  8    7 6  $\small\texttt{\def} \,$ macros, one of which is dynamic, a heavy toll is exacted during execution, with macro overrun at 1000 decimal, 854 hexadecimal (2132 decimal) and 10000000000 binary (1024 decimal) stars.

.     $$\require{begingroup}\begingroup . % . \def \stars #1{ \Throw #1 \Throw \Skip . } % ^spaces^ (space at line break needed too) . \def \Throw #1#2#3 #4#5 . { #4 #2#3 #4#5 . \StarDigit#1} . % ^no^spaces (line break needed) . % . \def \Skip #1 . { } . \def \StarDigit #1#2 { % e.g, \StarDigit 7*****[space] --> 57 stars . \DoN #1 {\texttt* \Skip } . \DoN A { #2 \Skip} . } % ^space (also A = 10) . \def \DoN #1#2{ % e.g, \DoN 3 {\text{Do me.}\Skip} . \def \N ##1#1{} . \N A #2 9 . #2 8 . #2 7 . #2 6 . #2 5 . #2 4 . #2 3 . #2 2 . #2 1 . #2 0 } . \stars{57} . \endgroup$$


Three features of this solution remain original, though not necessarily novel.

1. Use of a general-purpose repeater macro, $\small\texttt{\DoN}$, that can produce a variable number of stars and can multiply by 10 a recursive section of star-producing code.

2. The calls $~\small\texttt{\DoN}\,\small\texttt{#1}\,\small\texttt{{\texttt* \Skip}}~$ and $~\small\texttt{\DoN}\,\small\texttt{A}\,\small\texttt{{#2 \Skip}}~$ include incomplete calls to $\small\texttt{\Skip}$, declared as having a parameter, so that the line in $\small\texttt{\DoN}$: $$\small\texttt{ \N A #2 9 #2 8 ... 3 #2 2 #2 1 #2 0 }$$ effectively becomes, but with 8 fewer source-code tokens: $$\small \texttt{ \N A #2 \Skip 9 #2 \Skip 8 ... 3 #2 \Skip 2 #2 \Skip 1 #2 \Skip 0 }$$ (Do not attempt to breach code levels like this outside of a controlled puzzling zone.)

3. Reversal of digit order allows Horner’s Method, conjured and explained well in Davide Cervone’s answer, to be applied without storing intermediate results. Multiplication here means repetition. \small \begin{align} 257 ~ \to ~ & \texttt {\StarDigit7} \, \texttt {\StarDigit5} \, \texttt{\StarDigit2} \\[9mu] = ~ & \texttt {\StarDigit7} + 10 \, ( \kern2mu \texttt {\StarDigit5} \, \texttt{\StarDigit2} \, ) \\[9mu] = ~ & \texttt {\StarDigit7} + 10 \, ( \kern2mu \texttt {\StarDigit5} + 10 \cdot \texttt{\StarDigit2} \, ) \\[9mu] = ~ & \texttt {*******} + 10 \, ( \texttt {*****} + 10 \cdot \texttt{**} ) \\[9mu] = ~ & 100 \cdot \texttt {**} + 10 \cdot \texttt {*****} + \texttt{*******} \end{align}

### Initial solution, binary stars with overlapping templates

$$\require{begingroup}\begingroup % \def \0 #1\starrise#2\eternity{ #1\starrise\0#2\eternity } \def \Zer #10#2#3\Zer#4#5#6#7\eternity{ #1#6#4#2#3\Zer#4#5#6#7\eternity } \def \1 #1\starrise#2\eternity{ #1\starrise\1#2\eternity } \def \One #11#2#3\One#4#5#6#7\eternity{ #1#6#4#2#3\One#4#5#6#7\eternity } \def \stars #1{ \Zer \One #1 \. 0\Zer\Zer\ZerX \0\_ 1\One\One\OneX \1\_ \starrise \_ \eternity } \def \ZerX { \def\Zer{} \def\0{} } \def \OneX { \def\One{} \def\1{} } \def \ZerStars #1\_{#1\_#1\_} \def \OneStars #1\_{\texttt*#1\_#1\_} % \def \starrise { \let\0=\ZerStars \let\1=\OneStars } \def \eternity {} \def \_ {} \def \. {} \stars{111001} \endgroup$$

These stars are produced by $\small\texttt{\stars{111001}}$. An equivalent decimal version was presented too, but it was just plain unwieldy and is best forgotten. This binary version weighed in at around 180 replacement tokens.

$$\require{begingroup}\begingroup % \def \0 #1\starrise#2\eternity{ #1\starrise\0#2\eternity } \def \Zer #10#2#3\Zer#4#5#6#7\eternity{ #1#6#4#2#3\Zer#4#5#6#7\eternity } \def \1 #1\starrise#2\eternity{ #1\starrise\1#2\eternity } \def \One #11#2#3\One#4#5#6#7\eternity{ #1#6#4#2#3\One#4#5#6#7\eternity } \def \stars #1{ \Zer \One #1 \. 0\Zer\Zer\ZerX \0\_ 1\One\One\OneX \1\_ \starrise \_ \eternity } \def \ZerX { \def\Zer{} \def\0{} } \def \OneX { \def\One{} \def\1{} } \def \ZerStars #1\_{#1\_#1\_} \def \OneStars #1\_{\texttt*#1\_#1\_} % \def \starrise { \let\0=\ZerStars \let\1=\OneStars } \def \eternity {} \def \_ {} \def \. {} \stars{111001} \endgroup$$


The underlying mechanism takes advantage of how MathJax easily parses overlapping templates.


LINE         \Zer \One ... 0  1  ... \. 0 \Zer \Zer \ZerX .. 1  \One  \One \OneX

early
0 template   \Zer #1       0  #2 #3       \Zer #4

early
1 template        \One #1     1  #2 #3                          \One  #4

last
1 template                       \One #1                     1  #2 #3 \One #4



But the overlapped parsing had to be worked around in order to get the resultant digits to be evaluated in their correct order. In what amounts to an additional two passes, each parsed digit moves itself to the end before actually being evaluated.


LINE after parsing               \1  \1  \0  \1  ...

1st
order of  parsing               2nd 3rd     4th

desired order of evaluation           4th 3rd 2nd 1st
..........................
:                          :
"second" pass                                           V
\1 \1 \0 \1 ... \starrise
\1 \0 \1 ... \starrise  \1
\0 \1 ... \starrise  \1 \1
\1 ... \starrise  \0 \1 \1
... \starrise  \1 \0 \1 \1

• I didn't mean to say that there is a decimal-specify method, only that your approach clearly can be modified to work for any base, and that is nice. Mine also can be, and perhaps all could be, but having one that does was not part of the original challenge. – Davide Cervone Jul 22 '16 at 12:25
• Hint posted – Davide Cervone Jul 22 '16 at 14:08
• Alas, I don't think MathJax is up to the challenge of doing the counting itself. I actually meant write a javascript function to do it and post that in a code widget so that you can run it within the page. It would have a textbook where you paste your MathJax and it will report the result. – Davide Cervone Jul 28 '16 at 20:53
• Counting braces as one is a good idea, I think. Under those conditions, I think my solution is 91 tokens. I will adjust the wording of the problem. – Davide Cervone Jul 28 '16 at 21:17
• I'm looking forward to your dragon curve puzzle, @humn. There are several limitations on MathJax execution. MathJax has a maximum number of macro substitutions that it will make (in order to avoid infinite recursion), and a maximum size of its input buffer (so something like \def\x{\x abcd} won't make infinitely long input strings). The size of both limits can be set in MathJax's configuration (but we can't change that as users in SE sites). There are also browser-imposed limitations on run time, which is what you are seeing in Firefox. Those differ by browser, as you suspect. – Davide Cervone Jul 31 '16 at 15:34

## A Hint (My Solution is Below)

One of the key components of my solution (and one that others have asked about) is a macro that, given a single digit, produces that many stars. There are several approaches to this. One of them is to use one macro to produce another macro, and use the data given to the first macro as part of the template for the second. Here's what I mean:

\def\s#1{
\def\*##1#1##2##3.{##2}
\*  0{} 1{*} 2{**} 3{***} 4{****} 5{*****} 6{******}
7{*******} 8{********} 9{*********}.
}


With this definition, \s3 would generate ***, while \s0 would produce no stars:

$$\require{begingroup}\begingroup \def\s#1{ \def\*##1#1##2##3.{##2} \* 0{} 1{*} 2{**} 3{***} 4{****} 5{*****} 6{******} 7{*******} 8{********} 9{*********}. } \begin{array}{ll} \texttt{\s3}\quad&\s3\\ \texttt{\s7}\quad&\s7\\ \texttt{\s0}\quad&\s0 \end{array} \endgroup$$

The key is to use the #1 passed into \s when creating the macro \* internally. The result of \s3 is to define \*#13#2#3.{#2}, which read everything up to the first 3 (and throws it away), then reads the next argument (the collection of stars) and finally reads everything up to the . (and throws it away). It returns the #2, which is the proper number of stars. After defining \*, we call it with the proper data for each digit, and \* chooses the right one based on the value of the #1 passed to \s; the others are discarded by \*.

There are other ways to approach this as well that don't rely on listing stars explicitly, but generate them recursively. One thing to think about is that in the string 0123456789, the number of characters before the digit $n$ is the number of stars you would need for that $n$.

I hope these give you some ideas for new solutions to the puzzle.

## A New Solution

This is a solution that has 71 tokens, 4 static definitions, and 1 dynamic one. I have left my previous solution in the page below, since it includes an interesting use of % as both a delimiter and a loop terminator that is not present in this solution.

$$\require{begingroup}\begingroup \def\stars#1#2 {\D#1 \S % \texttt {#2}} \def\D#1 #2{#2#1} \def\S#1#2 #3 #4{ \def\N##1#1{} \N9\*8\*7\*6\*5\*4\*3\*2\*1\*0\stars{#2}#4#4#4#4#4#4#4#4#4#4 } \def\*#1#2 {#2* } \stars{57} \endgroup$$

See my other solution below for a description of Horner's method, and how it applies to this problem. The new code is given below:

$$\require{begingroup}\begingroup \def\stars#1#2 {\D#1 \S % \texttt {#2}} \def\D#1 #2{#2#1} \def\S#1#2 #3 #4{ \def\N##1#1{} \N9\*8\*7\*6\*5\*4\*3\*2\*1\*0\stars{#2}#4#4#4#4#4#4#4#4#4#4 } \def\*#1#2 {#2* } \stars{57} \endgroup$$


The \stars macro will be used recursively to perform Horner's method. The stars themselves will be stored directly after it, and the idea is to have \stars{ab} duplicate the stars that follow it 10 times, then produce a more stars, and then call \stars{b} followed by the larger number of stars. The \stars macro sets up a test to see if there are more digits to be processed, and arranges for the stars to be output via \texttt if not.

This uses \D to decide if there are more stars to be created; i.e., it detects \stars{} where the parameter is blank using the technique that we have seen for controlling loops before. It either calls \S if there are more digits to process, or moves the % to the front (commenting out the \S that will be in #1 when there are no more digits) and letting the \texttt call end the loop and print the stars.

The \S macro reads the next digit as #1 and any additional digits as #2; it reads (and discards) the %, newline, and \texttt as #3, and then gets the current set of stars as #4. It then defines \N to look for the digit in the list of digits that will follow, and throw away the higher ones; at the same time, it sets up the recursive call to \stars with the remaining digits, and duplicates the original stars 10 times following it. The \N call then throws away the data for the higher digits, and leaves the \* call for the proper digit. E.g., if the digit was a 4, then \N will remove the 9\*8\*7\*6\*5\*4 and leave \*3\*2\*1\*0 left to be processed.

The \* macro reads (and discards) the digit that follows it, and (reading past \stars{nn} and any existing stars) puts a star at the end of the line. Each \* does the same, meaning that 4 new stars will be added at the end of the line, in addition to the 10 copies of the stars that had been there previously.

After the last \* call, we have \start{nn} followed by the updated list of stars, and the process repeats. The \D call decides if more stars need to be added, and if there are no more digits, prints the result.

Here is a live trace version that produces 24 stars:

$$\require{begingroup}\begingroup \let\TT=\texttt\def\texttt#1{\\&&\color{green}{\TT{#1}}} \def\-#1#2{\scriptsize\TT{#1}& \longrightarrow&\break{#2}\\} \def\>#1#2 #3%@{\-{#1 #2}{#3}#3%@} \def\<#1#2 #3 #4 #5%@{\-{#1 #2}{\def\N##1#3{} #5}#4 #5%@} \def\break#1{\def\&{}\line.#1\endbreak\nextline \endbreak\endline} \def\line#1 #2\endbreak#3{#3#1 #2\endbreak#3} \def\nextline.#1 {\&\def\&{&&}\scriptsize\TT{#1}\\\line.} \def\endline.#1\endbreak#2\endline{\&\scriptsize\TT{#1}} \def\stars#1#2 {\>\stars[#1][#2] \D#1 \S % \texttt {#2}} \def\D#1 #2{\>\D[#1][#2] #2#1} \def\S#1#2 #3 #4{\<\S[#1][#2][#3][#4] #1 \def\N##1#1{\>\N[##1] } \N9\*8\*7\*6\*5\*4\*3\*2\*1\*0\stars{#2}#4#4#4#4#4#4#4#4#4#4 } \def\*#1#2 {\>\*[#1][#2] #2* } \begin{array}{lcl} &&\color{green}{\TT{\stars{24}}}\\ \stars{24} %@ \end{array} \endgroup$$

The initial \stars{24} call is at the top in green. The macros and their parameters are shown on the left, followed by an arrow, and the results of the macro expansion on the right (the complete input string is shown, with line breaks where appropriate). The final 24 stars are shown in green at the bottom.

## Solution Influenced by humn's Results

This is a solution that has $\require{cancel}\cancel{99}$ $\cancel{82}$ 80 tokens, $\cancel{6}$ 5 static definitions, and 1 dynamic one.

$$\require{begingroup}\begingroup \def\stars#1{\D%#1 \T \texttt} \def\D#1%#2#3 #4{#4{#1}%#2#3 #4} \def\T#1%#2{\S#2#1#1#1#1#1#1#1#1#1#1%} \def\S#1{\def\N##1#1{} \N9\*8\*7\*6\*5\*4\*3\*2\*1\*0\D } \def\*#1#2 {#2 *} \stars{57} \endgroup$$

The idea behind this is that a number in base 10 can be considered as a polynomial evaluated at $x=10$. For example, the number $15{,}392$ can be written

\begin{align} 15{,}392 &= 1\cdot 10{,}000 +5\cdot 1{,}000 + 3\cdot 100 + 9\cdot 10 + 2\\ &= 1\cdot 10^4 + 5\cdot 10^3 + 3\cdot 10^2 + 9\cdot 10 + 2\\ &= 1x^4 + 5x^3 + 3x^2 + 9x + 2\qquad\text{where x=10.} \end{align}

In general, the digits of the number are the coefficients of the terms in the polynomial. There is a computationally efficient means of evaluating a polynomial called Horner's Method, which rewrites the polynomial by factoring out $x$'s, as in:

\begin{align} x^4 + 5x^3 + 3x^2 + 9x + 2 &= x\cdot(x^3 + 5x^2 + 3x + 9) + 2\\ &= x\cdot(x\cdot(x^2 + 5x + 3) + 9) + 2\\ &= x\cdot(x\cdot(x\cdot(x\cdot 1+5) + 3) + 9) + 2 \end{align}

so

$$15{,}392 = 10\cdot(10\cdot(10\cdot(10\cdot 1 + 5) + 3) + 9) + 2.$$

This says to take the first digit, 1, multiply that by 10 and add the next digit, 5. Then multiply the result by 10 and add the next digit, 3. Then multiply that result by 10 and add the next digit, 9, and finally multiply that by 10 and add the final digit, 2. This is a recursive process the involves only two things: multiplying by 10 and adding a single digit.

How does this relate to producing stars? Well, if we have a way to produce 0 through 9 stars based on the digit, and a way of duplicating the current number of stars 10 times, then we can use the recursive process to generate the proper number of stars. That is what my code does:

$$\require{begingroup}\begingroup \def\stars#1{\D%#1 \T \texttt} \def\D#1%#2#3 #4{#4{#1}%#2#3 #4} \def\T#1%#2{\S#2#1#1#1#1#1#1#1#1#1#1%} \def\S#1{\def\N##1#1{} \N9\*8\*7\*6\*5\*4\*3\*2\*1\*0\D } \def\*#1#2 {#2 *} \stars{57} \endgroup$$


This sets up a loop like the ones we've seen before via the macro \D. The stars are stored following the \D up to the % (it starts out empty, since we haven't created any stars yet). The desired number of stars is stored to the right of the % up to the first space. Then we have the two commands \T and \texttt, the first being performed when there are still digits to process, and the second when we run out of digits. The \D macro reads the stars as #1, then the next digit as #2 and the remaining digits as #3, and finally the command to perform as #4. (When there are no more digits, #2 will read the \T, the #3 will be empty, and #4 will be the \texttt.) The \D macro simply puts everything back in place where it was (making sure the stars have braces around them), but copies the #4 to the beginning of the line, so that it will act on the stars and digits. That is, the \D is simply there to choose between \T and \texttt.

The \T command reads the stars and the first digit of the number (and we are guaranteed there is one at this point); its job is to perform the "multiply by 10 and add the next digit" action. Since the current number of stars is in #1, we do the "multiply by 10" by including 10 copies of #1 in the replacement text for \T. We also insert \S followed by the digit pulled from the number; we need to insert that many stars (to "add the digit"), and that is what \S does.

The \S macro uses a dynamic macro (\N) that uses the digit as a delimiter (as discussed in the hint). We could simply have used the \* macro from the hint, but because of all the stars and braces, that would add a lot of characters to the length of our solution. Instead, we use a macro based on humn's digit cascade approach. The \N macro is passed the data 9\*8\*7\*6\*5\*4\*3\*2\*1\*0\D, and it discards everything up to the digit that it was passed. For example, if we had \S4, then \N eats everything up to (and including) the 4, leaving \*3\*2\*1\*0\D.

The \* macro is the next thing to be executed. It reads the digit that follows (and throws it away), then everything up to the \D; it puts that back, along with the \D and adds a star after the \D. The effect is to leave us with \*2\*1\*0\D*. This leaves \* as the next thing to execute, and again it removes a digit and puts a star after the \D leaving \*1\*0\D**. It runs two more times, producing first \*0\D*** and then \D****. So the result is to add 4 more stars after the \D and leave \D as the next thing to perform. That is, \S4 adds 4 stars to the ones already following the \D (the ten copies of what was there before) and then sets up \D as the next thing to execute.

That puts us back to the starting point again, but with the proper number of stars between \D and %, and one fewer digit following the %. The \D macro either terminates with \textt if there are no more digits, or calls \T again, which duplicates the current stars 10 times and adds in the number given by the next digit. That is, \D and \T together perform Horner's method on the polynomial with the digits as coefficients, evaluated at $x=10$.

When all the digits are processed, the \textt command is moved to the front. Since \D guarantees that the stars have braces around them, this prints the final number of stars in the monospaces \tt font. Because we used % as the delimiter between the stars and the digits, when \texttt{...} is complete, the % then acts as a comment character, causing the remainder of the line to be ignored. So the loop terminates with no additional output.

Here is the live trace for \stars{24}:

$$\require{begingroup}\begingroup \def\X#1.{\texttt{#1}} \let\TT=\texttt\def\texttt#1{\\\color{green}{\TT{#1}}} \def\=#1#2{\quad\small\TT{#1} \longrightarrow\\\scriptsize\color{red}{\TT{#2}}} \def\>#1#2 #3.{\={#1 #2}{#3}\\#3.} \def\stars#1{\>\stars[#1] \D%#1 \T \texttt.} \def\D#1%#2#3 #4{\>\D[#1][#2][#3][#4] #4{#1}%#2#3 #4} \def\T#1%#2{\>\T[#1][#2] \S#2#1#1#1#1#1#1#1#1#1#1%} \def\S#1{\>\S[#1] \def\N##1#1{\>\N[##1] } \N9\*8\*7\*6\*5\*4\*3\*2\*1\*0\D } \def\*#1#2 {\>\*[#1][#2] #2 *} \begin{array}{l} \scriptsize\color{red}{\TT{\stars{24}}}\\ \stars{24} \end{array} \endgroup$$

Here, the red lines represent the current $\rm\TeX$ string to be processed, and the black lines give the macros and their parameters. The final output is in green at the bottom. There is an artifact of the self-trace code in the lines that show the definition of \N, since the definition includes the tracing code (the \>\N[##1], which should really not be shown), but I couldn't find a decent way to avoid it. Also, the line breaks show as spaces in the output (due to the fact that line breaks in web pages are treated as spaces).

Theoretically, the program could create an arbitrary number of stars, but the limitations imposed by MathJax on the number of macros calls allowed (in order to avoid run-away recursive macros) means we can produce 5049 stars, but not 5050. The approach could be adapted to other bases, but I haven't calculated the highest numbers possible for those.

• Really shows why everything is called a macro. Source code is continually "preprocessed." This just hasn't come up with the macros I've made for (La)TeX typesetting. How liberating! – humn Jul 22 '16 at 14:14
• Yes, the fact that $\rm\TeX$ is a macro language has significant implications for how it can be used. At least we don't have to worry about the difference between TeX's mouth and its stomach in MathJax (these are the actual technical terms used by Knuth in the $\rm{\TeX}Book$, and the distinction between the two also has big implications for macro writing in {\rm\TeX}. – Davide Cervone Jul 22 '16 at 15:06
• This is a fairly general technique that can be used to create if-then type conditionals, as well as multi-valued switch statements. Think of the stars as being collections of control sequences to be processed from which we pick one collection based on a condition. – Davide Cervone Jul 22 '16 at 15:23
• Clever use of % again, @humn, but I'm going to leave mine as is, since I like to make all that stars appear in one \textt{} call (technically, this makes the the result one item in the underlying math structure, whereas separate \texttt* calls are each a separate item). Of course, the incomplete macros in the loop terminate are what you started with your \let approach. It is also common in $\rm\TeX$ programming to take advantage of the macro language by including a macro at the end of another one, and have its parameters come from the tokens later in the input string. – Davide Cervone Jul 31 '16 at 15:29
• Note that it also occurs with the \D at the end of the \N call as well. – Davide Cervone Jul 31 '16 at 15:29

Partial

We could build upon the reflection solution by doing something like:

 \require{begingroup}\begingroup
\def\C#1#2|{\D#1|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\T}
\def\stars#1{\G|#1|}
\def\G#1|#2|{\R :#2|\R|\S}
\def\R#1:#2#3|#4{#4 #2#1:#3|#4}
\def\S|#1:#2\S{\C#1|}
\def\T#1{terminate}
\stars{123}
\endgroup

For \stars{123}:

$$\require{begingroup}\begingroup\def\C#1#2|{\D#1|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\M#2|\T}\def\stars#1{\G|#1|}\def\G#1|#2|{\R :#2|\R|\S}\def\R#1:#2#3|#4{#4 #2#1:#3|#4}\def\S|#1:#2\S{\C#1|}\def\T#1{terminate}\stars{123}\endgroup$$

But I'm not quite sure how to:

1. recurse to \C with \M by implementing \T correctly (like \S); or
2. make \D3| produce *\D2| and similar for all the digits such that \D| and \D0| yield empty strings.
• I think you are right that a macro like \D3 to produce 3 stars (somehow) is a key component. Can you get that to work in isolation? I also think you are on the right track to do 10 copies of the 12 part. I don't think you want to reverse the order, however (though the looping structure of \R is certainly useful, here). For efficiency, you might think about producing the stars for the 12 part first, and then duplicate that 10 times, rather than doing all the work for 12 ten separate times. – Davide Cervone Jul 20 '16 at 17:41
• PS, your \stars and \G can be combined into one macro. – Davide Cervone Jul 20 '16 at 17:43
• See my hint post for one possible solution to your second question. – Davide Cervone Jul 22 '16 at 15:33
• see my answer above for an example of how to get this approach to work. – Davide Cervone Jul 28 '16 at 21:10