Tidy up my bit string

Question

I have a series of binary switches, which I can represent as a bit string. The last person who used my switches left them in some arbitrary state without cleaning up, and it bugs me. I always keep the switches in one of four possible "tidy" configurations:

• All 1: e.g., 111111111
• All 0: e.g., 000000000
• Alternating 1 and 0: e.g., 10101010 or 01010101

However, in addition to being fastidious about my switch arrangements, I'm also very lazy, and want to extend the smallest amount of effort possible to reset the switches to one of my preferred states.

Challenge

Write a program or function that takes a sequence of ones and zeros of any length. It should output a result of the same length that shows the closest "tidy" configuration.

Input and output

• You may represent your bit sequence using a string or any language-native ordered type, such as a list or array. If using a non-string structure, items within the sequence may be number or string representations of 1 and 0.
  • Your strings may have leading and trailing characters like "..." or [...]
• Your input and output formats are not required to match. (For example, you may input a list and output a string.)
• Don't input or output base 10 (or other base) representations of the bit string. That's way too much effort to correspond back to switches -- I'm doing this because I'm lazy, remember?
• Output must be a sequence as specified above. Don't output an enumerated value saying which of the four configurations is the best (e.g., don't say, "solution is case #3"). Actually output a bit sequence in that configuration.
• Input may be of any length. Your code may not impose arbitrary limits on the size of the input.
  • If your language or interpreter imposes reasonable arbitrary limits on the size of an input or call stack (e.g, if you choose a recursive solution), then this is acceptable insofar as it is a shortcoming in your environment, not your code.

Notes

• The distance between two strings is the Hamming distance. You must find the "tidy" configuration of the same length at the input that has the fewest number of differences from the input.
• If multiple tidy configurations are equally best choices, you may output any best choice, or (at your option) multiple best choices, delimited in some way or as siblings in a data structure. The selection can be completely arbitrary and does not need to be consistent between executions.
• The input might already be a tidy state.

Examples

Input:  1111110
Output: 1111111

Input:  001010000
Output: 000000000

Input:          0010100
Allowed output: 0000000
Allowed output: 1010101
[You may choose either allowed output, or both]

Input:  1111
Output: 1111

Input:  10
Output: 10

Input:  010101101
Output: 010101010

Input:          110
Allowed output: 111
Allowed output: 010

Answer 1

Python 2, 127 103 101 bytes

lambda a:min(zip(*[[1,0,i%2,~-i%2]for i in range(len(a))]),key=lambda N:sum(o^b for o,b in zip(a,N)))

Try it online!

Makes the lists 111..., 000..., 101... and 010... with the first zip then finds the min of these lists with key function: sum of the xor of each element in the each possible output the input.

Answer 2

Python 3, 101 98 bytes

lambda s:min([p*len(s)for p in('1','0','10','01')],key=lambda l:sum(map(str.__ne__,l,s)))[:len(s)]

Try it online!

Answer 3

Pyth, 21 20 19 bytes

.iFm*ld].R.OdZ.TcQ2

Input/output as a list of 0s and 1s.
Try it here

Explanation

.iFm*ld].R.OdZ.TcQ2
              .TcQ2    Separate the bits at even and odd positions.
   m                   For each part...
        .R.OdZ         ... round the average bit...
    *ld]               ... and get a list of copies of that number.
.iF                    Interleave the results.

Answer 4

Jelly, 22 17 bytes

JµṠ,¬;‘Ḃ,ḂƲạ³S$ÐṂ

Try it online!

Outputs all minima.

Answer 5

Stax, 18 bytes

æQ|jX8ŽΓÜ\`\Δ○║á♦

Run and debug it

Answer 6

Ruby, 89 87 bytes

->l{[a=[0],b=[1],a+b,b+a].map{|i|i*a=l.size}.min_by{|i|l.zip(i).count{|c,d|c!=d}}[0,a]}

Try it online!

Answer 7

Husk, 18 bytes

ΣTm(Ṡm`K(iA)Ċ2)Set

Try it online!

Answer 8

Ruby, 105 87 bytes

->s{(0..3).map{|i|("%02b"%i*z=s.size)[0,z]}.min_by{|x|("%b"%eval("0b1#{x}^0b"+s)).sum}}

Try it online!

This code constructs the four "tidy" strings by elongating the bit representations of numbers 0 to 3 to the required size, and then selects the one that gives the minimum Hamming distance to our test string.

The distance is calculated by XORing the integer representations of strings, and in theory we should then count the number of set bits in the result. But in practice, string byte sum method works just as well, and is golfier. The only extra trick that is now necessary, is to pad one of the bit strings with an extra "1" in front: 0xb1... to prevent dropping of leading zeroes in the result, as they are important for sum.

Answer 9

Coconut, 75 bytes

Port of my Python answer.

s->min(map(x->x*len(s),('1','0','10','01')),key=sum..map$((!=),s))[:len(s)]

Try it online!

Answer 10

PHP, 117 116 bytes

for(;~$f=$argn[$i++];${1}.=0,${0}.=1,${2}.=~$i&1,${3}.=$i&1,$d[2|$f^$i&1]++)$d[$f]++;echo${array_flip($d)[min($d)]};

