Gelatin integer metagolf

Question

Gelatin is a worse version of Jelly. It is a tacit programming language that always takes a single integer argument and that has 7 (or maybe 16) commands.

Gelatin

Gelatin programs will always match the following regex:

^[+_DSa\d~]*$

i.e. they will only contain +_DSa0123456789~ characters. The commands in Gelatin are:

• Digits return their value (0 is \$0\$, 1 is \$1\$ etc.) Digits are stand alone, so 10 represents \$1\$ and \$0\$, not \$10\$
• a returns the argument passed to the Gelatin program
• D takes a left argument and returns it minus one (decremented)
• S takes a left argument and returns it's square
• + takes a left and a right argument and returns their sum
• _ takes a left and a right argument and returns their difference (subtract the right from the left)
• ~ is a special command. It is always preceded by either + or _ and it indicates that the preceding command uses the same argument for both the left and the right.

Each command - aside from ~ - in Gelatin has a fixed arity, which is the number of arguments it takes. Digits and a have an arity of \$0\$ (termed nilads), D and S have an arity of \$1\$ (termed monads, no relation) and + and _ have an arity of \$2\$ (termed dyads)

If + or _ is followed by a ~, however, they become monads. This affects how the program is parsed.

Tacit languages try to avoid referring to their arguments as much as possible. Instead, they compose the functions in their code so that, when run, the correct output is produced. How the functions are composed depends on their arity.

Each program has a "flow-through" value, v and an argument ω. v is initially equal to ω. We match the start of the program against one of the following arity patterns (earliest first), update v and remove the matched pattern from the start. This continues until the program is empty:

• 2, 1: This is a dyad d, followed by a monad M. First, we apply the monad to ω, yielding M(ω). We then update v to be equal to d(v, M(ω)).
• 2, 0: This is a dyad d, followed by a nilad N. We simply update v to be d(v, N)
• 0, 2: The reverse of the previous pattern, v becomes d(N, v)
• 2: The first arity is a dyad d, and it's not followed by either a monad or a nilad as it would've been matched by the first 2. Therefore, we set v to be d(v, ω)
• 1: The first arity is a monad M. We simply set v to be M(v)

For example, consider the program +S+~_2_ with an argument 5. The arities of this are [2, 1, 1, 2, 0, 2] (note that +~ is one arity, 1). We start with v = ω = 5:

• The first 2 arities match pattern 2, 1 (+S), so we calculate S(ω) = S(5) = 25, then calculate v = v + S(ω) = 5 + 25 = 30
• The next arity matches pattern 1 (+~). +~ means we add the argument to itself, so we double it. Therefore, we apply the monad to v, updating it to v = v + v = 30 + 30 = 60
• The next arity pattern is 2, 0 (_2), which just subtracts 2, updating v to v = v - 2 = 60 - 2 = 58
• Finally, the last arity pattern is 2 (_), meaning we update v to be v = v - ω = 58 - 5 = 53.
• There are now no more arity patterns to match, so we end the program

At the end of the program, Gelatin outputs the value of v and terminates.

In a more general sense, +S+~_2_ is a function that, with an argument \$\omega\$, calculates \$2(\omega + \omega^2) - 2 - \omega = 2\omega^2 + \omega - 2\$.

However, S+~+_2 is one byte shorter, which is our goal in this challenge.

---

Given an integer \$n\$ and a target integer \$m\$, you should output a valid Gelatin program that takes \$n\$ as input and outputs \$m\$. A valid Gelatin program is one where the arities always follow the five patterns above (so not S1S, or 123, etc.), and one that matches the described regex above.

However, this is not a code-golf challenge. Instead, your program will be scored on how short the generated Gelatin programs are for a set of 20 randomly generated inputs where \$-9999 \le n \le 9999\$. The shortest combined length wins.

I will be testing the submissions in order to get a final score. If your program times out on TIO for \$|n-m| > 500\$, please provide testing instructions. If, for whatever reason, you program fails to produce a correct output for any of the scoring cases, I cannot score your program and it is disqualified. This includes time and memory limitations, so please make your metagolfers somewhat efficient.

The MD5 hash of the list of inputs, in the form of a list of newline separated lines like n m, is

91e5dd2ab754ce0d96590f8f161e675b

