Binary Sequences

Question

Given a binary number A as input with d > 1 digits, output a binary number B with d digits according to the following rules for finding the nth digit of B:

• The first digit of B is zero if the first and second digits of A are equal; otherwise, it is one.

• If 1 < n < d, then if the (n-1)th, nth and (n+1)th digits of A are equal, then the nth digit of B is zero; otherwise, it is one.

• The dth digit of B is zero if the (d-1)th and dth digits of A are equal; otherwise, it is one.

Rules

String/list input/output format is fine. Another allowed way of input/output is an integer followed by the number of preceding zeros (or following the number of preceding zeros).

Make your code as short as possible.

Test Cases

00 -> 00
01 -> 11
11 -> 00
010111100111 -> 111100111100
1000 -> 1100
11111111 -> 00000000
01010101 -> 11111111
1100 -> 0110

Answer 1

Haskell, 59 58 54 bytes

f s=[1-0^(a-b+a-c)^2|a:b:c:_<-scanr(:)[last s]$s!!0:s]

Try it online!

f s=                        -- input is a list of 0 and 1
          s!!0:s            -- prepend the first and append the last number of s to s
      scanr(:)[last s]      --   make a list of all inits of this list
     a:b:c:_<-              -- and keep those with at least 3 elements, called a, b and c
    1-0^(a-b+a-c)^2         -- some math to get 0 if they are equal or 1 otherwise

Edit: @Ørjan Johansen saved 4 bytes. Thanks!

Answer 2

Jelly, 9 bytes

.ịṚjṡ3E€¬

Try it online!

I/O as list of digits.

Explanation:

.ịṚjṡ3E€¬
.ịṚ       Get first and last element
   j      Join the pair with the input list, thus making a list [first, first, second, ..., last, last]
    ṡ3    Take sublists of length 3
      E€  Check if each has all its elements equal
        ¬ Logical NOT each

Answer 3

05AB1E, 6 bytes

¥0.ø¥Ā

I/O is in form of bit arrays.

Try it online!

How it works

¥       Compute the forward differences of the input, yielding -1, 0, or 1 for each
        pair. Note that there cannot be two consecutive 1's or -1's.
 0.ø    Surround the resulting array with 0‘s.
    ¥   Take the forward differences again. [0, 0] (three consecutive equal 
        elements in the input) gets mapped to 0, all other pairs get mapped to a 
        non-zero value.
     Ā  Map non-zero values to 1.

Answer 4

05AB1E, 11 bytes

¬s¤)˜Œ3ù€Ë_

Try it online! or as a Test suite

Explanation

¬             # get head of input
 s            # move it to the bottom of the stack
  ¤           # get the tail of the input
   )˜         # wrap in list ([head,input,tail])
     Œ3ù      # get sublists of length 3
        €Ë    # check each sublists for equality within the list
          _   # logical negation

Answer 5

Haskell, 66 61 59 bytes

g t@(x:s)=map("0110"!!)$z(x:t)$z t$s++[last s]
z=zipWith(+)

Try it online! Input is a list of zeros and ones, output is a string. Usage example: g [0,1,0,1,1,1,1,0,0,1,1,1] yields "111100111100".

---

Previous 61 byte solution:

g s=["0110"!!(a+b+c)|(a,b,c)<-zip3(s!!0:s)s$tail s++[last s]]

Try it online!

Answer 6

J, 26 14 bytes

Credit to Emigna's 05AB1E solution

2=3#@=\{.,],{:

Try it online!

Original attempt

2|2#@="1@|:@,,.@i:@1|.!.2]

Try it online!

             ,.@i:@1              -1, 0, 1
                    |.!.2]         shift filling with 2
  2         ,                      add a row of 2s on top
         |:                        transpose
   #@="1                           count unique elements in each row
2|                                 modulo 2

Answer 7

Python 3, 58 bytes

lambda a:[len({*a[i and~-i:i+2]})-1for i in range(len(a))]

