10
\$\begingroup\$

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 2ⁿ-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 2³-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.

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Random thought - how is -12 distinguished from 12? \$\endgroup\$ Commented May 30 at 9:02
  • \$\begingroup\$ @htmlcoderexe the top one is omitted, and one bit is used for sign \$\endgroup\$ Commented May 30 at 9:34
  • \$\begingroup\$ @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. \$\endgroup\$ Commented May 30 at 10:22
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ Commented May 30 at 10:34
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Commented Jun 1 at 3:09

6 Answers 6

Reset to default
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Uiua 0.17.0-dev.1, 28 bytes SBCS

⍥(↘¯1⊂0\+×2+1⌊ₙ2⌵-⟜≡⌞˜⊡)∞⇡⧻.

Try on Uiua Pad!

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

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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)]
Improve this answer
\$\endgroup\$
3
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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}))
	}
}
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice to see more Go use on this site! \$\endgroup\$ Commented May 30 at 12:01
  • \$\begingroup\$ Suggest removing the math import \$\endgroup\$ Commented Jun 2 at 3:46

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.