16
\$\begingroup\$

Inspired by this video by Ben Eater. This challenge forms a pair with Decode 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. Encoding works as follows:

  • Start with some initial state, which is either J or K
  • For each bit to be encoded:
    • If the bit is a 0, switch the state from J to K or from K to J
    • If the bit is a 1, maintain the same state as before
    • and output that state

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 1s are read, an extra meaningless 0 bit is processed to ensure the signal never stays in the same state (J or K) for too long.

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.

Task

Given a non-empty binary string as input, encode the string using the USB implementation of NRZI described above, and output a string of Js or Ks.

Test-cases

Input              Output
=====================================
1                  J
0                  K
1000101            JKJKKJJ
00000000           KJKJKJKJ
11111111           JJJJJJKKK
001111100          KJJJJJJKJ
0011111100         KJJJJJJJKJK
00111111100        KJJJJJJJKKJK
0011111111111100   KJJJJJJJKKKKKKKJKJ
0011011000111001   KJJJKKKJKJJJJKJJ
01101000011101000111010001110000011100110011101000101111001011110111011101110111011101110010111001111001011011110111010101110100011101010110001001100101001011100110001101101111011011010010111101110111011000010111010001100011011010000011111101110110001111010110010001010001011101110011010001110111001110010101011101100111010110000110001101010001   KKKJJKJKJJJJKKJKJJJJKKJKJJJJKJKJKKKKJKKKJKKKKJJKJKKJJJJJKJJKKKKKJJJJKKKKJJJJKKKKJJJJKKKKJKKJJJJKJJJJJKJJKKKJJJJJKKKKJJKKJJJJKKJKJJJJKKJJKKKJKJJKJJJKJJKKJKKJJJJKJJJKJKKKJJJKKKKKJJJKKKJJKJJKKKKKJJJJKKKKJJJKJKJJKKKKJJKJKKKJKJJJKKKJJKJKJKKKKKKKJKKKKJJJKJKKKKKJJKKKJKKJKJJKKJKJJKKKKJJJJKJJJKKJKJJJJKKKKJKKKKJKKJJKKJJJJKKKJKKKKJJKKKJKJKKKJKJJJKKJJKJKK

Rules

  • The input should be a string or array of 1s and 0s or of trues and falses
  • The output should be a string or array, with the two states J and K being represented by any two distinct values
  • You may use any standard I/O method
  • Standard loopholes are forbidden
  • This is , so the shortest code in bytes wins
\$\endgroup\$
6
  • \$\begingroup\$ Sandbox \$\endgroup\$ – pxeger Jun 11 at 19:34
  • 1
    \$\begingroup\$ Should "After 6 consecutive 1 bits are written" be "... read"? \$\endgroup\$ – Jonathan Allan Jun 11 at 20:56
  • \$\begingroup\$ I see that we may choose what we output for J and K, but may we take an input where 0 means true and 1 means false? \$\endgroup\$ – Jonathan Allan Jun 11 at 23:07
  • \$\begingroup\$ @JonathanAllan 1: no - after you've written the Js or Ks corresponding to 6 consecutive 1 bits, you should pretend there's an extra 0 and encode that too. 2: I think I'm gonna say no on that. \$\endgroup\$ – pxeger Jun 12 at 5:53
  • 1
    \$\begingroup\$ @JonathanAllan ok, changed \$\endgroup\$ – pxeger Jun 12 at 13:52

14 Answers 14

5
\$\begingroup\$

Husk, 11 bytes

G=Jḋ126xḋ63

Try it online!

Input as array of 0s and 1s, output as array of 1s (for state J) and 0s (for state K): TIO header converts to Js and Ks.

       x    # split input on
        ḋ63 # binary digits of 63 = [1,1,1,1,1,1]
  J         # then join back together using
   ḋ126     # binary digits of 126 = [1,1,1,1,1,1,0]
G=          # and scan from the left by equality
\$\endgroup\$
0
5
\$\begingroup\$

JavaScript (ES6), 53 bytes

Expects a binary string. Returns an array of 0's and 1's.

s=>[...s.replace(/1{6}/g,'$&0')].map(q=c=>q^=c^!!++q)

Try it online!

Commented

This is a rather straightforward implementation in two steps.

s =>           // s = input string

               // STEP 1 - Bit stuffing
               //
[...s.replace( // replace in s:
  /1{6}/g,     //   each group of six consecutive 1's
  '$&0'        //   with the same group with a trailing 0
)]             // split the resulting string

               // STEP 2 - NRZI encoding
               //
.map(q =       // initialize q to a zero'ish, non-numeric value
  c =>         // for each character c:
  q ^=         //   invert q if ...
    c ^        //     ... c is not equal to the result of
    !!++q      //     the test 'q is a number'
               //     (0 on the 1st iteration, 1 afterwards)
)              // end of map()
\$\endgroup\$
4
\$\begingroup\$

Jelly, 12 bytes

7Ṭ¬©Ṗœṣ@j®⁼\

A monadic Link that accepts a list of integers (from \$[0,1]\$) and yields a list of integers (from \$[0,1]\$) where \$0\$ represents \$K\$.

