31
\$\begingroup\$

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.

Task

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).

Test-cases

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

Rules

  • 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
\$\endgroup\$
6
  • \$\begingroup\$ Sandbox \$\endgroup\$ – pxeger Jun 10 at 7:16
  • 2
    \$\begingroup\$ Bounty for the answer that will run on his 6502 breadboard computer. :) \$\endgroup\$ – 640KB Jun 10 at 13:44
  • 1
    \$\begingroup\$ do test cases say that initial J isn't present in the input? \$\endgroup\$ – Noone AtAll Jun 11 at 18:25
  • \$\begingroup\$ @NooneAtAll correct; the intial J is not part of the input \$\endgroup\$ – pxeger Jun 11 at 19:14
  • 2
    \$\begingroup\$ @640KB which 6502 platform are we supposed to target? I want to try using this emulator. \$\endgroup\$ – Razetime Jun 15 at 8:14

19 Answers 19

11
+200
\$\begingroup\$

convey, 31 25 bytes

Takes JK as 01.

>="*>0
",v+<"(6
{0>">>!`}

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

\$\endgroup\$
7
\$\begingroup\$

Husk, 11 bytes

σḋ126ḋ63Ẋ=Θ

Try it online!

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

Explanation

σḋ126ḋ63Ẋ=Θ
          Θ Prepend 0
        Ẋ=  map overlapping pairs by equality
σḋ126ḋ63    replace binary digits of 126 with binary digits of 63 (stolen from Luis Mendo)
\$\endgroup\$
1
  • 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\$ – Dominic van Essen Jun 11 at 23:06
6
\$\begingroup\$

MATL, 15 14 bytes

0ihd~126B63BZt

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

Try it online! Or verify all test cases.

Explanation

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
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 54 bytes

s=>s.replace(/./g,a=>s^(s=a>"J")?i=i>5?'':0:++i/i,i=0)

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

s=>s.flatMap(a=>s^(s=a)?i=i>5&&[]:++i>0,i=0)

Try it online!

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

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

R, 83 76 62 bytes

function(x)gsub('(1{6})0','\\1',Reduce(paste0,+!diff(c(0,x))))

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
))
\$\endgroup\$
2
  • 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\$ – Dominic van Essen Jun 10 at 23:53
  • \$\begingroup\$ @DominicvanEssen nice golf of the rle approach! \$\endgroup\$ – pajonk Jun 11 at 5:56
4
\$\begingroup\$

C (gcc), 79 76 bytes

-3 thanks to @ceilingcat

x;c;a(char*p){x=74;for(c=1;c*=*p==x,x=*p++;c=c>5?x=*p++,1:c+1)putchar(!!c);}

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.

Encoder

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

J, 26 bytes

Takes in JK as 0 1.

t#~0=_6|.(6$1)E.t=:2=/\0,]

Try it online!

t#~0=_6|.(6$1)E.t=:2=/\0,]
                       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
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 16 bytes

1p-Ṫv¬ṅ\16*:0+$V

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.

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

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

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

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ int can be shortened to +. \$\endgroup\$ – ovs Jun 10 at 11:32
  • \$\begingroup\$ @ovs thanks for the tip \$\endgroup\$ – wasif Jun 10 at 11:34
3
\$\begingroup\$

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.

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

Charcoal, 19 bytes

⪫⪪⭆θ⁼ι§⁺Jθκ⁺×1⁶0×1⁶

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
\$\endgroup\$
2
\$\begingroup\$

Stax, 16 bytes

Å3≈àE∩◄σ←π<δô╝ìà

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.

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

K (ngn/k), 23 bytes

*|+(126=2/)_7'(&6),0=':

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 *'|')
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 13 bytes

0ìø€ËJƵPbD¨.:

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

0ìø€ËJƵPbD¨.:  # full program
           .:  # replace all instances of...
      ƵP       # 126...
        b      # in binary...
           .:  # in...
     J         # joined...
    Ë          # are all digits of...
   €           # each element in...
               # implicit input...
  ø            # with each element paired with corresponding element in...
0              # literal...
 ì             # concatenated with...
               # implicit input...
    Ë          # equal...
           .:  # with...
       ƵP      # 126...
         bD    # in binary...
           ¨   # excluding the last digit
               # implicit output
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 61 bytes

n=>n.replace(/./g,(e,i)=>1-e^n[i-1]).replace(/1{6}0/g,111111)

Try it online!

I have tried to make sure it outputs numbers.

-10 bytes by pxeger

\$\endgroup\$
5
  • \$\begingroup\$ The second one doesn't work: /1{6}0/ needs to be adapted to true and false \$\endgroup\$ – pxeger Jun 10 at 8:21
  • \$\begingroup\$ 61: Try it online! \$\endgroup\$ – pxeger Jun 10 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\$ – Recursive Co. Jun 10 at 8:49
  • \$\begingroup\$ By modifying pxeger's version to take an array, 59 bytes \$\endgroup\$ – A username Jun 10 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\$ – Recursive Co. Jun 10 at 8:51
1
\$\begingroup\$

Jelly, 14 bytes

Ż⁼Ɲ0ȯ1בʋ7Ƒ?ɼƇ

Try it online!

Takes J and K as 0 and 1.

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

Retina 0.8.2, 31 bytes

(.)(?<=(\1.|^J)?)
$#2
1{6}0
6$*

Try it online! Link includes test cases. Explanation:

(.)(?<=(\1.|^J)?)

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

$#2

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

1{6}0
6$*

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

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

Jelly, 14 bytes

ŻI¬“~?‘B¤œṣjƭƒ

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.

\$\endgroup\$

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.