12
\$\begingroup\$

I struggle to easily encode big numbers in ><>. If only there was a program that could find the best way for me?

What is ><>

><>, pronounced "fish", is a esoteric 2dimentional programing language. We will consider a subset here, consisting of the following commands:

  • 0123456789 push one number to the stack, equal to the value of the digit
  • abcdef push one number to the stack. Interpreted as hex, so a will push 10, f will push 15 etc.
  • * multiply the top 2 numbers on the stack
  • + add the top 2 numbers on the stack
  • - subtract the top 2 numbers on the stack
  • , divide the top 2 numbers on the stack
  • % modulo the top 2 stack items
  • $ swap the top 2 stack values
  • @ move the top value of the stack back by 2
  • " start string parsing mode. Push the character values of each encountered character to the stack until encountering another ". Only printable ASCII characters are allowed for the purpose of this challenge.
  • ' same as " but only ends with a ' character.
  • ~ delete the top element of the stack.
  • : duplicate the top element of the stack

Only these commands may be used, so /\-|#xlp.gnoi!?&><^v;[]{}() are not allowed to be used, except inside strings. Inside strings, only ASCII printable characters may be used. Line breaks are not allowed to appear anywhere.

Your code must, when executed, push the specified number to the stack, and effect nothing else. Your snippet should be embed able in a bigger program in any place in any orientation.

You only need to handle positive integers. Your program should take at most O(n) time to complete encoding a single number.

Some examples

15 could be f

32 could be 48* or " "

1111 could be 1e4f*+f*+. This one likely can be made shorter.

You can test your programs by appending a n; at the end. It should print the correct number. Online interpreters include this one, this one, and this one. Score excludes the "printing the output" part.

Scoring

Your score is your total length of the encoding your programs produces for the following test cases:

  • all numbers between 1 and 1500 inclusive
  • the first 1000 primes (from wikipedia) whose value is greater than 1500
  • All numbers of the form $$ 3^a+b $$ where 0<=a<30 and -15<=b<=15, whose value is greater than 1500 and not one of the first 1000 primes.
  • All numbers of the form $$ 7^a + 5 \pm Fib(b)$$ for all 10 <= a < 18, 0<=b<29, and Fib(x) is the Fibonacci function, if they would not fall into any of the other categories. Fib(0)=0.

The full list can be found here.

(When there is overlap only count that test case once)

Lowest score wins. First answer is tiebreaker. You don't need to golf your code.

\$\endgroup\$
3
  • 4
    \$\begingroup\$ Note that in real ><> golfing, you can put unicode characters in strings to get much larger constants (restricting it to only printable ascii is what makes this challenge non-trivial) \$\endgroup\$
    – Jo King
    Dec 7, 2022 at 23:05
  • 1
    \$\begingroup\$ Is O(n) in the number or in its number of digits? \$\endgroup\$ Dec 10, 2022 at 17:33
  • 1
    \$\begingroup\$ @CommandMaster the number itself \$\endgroup\$
    – mousetail
    Dec 10, 2022 at 17:46

3 Answers 3

2
\$\begingroup\$

JavaScript (ES7), Score 29093

let cache = {};

function testSuite(list) {
  let size = 0;

  list.forEach(n => {
    let res = solve(n).join('');
    size += res.length;
    console.log(n + ': ' + res);
  });

  console.log("Total size: " + size);
}

function solve(n, depth = 0) {
  if(!cache[n]) {
    cache[n] = solveNew(n, depth);
  }
  return cache[n];
}