You can use the following test cases to test your answer. They have no bearing on your final score. You are under no obligation to golf your generating code.

This is a very naïve attempt, that simply adds or subtracts \$9\$ until it's within \$9\$ of the target, where it adds/subtracts the remaining gap. It scores 292 on the test cases, and 3494 on the scoring cases. You should aim to beat this at the very least.

Test cases

   n     m
   7     2    
  -8     7
   2     2
   1    -7
   2     1
   0    30
 -40    66
   5   -15
 -29    18
  24   -33
 187    -3
 417   512
-101  -108
 329   251
  86   670

Answer 1

Python 3, score 135

DYAD_MONAD = 0
DYAD_NILAD = 1
NILAD_DYAD = 2
DYAD = 3
MONAD = 4

nilads = {
	**{str(i): (lambda i: lambda argument: i)(i) for i in range(10)},
	"a": lambda argument: argument
}

monads = {
	"D": lambda x: x - 1,
	"S": lambda x: x * x,
	"+~": lambda x: x + x,
	"_~": lambda x: 0
}

dyads = {
	"+": lambda x, y: x + y,
	"_": lambda x, y: x - y
}

commands = {
	DYAD_MONAD: {
		d + m: (lambda D, M: lambda a, x: D(x, M(a)))(D, M)
	for d, D in dyads.items() for m, M in monads.items()},
	DYAD_NILAD: {
		d + n: (lambda D, N: lambda a, x: D(x, N(a)))(D, N)
	for d, D in dyads.items() for n, N in nilads.items()},
	NILAD_DYAD: {
		n + d: (lambda D, N: lambda a, x: D(N(a), x))(D, N)
	for d, D in dyads.items() for n, N in nilads.items()},
	DYAD: {
		d: (lambda D: lambda a, x: D(x, a))(D)
	for d, D in dyads.items()},
	MONAD: {
		m: (lambda M: lambda a, x: M(x))(M)
	for m, M in monads.items()}
}

import heapq

def f(n, m):

	# STATE VECTOR
	#
	# [current gelatin program length, current value, current gelatin program, last group type]

	def update(argument, pq, seen, state_vector, arity_config):
		length, value, program, last_type = state_vector
		for key, f in commands[arity_config].items():
			newval = f(argument, value)
			if abs(newval) > 20*abs(n)+abs(m) < abs(newval-n*n): continue
			if newval in seen: continue
			seen.add(newval)
			heapq.heappush(pq, (length + len(key), newval, program + key, arity_config))

	initial = (0, n, "", -1) # initially, the program is empty (so has length 0), the value is n, and there was no last group; -1 suffices to avoid breaking the check
	pq = [initial] # priority queue. we'll use heapq to keep the shortest program at the front so it's *guaranteed* to be an optimal solution
	seen = set()
	while True:
		length, value, program, last_type = sv = heapq.heappop(pq) # get the current shortest program; ties are ordered by value so this has no guarantee to be optimal in speed
# 		print(length, value, program, last_type)
# ^ DEBUGGING OUTPUT
		if value == m:
			return program
		if last_type != DYAD: # to prevent issues with 2 | 1 becoming 2,1 and 2 | 0,2 becoming 2,0 | 2, we will not allow 1 ... or 0 2 ... following a dyad
			update(n, pq, seen, sv, MONAD)
			update(n, pq, seen, sv, NILAD_DYAD)
		update(n, pq, seen, sv, DYAD_MONAD)
		update(n, pq, seen, sv, DYAD_NILAD)
		update(n, pq, seen, sv, DYAD)

score = 0

while True:
	try:
		n, m = map(int, input().split())
		output = f(n, m)
		print(output)
		score += len(output)
	except:
		print("FINAL SCORE:", score)
		break

Try it online!

Basically a rip-off of hyper-neutrino's initial answer, but with a branch cut based on the magnitude of current value:

if abs(newval) > 20*abs(n)+abs(m) < abs(newval-n*n): continue

First, let's list all the possible one-step operations for Gelatin (no-ops and duplicate operations are ignored):

input = x, current = v

2 1: +a  +D    +S    ++~  _a  _D    _S    _+~
     v+x v+x-1 v+x^2 v+2x v-x v-x+1 v-x^2 v-2x
