16
\$\begingroup\$

ZigZag encoding is a method of encoding signed integers to unsigned integers. Non-negative integers are multiplied by two. Negative integers are equal to their absolute values multiplied by two, minus one. Decoding is the inverse process.

Visualization of ZigZag encoding (Viotti, Juan & Kinderkhedia, Mital. (2022). A Survey of JSON-compatible Binary Serialization Specifications. arXiv.2201.02089. CC BY 4.0)

Write two programs or functions: One which takes a signed integer and ZigZag encodes it, and another which decodes a ZigZag-encoded integer. Your program or function should be able to accommodate the largest number types your language or platform supports.

This is . Your score is the combined number of bytes of your two programs or functions. Lowest score wins.

Rules

Test cases

Decoded Encoded
  -10      19
   -3       5
   -1       1
    0       0
    1       2
    3       6
   10      20
Improve this question
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Sandbox \$\endgroup\$ Commented Oct 23, 2024 at 14:45
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/93441/85334 \$\endgroup\$ Commented Oct 23, 2024 at 14:48
  • \$\begingroup\$ May we invert (signed integer) signs or index (unsigned integers) from 1? \$\endgroup\$ Commented Oct 24, 2024 at 18:25
  • 1
    \$\begingroup\$ @att No, sorry. \$\endgroup\$ Commented Oct 24, 2024 at 19:16

21 Answers 21

Reset to default
6
\$\begingroup\$

Jelly, 4 + 6 5 3 = 7 bytes

Encoder:

Ḥ»~$

Try it online!

Ḥ       Double the input.
 »      Take the maximum of that and
   $    its
  ~     bitwise NOT. (-1-n)

Decoder:

~¡H

Try it online!

-1 and inspiration for another -1 thanks to Jonathan Allan

Full program only. Try it modified for a test harness!

~      Bitwise NOT the input
 ¡     a number of times equal to itself.
  H    Halve that result.
Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

Japt, 8 7 5 + 5 = 13 12 10 bytes

Encoder

Ñ
w~U

Try it (includes all test cases)

Ñ\nw~U     :Implicit input of integer U
Ñ          :Multiply by 2
 \n        :Reassign to U
   w       :Maximum with
    ~U     :  Bitwise NOT of U

Decoder

϶U}c

Try it (includes all test cases

϶U}c     :Implicit input of integer U
Ï         :Function taking a 0-based iteration index as argument
 ¶U       :  Is equal to U
   }      :End function
    c     :Get the first integer from the sequence [0,-1,1,-2,2,-3,3,...] that returns true
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ So you encode with "Ñ aUgUa", a variant of Spanish agua. Interesting fluid coding. \$\endgroup\$ Commented Oct 23, 2024 at 16:08
5
\$\begingroup\$

R, 36 34 bytes

Encoder, 18 bytes

\(n)abs(n)*2-(n<0)

Attempt This Online!

Or

\(n)2*max(n,-n-.5)

Attempt This Online!

Decoder, 18 16 bytes

\(n)n%/%2-n%%2*n

Attempt This Online!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Set Theory: The Language, 3+3 = 6 bytes*

Encode

Flags: -iℤ -oℕ

↣ℤℕ

Decode

Flags: -iℕ -oℤ

↣ℕℤ

Explanation

In STTL, everything is represented as a mathematical set. For normal operations to work, they use "universes", a sort of context. The function ↣ "inject" is biversal, i.e. it uses two universes. ℕ refers to the naturals universe and ℤ to the integers universe. So the encoder ↣ℤℕ injects integers onto naturals, which follows the challenge requirement and more importantly the usual ℕ ↔ ℤ bijection in mathematics. ↣ℕℤ is required to form a bijection with ↣ℤℕ, and therefore does the inverse operation (casting a natural to an integer is done with → "convert").

Running

Save the code to files and run sttl encode.sttl -iℤ -oℕ <number> and sttl decode.sttl -iℕ -oℤ <number>. Remember that negative numbers have to be inputted with ¯ to not make it think it's flags.

Scoring

The flags are purely for nicer IO. The two programs are standalone: if you input the natural representation for sets (which is defined as such: 0 → ∅; n + 1 → n ∪ {n}) to the decoder you get the result as the integer representation of sets (which is defined as a pair of naturals as defined above, to be interpreted by subtracting their meanings; pairs are defined as (a, b) → {{a}, {a, b}}); the opposite applies for encoder.