function solveNew(n, depth = 0) {
  if(n < 16) {
    return [ n.toString(16) ];
  }
  if(n == 34) {
    return [ `'"'` ];
  }
  if(n > 31 && n < 127) {
    return [ '"' + String.fromCharCode(n) + '"' ];
  }
  if(depth > 1) {
    return null;
  }

  let sol = [];

  for(let d = Math.floor(n ** 0.5); d > 1; d--) {
    if(!(n % d)) {
      let r0 = solve(n / d, depth + 1),
          r1 = solve(d, depth + 1);

      if(r0 && r1) {
        if(isAscii(r1[r1.length - 1]) && isAscii(r0[0])) {
          [ r0, r1 ] = [ r1, r0 ];
        }
        sol.push([ ...r0, ...r1, "*" ]);
      }
    }
  }

  for(let o = -15; o <= 15; o++) {
    if(o) {
      let r0 = solve(n - o, depth + 1),
          r1 = solve(Math.abs(o), depth + 1);

      if(r0 && r1) {
        if(o > 0 && isAscii(r1[r1.length - 1]) && isAscii(r0[0])) {
          [ r0, r1 ] = [ r1, r0 ];
        }
        sol.push([ ...r0, ...r1, o < 0 ? "-" : "+" ]);
      }
    }
  }

  for(let j = 2; j <= 3; j++) {
    let q = Math.floor(n ** (1 / j)),
        op = ":".repeat(j - 1) + "*".repeat(j - 1);

    if(q > 2) {
      let r0, r1, d;

      d = n - q ** j;
      r0 = solve(q, depth + 1);
      r1 = solve(d, depth + 1);

      if(r0 && r1) {
        sol.push([ ...(d ? r1 : []), ...r0, op, ...(d ? [ "+" ] : []) ]);
      }

      d = (q + 1) ** j - n;
      r0 = solve(q + 1, depth + 1);
      r1 = solve(d, depth + 1);

      if(r0 && r1) {
        sol.push([ ...r0, op, ...(d ? [ ...r1, "-" ] : []) ]);
      }
    }
  }

  if(!sol.length) {
    return null;
  }

  sol = sol.map(mergeAscii);
  sol.sort((a, b) => a.join('').length - b.join('').length);

  return sol[0];
}

function mergeAscii(a) {
  if(isAscii(a[0]) && isAscii(a[1])) {
    let b0 = a[0].slice(1, -1),
        b1 = a[1].slice(1, -1);

    if(!b0.match(a[1][0])) {
      return [ a[1][0] + b0 + b1 + a[1][0], ...a.slice(2) ];
    }
    if(!b1.match(a[0][0])) {
      return [ a[0][0] + b0 + b1 + a[0][0], ...a.slice(2) ];
    }
  }
  return a;
}

function isAscii(v) {
  return v[0] == '"' || v[0] == "'";
}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Nice answer, though it does work especially well on the 3^n+b test cases compared to other numbers. \$\endgroup\$
    – mousetail
    Dec 8, 2022 at 12:22
  • \$\begingroup\$ I added more test cases, when you get a chance please update your score \$\endgroup\$
    – mousetail
    Dec 8, 2022 at 13:45
2
\$\begingroup\$

Python 3, score 28806

import functools
import itertools
#import sympy
import math

STRINGABLE = sorted(b'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~ ', reverse=True)
MAX = max(STRINGABLE)
ONECHAR = [*STRINGABLE, *range(15, 0, -1)]
MULTIPLES_O = {a*b:(a,b) for a in ONECHAR for b in ONECHAR}
SUMS_O = {a+b:(a,b) for a in ONECHAR for b in ONECHAR}
MM = {*range(16), *STRINGABLE}

def stringify(n):
    infix = ''
    prefix = ''
    postfix = ''
    options = []
    while True:
        if n < 16:
            postfix = hex(n)[2:] + postfix
            break
        if n in STRINGABLE:
            prefix += chr(n)
            break
        if n in SUMS_O:
            a,b = SUMS_O[n]
            postfix = '+' + postfix
            if a < 16:
                postfix = hex(a)[2:] + postfix
            else:
                prefix += chr(a)
            if b < 16:
                postfix = hex(b)[2:] + postfix
            else:
                prefix += chr(b)
            break
        if n in MULTIPLES_O:
            a,b = MULTIPLES_O[n]
            postfix = '*' + postfix
            if a < 16:
                postfix = hex(a)[2:] + postfix
            else:
                prefix += chr(a)
            if b < 16:
                postfix = hex(b)[2:] + postfix
            else:
                prefix += chr(b)
            break
        for i in ONECHAR:
            if n+i in SUMS_O or n+i in MULTIPLES_O or n+i in ONECHAR:
                n += i
                postfix = '-' + postfix
                if i < 16:
                    postfix = hex(i)[2:] + postfix
                else:
                    prefix += chr(i)
                break
            if n-i in SUMS_O or n-i in MULTIPLES_O or n-i in ONECHAR:
                n -= i
                postfix = '+' + postfix
                if i < 16:
                    postfix = hex(i)[2:] + postfix
                else:
                    prefix += chr(i)
                break
        else:
            for i in ONECHAR:
                c = set(range(n%i, MAX+1, i)) & MM
                if c:
                    if 0 in c:
                        prefix += chr(i)
                        postfix = '*' + postfix
                        n //= i
                        break
                    j = max(c)
                    if j in STRINGABLE:
                        prefix += chr(j)
                        postfix = '+' + postfix
                    else:
                        postfix = hex(j)[2:] + '+' + postfix
                    if i in STRINGABLE:
                        prefix += chr(i)
                        postfix = '*' + postfix
                    else:
                        postfix = hex(i)[2:] + '*' + postfix
                    n = (n-j) // i
                    break
        # make n smaller ...
        options.append("'" + prefix + "'" + most(n,0) + postfix)
    options.append("'" + prefix + "'" + postfix)
    return min(options, key=len)

