Shortest representation of an Underload number

13

2

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.

algorithmshark

Posted 2014-04-22T21:12:53.697

Reputation: 8 144

@Geobits I've said nothing about execution time, so as long as you can prove it'll give the correct answer eventually, you're good. – algorithmshark – 2014-04-23T03:00:01.433

2

This problem relates to addition chains; specifically, the length of the correct answer for input x is 2*A117498(x) where A117498 gives the optimal combination of binary and factor methods for finding an addition chain.

– Peter Taylor – 2014-04-24T12:04:20.720

Answers

4

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.

Peter Taylor

Posted 2014-04-22T21:12:53.697

Reputation: 41 901

Haha, an input of 3 takes more then three seconds to execute on the web interpreter. Golfing at its finest. – algorithmshark – 2014-04-23T17:38:37.600

@algorithmshark, you can speed it up quite a bit with a spot of deduplication. Insert .& just after the inner loop (i.e. between ~}% and }*. – Peter Taylor – 2014-04-23T17:46:37.543

4

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)
'::*:*:*:*::***'

isaacg

Posted 2014-04-22T21:12:53.697

Reputation: 39 268

1

"min of strings gives one of the shortest strings" isn't true unless you supply the optional argument key=len. It's gives the lexicographically earliest string. (Example). Since '*' < ':' this means that you have a bias towards solutions involving powers of 2, but are they always the shortest?

– Peter Taylor – 2014-04-24T10:32:21.317

1Answer: actually the bias is more complicated, but it doesn't always give the correct answer. The smallest counterexample is u(33), for which sorting lexicographically gives the 14-char ::**::*::*:*** but sorting by length gives the 12-char ::*:*:*:*:** – Peter Taylor – 2014-04-24T10:52:00.683

1I never knew that about Python string comparisons. I have updated my answer. – isaacg – 2014-04-24T15:34:50.047

4

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.
]((=

Peter Taylor

Posted 2014-04-22T21:12:53.697

Reputation: 41 901

It would be possible to shave one by replacing 3+ with ) (exploiting the fact that []0= leaves nothing on the stack) if it weren't that []2> leads to an error. – Peter Taylor – 2014-04-24T09:54:06.667

[]2> yields [] without error. – Howard – 2014-04-24T12:34:16.507

@Howard, ah, golfscript.apphb.com must be running an old version. But it turns out that I was wrong, because that replacement leads to getting the wrong output for input '1'.

– Peter Taylor – 2014-04-24T13:09:00.090

Which you can fix with ((= instead of -1=. – Howard – 2014-04-24T13:37:01.670

And golfscript.apphb.com indeed runs an old version, the nested loops example doesn't work.

– Howard – 2014-04-24T13:40:25.113

@Howard, true, I'd experimented with that earlier but it didn't give a saving by itself. – Peter Taylor – 2014-04-24T13:41:03.020

So @w0lf prevents further enhancements ;-) Actually golfscript.apphb.com saved me several times when I was away from my computer but urgently needed to do some golfing.

– Howard – 2014-04-24T13:45:49.513

I was experimenting with x^%.s*/* now for quite some time (which would save 1 char if it wasn't for the zero case). Anyways, you can get rid of the variable s and replace it with -3$ - just to get remove a variable ;-) – Howard – 2014-04-24T16:28:56.730

@Howard, I know, although I prefer 2~$ for consistency. – Peter Taylor – 2014-04-24T16:31:20.837

3

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.

Howard

Posted 2014-04-22T21:12:53.697

Reputation: 23 109

Wow, I thought that a factoring based approach would be quite a bit longer than a brute force approach. – Peter Taylor – 2014-04-23T10:32:53.093

@PeterTaylor I thought so too but it turned out that it is not the case. Moreover, my brute force solution was a bit longer than yours ;-) – Howard – 2014-04-23T12:52:58.513

Would you mind explaining what each portion does? I can only follow up until the :x(= bit. Also, +1 for being able to run 49 in a reasonable amount of time. – algorithmshark – 2014-04-23T17:45:44.407

@algorithmshark I'm still working on the solution so it might still change a lot (as it just did). Mainly, the part x,2>{x\%!}, gives all true divisors of x, {.v=x@/v=+}/ then concatenates the solutions for d and x/d for all divisors d. {,}$ sorts them by length and 0= takes the shortest of them (plus the initial :(x-1)* case). – Howard – 2014-04-23T20:14:45.613

2

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.

user62131

Posted 2014-04-22T21:12:53.697

Reputation:

0

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.

user62131

Posted 2014-04-22T21:12:53.697

Reputation:

0

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

user62131

Posted 2014-04-22T21:12:53.697

Reputation:

0

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

algorithmshark

Posted 2014-04-22T21:12:53.697

Reputation: 8 144