Improve this answer
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Cool language, but are these functions or snippets? \$\endgroup\$ Commented Oct 25, 2024 at 11:05
  • \$\begingroup\$ debatable, there is no way to define functions currently \$\endgroup\$ Commented Oct 25, 2024 at 13:55
  • \$\begingroup\$ @noodleperson probably fixed \$\endgroup\$ Commented Oct 25, 2024 at 14:17
  • 2
    \$\begingroup\$ I don't think it's valid still because we count programs that must be ran with flags as different languages than without flags, and I assume the encoder and decoder are supposed to be in the same language \$\endgroup\$ Commented Oct 25, 2024 at 14:23
  • 1
    \$\begingroup\$ @noodleperson maybe let's move to chat to figure out what to do \$\endgroup\$ Commented Oct 25, 2024 at 14:25
5
\$\begingroup\$

K (ngn/k), 10+6=16 8+6 = 14 bytes

Encoder:

+/~~!-2*

Decoder:

-1/!-:

Try it online!

     -2*    negative double
    !       range to/from 0
+/~~        count nonzero

   !-:      range -x...-1
-1/         convert from base -1
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

iogii 12 bytes

encoder 6

2*:_(X

2* dup negate pred max

Try it

Max of 2* thing and its complement as others have done

decoder 6

}_bW1_

countTo negate backwards baseFrom 1 negate

Try it

Based on att's K solution

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

APL+WIN, 13 + 17 = 30 bytes

Index origin = 0

Encoder:- Prompts for integer

(0⌊×n)+2×|n←⎕

Try it online! Thanks to Dyalog Classic

Decoder:- Prompts for integer

1 ¯1[2|n]×⌈.5×n←⎕

Try it online! Thanks to Dyalog Classic

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

Go, 107 bytes

func e(a int)int{o:=a*2;if a<0{o=(-a)*2-1};return o}
func d(a int)int{o:=a/2;if a%2>0{o=-(a+1)/2};return o}

Attempt This Online!

e encodes, and d decodes.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 87 bytes \$\endgroup\$ Commented Jun 22 at 20:02
3
\$\begingroup\$

05AB1E, 10 8 (4+4) bytes

Encoder:

·D±M

Try it online or verify all test cases.

Decoder:

F±};

-2 bytes porting the decoder of @UnrelatedString's Jelly answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Original decoder (6 bytes):

±‚;ʒ.ï

Outputs as a singleton.

Try it online or verify all test cases.

Explanation:

·      # Double the (implicit) input-integer
 D     # Duplicate this
  ±    # Take the bitwise-NOT of the copy: -n-1
   M   # Push a copy of the maximum value of the stack
       # (which is output implicitly as result)

F      # Loop the (implicit) input-integer amount of times:
 ±     #  Take the bitwise-NOT: -n-1
       #  (which uses the implicit input-integer in the first iteration)
  };   # After the loop: halve the result
       # (which is output implicitly as result)

±      # Take the bitwise-NOT of the (implicit) input-integer
 ‚     # Pair it with the (implicit) input-integer
  ;    # Halve each
   ʒ   # Filter this pair by:
    .ï #  Is it an integer?
       # (after which the resulting singleton is output implicitly)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Halfwit, 17 16 12 (5.5+6.5) bytes

Encoder:

+?><l[n+N

-4 bytes thanks to emanresuA.

Try it online or verify all test cases.

Decoder:

(>M<+N;>{</

Try it online or verify all test cases.

This language feels as inefficient as I remember. 😅

Explanation:

+                # Add the (implicit) input-bigint to itself to double it
 ?               # Push the input again
  ><             # Push compressed 0
    l            # Check if the input is smaller than 0
     [           # If it is indeed negative:
      n+         #  Add 1
        N        #  And then negate it
                 # (after which the result is output implicitly)

(                # Loop the (implicit) input-bigint amount of times:
 >M<             #  Push compressed integer 1
    +            #  Add it to the current bigint
                 #  (which uses the implicit input-bigint in the first iteration)
     N           #  Then negate it
      ;>{<       # After the loop: push compressed 2
          /      # Integer-divide
                 # (after which the result is output implicitly)
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Oh hey it's that awful language I made two years ago! +?><l[n+N saves four bytes on the encoder. \$\endgroup\$ Commented Oct 25, 2024 at 21:02
  • \$\begingroup\$ @emanresuA Thanks! Pretty stupid of me to not use + instead of >{<*. I didn't knew about n being 1 outside of loops though, so thanks for the ?><l[n+N portion. :) \$\endgroup\$ Commented Oct 27, 2024 at 0:42
  • \$\begingroup\$ I guess my original approach with the >{<* replaced with + and both >M< replaced with n would have worked for 9 characters as well, but it's -2.5 bytes instead of -4. :) \$\endgroup\$ Commented Oct 27, 2024 at 0:49
3
\$\begingroup\$

JavaScript (ES6), 23 bytes

-6 thanks to @Neil
-1 thanks to @m90

Encoder (12 bytes)

n=>n*2^n>>31

Try it online!

Decoder (11 bytes)

n=>n/2^-n%2

Try it online!

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ n=>n/2^-n%2 for the decoder. \$\endgroup\$ Commented Oct 24, 2024 at 7:35
  • 1
    \$\begingroup\$ n=>n*2^-(n<0) for the encoder. \$\endgroup\$ Commented Oct 24, 2024 at 7:35
  • 1
    \$\begingroup\$ A further improvement to the encoder is n=>n*2^n>>31. (Because the bitwise operations already convert their arguments to 32-bit integers, this doesn't reduce the validity range.) \$\endgroup\$ Commented Nov 4, 2024 at 15:35
2
\$\begingroup\$

Google Sheets, 17 + 24 = 41 bytes

Encoder

=2*abs(A1)-(A1<0)

Decoder

=int(B1/(2-4*isodd(B1)))

screenshot

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

Python, encoder 22 bytes, decoder 19 bytes

e=lambda x:max(x+x,~x-x)
d=lambda x:x//2-x%2*x

Attempt This Online!

Python, encoder 22 bytes, decoder 23 bytes

e=lambda x:max(x+x,~x-x)
d=lambda x:[x,-x][x&1]>>1

Attempt This Online!

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

x86 32-bit machine code, 6 + 7 = 13 bytes

99 D1 E0 31 D0 C3
D1 E8 19 D2 31 D0 C3

Try it online!

Uses the regparm(1) calling convention – argument in EAX, result in EAX.

In assembly:

e:  cdq             # Sign-extend EAX into EDX:EAX.
                    #  This sets every bit of EDX to the sign bit of EAX.
    shl eax, 1      # Shift EAX left by 1 bit.
    xor eax, edx    # Exclusive-or EAX with EDX.
                    #  This inverts all bits if the sign bit was 1.
                    #  (In two's complement notation, that turns n into -n-1.)
                    #  x becomes 2x if nonnegative, -2x-1 if negative.
    ret             # Return.

d:  shr eax, 1      # Shift EAX right by 1 bit. The low bit goes into CF.
    sbb edx, edx    # Subtract EDX+CF from EDX, so it becomes -CF.
    xor eax, edx    # Exclusive-or EAX with EDX.
                    #  This inverts all bits if the low bit was 1.
                    #  2n becomes n; 2n+1 becomes -n-1.
    ret             # Return.

This can be reduced to 10 bytes by providing the two functions together and sharing code, if that is allowed:

D1 E8 EB 01 C0 19 D2 31 D0 C3

Try it online!

The decoding function starts at the beginning, and the encoding function starts after the first 3 bytes.

In assembly:

d:  shr eax, 1      # Shift EAX right by 1 bit. The low bit goes into CF.
    .byte 0xEB      # This byte and the next form JMP with displacement +1,
                    #  jumping to the SBB instruction.
e:  .byte 0x01      # This byte and the next form 'add eax, eax'.
    .byte 0xC0      #  The value of EAX is doubled. The high bit goes into CF.
    sbb edx, edx    # Subtract EDX+CF from EDX, so it becomes -CF.
    xor eax, edx    # Exclusive-or EAX with EDX.
    ret             # Return.
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ So basically the encoder could be the same as the decoder, except with the r changed to an l? I guess it makes sense, as you're moving that bit, while all the other bits get flipped if it was a 1 bit. \$\endgroup\$ Commented Oct 25, 2024 at 12:43
2
\$\begingroup\$

Raku, 14 + 27 = 41 bytes

Encoder:

.abs*2-($_ <0)

Attempt This Online!

Decoder:

($_/2).ceiling*(1-2*($_%2))

Attempt This Online!

Encoder: take 2 times the absolute value then maybe subtract 1 depending on negativity.

Decoder: do ceil-division then determine the sign over evenness.

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

C (gcc), 22 + 19 = 41 bytes

e(n){n=(n*=2)<0?~n:n;}d(n){n=-(n&1)^n/2;}

Try it online!

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

Vyxal 3, 5 + 5 = 10 bytes

Encoder: (Vyxal It Online!)

ÞṬN$Ḟ

Decoder: (Vyxal It Online!)

ÞṬN$i

Explanation of the encoder:

ÞṬN$Ḟ­⁡​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌­
   $Ḟ  # ‎⁡The index of the input in:
ÞṬ     # ‎⁢  The set of integers (0, 1, -1, 2, -2, ...)
  N    # ‎⁣  Negated (0, -1, 1, -2, 2, ...)

The decoder works the same way, except with indexing instead of finding the index.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 22 18 bytes

Encoder, 10 bytes

ＮθＩ⁻⊗↔θ‹θ⁰

Try it online! Link is to verbose version of code. Explanation: Port of @doubleunary and @pajonk's encoders.

Decoder, 12 8 bytes

Ｉ↨…±Ｎ⁰±¹

Try it online! Link is to verbose version of code. Explanation: Port of @att's decoder.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 8+10=18 bytes

Both functions use the same formulas as pajonk's R sol.

Encoder, 8 bytes

+:@|-<&0

Attempt This Online!

+:@|-<&0
     <&0   NB. less than 0?
+:@|       NB. absolute value(|) then(@) double(+:)
    -      NB. subtraction

Decoder, 10 bytes

<.@-:-+:|]

Attempt This Online!

<.@-:-+:|]
         ]   NB. input
      +:     NB. double the input
        |    NB. mod
<.@-:        NB. halve(-:) then(@) floor(<.), aka integer division
     -       NB. subtraction
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

AWK, 21+23=44 bytes

Encoder

$0=$1>=0?2*$1:-2*$1-1

Try it online!

Decoder

$0=$1%2?-($1+1)/2:$1/2

Try it online!

Unified 48 bytes

$0=$1~/e/?$2>=0?2*$2:-2*$2-1:$2%2?-($2+1)/2:$2/2

Try it online!

Combined example: awk -f zigzag.awk <<< "d 19" or "e -10" for decode/encode respectively.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you save any bytes by splitting this into two programs instead of testing for d/e? \$\endgroup\$ Commented Oct 28, 2024 at 14:27
  • \$\begingroup\$ Thank you, updated it with the split. \$\endgroup\$ Commented Oct 28, 2024 at 21:00
1
\$\begingroup\$

Math, 19 + 33 = 52 bytes

Encoder: Actual Source:

f(x)={x<0:-2x-1,2x}

Formatted Latex: $$ f(x)=\{x<0:-2x-1,2x\} $$ Decoder: Actual Source:

g(x)={0<=mod(x,2)<1:x/2,(x+1)/-2}

Formatted Latex: $$ g(x)=\{0\le mod(x,2):x/2,(x+1)/2)\} $$

Link to Desmos

*Desmos requires quite verbose latex code, so the formatted latex can't be directly copied into Desmos. I counted the equation in the actual source for determining my byte count.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! We require solutions to be full programs or functions - in desmos's case, functions, so you should prepend a f(x)= to each of these. You probably want to include the actual source code as well as formatted latex, and you might want to include a desmos.com/calculator link to demonstrate this. Also, the code that you copy out of desmos is quite verbose - we have a tips for golfing in desmos page that includes tricks to shorten things. \$\endgroup\$ Commented Oct 30, 2024 at 1:41
  • \$\begingroup\$ What you should count is the length of the source code that can be pasted into desmos - in this case, that's f(x)=\{x<0:-2x-1,2x\} and g(x)=\{0<=\mod(x,2)<1:x/2,(x+1)/-2\} with a leading newline on both (see this for why) \$\endgroup\$ Commented Oct 30, 2024 at 3:11
  • \$\begingroup\$ Will do when I have time \$\endgroup\$ Commented Nov 12, 2024 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.