def evaluate(s):
    import io
    s = io.StringIO(s)
    stack = []
    while True:
        c=s.read(1)
        if c=='': break
        if c in '0123456789abcdef':
            stack.append(int(c, 16))
        elif c in '*+-%':
            stack.append(eval(f'{stack.pop()}{c}{stack.pop()}'))
        elif c == ':':
            stack.append(stack[-1])
        elif c == '~':
            stack.pop()
        elif c == '$':
            stack.append(stack.pop(-2))
        elif c == '@':
            stack.insert(-2, stack.pop())
        elif c == '"':
            while True:
                c = s.read(1)
                if c == '"': break
                stack.append(ord(c))
        elif c == "'":
            while True:
                c = s.read(1)
                if c == "'": break
                stack.append(ord(c))
        elif c == ',':
            raise NotImplementedError
    return stack

def factor(n):
    from collections import Counter
    p = 2
    l = []
    while n > 1:
        if p*p > n:
            l.append(n)
            break
        if n%p:
            p += 1 + p%2
        else:
            l.append(p)
            n //= p
    return Counter(l)

#factor = sympy.factorint

def two_squares(n):
    C = factor(n)
    for i in C:
        if i%4 == 3 and C[i]%2: return False
    return True

def product(l):
    z = 1
    for i in l:
        z *= i
    return z

def divisors(n):
    F, C = zip(*factor(n).items())
    for t in itertools.product(*(range(i+1) for i in C)):
        yield product(i**j for i,j in zip(F, t))

#from sympy import divisors