Run as pipe with -nR or try it online.

Answer 11

JavaScript (Node.js), 101 100 bytes

s=>[0,1,10,"01"].map(m=x=>[...t="".padEnd(s.length,x)].map((x,i)=>c+=x^s[i],c=0)&&m<c||(m=c,T=t))&&T

Try it online!

Answer 12

Jelly, 16 bytes

J1;Ḃ;¬$Ʋ€Z=³S$ÐṀ

Try it online!

Sort of similar to dylnan's answer, which I noticed afterwards, but I think the method is unique enough to warrant a separate answer.

Explanation

J1;Ḃ;¬$Ʋ€Z=³S$ÐṀ  Main Link
J                 Range from 1 to len(z)
        €         For each element
       Ʋ
 1                1
  ;Ḃ              [1, k % 2]
    ¬$            Append the logical NOT of the list ([1, k%2, 0, !k%2])
         Z        Zip (basically, it generates a 4-long list per element, and then transposes it into the four lists)
              ÐṀ  Take the maximum element via
          =³S$    the number of matching elements (pairwise-equality into sum)

Answer 13

Java 10, 182 179 178 170 bytes

a->{int l=a.length,b[][]=new int[4][l],i=4*l,y,r=l,R[]=a;for(;i-->0;)b[y=i/l][i%l]=y<2?y:i%l+2/y&1;for(var B:b){for(i=y=0;i<l;)y+=a[i]^B[i++];if(y<r){r=y;R=B;}}return R;}

-11 bytes thanks to @ceilingcat.

Try it online.

Explanation:

a->{                  // Method with integer-array as both parameter and return-type
  int l=a.length,     //  Length of the input-array
      b[][]=new int[4][l],
                      //  Integer matrix of 4 rows and `l` columns
      i=4*l,          //  Index integer
      y,              //  Temp integer
      r=l,            //  Result smallest difference with the input-array
      R[]=a;          //  Result-integer array
  for(;i-->0;)        //  Loop over the cells:
    b[y=i/l][i%l]=    //    Set `y` to the current cell's y-coordinate,
                      //    and fill this cell in the matrix with:
      y<2?            //     If this is the first or second row:
       y              //      Fill this cell with this 0 or 1 from `y`
      :               //     Else:
       i%l+2/y&1;     //      Fill it with `(x+2//y)%2` instead
                      //      (which is `x%2` for the third row
                      //       and `(x+1)%2` for the fourth row)
  for(var B:b){       //  Loop over the rows of the matrix:
    for(i=y=0;        //   Reset `y` to 0, and use it as sum
        i<l;)         //   Inner loop over the cells of the matrix
      y+=a[i]^B[i++]; //    Add the xor of the values at the same positions
                      //    of both the input array and current row to the sum
    if(y<r){          //   If the sum is smaller than the current smallest difference:
      r=y;            //    Set the sum as new smallest difference
      R=B;}}          //    Set the result-array `R` to the current row of the matrix
  return R;}          //  Return the resulting array with the smallest difference

Example: Input-array [0,1,0,1,0,1,1,0,1]

The first nested loop creates the following matrix, where the rows are the same length as the input:

[[0,0,0,0,0,0,0,0,0],
 [1,1,1,1,1,1,1,1,1],
 [0,1,0,1,0,1,0,1,0],
 [1,0,1,0,1,0,1,0,1]]

The second nested loops uses an XOR between each value at the same position in this row and the input-array, and sums that together:

[0^0 + 1^0 + 0^0 + 1^0 + 0^0 + 1^0 + 1^0 + 0^0 + 1^0 = 5,
 0^1 + 1^1 + 0^1 + 1^1 + 0^1 + 1^1 + 1^1 + 0^1 + 1^1 = 4,
 0^0 + 1^1 + 0^0 + 1^1 + 0^0 + 1^1 + 1^0 + 0^1 + 1^0 = 3,
 0^1 + 1^0 + 0^1 + 1^0 + 0^1 + 1^0 + 1^1 + 0^0 + 1^1 = 6]

And then it returns the row with the lowest XOR-sum, which is [0,1,0,1,0,1,0,1,0] (3) in this case.

Answer 14

05AB1E, 14 13 12 bytes

dāÈ‚D≠«Σ^O}н

Port of the approach I used in my Java answer.

Try it online or verify all test cases.

Explanation:

             # Create the list of 1s the same length as the input-list:
d            #  Check for each value in the (implicit) input-list if it's non-negative (≥0)
             # Create the list of alternating 0s/1s (starting at 0):
 ā           #  Push a list in the range [1, list-length) (without popping the list)
  È          #  Then check for each whether it's even (1 if even; 0 if odd)
   ‚         # Pair the two lists together
             # Create the list of 0s and list of alternating 1s/0s (starting at 1):
    D        #  Duplicate the pair of lists
     ≠       #  And invert each boolean by checking !=1
      «      # And then merge them together to have a list of four lists
       Σ     # Sort the list of lists by:
        ^    #  XOR the values of the current inner list and (implicit) input-list
             #  (at the same positions)
         O   #  And then sum it to get the amount of 1s
          }н # And after the sorting: only leave the first list (with the smallest sum)
             # (which is output implicitly as result)