# Tidy up my bit string

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


# Python 2, 127103 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.

# 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!

# Pyth, 2120 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.


JµṠ,¬;‘Ḃ,ḂƲạ³S$ÐṂ  Try it online! Outputs all minima. # Stax, 18 bytes æQ|jX8Å½ΓÜ\\Δ○║á♦  Run and debug it # 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! # Husk, 18 bytes ΣTm(ṠmK(iA)Ċ2)Set  Try it online! # 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. # 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!

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


# Java 10, 182179178 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.

# 05AB1E, 1413 12 bytes

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


Port of the approach I used in my Java answer.

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)