7
\$\begingroup\$

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

12 Answers 12

2
\$\begingroup\$

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.

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

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!

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

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

Jelly, 22 17 bytes

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

Try it online!

Outputs all minima.

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

Stax, 18 bytes

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

Run and debug it

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

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!

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

Husk, 18 bytes

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

Try it online!

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

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.

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

Java 10, 182 bytes

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

Not really happy with the byte-count, but it's working..

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 size 4 by `l`
      i=4,j,          //  Index integers
      r=l,            //  Result smallest difference with the input-array
      R[]=a;          //  Result-integer array
  for(;i-->0;)        //  Loop `i` 4 times
    for(j=l;j-->0;)   //   Inner loop over the input-array
      b[i][j]=        //    Fill the cell in the matrix at index `i,j` with:
        i<2?          //     If `i` is 0 or 1:
         i            //      Fill it with `i`
        :i>2?         //     Else-if `i` is 3 instead:
         -~j%2        //      Fill it with `(i+1)%2`
        :             //     Else (`i` is 2 instead):
         j%2;         //      Fill it with `i%2`
  for(int[]B:b){      //  Loop over the rows of the matrix
    for(i=j=0;        //   Reset `j` to 0, and use it as sum
        i<l;)         //   Inner loop over the cells of the matrix
      j+=a[i]^B[i++]; //    Add the xor of the values at the same positions
                      //    of both the input array and current row to sum `j`
    if(j<r){          //   If sum `j` is smaller than the current smallest difference
      r=j;            //    Set `j` as new smallest difference
      R=B;}}          //    And 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.

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

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!

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

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.

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

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!

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