String to Bit Transition

9

2

Task

Given an input string of one or more ASCII characters which codepoints are between 0 and 128 (exclusive), do the following:

  1. Convert each character into its 7-bit ASCII code (if the ASCII code is less than 7 bits, put leading zero bits)
  2. Concatenate all bits (this results in 7*n bits where n is the number of characters)
  3. For each bit in this bitstream, print 1 if it is different from the previous bit, and print 0 otherwise. The first output bit is always 1.

Example

Input:

Hi

Output:

11011001011101

Explanation:

The string "Hi" has the ASCII codes

72 105

which in bits are:

1001000 1101001

And the transition bits indicators:

11011001011101

This is code golf. Lowest byte count wins.

Test Cases

Test case 1:

Hello World!
110110010101110011010101101010110001110000111110000110000001011101101010101100110001

Test case 2:

%% COMMENT %%
1110111111011111100001100010010100001010110101011010011101010011111110011000001101111110111

Test case 3 (credit to Luis Mendo):

##
11100101110010

Congrats to Luis Mendo for the shortest solution with 9 bytes in MATL!

justhalf

Posted 2019-07-10T01:37:21.267

Reputation: 2 070

I'm confused - don't you mean 1 if the bit is different than the previous one? – Chas Brown – 2019-07-10T03:10:13.680

Oops, yeah, sorry, fixed that. Error after editing. Thanks @ChasBrown – justhalf – 2019-07-10T03:26:55.503

There are 7! Way at last concatenate 2 7 bits string, and you not show either in example which one – RosLuP – 2019-07-10T08:42:00.157

2Suggested test case ## (leading 0 bit; some answers currently fail because of that) – Luis Mendo – 2019-07-10T09:25:28.210

4How is this a duplicate of the Manchester encoding challenge? Am I missing something? – gastropner – 2019-07-10T10:25:56.737

2The other challenge says converting an input stream of bits into a double-rate output stream, with each input '1' translated to a '01' and each input '0' translated to a '10'. So not dupe in my opinion. If a large number of people upvote @gastropner's comment above I can un-dupe (or any other user with that ability) – Luis Mendo – 2019-07-10T11:24:33.733

1@Shaggy: Both test cases include a space, which has only a single bit set, and not the 7th. So I don't think the problem statement is guaranteeing that each ascii code will be exactly 7 bits in length. – recursive – 2019-07-10T15:05:55.723

@Shaggy, yes, I perhaps should clarify that if the ascii code is less than 7-bit it should be prepended with leading zeros. And, like recursive said, the space character already has less than 7 bits. – justhalf – 2019-07-10T16:26:54.507

@LuisMendo, the % character (second test case) also starts with 0. – justhalf – 2019-07-10T16:58:27.217

@justhalf In some languages, if at least on character has all 7 bits (i.e. starts with 1) then all characters in the string are converted to 7 bits, even if fewer bytes would suffice for some characters. Consider this example in Octave, and compare with this, which only produces 6 bits. My test case was aimed to catch that sort of mistake

– Luis Mendo – 2019-07-10T17:05:35.453

Ah, ok. I am not familiar with that. Thanks for catching that! I'll add the third test case. – justhalf – 2019-07-10T17:06:42.707

Do I need to support a string of length 0? Also, I can save a few bytes if it is guaranteed that for characters wider than 7-bits, all bits above the 7th are 0 - I'll assume that's the case unless you say otherwise – SmileAndNod – 2019-07-17T01:31:12.707

Bits above the 7th are all 0 -> yes, since the maximum code point that I would like to test is 127 (less than 128), as given in the description. String of length 0 I haven't really considered, but I guess it should be supported. – justhalf – 2019-07-17T12:29:21.157

Does the code have to support embedded zero bytes? (for example, C uses zero bytes as string terminator). – celtschk – 2019-07-17T21:20:30.417

It's ok to not handle null bytes. – justhalf – 2019-07-17T21:46:15.070

1@SmileAndNod On second thought, I think you don't need to handle empty string. – justhalf – 2019-07-17T21:47:44.403

Answers

4

MATL, 9 bytes

Hj7&B!hdg

Try it online!

Explanation

H     % Push 2
j     % Read line of input, unevaluated
7&B   % Convert to binary with 7 bits. Gives a 7-column matrix
!     % Transpose
h     % Concatenate horiontally. The matrix is read in column-major order
d     % Consecutive differences
g     % Convert to logical. Implicitly display