2 0: +1 .. +9 _1 .. _9
0 2: 0_ .. 9_
1  : D   S   +~ _~
     v-1 v^2 2v 0

Now, there are very limited number of operations that can reduce the magnitude of the current number. Assuming x is positive, there are v-d (where 1<=d<=9), v-x, v-2x, and v-x^2. Squaring tends to overshoot the numbers significantly, and if it can't get close to the target number by using a small number of these steps, there is no reason to consider that branch.

I initially thought that v-x^2 is useless and it's fine to prune anything that goes over some_const*abs(n), but soon found that v-x^2 is useful in some special cases like 100 1881 where it can be solved in 5 bytes only by going through a number close to n^2: 9+S_S.

If allowing single use of _S turns out to be insufficient, I can always extend the condition like

if all(abs(newval - n*n*i) > (20-2*i)*abs(n)+abs(m) for i in range(5)): continue

at the cost of increased running time and memory usage. I think it won't MemoryError for any reasonable constant instead of 5 in range(5).

Answer 2

Python 3, score 238

In order to run without running out of memory, I had to make it somewhat suboptimal :( there's probably a better heuristic for this.

DYAD_MONAD = 0
DYAD_NILAD = 1
NILAD_DYAD = 2
DYAD = 3
MONAD = 4

nilads = {
    **{str(i): (lambda i: lambda argument: i)(i) for i in range(10)},
    "a": lambda argument: argument
}

monads = {
    "D": lambda x: x - 1,
    "S": lambda x: x * x,
    "+~": lambda x: x + x,
    "_~": lambda x: 0
}

dyads = {
    "+": lambda x, y: x + y,
    "_": lambda x, y: x - y
}

commands = {
    DYAD_MONAD: {
        d + m: (lambda D, M: lambda a, x: D(x, M(a)))(D, M)
    for d, D in dyads.items() for m, M in monads.items()},
    DYAD_NILAD: {
        d + n: (lambda D, N: lambda a, x: D(x, N(a)))(D, N)
    for d, D in dyads.items() for n, N in nilads.items()},
    NILAD_DYAD: {
        n + d: (lambda D, N: lambda a, x: D(N(a), x))(D, N)
    for d, D in dyads.items() for n, N in nilads.items()},
    DYAD: {
        d: (lambda D: lambda a, x: D(x, a))(D)
    for d, D in dyads.items()},
    MONAD: {
        m: (lambda M: lambda a, x: M(x))(M)
    for m, M in monads.items()}
}

def heuristic(diff, length):
    return (diff * length ** 3)

import heapq

# STATE VECTOR
#
# [heuristic value, current value, desired, current gelatin program, last group type]

def update(argument, pq, seen, state_vector, arity_config):
    _, value, desired, program, last_type = state_vector
    for key, f in commands[arity_config].items():
        newval = f(argument, value)
        if newval in seen: continue
        seen.add(newval)
        heapq.heappush(pq, (heuristic(abs(newval - desired), len(program + key)), newval, desired, program + key, arity_config))

def f(n, m):
    initial = (heuristic(abs(n - m), 0), n, m, "", -1) # initially, the program is empty (so has length 0), the value is n, and there was no last group; -1 suffices to avoid breaking the check
    pq = [initial] # priority queue. we'll use heapq to keep the shortest program at the front so it's *guaranteed* to be an optimal solution
    seen = set()
    while True:
        _, value, desired, program, last_type = sv = heapq.heappop(pq) # get the current shortest program; ties are ordered by value so this has no guarantee to be optimal in speed
#         print(_, value, desired, program, last_type)
# ^ DEBUGGING OUTPUT
        if value == m:
            return program
        if last_type != DYAD: # to prevent issues with 2 | 1 becoming 2,1 and 2 | 0,2 becoming 2,0 | 2, we will not allow 1 ... or 0 2 ... following a dyad
            update(n, pq, seen, sv, MONAD)
            update(n, pq, seen, sv, NILAD_DYAD)
        update(n, pq, seen, sv, DYAD_MONAD)
        update(n, pq, seen, sv, DYAD_NILAD)
        update(n, pq, seen, sv, DYAD)

score = 0

while True:
    try:
        n, m = map(int, input().split())
        output = f(n, m)
        print(output)
        score += len(output)
    except:
        print("FINAL SCORE:", score)
        break

Try it online!