Try it online!

Answer 8

Husk, 15 11 bytes

Ẋȯ¬EėSJ§e←→

Takes input as a list, try it online! Or try this one that uses strings for I/O.

Explanation

Ẋ(¬Eė)SJ§e←→ -- implicit input, for example [1,0,0,0]
      SJ     -- join self with the following
        §e   --   listify the
                  first and
                  last element: [1,0]
             -- [1,1,0,0,0,0]
Ẋ(   )       -- with each triple (eg. 1 0 0) do the following:
    ė        --   listify: [1,1,0]
   E         --   are all equal: 0
  ¬          --   logical not: 1
             -- [1,1,0,0]

Answer 9

Jelly, 8 bytes

I0;;0In0

I/O is in form of bit arrays.

Try it online!

How it works

I0;;0In0  Main link. Argument: A (bit array of length d)

I         Increments; compute the forward differences of all consecutive elements
          of A, yielding -1, 0, or 1 for each pair. Note that there cannot be
          two consecutive 1's or -1's.
 0;       Prepend a 0 to the differences.
   ;0     Append a 0 to the differences.
     I    Take the increments again. [0, 0] (three consecutive equal elements in A)
          gets mapped to 0, all other pairs get mapped to a non-zero value.
      n0  Perform not-equal comparison with 0, mapping non-zero values to 1.

Answer 10

JavaScript (ES6), 45 bytes

Takes input as an array of characters. Returns an array of integers.

a=>a.map((v,i)=>(i&&v^p)|((p=v)^(a[i+1]||v)))

Test cases

let f =

a=>a.map((v,i)=>(i&&v^p)|((p=v)^(a[i+1]||v)))

console.log(JSON.stringify(f([..."00"])))           // -> 00
console.log(JSON.stringify(f([..."01"])))           // -> 11
console.log(JSON.stringify(f([..."11"])))           // -> 00
console.log(JSON.stringify(f([..."010111100111"]))) // -> 111100111100
console.log(JSON.stringify(f([..."1000"])))         // -> 1100
console.log(JSON.stringify(f([..."11111111"])))     // -> 00000000
console.log(JSON.stringify(f([..."01010101"])))     // -> 11111111
console.log(JSON.stringify(f([..."1100"])))         // -> 0110

Commented

a =>                  // given the input array a
  a.map((v, i) =>     // for each digit v at position i in a:
    (                 //   1st expression:
      i &&            //     if this is not the 1st digit:
           v ^ p      //       compute v XOR p (where p is the previous digit)
    ) | (             //   end of 1st expression; bitwise OR with the 2nd expression:
      (p = v) ^       //     update p and compute v XOR:
      (a[i + 1] ||    //       the next digit if it is defined
                   v) //       v otherwise (which has no effect, because v XOR v = 0)
    )                 //   end of 2nd expression
  )                   // end of map()

Answer 11

Mathematica, 56 bytes