Luis Mendo

Posted 2019-07-10T01:37:21.267

Reputation: 87 464

1This is the shortest so far. +1. It's fun to have a built-in for consecutive differences. – justhalf – 2019-07-12T05:19:17.837

5

Python 2, 58 bytes

n=1
for c in input():n=n<<7|ord(c)
print'1'+bin(n^n/2)[4:]

Try it online!

xnor

Posted 2019-07-10T01:37:21.267

Reputation: 115 687

4

Japt -P, 11 bytes

Takes advantage of the fact that spaces can be coerced to 0 in JavaScript when trying to perform a mathematical or, in this case, bitwise operation on it.

c_¤ù7Ãä^ i1

Try it or run all test cases

c_¤ù7Ãä^ i1     :Implicit input of string
c_              :Map codepoints
  ¤             :  Convert to binary string
   ù7           :  Left pad with spaces to length 7
     Ã          :End map
      ä^        :XOR consecutive pairs
         i1     :Prepend 1
                :Implicitly join and output

Shaggy

Posted 2019-07-10T01:37:21.267

Reputation: 24 623

The 7-bit means that if it is 32 (for space character), it would be 0100000. Also the % character (37) would be 0100101 – justhalf – 2019-07-10T16:58:04.387

It's working now. +1 – justhalf – 2019-07-10T17:04:10.223

2

CJam, 21 bytes

1q{i2b7Te[}%e__(;.^);

Try it online!

Explanation

Showing the stack with a sample input of 5:

1 q      e# Push 1 and then the whole input: 1 "5"
{
  i      e# Convert to its char code: 1 [53]
  2 b    e# Convert to binary: 1 [[1 1 0 1 0 1]]
  7 T e[ e# Left-pad with 0 to length 7: 1 [[0 1 1 0 1 0 1]]
} %      e# Map this block over every character in the string
e_       e# Flatten array: 1 [0 1 1 0 1 0 1]
_ ( ;    e# Duplicate array and remove its first element: 1 [0 1 1 0 1 0 1] [1 1 0 1 0 1]
. ^      e# Element-wise xor: 1 [1 0 1 1 1 1 1]
) ;      e# Remove and pop the last element of the array: 1 [1 0 1 1 1 1]
         e# Stack implicitly printed: 1101111

To see if a bit is different from the previous bit, we do a vector (element-wise) xor between the bit array and the bit array without the first element. We also remove the last bit of the result, because it is always the last bit of the longer array unchanged.

NinjaBearMonkey

Posted 2019-07-10T01:37:21.267

Reputation: 9 925

2

Ruby -p, 68 57 bytes

-11 bytes by shamelessly stealing the method used by xnor's Python solution.

l=1
gsub(/./){l=l<<7|$&.ord}
$_=?1+(l^l/2).to_s(2)[2..-1]

Try it online!

Original solution:

gsub(/./){'%07b'%$&.ord}
l=p
gsub(/./){b=$&.ord-48;r=l ?l^b:1;l=b;r}

Try it online!

Value Ink

Posted 2019-07-10T01:37:21.267

Reputation: 10 608

2

APL (Dyalog Unicode), 16 bytesSBCS

Full program. Prompts for string from stdin.

1,2≠/∊1↓¨11⎕DR¨⍞

Try it online!

⍞ prompt for input ("a quote in a console")

11⎕DR¨ change each character to bit-Boolean Data Representation

1↓¨ drop the first bit from each

∊ ϵnlist (flatten)

2≠/ pairwise difference

1, prepend a one

Adám

Posted 2019-07-10T01:37:21.267

Reputation: 37 779

2

Jelly, 12 bytes

O+Ø⁷BḊ€FIA1;

Try it online!

Nick Kennedy

Posted 2019-07-10T01:37:21.267

Reputation: 11 829

2

Octave, 36 30 bytes

Fix thanks to Luis Mendo

-2 bytes thanks to Sanchises 

@(a)[1;~~diff(de2bi(a,7)'(:))]

Try it online!

Expired Data

Posted 2019-07-10T01:37:21.267

Reputation: 3 129

You can probably shave off quite a few bytes with de2bi. – Sanchises – 2019-07-13T12:18:19.860

Wasn't working for me before @sanchises but I'll take another look when I can – Expired Data – 2019-07-13T12:23:37.657

Try it online! – Sanchises – 2019-07-13T15:08:24.493

2

Charcoal, 25 bytes

⭆θ◧⍘℅鲦⁷←Ｗⅈ←Ｉ﹪⍘ＫＤ²←01 ²1

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

⭆θ◧⍘℅鲦⁷←

Convert all the characters to binary and pad them to a length of 7 and then print them, but leave the cursor over the last digit.

Ｗⅈ

Repeat until the cursor is over the first digit.

←Ｉ﹪⍘ＫＤ²←01 ²

Calculate whether the digits are different and overwrite each digit with the difference.

1

Overwrite the first digit with a 1.

Neil

Posted 2019-07-10T01:37:21.267

Reputation: 95 035

2

PowerShell, 73 56 49 bytes

$args|%{$b=+$_
6..0}|%{+($c-ne($c=($b-shr$_)%2))}

Try it online!

-17 bytes thanks to mazzy :)

Andrei Odegov

Posted 2019-07-10T01:37:21.267

Reputation: 939

1-17 bytes :D – mazzy – 2019-07-10T15:52:18.507

Awesome, you have to post it yourself. – Andrei Odegov – 2019-07-10T16:50:16.913

this answer for you. my princess is in another castle :)))) – mazzy – 2019-07-10T16:56:37.723

