Optimal Assembly Jump Distance

Question

In some forms of assembly, there are separate "short jump" and "long jump" instructions. However, these jumps can themselves have different lengths, which can affect the distance other jumps need to jump and thus their optimal jump length.

This assembly language will be bit based; there are no bytes and each measure is in bits.

For a jump of absolute length at most 2n-1, the jump instruction costs n*2 bits. It is impossible to jump 0 distance. Jump is the only instruction that exists in this language.

Your challenge

Given an array like this:

[1,2,0]

Which represents code like this:

0: goto 1;
1: goto 2;
2: goto 0;

Calculate how far each instruction needs to jump. Then output either:

• The absolute location of each instruction when compiled, in bits

  In this case, [0, 6, 12]. A 6 length jump instruction can jump up to 23-1=7.

• The length of each instruction when compiled. You may optionally exclude the last value.

  In this case, [6, 6, 8]

• How far each instruction jumps.

  In this case, [6, 6, -12]

def f(m):
 lengths = [2 for i in m]
 valid = False
 while not valid:
 valid = True
 positions = [sum(lengths[:i])for i in range(len(m))]
 for i, u, length, position in zip(range(len(m)), m, lengths, positions):
 p2 = positions[u]
 distance = abs(p2 - position)
 if 2**(length//2) <= distance:
 lengths[i]+=2
 valid = False
 break
 return positions, lengths, [positions[u] - position for u,position in zip(m, positions)]

Example Code

Test Cases

Test Case	Absolute Locations	Lengths	jump distance
[1, 2, 0]	[0, 6, 12]	[6, 6, 8]	[6, 6, -12]
[2, 2, 0]	[0, 8, 14]	[8, 6, 8]	[14, 6, -14]
[3, 0, 0, 0]	[0, 10, 18, 28]	[10, 8, 10, 10]	[28, -10, -18, -28]
[4, 0, 0, 0, 0]	[0, 12, 20, 30, 40]	[12, 8, 10, 10, 12]	[40, -12, -20, -30, -40]
[8, 0, 6, 8, 8, 0, 7, 8, 0]	[0, 14, 22, 34, 46, 58, 70, 76, 82]	[14, 8, 12, 12, 12, 12, 6, 6, 14]	[82, -14, 48, 48, 36, -58, 6, 6, -82]

Reminder you only need to output one of absolute locations, lengths, or jump distances. Which one you choose is up to you.

• htmlcoderexe: Random thought - how is -12 distinguished from 12?
• l4m2: @htmlcoderexe the top one is omitted, and one bit is used for sign
• htmlcoderexe: @l4m2 not sure what you meant by "the top one is omitted", but I also see that for example 14 and -14 in test cases both are length 8 - description mentions that corresponding to 2^4-1 maximum distance (15) which makes sense and there is indeed space for an extra bit (quite a few, even, given that 8 bits can store 256 different values), so maybe I am just over-focusing on something in the wording that's not really relevant. But it seems the "instructions" more or less require 2 bits per 1 bit of absolute value for some reason, while a sign bit would only be 1 extra regardless of the size.
• l4m2: @htmlcoderexe Since 0 distance is not allowed, one can encode 1 to 7 as (empty) 0 1 00 01 10 11. And each digit with a bit whether end, and a sign, exactly the length shown in question
• Peter Cordes: Fun fact: there is one real ISA where instruction boundaries were variable bit-lengths not a multiple of the byte width, and not byte-aligned: en.wikipedia.org/wiki/Intel_iAPX_432#Instruction_format. This design was widely considered a mistake, as it proved very slow and costly in transistor budget to implement in hardware. I don't think it had varint or other variable-length jump distance encodings, though. :P

Answer 1

Pyth, 19 bytes

u.eyl.Bs:G.*S,bkQm1

Try it online!

Outputs the lengths.

Explanation

u.eyl.Bs:G.*S,bkQm1Q # implicitly add Q
 # implicitly assign Q = eval(input())
 m1Q # array of ones with length Q
u # repeatedly apply lambda G to this until duplicate result is obtained
 .e Q # map lambda b,k over enumerated Q 
 ,bk # (b, k)
 S # sorted
 .* # splat as arguments to
 :G # slice G between two indices
 s # take the sum
 .B # convert to binary string
 l # take the length
 y # multiply by 2

Answer 2

Uiua 0.17.0-dev.1, ^{(削除) (削除ここまで)} 28 bytes ^SBCS

⍥(↘ ×ばつ2+1⌊n2⌵-⟜≡⌞ ̃⊡)∞⇡⧻.

Try on Uiua Pad!

Outputs the absolute locations. This code repeatedly recomputes the locations until it stops changing.

Answer 3

Python 3, (削除) 169 (削除ここまで) (削除) 163 (削除ここまで) (削除) 160 (削除ここまで) (削除) 151 (削除ここまで) 150 bytes

^{-6 bytes thanks to @l4m2 (comment link)
-3 bytes
-9 bytes thanks to @mousetail (OP) (comment link)
-1 bytes thanks to @l4m2 (comment link)}

def f(m):
 c=len(m);l=v=[2]*c
 while v:
 for i,u,e,o in zip(R:=range(v:=0,c),m,l,p:=[sum(l[:i])for i in R]):
 if(p[u]-o)**2>>e:l[v:=i]+=2
 return p

Outputs the absolute locations.

---

Previous versions

A (small) collection of some previous iterations of the current code that I had when before each time I was about to post, I thought of another byte save. This is aside from the 169 byte version - the first iteration I actually managed to publish - and following golfs that end up here.

For example, when I was about to post the 200-byte version, I re-read the question and realized I only had to only output 1 of the absolute locations, lengths, and jump distances. This led to my first published version for 169 bytes.

I have double checked that all versions - including the current version - pass all the test-cases that the OP has set.

151 bytes

def f(m):
 c=len(m);l=v=[2]*c
 while v:
 for i,u,e,o in zip(R:=range(v:=0,c),m,l,p:=[sum(l[:i])for i in R]):
 if(p[u]-o)**2>>e:l[i]+=2;v=1
 return p

160 bytes

def f(m):
 c=len(m);l,v=[2]*c,1
 while v:
 v=0
 for i,u,e,o in zip(R:=range(c),m,l,p:=[sum(l[:i])for i in R]):
 if(p[u]-o)**2>>e:l[i]+=2;v=1;break
 return p

163 bytes

def f(m):
 c=len(m);l,v,R=[2]*c,0,range(c)
 while~-v:
 v,p=1,[sum(l[:i])for i in R]
 for i,u,e,o in zip(R,m,l,p):
 if(p[u]-o)**2>>e:l[i]+=2;v=0;break
 return p

169 bytes

def f(m):
 c=len(m);l,v,R=[2]*c,0,range(c)
 while~-v:
 v,p=1,[sum(l[:i])for i in R]
 for i,u,e,o in zip(R,m,l,p):
 if abs(p[u]-o)>>(e>>1):l[i]+=2;v=0;break
 return p

200 bytes

def f(m):
 c=len(m);l,v,R=[2]*c,0,range(c)
 while~-v:
 v,p=1,[sum(l[:i])for i in R]
 for i,u,e,o in zip(R,m,l,p):
 if abs(p[u]-o)>>(e//2):l[i]+=2;v=0;break
 return p,l,[p[u]-o for u,o in zip(m,p)]

201 bytes

def f(m):
 c=len(m);l,v,R=[2]*c,0,range(c)
 while v<1:
 v,p=1,[sum(l[:i])for i in R]
 for i,u,e,o in zip(R,m,l,p):
 if abs(p[u]-o)>>(e//2):l[i]+=2;v=0;break
 return p,l,[p[u]-o for u,o in zip(m,p)]

202 bytes

def f(m):
 c=len(m);l,v,R=[2]*c,0,range(c)
 while v<1:
 v,p=1,[sum(l[:i])for i in R]
 for i,u,e,o in zip(R,m,l,p):
 if abs(p[u]-o)>=1<<e//2:l[i]+=2;v=0;break
 return p,l,[p[u]-o for u,o in zip(m,p)]

203 bytes

def f(m):
 l,v,R=[2]*len(m),0,range(len(m))
 while v<1:
 v,p=1,[sum(l[:i])for i in R]
 for i,u,e,o in zip(R,m,l,p):
 if abs(p[u]-o)>=1<<e//2:l[i]+=2;v=0;break
 return p,l,[p[u]-o for u,o in zip(m,p)]

213 bytes

def f(m):
 l,v=[2]*len(m),0
 while v<1:
 v,p=1,[sum(l[:i])for i in range(len(m))]
 for i,u,e,o in zip(range(len(m)),m,l,p):
 if abs(p[u]-o)>=2**(e//2):l[i]+=2;v=0;break
 return p,l,[p[u]-o for u,o in zip(m,p)]

• l4m2: Better square than abs here
• mousetail: 151 bytes
• l4m2: Python, 150 bytes: def f(m): c=len(m);l=v=[2]*c while v: for i,u,e,o in zip(R:=range(v:=0,c),m,l,p:=[sum(l[:i])for i in R]): if(p[u]-o)**2>>e:l[v:=i]+=2 return p

Answer 4

JavaScript (Node.js), 94 bytes

x=>(g=_=>t.map((c,i)=>(h=j=>j--&&t[j]+h(j),h(i)-h(x[i]))**2>>c&&g(t[i]+=2)))(t=x.map(_=>2))&&t

Try it online!

Answer 5

05AB1E, (削除) 16 (削除ここまで) 15 bytes

dΔx.\DIèαyo@+}·

Outputs the lengths.

Try it online or verify (almost) all test cases (the largest test case is omitted, because it'll time out).

Explanation:

d # Convert each value in the (implicit) input-list to a 1
 # (by using an >=0 check)
 Δ # Loop until the result no longer changes:
 x # Double each value in the current list (without popping)
 .\ # Undelta it (basically the cumulative sums with prepended 0)
 D # Duplicate that list
 Iè # 0-based index the input-list into that copy
 α # Take the absolute difference at the same positions with the undelta-list
 # (which will ignore the additional trailing item of the undelta-list)
 y # Push the current list again
 o # Take 2 to the power each
 @ # Do an >= check on the values at the same positions in the lists
 + # Add these 0s/1s to the current list
 }· # After the changes-loop: double each value
 # (after which the result is output implicitly)

Try it online with added debug-lines.

Answer 6

Go, (削除) 429 (削除ここまで) (削除) 397 (削除ここまで) (削除) 321 (削除ここまで) (削除) 317 (削除ここまで) (削除) 283 (削除ここまで) (削除) 282 (削除ここまで) 277 bytes

Saved (32+たす76+たす4+たす34+たす1+たす5=わ152) bytes thanks to @ceilingcat

Golfed version. Attempt This Online!

func f(m[]int)([]int,[]int,[]int){v,g:=0,func(l[]int)[]int{return make([]int,len(l))}
l:=g(m)
p,o:=l,l
for i:=range l{l[i]=2}
for v<1{v=1
p=g(l)
for i:=range^-len(l){p[i+1]=p[i]+l[i]}
o=g(l)
for i,u:=range m{y:=p[u]-p[i]
o[i]=y
if y*y>>l[i]>0{l[i]+=2
v=0
break}}}
return p,l,o}

Ungolfed version. Attempt This Online!

package main
import (
	"fmt"
	"math"
	"strings"
)
func formatMd(k []interface{}) string {
	var parts []string
	for _, i := range k {
		parts = append(parts, fmt.Sprintf("`%v`", i))
	}
	return strings.Join(parts, "|")
}
func f(m []int) ([]int, []int, []int) {
	lengths := make([]int, len(m))
	for i := range lengths {
		lengths[i] = 2
	}
	
	valid := false
	for !valid {
		valid = true
		positions := make([]int, len(m))
		for i := 1; i < len(m); i++ {
			positions[i] = positions[i-1] + lengths[i-1]
		}
		
		for i, u := range m {
			position := positions[i]
			p2 := positions[u]
			distance := int(math.Abs(float64(p2 - position)))
			if int(math.Pow(2, float64(lengths[i]/2))) <= distance {
				lengths[i] += 2
				valid = false
				break
			}
		}
	}
	
	positions := make([]int, len(m))
	for i := 1; i < len(m); i++ {
		positions[i] = positions[i-1] + lengths[i-1]
	}
	
	offsets := make([]int, len(m))
	for i, u := range m {
		offsets[i] = positions[u] - positions[i]
	}
	
	return positions, lengths, offsets
}
func main() {
	testCases := [][]int{
		{1, 2, 0},
		{2, 2, 0},
		{3, 0, 0, 0},
		{4, 0, 0, 0, 0},
		{8, 0, 6, 8, 8, 0, 7, 8, 0},
	}
	
	for _, tc := range testCases {
		positions, lengths, offsets := f(tc)
		fmt.Printf("|`%v`|%s|\n", tc, formatMd([]interface{}{positions, lengths, offsets}))
	}
}

• mousetail: Nice to see more Go use on this site!
• ceilingcat: Suggest removing the math import