Shortest representation of an Underload number

Question

Flavour text

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 : and * 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: (A):* = (A)(A)* = (AA).
• ::** is the Underload numeral 3: (A)::** = (A)(A):** = (A)(AA)* = (AAA).
• :::*** is the Underload numeral 4.
• :*:* is also the Underload numeral 4: (A):*:* = (AA):* = (AA)(AA)* = (AAAA).

In general, you will find that, if M and N are the Underload numerals M and N, then :N* is the numeral N+1, and MN is the numeral M×N.

The challenge

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 - OUTPUT.")

• 1 - .
• 2 - :*.
• 5 - ::*:** (2×2+1).
• 7 - ::*::*** (2×3+1) or :::**:** (3×2+1).
• 33 - ::*:*:*:*:** (2×2×2×2×2+1).
• 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 : and *, etc.

Answer 1

GolfScript (61 60 55 54 53 chars)

~:X'']({:A{.'.+'\*A{2$+}%~}%}*{,}${1\~X=}?{44/'*:'=}%

This is less tricky than my earlier version and takes a slightly different approach, but it's still brute force. We know that ':'X*'*'X*+ is a candidate solution, so if we generate all well-balanced strings up to that length and take the shortest one which evaluates to the right thing we can be certain to find one.

# Evaluate input and store the target number in X
~:X
# Seed the generator with the empty string
'']
# X times...
({
    # Store the array of strings so far into A
    :A
    # Generate A' by mapping each element
    {
        # Dup: this leaves an untouched copy of the current string
        .
        # Wrap the duplicate in .+
        '.+'\*
        # For each element in A, generate that element suffixed with the current string
        A{2$+}%~
    }%
}*
# Order by length
{,}$
# Find the first element which evaluates to X
{1\~X=}?
# tr .+ :*
{44/'*:'=}%

Thanks to Howard, from whose solution I've stolen a couple of 1-char tweaks.

Answer 2

Python 2.7 - 87 84 92

u=lambda n:n>1and min([u(i)+u(n/i)for i in range(2,n)if n%i<1]+[':'+u(n-1)+'*'],key=len)or''

Explanation:
This is a pretty straightforward solution. It recursively tests all possible representations of n as either the product of two numbers or as :(n-1)*, and then finds the minimum length solution. range(2,n) is necessary so that the recursion has bounded depth, and n<2 gives the base case.

Notes:
i and n/i are the two factors of n. The ... and ... or ... replacement for ... if ... else ... doesn't work because '' evaluates to false. min of strings gives one of the shortest strings. Python 2.7 saves 1 character by using / instead of //.

Edit: Moved the base case to the back of the expression, allowing me to use ... and ... or ... and shave a couple spaces.

Test cases:

u(1)
''
u(5)
'::*:**'
u(49)
'::*:*:*:*::***'

Answer 3

GolfScript (54 53 chars)

This is an approach which is in the spirit of Howard's (build strings which evaluate to the correct value and select the shortest, rather than brute force through candidate strings to find those which evaluate to the correct value), but is sufficiently different that I think it belongs in a separate answer.

~.''':*':s@,{):x,2>{:^~$x^/~$+{s\*}x^%*}%{,}$0=}/]((=

Online demo not available because it runs a buggy version of the interpreter.

# Let <N> denote the string which evaluates to N
# We want to enter the main loop with three values on the stack: <0> <1> <2>
# However, we'll never use <0>, so we can actually replace that with any value at all.
# Getting the input from underneath 3 items would normally use two stack manipulations.
# Trick: let's use the input value for <0>! (This gives a further bonus later).
# NB We store the value of <2> in the variable s
~.''':*':s@
# for x=1 to input_value ...
,{):x
    # for ^=2 to x-1 ...
    ,2>{:^
        # Use negative stack offsets to index the stack from the start
        # I.e. -1$ gets the first item on the stack, which is <0>
        # -2$ gets the second item on the stack, which is <1>
        # In general, val~$ gets <val>
        ~$x^/~$+
        # We have the string <^><x / ^> on the stack.
        # Increment it (x % ^) times to get a candidate <x>.
        {s\*}x^%*
    }%
    # Select a shortest string.
    {,}$0=
}/
# Group the stack into one array and select the appropriate offset,
# reusing that hacky <0> substitute for the offset.
]((=

Answer 4

GolfScript, 63 58 56 characters

~n./\{:v~[':*'1$*v,,2>{v,\%!},{.v=v,@/v=+}/]{,}$0=]}*-2=

The code takes input on STDIN and prints the result.

Examples:

> 49
:::**:*:*:*:**

> 1234
::::*:*:*:**:*:*:**::**::***

You can test your own cases online.

Answer 5

Brachylog 2, 30 (maybe eventually 26) bytes, language postdates challenge

Here's a function which works with the current Brachylog 2 implementation (and returns a list of character codes because the current implementation is having some issues with string handling):

∧.l∧?{ḋp~c×ᵐ{-₁↰₁:[42,58]c↻}ᵐc}

Try it online!

The language is still very new. Here's a 26 byte version of the program that should work according to the specification, but uses some unimplemented features, and thus isn't valid yet, but maybe will be in future (it's also even less efficient):

{ḋp~c×ᵐ{-₁↰₁:"*:"c↻}ᵐc}ᶠlᵒh

Explanation

∧.l∧?{ḋp~c×ᵐ{-₁↰₁:[42,58]c↻}ᵐc}
∧.l∧?                            Evaluation hint: try shortest outputs first
     {                        }  Define an inner function
      ḋ                          Prime factor decomposition of the input
       p                         Find a permutation
        ~c                       Find an inverse concatenation (i.e. partition)
          ×ᵐ                     Take the product of each set inside the partition
      ḋp~c×ᵐ                     Find a decomposition into factors ≥ 2
            {              }ᵐ    For each of those factors:
             -₁                  Decrement it
               ↰₁                Call the inner function recursively
                 :[42,58]c       Append "*:" (as character codes)
                          ↻      Move the last element to the start
                             c   Append the results together

The basic idea is fairly simple: we alternate between decomposing the number into (1 or more) factors (not necessarily prime factors, but factors of 1 are not allowed), and expressing each of those as 1 + (a representation obtained from a recursive call). This is guaranteed to search all possible Underload representations of the number (we can apply a multiplication stage "twice in a row" by multiplying together more than 2 numbers, and an increment stage twice in a row via separating them with a multiplication stage that multiplies together just one number). We don't need an explicit base case, because decomposing 1 into prime factors gives us an empty list, and thus we construct it with a multiplication stage that multiplies zero numbers together.

The program is fairly inefficient, especially because the evaluation order hint I gave (generate answers shortest to longest in terms of the size of the eventual output), while solving the "shortest" part of the question, isn't that great in terms of actually making the program complete quickly (a much more useful hint would be "generate only the shortest answer at each recursive stage", but that takes more bytes…). Additionally, ḋp~c×ᵐ can generate multiplicative partitions several times each, making the program do a lot of redundant work.

Answer 6

Jelly, 33 bytes, language postdates challenge

ÆḌḊµ⁹÷Ñ;Ñð€
’ß”:;;”*W;ÇLÞḢµ“”>1$?

Try it online!

A straightforward brute force solution.

Explanation

Main program

’ß”:;;”*W;ÇLÞḢµ“”>1$?
              µ  >1$?  If input is greater than 1, then:
’ß                       Run recursively on the input - 1
  ”:;                    Prepend a colon
     ;”*                 Append an asterisk
        W;               Cons to:
          Ç                the result of the helper, on {the original input}
           LÞ            Sort by length
             Ḣ           Take the first (i.e. shortest) result
               “”      Otherwise, return an empty string

The main program uses the helper function to enumerate all possible ways to produce the value via multiplication, then tries producing the value by addition, and returns the shortest possibility. It also handles the base case (an input of 1).

Helper function

ÆḌḊµ⁹÷Ñ;Ñð€
ÆḌ µ     ð€            For all proper factors of the input
  Ḋ                    except the first (i.e. 1):
    ⁹÷                   Divide it into the input;
      Ñ                  Run the main program on it;
       ;                 Append the result of:
        Ñ                  the main program run on {the factor}

The helper function tries all possible methods of expressing the input as a multiplication of two numbers, and mutual-recursively calls the main program in order to get at their shortest representations.

Answer 7

GNU Prolog, 96 bytes

v(N)-->{N#=1};{N#=A*B,A#<B,B#<N},v(A),v(B);{N#=M+1},":",v(M),"*".
s(N,S):-length(S,_),v(N,S,[]).

The first line is a grammar that implements Underload evaluation, and works in the reverse direction (actually, it doesn't quite work in the forward direction due to the A#<B constraint; change this to A#<N for a slower program that works both ways round). The second line defines the function-like predicate s (which is the function that's implemented as a solution to this program) which finds the shortest possible string which evaluates to the number given as input (this is frustratingly verbose for what's a relatively simple task, but that's Prolog for you…).

The program should be pretty self-explanatory, given that it's more or less a direct translation of the specification to a grammar, and then to Prolog syntax; the definition of v says that N is 1 in an empty string, or N is A × B (with A less than B less than N) and the string is the concatenation of v(A) and v(B), or N is M + 1 and the string is : concatenated with v(M) concatenated with *. The second line is a bit subtler; length(S,_) means "S has some length", but specifying this as the first thing on the line acts as a hint to the Prolog implementation that it should check the shortest lengths first (which means we'll get the shortest possible length for a return value).

Answer 8

J - 81 char

For posterity, this was the best that I could do in J.

_2{::(0&(][,0{<@;"1@({~#(#~]-:"1<.)@(],.%)2}.i.@#)(/:#&>)@,':'<@,'*',~>@{:),~)&a:

We create a list of results, beginning with two empty strings (that's the ,~ and a:) representing 0 (never used) and 1, and then iterate a verb over them (sneaky use of hooks, trains and &) that appends the next number's shortest representation.

The actual verb that we iterate uses the length of the list as an indicator of what number we are operating on. First, we factor this number into pairs of factors (#(#~]-:"1<.)@(],.%)2}.i.@#), and retrieve each pair by pulling from the array ({~). We turn each of those pairs (there could be 0 of them if the number is prime) into single strings (<@;"1).

Then we append to that list the entry for the previous result bracketed by : and *, and sort this list by length ((/:#&>)). Finally, we take the first result from this list (0{) and append that to the end of the base array ([,). When the loop is done iterating, we have a list of length 2 more than the input, starting at 0. So what we have to return is the next-to-last string (_2{::).

   un =: _2{::(0&(][,0{<@;"1@({~#(#~]-:"1<.)@(],.%)2}.i.@#)(/:#&>)@,':'<@,'*',~>@{:),~)&a:
   un 49
::*:*:*:*::***
   un 1234
:*::*:*:*::*::***::*::*:****
   un 10010
:*::*:*::***::*:*:*:*:*:*:*::***
   2 * (1 + 3 * 2^2) * (1 + 3 * 2^7)
10010
   6!:2 'un 10010'   NB. time in seconds
19.5539