Inspired by this video by Ben Eater. This challenge forms a pair with Encode USB packets.

The USB 2.0 protocol uses, at a low level, a line code called non-return-to-zero encoding (specifically, a variant called NRZI), in which a stream of bits is encoded into a stream of two electrical level states J and K. Decoding works as follows:

  • Start with some initial state, which is either J or K
  • For each state to be decoded:
    • If the state is different to the previous state, write a 0.
    • If the state is the same as the previous state, write a 1.

For this challenge, we will assume the encoding starts in state J.

However, it's not that simple: an additional process called bit stuffing takes place, which is designed to make it easier to detect if the signal has dropped out. After 6 consecutive 1 bits are written, a meaningless 0 bit is written to ensure the signal never stays in the same state (J or K) for too long. When decoding, you need to take this into account and remove the 0 bit that necessarily occurs after 6 consecutive 1s.

The full USB specification is available here on the USB website, or mirrored (and easier to access) here, but I'd caution you before reading it because it's extremely long and the pertinent information is hard to pin down.


Given a non-empty list of Js or K states as input, decode the string using the USB implementation of NRZI described above, and output a binary string.

You may assume the input will never contain invalid data with incorrect bit stuffing (i.e., it will never contain 7 consecutive 1s).


Input              Output
J                  1
K                  0
JKJKKJJ            1000101
KJKJKJKJ           00000000
JJJJJJKKK          11111111
KJJJJJJKJ          001111100
KJJJJJJJKJK        0011111100
KJJJJJJJKKJK       00111111100
KJJJJJJJJKJ        (incorrect bit stuffing; does not need to be handled)
KJJJKKKJKJJJJKJJ   0011011000111001
KKKJJKJKJJJJKKJKJJJJKKJKJJJJKJKJKKKKJKKKJKKKKJJKJKKJJJJJKJJKKKKKJJJJKKKKJJJJKKKKJJJJKKKKJKKJJJJKJJJJJKJJKKKJJJJJKKKKJJKKJJJJKKJKJJJJKKJJKKKJKJJKJJJKJJKKJKKJJJJKJJJKJKKKJJJKKKKKJJJKKKJJKJJKKKKKJJJJKKKKJJJKJKJJKKKKJJKJKKKJKJJJKKKJJKJKJKKKKKKKJKKKKJJJKJKKKKKJJKKKJKKJKJJKKJKJJKKKKJJJJKJJJKKJKJJJJKKKKJKKKKJKKJJKKJJJJKKKJKKKKJJKKKJKJKKKJKJJJKKJJKJKK   01101000011101000111010001110000011100110011101000101111001011110111011101110111011101110010111001111001011011110111010101110100011101010110001001100101001011100110001101101111011011010010111101110111011000010111010001100011011010000011111101110110001111010110010001010001011101110011010001110111001110010101011101100111010110000110001101010001


  • The input should be a string or array, with the two states J and K being represented by two distinct values of your choice (within reason)
  • The output should be a string or array of 1s and 0s or of trues and falses
  • You may use any standard I/O method
  • Standard loopholes are forbidden
  • This is , so the shortest code in bytes wins
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Commented Jun 10, 2021 at 7:16
  • 3
    \$\begingroup\$ Bounty for the answer that will run on his 6502 breadboard computer. :) \$\endgroup\$
    – 640KB
    Commented Jun 10, 2021 at 13:44
  • 1
    \$\begingroup\$ do test cases say that initial J isn't present in the input? \$\endgroup\$ Commented Jun 11, 2021 at 18:25
  • \$\begingroup\$ @NooneAtAll correct; the intial J is not part of the input \$\endgroup\$
    – pxeger
    Commented Jun 11, 2021 at 19:14
  • 2
    \$\begingroup\$ @640KB which 6502 platform are we supposed to target? I want to try using this emulator. \$\endgroup\$
    – Razetime
    Commented Jun 15, 2021 at 8:14

19 Answers 19


convey, 31 25 bytes

Takes JK as 01.


Try it online!