Try it online! Or see the test-suite.

How?

7Ṭ¬©Ṗœṣ@j®⁼\ - Link: list of integers in [0..1], A
7            - seven
 Ṭ           - untruth -> [0,0,0,0,0,0,1]
  ¬          - logical NOT -> [1,1,1,1,1,1,0]
   ©         - copy to register
    Ṗ        - pop -> [1,1,1,1,1,1]
     œṣ@     - (A) split on sublists equal to (that)
         ®   - recall from register
        j    - (split list) join (register value)
           \ - cumulative reduce with:
          ⁼  -   (left) equals (right)?

11 if we could take input with 0 meaning true and 1 meaning false with 7Ṭ©Ṗœṣ@j®⁻\.

\$\endgroup\$
3
\$\begingroup\$

convey, 31 bytes

Outputs KJ as 01.

v|6
0"("=0
+*6!<}
""~,="
{ 5 1<

Try it online!

In the top left is a counter that gets incremented by the input 1s + and reset whenever it reaches 6 |6 or the input has a 0 *. If it reaches 6, it also injects a 0 into the stream (the ("=0 6!< part). Because the input stream would be faster (the 0 would get there 2 bits too late), we delay it by 5 ticks ~5. On the bottom right is the current output bit that gets flipped on 0s with = and then copied into the output =}.

enter image description here

\$\endgroup\$
3
\$\begingroup\$

R, 59 bytes

function(x)cumsum(49-utf8ToInt(gsub('(1{6})','\\10',x)))%%2

Try it online!

Regex-based bit-stuffing stolen from inspired by pajonk's R answer to the paired usb-decoding challenge.

The state-switching is achieved here by determining whether the cumulative sum is odd or even.

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 16 bytes

\16*:0+V1$(nɽ߬…

Try it Online!

\16*             # Six ones
    :0+          # Duplicate and append a 0
       V         # Replace in input
        1$       # Starting with a one
          (      # Iterating through the string
             ߬  # Flip if...
           nɽ    # It's a 1
               … # Print without popping

Returns 1 for J and 0 for K. Here's a version that does JKs.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 14 bytes

“?~‘Bœṣjƭƒ^¬¥\

Try it online!

-2 bytes thanks to Nick Kennedy

“?~‘Bœṣjƭƒ^¬¥\  Main Link; accepts a list of [0, 1] on the left
“?~‘            63, 126
    B           To binary ([1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0])
         ƒ      Reduce starting with the input:
        ƭ       Tie; cycle
     œṣ         The first time, split on sublist ([1, 1, 1, 1, 1, 1])
       j        The second time, join on [1, 1, 1, 1, 1, 1, 0]
             \  Cumulative reduce
          ^´   Each time, XOR, and then logical NOT
\$\endgroup\$
2
  • \$\begingroup\$ -2 bytes \$\endgroup\$ – Nick Kennedy Jun 11 at 22:11
  • 1
    \$\begingroup\$ @NickKennedy ah I keep forgetting hooked f. Thanks :D \$\endgroup\$ – hyper-neutrino Jun 12 at 1:15
3
\$\begingroup\$

<>^v, 161 bytes

1±n"0"o"1"i0q.h"J"j"K"kJtv
v   v=ICc®NHn)N  v=N-?1¿H<
    >Q)7=v_qv    >`!     ~
 vcOn(Nq0<  v    >Ktv    T
v<          <>TJ=^Jtv    ^
>C         O=^      >    ^

Explanation

First line
1±n"0"o"1"i0q.h"J"j"K"kJtv

1                          Push 1 to stack
 ±                         Negate
  n                        Store in variable `n`
   "0"                     Push "0"
      o                    Store in variable `o`
       "1"                 Push "1"
          i                Store in variable `i`
           0               Push 0
            q              Store in variable `q`
             .             Read line from stdin
              h            Store in variable `h`
               "J"         Push "J"
                  j        Store in variable `j`
                   "K"     Push "K"
                      k    Store in variable `k`
                       J   Push value of variable `j` ("J")
                        t  Store in variable `t`
                         v Redirect instruction pointer down

The variables i and o store the values "1" and "0"", j and k store "J" and "K". h contains the line read from stdin (1's and 0's). q, initialized to 0, will be used for bit stuffing. n is the "current character pointer".

The main loop
v   v=ICc®NHn)N  v=N-?1¿H< <-- loop starts here
    >Q)7=v_qv    >`!     ~
 vcOn(Nq0<  v    >Ktv    T
v<          <>TJ=^Jtv    ^
>C         O=^      >    ^
[start of loop]
<    Send instruction pointer leftward
H    Push value of variable `h` to stack
¿    Push length of top of stack
1    Push 1
?    Swap top two elements
-    Substract second element of stack to top of stack
N    Push value of variable `n`
=    If the top two elements of the stack (length of `h` - 1 and `n`) are equal (reached end of string)
    v    Send instruction pointer down
    >    Send instruction pointer right 
    `    Print newline
    !    Exit
N    Push value of variable `n` (character index in string)
)    Increment top of stack (increment character index in string)
n    Pop and write to variable `n`
H    Push value of variable `h` (string that was previously read from stdin and that contains the 0's and 1's
N    Push value of variable `n`
®    Set top of stack to (second element of stack)[top of stack] (character read)
c    Write to variable `c` ("current")
C    Push value of variable `c` (variable write pops the stack)
I    Push value of variable `i` ("1")
=    If the top two elements of the stack (current character and "1") are equal
    v    Send instruction pointer down
    >    Send instruction pointer right
    Q    Push value of variable `q`
    )    Increment top of stack
    7    Push 7
    =    If the top two elements of the stack are equal (`q` and 7)
        v    Send the instruction pointer down
        <    Send the instruction pointer left
        0    Push 0
        q    Pop stack and write to variable `q`
        N    Push value of variable `n`
        (    Decrement top of stack
        n    Pop stack and write to variable `n`
        O    Push value of variable `o` ("0")
        c    Pop stack and write to variable `c` (current character)
        v    Send instruction pointer down
        <    Send instruction pointer left
        Go to [loop-continuation]
    Else
    _    Pop stack (remove the 7)
    q    Pop stack and write to variable `q`
    v    Send instruction pointer down
    v    Same as previous, only for readability
    <    Send instruction pointer left
    <    Same
    Go to [loop-continuation]
[loop-continuation]
Else
v.   Send instruction pointer down
v.   Same
>.   Send instruction pointer right
C.   Push value of variable `c` to stack (current character)
O.   Push value of variable `O` ("0")
=.   If the top two elements of the stack (current character and "0") are equal
    ^    Send instruction pointer up
    >.   Send instruction pointer right
    T.   Push to stack value of variable `t` (current state, J or K)
    J.   Push to stack value of variable `j` ("J")
    =    If the top two elements of the stack (current state and "J" are equal)
        ^.   Send instruction pointer up
        >.   Send instruction pointer left
        K.   Push value of variable `k` ("K")
        t.   Pop stack and write to variable `t`
        v.   Send instruction pointer down
        Continue at the [here] indicator
    Else
    J    Push value of variable `j` ("J")
    t.   Pop stack and write to variable `t`
    v.   Send instruction pointer down
    Continue at the [here] indicator
[here]
>.   Send instruction pointer right
^.   Send instruction pointer up
^.   Same
T.   Push value of variable `t` ("J" or "K")
~.   Print top of stack without newline
Go to [start of loop] indicator

That can be clarified to :

while has not reached end of string:
    increment character_index
    current_character = string[character_index]
    if current_character is a 1:
        increment one_count
        if one_count is 7:
            set one_count to zero
            decrement character_index
            current_character = 0
    if current_character is a 0:
        if state is J:
            state = K
        else:
            state = J
    print state
print newline
exit

run online - largest input

run online - enter input yourself

\$\endgroup\$
3
\$\begingroup\$

Red, 79 bytes

func[x][p: 0 x: replace/all x"111111""1111110"forall x[prin p: 49 - x/1 xor p]]

Try it online!

Both input and output are strings of \$1\$s and \$0\$s. Output is done by printing. Despite the unwieldy string replacement, other ways to account for the extra zero bit tend to be even longer.

\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 33 32 bytes

1{6}
$&0
{+rT`d`JK`K.
1T`d`KJ`\d

Try it online! Link includes test cases. Explanation:

1{6}
$&0

Perform bit-stuffing.

{`

Make as many replacements as possible.

+rT`d`JK`K.

Change 0 after a K to J and 1 after a K to K. Change starting with the character after the last K (and working back, not that it matters), and keep replacing characters until there are no digits after a K.

1T`d`KJ`\d

The first remaining digit is not after a K, so change 0 to K and 1 to J.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 24 bytes

≔⪫⪪S×1⁶⁺×1⁶0θ⭆θ§JK№…θ⊕κ0

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

≔⪫⪪S×1⁶⁺×1⁶0θ

Perform bit-stuffing.

⭆θ§JK№…θ⊕κ0

For each prefix of the string count the number of 0s and output K if it is odd and J if it is even.

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 21 bytes

0=\.'(t,$0)/(t:6#$1)\

Try it online!

Takes input as a string of "1"s and "0"s. Returns a list of 0s (for J) and 1s (for K).

  • do a string replace of "111111" with "1111110"
    • (t:6#$1) store "111111" in variable t
    • (t,$0) append a "0" to the end of t, generating "1111110"
  • .' convert each character to an integer
  • 0=\ use a equals-scan, seeded with 0 (this does the non-return-to-zero part)
\$\endgroup\$
2
\$\begingroup\$

Haskell, 85 bytes

map("JK"!!).(0%)
j%(1:1:1:1:1:1:y)=j:j:j:j:j:j:j%(0:y)
j%(i:y)|k<-i^j*j^i=k:k%y
j%e=e

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 84 80 78 bytes

-6 thanks to @ceilingcat

x;c;a(char*p){for(c=0,x=1;*p;c>5&&a(L"10"+x))putchar(x^=*p<49),c=*p++/49*-~c;}

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

For output as actual J and K, Try it online!

Decoder

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.