Boole[!Equal@@#&/@Partition[ArrayPad[#,1,"Fixed"],3,1]]&

Try it online!

Answer 12

Jelly, 16 bytes

ḣ2W;ṡ3$;ṫ-$W$E€¬

Try it online!

I was going to golf this but Erik has a shorter solution already and golfing mine would just bring mine closer to his. I'm still golfing but I won't update unless I can beat him or find a unique idea.

Explanation

ḣ2W;ṡ3$;ṫ-$W$E€¬  Main Link
ḣ2                First 2 elements
  W               Wrapped into a list (depth 2)
   ;              Append
    ṡ3$           All overlapping blocks of 3 elements
       ;          Append
        ṫ-$W$     Last two elements wrapped into a list
             E€   Are they all equal? For each
               ¬  Vectorizing Logical NOT

Answer 13

Perl 5, 62 + 1 (-n) = 63 bytes

s/^.|.$/$&$&/g;for$t(0..y///c-3){/.{$t}(...)/;print$1%111?1:0}

Try it online!

Answer 14

Husk, 10 bytes

Ẋo±≠↔Θ↔ΘẊ-

Try it online!

Thanks to Zgarb for -1 byte.

Answer 15

Japt, 14 13 12 bytes

Partly ported from Dennis' Jelly solution. Input & output are arrays of digits.

ä- pT äaT mg

Saved a byte thanks to ETHproductions.

Try it

---

Explanation

Implicit input of array U. ä- gets the deltas of the array. pT pushes 0 to the end of the array. äaT first adds another 0 to the start of the array before getting the absolute deltas. mg maps over the elements of the array returning the sign of each element as -1 for negative numbers, 0 for 0 or 1 for positive numbers.

Answer 16

Python 3, 54 bytes

lambda x:[n^1in x[i-(i>0):i+2]for i,n in enumerate(x)]

I/O is in form of Boolean arrays.

Try it online!

Answer 17

J, 32 Bytes

B=:2&(+./\)@({.,],{:)@(2&(~:/\))

How it works:

B=:                              | Define the verb B
                       2&(~:/\)  | Put not-equals (~:) between adjacent elements of the array, making a new one
            ({.,],{:)            | Duplicate the first and last elements
   2&(+./\)                      | Put or (+.) between adjacent elements of the array

I left out some @s and parenthesis, which just make sure it goes together nicely.

A step by step example:

    2&(~:/\) 0 1 0 1 1 1 1 0 0 1 1 1
1 1 1 0 0 0 1 0 1 0 0

    ({.,],{:) 1 1 1 0 0 0 1 0 1 0 0
1 1 1 1 0 0 0 1 0 1 0 0 0

    2&(+./\) 1 1 1 1 0 0 0 1 0 1 0 0 0
1 1 1 1 0 0 1 1 1 1 0 0

    B 0 1 0 1 1 1 1 0 0 1 1 1
1 1 1 1 0 0 1 1 1 1 0 0

Answer 18

Retina, 35 bytes

(.)((?<=(?!\1)..)|(?=(?!\1).))?
$#2

Try it online! Link includes test cases. Explanation: The regex starts by matching each input digit in turn. A capture group tries to match a different digit before or after the digit under consideration. The ? suffix then allows the capture to match 0 or 1 times; $#2 turns this into the output digit.

Answer 19

Pyth, 15 bytes

mtl{d.:++hQQeQ3

Try it here!

Alternatively:

• mtl{d.:s+hQeBQ3.
• .aM._M.+++Z.+QZ.

This prepends the first element and appends the last element, then gets all overlapping substrings of length 3, and finally takes the number of distinct elements in each sublist and decrements it. This mess has been done on mobile at midnight so I wouldn’t be surprised if there are some easy golfs.

Answer 20

Gaia, 9 bytes

ọ0+0¤+ọ‼¦

Try it online!

Explanation

ọ0+0¤+ọ‼¦ ~ A program accepting one argument, a list of binary digits.

ọ         ~ Deltas.
 0+       ~ Append a 0.
   0      ~ Push a zero to the stack.
    ¤     ~ Swap the top two arguments on the stack.
     +    ~ Concatenate (the last three bytes basically prepend a 0).
      ọ   ~ Deltas.
        ¦ ~ And for each element N:
       ‼  ~ Yield 1 if N ≠ 0, else 0.

Gaia, 9 bytes

ọ0¤;]_ọ‼¦

Try it online!

Answer 21

C, 309 bytes

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(int argc,char** argv){int d=strlen(argv[1]);char b[d + 1];char a[d + 1];strcpy(a, argv[1]);b[d]='\0';b[0]=a[0]==a[1]?'0':'1';for(int i=1;i<d-1;i++){b[i]=a[i]==a[i+1]&&a[i]==a[i - 1]?'0':'1';}b[d-1]=a[d-1]==a[d-2]?'0':'1';printf("%s\n",b);}

Not exactly a language fit for golfing, but worth an answer none-the-less. Try it out here!

Explanation

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv) {
    /* Find the number of digits in number (taken in as a command line argument) */
    int d = strlen(argv[1]);
    
    /* d + 1 to account for d digits plus the null character */
    char b[d + 1];
    char a[d + 1];

    /* Saves having to type argv[1] every time we access it. */
    strcpy(a, argv[1]);

    /* Set the null character, so printf knows where our string ends. */
    b[d] = '\0';

    /* First condition */
    /* For those not familiar with ternary operators, this means b[0] is equal to '0' if a[0] equals a[1] and '1' if they aren't equal. */
    b[0] = a[0] == a[1] ? '0' : '1';

    /* Second condition */
    for(int i = 1; i < d - 1; i++) {
        b[i] = a[i] == a[i+1] && a[i] == a[i - 1] ? '0' : '1';
    }

    /* Third condition */
    b[d - 1] = a[d - 1] == a[d - 2] ? '0' : '1';

    /* Print the answer */
    printf("%s\n", b);
}

Answer 22

APL+WIN, 29 bytes

(↑b),(×3|3+/v),¯1↑b←×2|2+/v←⎕

Prompts for screen input as a vector of digits and outputs a vector of digits.

Explanation

b←×2|2+/v signum of 2 mod sum of successive pairs of elements

×3|3+/v signum of 3 mod sum of successive triples of elements

(↑b),...., ¯1↑b concatenate first and last elements of b for end conditions

Answer 23

SNOBOL4 (CSNOBOL4), 273 bytes

	I =INPUT
	D =SIZE(I)
N	P =P + 1
	EQ(P,1)	:S(S)
	EQ(P,D)	:S(E)
	I POS(P - 2) LEN(2) . L
	I POS(P - 1) LEN(2) . R
T	Y =IDENT(L,R) Y 0	:S(C)
	Y =Y 1
C	EQ(P,D) :S(O)F(N)
S	I LEN(1) . L
	I POS(1) LEN(1) . R :(T)
E	I RPOS(2) LEN(1) . L
	I RPOS(1) LEN(1) . R :(T)
O	OUTPUT =Y
END

Try it online!

	I =INPUT			;* read input
	D =SIZE(I)			;* get the string length
N	P =P + 1			;* iNcrement step; all variables initialize to 0/null string
	EQ(P,1)	:S(S)			;* if P == 1 goto S (for Start of string)
	EQ(P,D)	:S(E)			;* if P == D goto E (for End of string)
	I POS(P - 2) LEN(2) . L		;* otherwise get the first two characters starting at n-1
	I POS(P - 1) LEN(2) . R		;* and the first two starting at n
T	Y =IDENT(L,R) Y 0	:S(C)	;* Test if L and R are equal; if so, append 0 to Y and goto C
	Y =Y 1				;* otherwise, append 1
C	EQ(P,D) :S(O)F(N)		;* test if P==D, if so, goto O (for output), otherwise, goto N
S	I LEN(1) . L			;* if at start of string, L = first character
	I POS(1) LEN(1) . R :(T)	;* R = second character; goto T
E	I RPOS(2) LEN(1) . L		;* if at end of string, L = second to last character
	I RPOS(1) LEN(1) . R :(T)	;* R = last character; goto T
O	OUTPUT =Y			;* output
END

Answer 24

C (tcc), 64 62 56 bytes

c,p;f(char*s){for(p=*s;c=*s;p=c)*s=p-c==c-(*++s?:c)^49;}

I/O is in form of strings. The function f modifies its argument s in place.

Try it online!

Answer 25

Common Lisp, 134 bytes

(lambda(a &aux(x(car a))(y(cadr a)))`(,#1=(if(= x y)0 1),@(loop for(x y z)on a while y if z collect(if(= x y z)0 1)else collect #1#)))

Try it online!