Compares = the string with itself with a J prepended ,0. The middle loop just adds the comparisons to a counter (starting with 0) that gets reset on a 0. Only take ! elements where the previous counter was less than 6 (6.

enter image description here


Husk, 11 bytes


Try it online!

Takes an array of bits(0=J, 1=K), outputs an array of bits(formatted as string for convenience)


          Θ Prepend 0
        Ẋ=  map overlapping pairs by equality
σḋ126ḋ63    replace binary digits of 126 with binary digits of 63 (stolen from Luis Mendo)
  • 2
    \$\begingroup\$ This is funny: I just answered the 'encode USB' challenge in Husk, and thought I'd come here to do it the other way around... only to find that you've already beaten me to it with almost exactly the same approach (and same bytes)! \$\endgroup\$ Commented Jun 11, 2021 at 23:06

MATL, 15 14 bytes


Input is an array with 0 for 'J' and 1 for 'K'.

Try it online! Or verify all test cases.


0       % Push 0
i       % Input: string
h       % Concatenate
d       % Consecutive differences
~       % Negate: converts nonzero to 0, and zero to 1. Gives a numeric vector (*)
126B    % Push 126, convert to binary. Gives [1 1 1 1 1 1 0]
63B     % Push 63, convert to binary. Gives [1 1 1 1 1 1]
Zt      % String replace (works for numeric vectors too). Replaces [1 1 1 1 1 1 0]
        % by [1 1 1 1 1 1] in (*)
        % Implicit display

JavaScript (ES6), 54 bytes


Try it online!

Take input as a string of "J" / "K". Output a string with "0" and "1".

And f=J=>J.replace(/./g,a=>J^(J=a>f)?i=i>5?'':0:++i/i,i=0) is 54 bytes too.

JavaScript (ES6), 44 bytes


Try it online!

Take input as an array of false (for "J") and true (for "K"). Output an array of false and true.

  • \$\begingroup\$ i guess the they functions are not assigned to a variable \$\endgroup\$
    – Drdilyor
    Commented Jun 10, 2021 at 15:54

R, 83 76 62 bytes


Try it online!

Takes input as 0(J) and 1(K).

Outputs string of 1s and 0s.

Change of approach after looking at @Luis Mendo's answer.

function(x)    # function taking x as input
gsub(          # replace all occurences of
'(1{6})0',     # 6 ones and a zero
'\\1',         # with just 6 ones (first capturing group)
Reduce(paste0, # in a following vector collapsed to string
+!diff(c(0,x)) # negated differences of x with 0 prepended 
               # converted from logical to numeric with unary +
               # this would be the output without bit stuffing
  • 1
    \$\begingroup\$ Nice. I got 68 bytes without regex, but then realised it's almost the same as your before-change-of-approach version... \$\endgroup\$ Commented Jun 10, 2021 at 23:53
  • \$\begingroup\$ @DominicvanEssen nice golf of the rle approach! \$\endgroup\$
    – pajonk
    Commented Jun 11, 2021 at 5:56

C (gcc), 79 76 bytes

-3 thanks to @ceilingcat


Try it online! Takes input as J and K, outputs with bytes 0x00 and 0x01 for 0 and 1.

For output as numeric 0 and 1, Try it online! for 78 bytes.



J, 26 bytes

Takes in JK as 0 1.


Try it online!

                       0,] prepend a J
                   2=/\    pair-wise equal
                t=:        store as t
         (6$1)E.           bitmask of places where 6 ones starts
     _6|.                  shifted by 6 bits
   0=                      negate
t#~                        take only truthy bits from t

Vyxal, 16 bytes


Try it Online!

1p               # Prepend a 1
  -              # Differences - truthy if unchanged, falsy if changed
   Ṫ             # Get rid of last
    v¬           # Vectorised not
      ṅ          # Joined
       \16*      # Six ones
           :     # Duplicate
            0+   # Append a 0 to the first
              $  # Swap
               V # Replace

Takes the difference of the list with a 1 prepended and the list itself, NOTted, to get the values. Then spend the remaining 10 bytes on doing the bit stuffing.


PHP -F, 96 bytes

for($s=$r=$argn;$s[++$i]!='';)$r[$i]=+!abs($s[$i]-$s[$i-1]);echo str_replace(1111110,111111,$r);

Try it online!

Well, I.. tried.. to make it short.. hum!

takes a string of 0 (J) and 1 (K) as input


Python 2, 77 bytes

lambda s:''.join((`+(x==y)`for x,y in zip('J'+s,s))).replace('1'*6+'0','1'*6)

Try it online!

-2 bytes thanks to @ovs

  • 2
    \$\begingroup\$ int can be shortened to +. \$\endgroup\$
    – ovs
    Commented Jun 10, 2021 at 11:32
  • \$\begingroup\$ @ovs thanks for the tip \$\endgroup\$
    – Wasif
    Commented Jun 10, 2021 at 11:34
  • \$\begingroup\$ for .. in qualifies as generator expression, so you can drop one pair of parenthesis and save two more bytes. \$\endgroup\$
    – movatica
    Commented Aug 9, 2021 at 23:05

Red, 79 bytes

func[x][p: s: 0 collect[foreach i x[s: any[all[s < 6 keep p = i s + 1]0]p: i]]]

Try it online!

Takes input as a block of \$1\$s and \$0\$s, outputs a block of booleans.

Test suite on TIO uses two additional transformation functions that allow reading inputs from JK-strings as in task specification and convert output to numbers for nicer visualization.


05AB1E, 13 12 bytes

-1 thanks to Kevin Cruijssen.


Try it online! Uses 0 for J and 1 for K.

0ìüQJƵPbD¨.:  # full program
          .:  # replace all instances of...
     ƵP       # 126...
       b      # in binary...
          .:  # in...
    J         # joined...
  ü           # are all digits of each element in...
0             # literal...
 ì            # concatenated with...
              # implicit input...
   Q          # equal...
          .:  # with...
      ƵP      # 126...
        bD    # in binary...
          ¨   # excluding the last digit
              # implicit output
  • 1
    \$\begingroup\$ -1 byte by replacing ø€Ë with üQ. \$\endgroup\$ Commented Aug 5, 2021 at 7:33
  • \$\begingroup\$ @KevinCruijssen Thanks! \$\endgroup\$
    – Makonede
    Commented Aug 6, 2021 at 19:44

Charcoal, 19 bytes


Try it online! Link is to verbose version of code. Explanation:

   θ                Input string
  ⭆                 Map over characters and join
        J           Literal string `J`
       ⁺            Concatenated with
         θ          Input string
      §             Indexed by
          κ         Current index
    ⁼               Equals
     ι              Current character
 ⪪                  Split on
             1      Literal string `1`
            ×       Repeated
              ⁶     Literal `6`
           ⁺        Concatenated with
               0    Literal string `0`
⪫                   Join with
                 1  Literal string `1`
                ×   Repeated
                  ⁶ Literal `6`
                    Implicitly print

Stax, 16 bytes


Run and debug it

takes in a string/array of bytes 0x00 for J and 0x01 for K.

Outputs a string, same as the given testcases.

Sadly, this 14 byte program doesn't work since stax auto-replaces null bytes with spaces.


K (ngn/k), 25 bytes


Try it online!

Takes J as 0, and K as 1. Returns a list of 0s and 1s.

  • 0=': run an equals-each-prior, seeded with 0 on the (implicit) input, handling the non-return-to-zero part
  • 7':(&6), prepend 6 0s to the input, then slice into length-7 sliding windows. the first 6 slices will contain some dummy 0s
  • (126=2/')_ drop chunks of 1 1 1 1 1 1 0, i.e. where the last value in the chunk is a dummy 0 inserted for bit stuffing purposes
  • *|+ return the last value of each chunk (saves a byte over *'|')

JavaScript (Node.js), 61 bytes


Try it online!

I have tried to make sure it outputs numbers.

-10 bytes by pxeger

  • \$\begingroup\$ The second one doesn't work: /1{6}0/ needs to be adapted to true and false \$\endgroup\$
    – pxeger
    Commented Jun 10, 2021 at 8:21
  • \$\begingroup\$ 61: Try it online! \$\endgroup\$
    – pxeger
    Commented Jun 10, 2021 at 8:47
  • \$\begingroup\$ @pxeger First comment: the second one was not the final solution, just a remark, so I will remove that. Second comment: I'll edit that into the answer. \$\endgroup\$
    – user100690
    Commented Jun 10, 2021 at 8:49
  • \$\begingroup\$ By modifying pxeger's version to take an array, 59 bytes \$\endgroup\$
    – emanresu A
    Commented Jun 10, 2021 at 8:50
  • \$\begingroup\$ @Ausername Thanks, but I'd like to keep it with the string version. Feel free to post yours as an answer \$\endgroup\$
    – user100690
    Commented Jun 10, 2021 at 8:51

Jelly, 14 bytes


Try it online!

Takes J and K as 0 and 1.


Retina 0.8.2, 31 bytes


Try it online! Link includes test cases. Explanation:


For each letter, look behind for a possible duplicate or a leading J.


If it was then replace it with a 1 otherwise replace it with a 0.


Remove the 0 that appears after a run of six 1s.


Jelly, 14 bytes


Try it online!

A monadic link taking the argument as a vector of 0 (=J) and 1 (=K) and returning a vector of 0 and 1.


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.