@functools.lru_cache(None)
def power(n):
    if n < 2: return ''
    options = [':'+power(n-1)+'*']
    for i in divisors(n):
        if 1 < i*i <= n:
            options.append(power(i)+power(n//i))
    return min(options, key=len)

def nth_root(k, p):
    x = int(k**(1./p))+1
    x1 = x-1
    while x1 < x:
        x = x1
        xp1 = x**(p-1)
        x1 = ((p-1)*x+k//xp1)//p
    return x

#nth_root = lambda k,p:sympy.integer_nthroot(k, p)[0]

def massage(x, p):
    options = [most(x) + power(p)]
    if p%2 and p > 2:
        options.append(most(x*x) + power(p//2) + most(x) + '*')
    return min(options, key=len)

def powerful(n):
    possibilities = []
    for p in range(2, n):
        x = nth_root(n, p)
        if x == 1:
            d2 = (x+1)**p-n
            if d2 < n and x+1 < n: possibilities.append((d2,x+1,p,'-'))
            break
        d1 = n-x**p
        if d1 == 0:
            if x < n: possibilities.append((d1,x,p,None))
            continue
        d2 = (x+1)**p-n
        if d1 < n and x < n: possibilities.append((d1,x,p,'+'))
        if d2 < n and x+1 < n: possibilities.append((d2,x+1,p,'-'))
    options = [most(d,0) + massage(x, p) + s if d else massage(x, p) for d,x,p,s in sorted(possibilities)[:2]]
    return min(options, key=len)

def power2(n):
    possibilities = []
    for b in range(2, 20):
        bc = 1
        for c in range(1, n):
            bc *= b
            a = n//bc
            if a*bc == n:
                possibilities.append((a,b,c,None,''))
                continue
            d = (a+b)*bc - n
            possibilities.append((a+1,b,c,d,'-'))
            if a == 0: break
            d = n - a*bc
            possibilities.append((a,b,c,d,'+'))
    a,b,c,d,s = min(possibilities, key=lambda t:t[0]+t[1]+(t[3]or 0))
    postfix = most(a) + '*' if a > 1 else ''
    if d is None: return most(b) + power(c) + postfix
    return most(d) + most(b) + power(c) + postfix + s

def split(n):
    D = sorted(i for i in divisors(n) if 1 < i*i <= n)
    if len(D) == 0: return
    options = []
    for d in D[-3:]:
        options.append(most(d,0) + most(n//d,0) + '*')
        options.append(most(d,0) + ':' + most(n//d - d) + '+*')
        options.append(most(n//d,0) + ':' + most(n//d - d) + '$-*')
    return min(options, key=len)

def optimize(s):
    return s.replace("''", '')

winners = [0,0,0]

@functools.lru_cache(None)
def most(n, depth=1):
    if n < 16:
        return hex(n)[2:]
    if n < 31:
        return hex(n-15)[2:] + 'f+'
    if depth:
        return stringify(n)
    options = [stringify(n), powerful(n), split(n)]#, power2(n)]
    options = [(optimize(s),i) if s else (s,i) for i,s in enumerate(options)]#list(map(optimize, filter(None, options)))
    s,i = min(options, key=lambda t:len(t[0]) if t[0] else 1000000000)
    winners[i] += 1
    return s

#most(7**2)

def fib(n):
    a,b = 0,1
    for _ in range(n):
        a,b = b,a+b
    return a

if __name__ == '__main__':
    L = sorted(I for I in {*range(1, 1501), *[i for i in range(1501, 7920) if list(factor(i).values()) == [1]], *[3**a+b for a in range(30) for b in range(-15, 16)], *[7**a + 5 + m*fb for fb in [fib(b) for b in range(30)] for a in range(10, 18) for m in [1,-1]]} if I > 0)
    O = [most(i,0) for i in L]
    for i,j in zip(O, L):
        if evaluate(i)[0] != j:
            print(i, j, evaluate(i))
            break
        print(f'{j}: {i}')
    else:
        print('Success!')
    s = ''.join(O)
    print(len(s))
    print('\n' in s)
    print(winners)

Try it online!

There are three methods this uses.

The first is to try to express the number using a single string of characters, and several multiplications/additions (more or less, it can also use single digits (0-f) outside of the string).

The next is to try to find a power that is close to the number, and express the number as a^p + b.

The third is to express the number as a product of two numbers (of similar magnitude).

It also removes any occurrences of '' (this saves nearly 200 bytes!)

\$\endgroup\$
1
  • \$\begingroup\$ Very impressive \$\endgroup\$
    – mousetail
    Dec 10, 2022 at 17:58
0
\$\begingroup\$

Python, score=28800

import requests
import string
import itertools

real_printables = {ord(i) for i in (
    set(string.printable) - set('\n\t\r\x0b\x0c'))}


def get_factors(num, quote):
    quote_free_printables = real_printables - {ord(quote)}

    terms = []
    factors = []
    while num > 0:
        if num <= 15:
            terms.append(num)
            break
        if num in quote_free_printables:
            terms.append(num)
            break

        for factor in sorted(quote_free_printables,
                             reverse=True):
            if num % factor == 0:
                break
        else:
            for factor in sorted(quote_free_printables, reverse=True):
                if num % factor in quote_free_printables:
                    break
            else:
                for factor in range(15, 4, -1):
                    if num % factor == 0:
                        break
                else:
                    factor = 15

        assert factor != 1
        terms.append(num % factor)
        factors.append(factor)
        num //= factor
    return terms, factors


def encode_char_safe(char, quote):
    if char in real_printables - {ord(quote)}:
        return chr(char)
    elif 0 <= char <= 15:
        return f"{quote}{'0123456789abcdef'[char]}{quote}"
    else:
        raise ValueError(f"invalid char: {char}")


def encode_naive(num, quote):
    string = ''
    multiplication_section = ''

    terms, multiples = get_factors(num, quote)
    # print(terms, multiples)
    for index, (term, multiple) in enumerate(zip(terms, multiples)):
        if term != 0:
            string += encode_char_safe(term, quote) + encode_char_safe(multiple, quote)
            if index == 0:
                multiplication_section = '+' + multiplication_section
            else:
                multiplication_section = '+*' + multiplication_section
        else:
            string += encode_char_safe(multiple, quote)
            if index != 0:
                multiplication_section = '*' + multiplication_section

    assert len(terms) == len(multiples) + 1
    assert 1 not in multiples
    if terms[-1] != 1 or len(terms)==1:
        string += encode_char_safe(terms[-1], quote)
        if len(multiples) > 0:
            multiplication_section = '*' + multiplication_section

    return f"{quote}{string}{quote}{multiplication_section}".replace(
        quote*2, "")


def encode_maybe_power(num, quote):
    return min(
            (
                encode_naive(int(num ** (1/a)), quote)+b for a, b in zip(
                    (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
                     18),
                    ('', ':*', '::**', ':*:*', '::::****', ':*::**',
                     '::::::******', ':*:*:*', '::**::**', ':*::::****',
                     '::::::::::**********', ':*:*::**',
                     '::::::::::::************', ':*::::::******',
                     '::**::::****', ':*:*:*:*',
                     ':::::::::::::::****************',
                     ':*::**::**'
                     ))
                if int(num ** (1/a))**a == num
            ),
            key=len
        )


def encode_maybe_divide(num, quote):
    return min(
            (
                (
                    encode_maybe_power(num, quote) if i == 1
                    else
                    (
                        quote + encode_char_safe(i, quote) + quote +
                        encode_maybe_power(num//i, quote) + '*'
                    ).replace(quote*2, '')
                )
                for i in itertools.chain(
                    range(1, 16),
                    real_printables - {ord(quote)}
                )
                if num % i == 0
            ),
            key=len
    )


def number_with_subtraction(num, sub, quote):
    if sub == 0:
        return encode_maybe_divide(num, quote).replace(quote*2, '')
    elif sub > 0:
        return (
                quote + encode_char_safe(abs(sub), quote) + quote +
                encode_maybe_divide(num-sub, quote)
            ).replace(quote*2, '')+'+'
    elif sub > -16:
        return (
                encode_maybe_divide(num-sub, quote) + quote +
                encode_char_safe(abs(sub), quote) + quote
            ).replace(quote*2, '')+f'-'
    else:
        return (
                quote + encode_char_safe(abs(sub), quote) + quote +
                encode_maybe_divide(num-sub, quote)
            ).replace(quote*2, '')+f'$-'


def encode(num):
    if num < 16:
        return '0123456789abcdef'[num]
    return min((
            number_with_subtraction(num, b, quote).replace(quote*2, '')
            for quote in ('"', "'")
            for b in itertools.chain(range(-15, 16), *(
                (i, -i) for i in real_printables - {ord(quote)}
            ))
            if num-b > 0
        ), key=len)


# test_cases = range(500, 510)

test_cases = requests.get(
   "https://gist.githubusercontent.com/mousetail/"
   "fcd558c39f9d1a680db3de1c25e823de/raw/"
   "c91113d663cf4d3f3cef7ad44d5ced22239f964e/test_cases.csv").text.split("\n")

total_length = 0
for test_case in test_cases:
    res = encode(int(test_case))
    total_length += len(res)
    print(f"{test_case:>8}\t{res:>8}")
print(total_length)

Technically runs in O(log N).

Basically runs in 3 steps:

  • Try adding or subtracting every printable character to try to make it a perfect multiple
  • The dividing by every printable to make it a perfect power
  • If it is a perfect power try rooting it. This is the most important saving, and the main goal of the top 2 steps.
  • Now the main part of the loop. Basically we want to convert the remaining number to base ord('~'). However, if this would lead to digits that are not printable we take a smaller base instead. Base is adjusted for each individual digit.

The score for just the last step would be 33749.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Input 16, Output f+(Stack underflow) \$\endgroup\$
    – l4m2
    Dec 13, 2022 at 7:30
  • \$\begingroup\$ @l4m2 oops, I'll take a look what's going wrong \$\endgroup\$
    – mousetail
    Dec 13, 2022 at 7:45
  • \$\begingroup\$ @l4m2 has been fixed \$\endgroup\$
    – mousetail
    Dec 13, 2022 at 10:46
  • 1
    \$\begingroup\$ ['', ':*', '::**', ':*:*', '::*:**', ':*::**', '::*::***', ':*:*:*', '::*:*:**', ':*::*:**', '::*::*:***', '::**:*:*', ':::**:*:**', ':*::*::***', '::**::*:**', ':*:*:*:*', '::*:*:*:**', '::**:*::**'] are shorter powers (saves 36) \$\endgroup\$
    – gsitcia
    Dec 13, 2022 at 17:02

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.