1@mazzy, some more -7 bytes :) – Andrei Odegov – 2019-07-10T23:08:56.913

awesome and brilliant! 【ツ】 – mazzy – 2019-07-11T04:41:52.280

1

Stax, 13 12 bytes

ìEÖâU₧(~¬8IE

Run and debug it

If it's guaranteed that all input characters have the 7th bit set, as some answers assume, it can be done in 10 bytes

recursive

Posted 2019-07-10T01:37:21.267

Reputation: 8 616

1

Python 2, 104 bytes

lambda w:reduce(lambda(A,P),C:(A+'10'[P==C],C),bin(reduce(lambda a,c:a*128+ord(c),w,1))[3:],('','x'))[0]

Try it online!

A quick stab at it.

Chas Brown

Posted 2019-07-10T01:37:21.267

Reputation: 8 959

Clever trick with a*128+ord(c)! But isn't the reduce and lambda kind of costly? – justhalf – 2019-07-10T03:54:06.000

1

K (ngn/k), 9 13 bytes

Solution:

~=':,/(7#2)\'

Try it online!

Explanation:

~=':,/(7#2)\' / the solution
           \' / convert each
      (   )   / do this together
       7#2    / 2 2 2 2 2 2 2
    ,/        / flatten
 =':          / equal to each-previous?
~             / not

Notes:

  • +4 bytes to support strings consisting only of 6-bit chars

streetster

Posted 2019-07-10T01:37:21.267

Reputation: 3 635

This seems to fail for input # for example (output only has 6 bits) – Luis Mendo – 2019-07-10T09:19:22.957

@streetster, do you want to post the fixed version? – justhalf – 2019-07-11T14:18:01.020

1

Dart, 213 168 bytes

f(s,{t,i}){t=s.runes.map((r)=>r.toRadixString(2).padLeft(7,'0')).join().split('').toList();for(i=t.length-1;i>0;i--)t[i]=t[i]==t[i-1]?'0':'1';t[0]='1';return t.join();}

Previous one-liner

f(String s)=>'1'+s.runes.map((r)=>r.toRadixString(2).padLeft(7,'0')).join().split('').toList().reversed.reduce((p,e)=>p.substring(0,p.length-1)+(p[p.length-1]==e?'0':'1')+e).split('').reversed.join().substring(1);

Try it online!

This verbosity and lack of easy built ins is really killing this one. Still managed to pull a one liner though.

  • -45 bytes by not using a one liner and using a for loop

Elcan

Posted 2019-07-10T01:37:21.267

Reputation: 913

1

Python 3, 88 84 bytes

l=2;s=''
for c in''.join(f'{ord(c):07b}'for c in input()):s+='01'[l!=c];l=c
print(s)

Try it online!

I feel that the assignments should be avoidable, but couldn't think of any way to do that.

Update:

justhalf

Posted 2019-07-10T01:37:21.267

Reputation: 2 070

184 bytes – movatica – 2019-07-25T10:01:53.007

1

Kotlin, 182 bytes

var l='6'
fun f(b:String)=b.fold(""){t,i->t+"".a(i.toInt())}.map{if(l==it){l=it;0} else {l=it;1}}
fun String.a(v:Int):String=if(v<=0)"${this}0".reversed() else "${this}${v%2}".a(v/2)

Try it online!

Hopefully I can improve this soon, I feel like there must be some spots for improvement but I can't think right now

Quinn

Posted 2019-07-10T01:37:21.267

Reputation: 1 153

1

JavaScript (V8), 150 95 bytes

-55 thanks to @dana

x=>[...[...x].reduce((a,c)=>a+c.charCodeAt(0).toString(2).padStart(7,0),"")].map(c=>x!=(x=c)|0)

Try it online!

Geza Kerecsenyi

Posted 2019-07-10T01:37:21.267

Reputation: 1 892

1

Ruby -p, 50 bytes

gsub(/./){"%07b"%$&.ord}
gsub(/./){$`=~/#$&$/?0:1}

Try it online!

Explanation

First line, same as Value Ink's answer:

gsub(/./){       $&    }   # Replace each character $&…
                   .ord    # …with its ASCII code…
                %          # …formatted as…
          "%07b"           # …binary digits padded to 7 places.

Second line:

gsub(/./){      $&      }  # Replace each character $&…
          $`               # …if the text to its left…
            =~             # …matches…
              /#  $/       # …the Regexp /c$/ where "c" is the character…
                    ?0:1   # …with 0, or 1 otherwise.

In Ruby you can use interpolation in Regexp literals, e.g. /Hello #{name}/, and for variables that start with $ or @ you can omit the curly braces, so if e.g. $& is "0" then the grawlixy /#$&$/ becomes /0$/.

Jordan

Posted 2019-07-10T01:37:21.267

Reputation: 5 001

1

Perl 5 -p, 60 bytes

s/./sprintf'%07b',ord$&/ge;s/.(?=(.))/0|$&^$1/ge;s/^/1/;chop

Try it online!

Xcali

Posted 2019-07-10T01:37:21.267

Reputation: 7 671

1

C (gcc (MinGW)), 90 bytes

Requires a compiler providing itoa().

n[9],b,c;f(char*s){for(b=*s<64;c=*s++;printf("%07s",itoa((c^c/2)&127,n,2)))c|=b<<7,b=c&1;}

gastropner

Posted 2019-07-10T01:37:21.267

Reputation: 3 264

88 bytes – ceilingcat – 2019-09-13T22:28:49.437

1

Emojicode, 263 bytes

➡️sb❗️❗️sb❗️➕128 2❗️1 7❗️➡️s?➡️pb s↪️bp0❗️1❗️b➡️p

Try it online here.

Ungolfed:

    Main code block
     ➡️   s   Start with s as the empty string
     b       For each byte b in the input ...
    ❗️ ❗️ 
         s   ... append ...
              b ❗️ ➕ 128   ... b + 128 (this gives the leading zero(s) in case the binary representation of b is shorter than 7 digits) ...

                 2   ... in binary ...
              ❗️
              1 7   ... without the leading one ...
           ❗️
        
        ➡️  s   ... to s
    
    ? ➡️   p   This will be used as the previous character, by assigning it neither 0 nor 1 we assure the first bit output is always a one
     b s    For each character in s:
        ↪️ b  p    If it is the same as the previous character ...
             0 ❗️   ... output a zero ...
              ... else ...
             1 ❗️  ... output a one
        
        b ➡️  p   And the current character becomes the new previous character.

O.O.Balance

Posted 2019-07-10T01:37:21.267

Reputation: 1 499

1

Tcl, 215 167 140 bytes

{{s {B binary} {X ~$w/64}} {join [lmap c [split $s {}] {$B scan $c c w;$B scan [$B format i [expr 2*$w^$w^$X<<7]] B7 r;set X $w;set r}] ""}}

Try it online!

Uses shift-by-one and exclusive-or to detect transitions. Carries lsb of current character to msb of next character. Combines output for each character by joining list returned by lmap.

Uses lambdas with default arguments to save bytes on initialization and repeated commands.

Relies heavily on order of operation. Works for empty string.

SmileAndNod

Posted 2019-07-10T01:37:21.267

Reputation: 119

1

Python3.8, 72 bytes

Solution:

lambda a:["10"[a==(a:=x)]for x in"".join(bin(ord(i)+128)[3:]for i in a)]

Explanation:

Ever since Python 3.8 introduced assignment expressions (rather than the standard assignment statements), I have wanted to use them in a list comprehension that needs to remember the last item. This is not the best way to do this but demonstrates an interesting method of using the assignment expression.

The code creates a lambda function which takes the required argument which is the string to convert. When called, the function proceeds as follows. Every character in a is converted to its character code which 128 is added to for dealing with 6-bit characters (the binary representation will always be 8 bits and we can chop off the first bit). This number is converted to binary and the header (0x) and the initial 1 from adding 128 is chopped off. These new strings are then joined into one larger string.

For each character in this new string (which contains the concatenated 7-bit representation of the text), it is checked if the character is the same as the previous character. What happens with the first character? The first result character should always be "1" so we just have to make sure that whatever is in the last character variable is neither "1" nor "0". We do this by reusing the original parameter now that we are not using it anymore. This may be a problem if the original string was a single "0" (a single "1" just happens to work) but we will ignore that.

During the comparison, the previous character was evaluated first so when we use the assignment expression to set the previous character variable to the current character, it does not affect the comparison expressions' evaluation.

The comparison either produces True or False which can also be used as 1 or 0 respectively in Python, so they are used to look up either a "1" or "0" in a string

infinityCoding

Posted 2019-07-10T01:37:21.267

Reputation: 11

You can save some bytes by using string format literals: bin(ord(i)+128)[3:] -> f"{ord(i):07b}" – movatica – 2019-07-25T10:02:54.487

1

05AB1E (legacy), 12 bytes

Çb7jð0:¥ÄJ1ì

Uses the legacy version of 05AB1E, since j implicitly joins the strings together, which requires an explicit J after the j in the new version of 05AB1E.

Try it online or verify all test cases.

Explanation:

Ç             # Convert the (implicit) input-string to a list of ASCII code-points
              #  i.e. "Hi#" → [72,105,35]
 b            # Convert each integer to a binary string
              #  → ["1001000","1101001","100011"]
  7j          # Prepend each with spaces to make them length 7,
              # and join everything together to a single string implicitly
              #  → "10010001101001 100011"
    ð0:       # Replace all those spaces with 0s
              #  → "100100011010010100011"
       ¥      # Get the deltas of each pair of 1s/0s
              #  → [-1,0,1,-1,0,0,1,0,-1,1,-1,0,1,-1,1,-1,0,0,1,0]
        Ä     # Get the absolute value of this
              #  → [1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,0]
         J    # Join them all together
              #  → "10110010111011110010"
          1ì  # And prepend a 1
              #  → "110110010111011110010"
              # (after which the result is output implicitly)

Kevin Cruijssen

Posted 2019-07-10T01:37:21.267

Reputation: 67 575

1

Haskell, 137 bytes

import Data.Char
b 0=[]
b n=odd n:b(n`div`2)
d x|x='1'|1<2='0'
c=('1':).map d.(zipWith(/=)<*>tail).concatMap(reverse.take 7.b.(+128).ord)

Try it online!

The biggest problem here is converting booleans (result of the XOR) to '0'/'1'.

Lamdba

Posted 2019-07-10T01:37:21.267

Reputation: 11

1

PHP, 90 bytes

for(;$c=ord($argn[$j++]);$o.=sprintf('%07b',$c));for(;($q=$o[$i++])>'';$p=$q)echo$p!=$q|0;

Try it online!

640KB

Posted 2019-07-10T01:37:21.267

Reputation: 7 149

0

C# (Visual C# Interactive Compiler), 80 bytes

s=>{for(int p,c=2,i=0;i<7*s.Length;Write(p==c?0:1))(p,c)=(c,1&s[i/7]>>6-i++%7);}

Try it online!

dana

Posted 2019-07-10T01:37:21.267

Reputation: 2 541

0

JavaScript (V8), 73 bytes

s=>[...c=s.repeat(7)].map((_,i)=>(c=1&s.charCodeAt(i/7,p=c)>>6-i%7)!=p|0)

Try it online!

dana

Posted 2019-07-10T01:37:21.267

Reputation: 2 541

Asked: 2019-07-10T01:37:21.267

Viewed: 1 067 times

Active: 2019-08-08T18:19:42.717