23
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You should have waiting 10 more minutes, then you would have got a hat. Nice challenge though! \$\endgroup\$ – caird coinheringaahing Dec 14 '17 at 20:59
  • \$\begingroup\$ @cairdcoinheringaahing I remember those last year... oh, well. :-( \$\endgroup\$ – 0WJYxW9FMN Dec 14 '17 at 21:00
  • 2
    \$\begingroup\$ Suggested test case: 1100 -> 0110 (the first 2 digits of the output are always identical in all other test cases; ditto for the last 2 digits) \$\endgroup\$ – Arnauld Dec 15 '17 at 9:15
  • \$\begingroup\$ It's nice to see that no downvotes have been cast on this challenge or on its twenty-five answers. Well done, everyone! \$\endgroup\$ – 0WJYxW9FMN Dec 29 '17 at 19:21

25 Answers 25

7
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ If you don't mind switching to string output, then "0110"!!(a+b+c) saves a byte. \$\endgroup\$ – Laikoni Dec 14 '17 at 21:31
  • \$\begingroup\$ @Laikoni: Thanks, but I've found also a byte in my math. \$\endgroup\$ – nimi Dec 14 '17 at 23:07
  • 2
    \$\begingroup\$ [last s] can be moved to the scanr initial value. \$\endgroup\$ – Ørjan Johansen Dec 14 '17 at 23:20
  • \$\begingroup\$ wow. inits (with the import); abs; if-then-else; map (take 3); zipWith; takeWhile (not.null) ; chunksOf (with its import) ... all golfed away! is there a hall of golfing fame, somewhere, anywhere? \$\endgroup\$ – Will Ness Dec 15 '17 at 22:08
7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Almost the same with my attempt :P \$\endgroup\$ – Leaky Nun Dec 14 '17 at 21:18
  • \$\begingroup\$ @LeakyNun it's quite common to get identical code in easier challenges ;p \$\endgroup\$ – Erik the Outgolfer Dec 14 '17 at 21:19
  • 2
    \$\begingroup\$ Could you add an explanation? \$\endgroup\$ – caird coinheringaahing Dec 14 '17 at 23:26
  • \$\begingroup\$ @cairdcoinheringaahing You most likely understand the code, but I am adding this as a reference for everyone until Erik adds one (if he does): .ị - Gets the element at index 0.5. Since floor(0.5) ≠ ceil(0.5), returns the elements at indexes 0 and 1. Jelly is one indexed, thus 0 actually grabs the last element. reverses the pair (because they are returned as last, first). Then j joins the pair on the input and ṡ3 splits it into overlapping slices of length 3. E€ checks (for each list) if all the elements are equal, and ¬ logically negates each. \$\endgroup\$ – Mr. Xcoder Dec 15 '17 at 6:07
6
\$\begingroup\$

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

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

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Clever way of making infixes of 3 at the start and end. \$\endgroup\$ – cole Dec 15 '17 at 2:01
2
\$\begingroup\$

Python 3, 58 bytes

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

Try it online!

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

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

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.
\$\endgroup\$
  • \$\begingroup\$ I arrived at a funny alternative, maybe you can draw inspiration from this: I0,0jI¬¬ \$\endgroup\$ – Mr. Xcoder Dec 15 '17 at 6:14
2
\$\begingroup\$

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()
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 56 bytes

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

Try it online!

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

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

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

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Shortened to 49 bytes: Try it online! \$\endgroup\$ – Dada Dec 15 '17 at 12:30
  • \$\begingroup\$ You should post it as an answer. I don't want to take credit for your work. That s;..$; construct at the end is nifty. I'll have to remember that one. \$\endgroup\$ – Xcali Dec 15 '17 at 13:45
1
\$\begingroup\$

Husk, 10 bytes

Ẋo±≠↔Θ↔ΘẊ-

Try it online!

Thanks to Zgarb for -1 byte.

\$\endgroup\$
  • \$\begingroup\$ Ẋo±≠ saves a byte. \$\endgroup\$ – Zgarb Dec 15 '17 at 9:30
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hmm, I wonder if there's a good way to make a method that puts an item at the beginning and end of an array, like in the 05AB1E answer. I think that would make it 1 byte shorter... \$\endgroup\$ – ETHproductions Dec 15 '17 at 21:59
  • \$\begingroup\$ @ETHproductions, for the likes of A.ä() which prepends its second argument, you could add a 3rd argument that gets appended. So, in this case, pT äaT could become äaTT for a 2 byte saving. \$\endgroup\$ – Shaggy Dec 16 '17 at 0:53
1
\$\begingroup\$

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!

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

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

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.

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

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.

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

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!

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

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);
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG :) \$\endgroup\$ – Shaggy Dec 16 '17 at 0:55
0
\$\begingroup\$

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

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

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!

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

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!

\$\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.