The stack-based esolang Underload has some interesting ties to functional programming. One of them is its treatment of the numerical datatype—like the lambda calculus, you represent the natural number N by a function which perform an action N times.
To make things simple, we will only consider only the following subset of Underload commands:
:- This command duplicates the top item on the stack.
*- This command concatenates the top two items on the stack into a single item.
We define an Underload numeral N as a string of
* which, when executed, consume the top item on the stack, and produce N copies of that item concatenated together. Some examples:
- There are no Underload numerals 0, -1, 1/2, π.
- The empty string
is the Underload numeral 1, because it leaves the stack untouched.
:*is the Underload numeral 2, because it duplicates the top item, and then concatenates those two copies together into a single item:
::**is the Underload numeral 3:
:::***is the Underload numeral 4.
:*:*is also the Underload numeral 4:
In general, you will find that, if
N are the Underload numerals M and N, then
:N* is the numeral N+1, and
MN is the numeral M×N.
Your task is to write the shortest program (taking input on STDIN) or function (taking input via argument) which produces the shortest representation of the Underload numeral for its input as a string. That is to say, if the input is a positive natural number N > 1, you must produce an Underload numeral N whose length in characters is less than or equal to that of every other Underload numeral N.
Sample inputs and outputs: ("Input -
- 1 -
- 2 -
- 5 -
- 7 -
- 33 -
- 49 -
::*:*:*:*::***(16×3+1, length 14) but not
::*::***::*::***(7×7, length 16).
If the input is not a positive natural number, you are free to return an error, produce undefined behaviour, or even fail to terminate. An explanation of your submission's method of finding the answer is appreciated.
Standard loophole restrictions apply: no extra input, no web requests, output/return value must be exactly the answer and not an infinite random stream of