21
\$\begingroup\$

The input:

As an example, take a list containing a number of bits (in this case, 32):

11000010000100111011000011001011

We can calculate a simple checksum of this data by dividing it into evenly sized blocks, and taking the XOR of each of them. For example, with eight bit blocks:

11000010
00010011
10110000
11001011

10101010

We then append this to the end, making it 40 bits:

1100001000010011101100001100101110101010

This will be the form your input is given in.

To validate a checksum in this form, you just take the XOR of each block, including the checksum. If it's valid, it will result in a string of zeroes.

The challenge:

I've got a bunch of data with checksums. The problem is, I don't remember what the block size was! Your task is to write a program or function which takes input of any length, and returns all of the block sizes where the checksum is valid.

Blocks with sizes that do not fit evenly into the input should be ignored (so 7 would not be allowed in the output given 00000000). In the example above, the valid block sizes would be [1, 2, 4, 8], and the invalid ones would be [5, 10, 20].

Note that block sizes of one are possible (valid if the XOR of every bit in the string results in 0). A block the size of the entire string is not valid (so 8 would not be allowed in the output given 00000000), and blocks with sizes less than two do not need to be handled.

You can produce output and take input in any reasonable manner, such as lists of bits, strings of 0s and 1s, integers representing the binary values, etc.

This is , so shortest answer in bytes per language wins!

Test cases:

1100100001000000  ->  [1, 2, 4]
010010100100      ->  [1, 2, 3]
0000000000        ->  [1, 2, 5]
101101000         ->  [1, 3]
10010110          ->  [1, 2]
10000000          ->  []
0101010           ->  []
11                ->  [1]
1                 ->  (does not need to be handled)
                  ->  (does not need to be handled)
\$\endgroup\$
4
  • 2
    \$\begingroup\$ It appears that all existing test cases happen to work when XOR'ing in decimal as well. Suggested test case: 1100100001000000 -> [1, 2, 4]. \$\endgroup\$ – Arnauld Dec 9 '20 at 15:29
  • \$\begingroup\$ @Arnauld ​Added \$\endgroup\$ – Redwolf Programs Dec 9 '20 at 15:33
  • \$\begingroup\$ @Arnauld how does one XOR in decimal? \$\endgroup\$ – user253751 Dec 10 '20 at 16:32
  • \$\begingroup\$ @user253751 "XOR'ing in decimal" was a shortcut. I meant "XOR'ing the numbers parsed in decimal instead of binary", e.g. doing 1000 xor 100 (which is 908, or 0b1110001100 in binary) instead of 0b1000 xor 0b100 (which is 0b1100, or 12 in decimal). \$\endgroup\$ – Arnauld Dec 10 '20 at 16:44

19 Answers 19

11
\$\begingroup\$

05AB1E, 10 8 bytes

Input is a list of bits.

gѨʒιOÈP

Try it online!

Commented:

gÑ          # push the divisors of the length of the input
  ¨         # remove the last one (the length itself)
   ʒ        # filter this list on:
    ι       #   push [a[0::b], a[1::b], ..., a[(b - 1)::b]] where a is the input b the divisor
            #   this groups the digits from each group at the same index together
     O      #   sum each list
      ÈP    #   are all sums even?
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Wow, I like the base-10 version! I think it should work by arguing from the most-significant bit side. The highest power of 10 has its "own" MSB, and then argue by induction. \$\endgroup\$ – A. Rex Dec 9 '20 at 11:39
  • 1
    \$\begingroup\$ @A.Rex This is what I thought as well (see the revision history), but the induction step is not that simple since removing the highest 1 digit changes a lot of lower bits in the binary representation. \$\endgroup\$ – ovs Dec 9 '20 at 12:04
  • 1
    \$\begingroup\$ Consider the highest power of ten in your block size. It has its own MSB, so when you XOR the numbers together, that bit indicates whether there were an even number of 1s in that power of ten. If there were an odd number, you're done: checksum invalid, no matter what less significant digits you have! If there were an even number, you keep going by induction. You're right that this power of ten has other bits lower down, but we just decided there were an even number of 1s in this position, so all the lower bits cancel! \$\endgroup\$ – A. Rex Dec 9 '20 at 12:26
  • 1
    \$\begingroup\$ @Arnauld points out in discussion below other answers that my proof is bogus and the claim is false!! :( \$\endgroup\$ – A. Rex Dec 9 '20 at 15:31
  • 1
    \$\begingroup\$ @A.Rex Ah, too bad :( But thanks for notifying me \$\endgroup\$ – ovs Dec 9 '20 at 16:59
8
\$\begingroup\$

K (ngn/k), 33 31 bytes

{(&/2!1+/#[;x]0N,)#&~(!#x)!'#x}

Try it online!

Takes input as a list of 0s and 1s.

I think this can be golfed further...

  • &~(!#x)!'#x divisors of the length of the input
  • (...)#... filter right side (divisors) for the condition on the left-hand side
  • #[;x]0N, split the input into equal pieces, each of length corresponding to the current divisor
  • &/2!1+/ are there an even number of 1's in all "columns" of the split-out input?
\$\endgroup\$
5
\$\begingroup\$

Add++, 29 bytes

D,g,@@,T2€BbB^
L,bLd1_Rþ%A$þg

Try it online!

I'm surprised Add++ was this short. Takes input as a list of bits

How it works

D,		; Define a helper function
	g,	; called g
	@@,	; that takes 2 arguments e.g. [8 [1 1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0]]
	T	; Split into chunks; [[1 1 0 0 0 0 1 0] [0 0 0 1 0 0 1 1] [1 0 1 1 0 0 0 0] [1 1 0 0 1 0 1 1] [1 0 1 0 1 0 1 0]]
	2€Bb	; Convert from binary; [67 200 13 211 85]
	B^	; Reduce by XOR; 0

L,		; Define an unnamed lambda
		; Example argument: [1 1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0]
	bL	; Length; 40
	d	; Duplicate; [40 40]
	1_	; Decrement; [40 39]
	R	; Range; [40 [1 2 3 ... 37 38 39]]
	þ%	; Filter false Mod; [1 2 4 5 8 10 20]
	A$	; Push the argument below; [[1 1 0 ... 0 1 0] [1 2 4 5 8 10 20]]
	þg	; Filter false on g; [1 2 4 8]
\$\endgroup\$
0
5
\$\begingroup\$

Brachylog, 16 bytes

⟨{ġ\+ᵐ~×₂ᵐl}ᶠxl⟩

Try it online!

⟨{ġ\+ᵐ~×₂ᵐl}ᶠxl⟩
⟨            x ⟩ remove
              l  the input's length from
 {         }ᶠ    all results of:
  ġ               split the input into equal sized groups
   \              transpose
    +ᵐ            the sum of each column is
      ~×₂ᵐ        the result of a multiplication of some number by 2
          l       get the length of the block
\$\endgroup\$
5
\$\begingroup\$

Husk, 12 bytes

fö¬ΣFz≠C¹hḊL

Try it online!

f               # filter truthy elements x of
          ḊL    # the divisors of the length of the input
         h      # except the last one (the length itself)
                # using this function:
 ö              # apply 4 operations:
  ¬             #   NOT
   Σ            #   the sum of
    F           #   folding each pair of elements by
     z          #     zipping each pair together by
      ≠         #     xor (not equal)
       C¹       #   to the input split into blocks of size x
\$\endgroup\$
4
\$\begingroup\$

SageMath, 99 104 bytes

f=lambda s:[d for d in divisors(len(s))[:-1]if 0^eval("^".join(["0b"+s[x:x+d]for x in(0,d..len(s)-1)]))]

The two instances of the ^ operator here are actually different operators! Sage preprocesses the source code to treat ^ as exponentiation, but eval is just ordinary Python eval, which treats ^ as bitwise xor.

The expression 0^X is used as a shorter way to express X==0. It works because 0⁰=1, whereas 0ⁿ=0 for non-zero n. (This trick was used by Julia Robinson in her work on Hilbert’s Tenth Problem, and is employed in the famous paper Diophantine representation of the set of prime numbers.)

This function takes its input as a string of zeroes and ones, and returns a list of numbers.


Edit: Thanks to ovs for pointing out that I had overlooked the part of the problem statement that says blocks the size of the whole string are not allowed.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ This currently fails on the all 0 case, since divisors includes the number itself, which can be fixed with divisors(len(s))[:-1]. A slightly different method which counts the number of 1's instead of evaluating the XOR comes in at 90 bytes: f=lambda s:[d for d in divisors(len(s))[:-1]if~-any(s[x::d].count('1')%2for x in(0..d-1))]. \$\endgroup\$ – ovs Dec 9 '20 at 18:36
  • \$\begingroup\$ Thanks @ovs! I missed the requirement that blocks the size of the whole string are not allowed. Your method is so clever and so different, I wonder if you should post it as a separate answer. (Or is that not the done thing in these parts?) \$\endgroup\$ – Robin Houston Dec 9 '20 at 19:06
  • 2
    \$\begingroup\$ After writing the comment I already posted a pure Python answer using this approach. If you want to include this in your answer you can, but that is your choice ;) \$\endgroup\$ – ovs Dec 9 '20 at 19:25
4
\$\begingroup\$

Ruby 2.7 -nl, 85 75 bytes

Saved a whooping 10 bytes, thanks to Dingus!

p (1...~/$/).select{|i|~/$/%i+eval($_.scan(/.{#{i}}/).map{|i|i.to_i 2}*?^)<1}

Try it online!

TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, i.e., _1, which saves 2 bytes.

\$\endgroup\$
1
  • \$\begingroup\$ @Dingus - I'd just forgot about ~/$/ + didn't knew about eval in ruby! \$\endgroup\$ – vrintle Dec 10 '20 at 5:01
3
\$\begingroup\$

Perl 5 -lF, 68 bytes

map{@a=$i=0;//;map$a[$i++%$']+=$_,@F;@F%$_+(grep$_%2,@a)||say}1..$#F

Try it online!

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

Python 3.8, 110 bytes

lambda n:(l:=len(n))and[b for b in range(1,l)if not(eval('^'.join('0o'+n[a:a+b]for a in range(0,l,b)))or l%b)]

Try it online!

Inputs a string of \$1\$s and \$0\$s and returns a list of all possible block sizes where the checksum is valid.

\$\endgroup\$
3
\$\begingroup\$

Python 3, 94 86 bytes

Input is a list of bits.

lambda s:[d for d in range(1,len(s))if~-any(len(s)%d+sum(s[x::d])%2for x in range(d))]

Try it online!

Commented:

lambda s:[                       ]    # lambda function with a list of digits s as input and a list of integers as output
  d for d in range(1,len(s))          # take the block size d in 1,2,...len(s)-1
    if ~-any(  for x in range(d))     # if for no index in 0,1,...,d-1
      len(s)%d                        #   the block size does not divide the input size
      +sum(s[x::d])%2                 #   or there is an odd number of 1's at this index

Python 3.8, 86 bytes

Same length as a recursive function

f=lambda s,d=1,x=0:s[d:]and[x][d-x:]+f(s,d+(w:=len(s)%d+sum(s[x::d])%2+x//d>0),~-w*~x)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 62 bytes

sTr/@Mod[i=0;1+##&@@s~Partition~UpTo@i++&/@s,2]~Cases~{1..}

Try it online!

Input a list of bits.

Xor gives the same result as the sum of its arguments mod 2, but Xor is not Listable, while Plus and Mod are.

Mathematica's Listable functions only reduce when all arguments are lists of the same length or scalars. Thus if the block size does not evenly divide the total length, so Plus remains unevaluated. The resulting expresion Plus[...] cannot be matched by {1..}.

Mod[i=0;1+##&@@s~Partition~UpTo@i++&/@s,2]  (* calculate bitwise complements of possible checksums of the input *)
% ~Cases~{1..}                              (* find those which only contain 1s *)
Tr/@ %                                      (* get the length of each. *)
\$\endgroup\$
2
\$\begingroup\$

Jelly, 11 bytes

LÆḌs@^/ẸɗÐḟ

Try it online!

Input as a list of bits, the Footer does this for you

How it works

LÆḌs@^/ẸɗÐḟ - Main link. Takes a list of bits, B, on the left
L           - Length of B
 ÆḌ         - Proper divisors
        ɗÐḟ - Filter proper divisors k, keeping those which return False:
   s@       -   Split B into pieces of length k
     ^/     -   Reduce columnwise by XOR
       Ẹ    -   Are any true?

Monads you could use instead of :

  • S: Sum of columns
  • T: Indexes of non-zero elements
  • : Convert from binary
  • : Convert from decimal
  • : Generate an array which would yield the original argument under T
  • : Maximum
  • §: Sum of rows
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 29 bytes

IΦLθ∧ι¬∨﹪Lθι⌈﹪↨ΣE⪪θι⍘λ⊕Lθ⊕Lθ²

Try it online! Link is to verbose version of code. Explanation: Charcoal has no bitwise Or operator nor an easy way to reduce it over an array so I emulate it by performing a sum using a large base and then separately reducing each digit modulo 2.

   θ                            Input string
  L                             Length
 Φ                              Filter over implicit range
     ι                          Current value (i.e. is non-zero)
    ∧                           Logical And
      ¬                         Logical Not
         Lθ                     Length of input string
        ﹪                       Modulo (i.e. does not divide by)
           ι                    Current value
       ∨                        Logical Or
                  θ             Input string
                 ⪪ ι            Split into substrings of current length
                E               Map over substrings
                     λ          Current substring
                    ⍘           Convert string from base
                      ⊕Lθ       Incremented input length
               Σ                Take the sum
              ↨                 Convert to array using base
                         ⊕Lθ    Incremented input length
             ﹪              ²   Vectorised modulo by 2
            ⌈                   Take the maximum i.e. are any odd?
I                               Cast to string
                                Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Scala, 95 93 bytes

b=>1.to(b.size/2)filter{s=>b.grouped(s).reduce((_,_).zipped.map(_^_)).toSet==Set(b.size%s*2)}

Try it online!

Accepts input as a list of ints.

b is the input block. 1.to(b.size/2) is a range of all possible block sizes, and filter{s=>...} is used to keep only those that divide b evenly and that result in a string of zeroes.

b.grouped(s) splits b into chunks of size s, then reduce is used to xor all the chunks together. The function to reduce with is (_,_).zipped.map(_^_) (the underscores are placeholders for actual parameters). (_,_).zipped zips the two lists together, and map(_^_) applies xor to each pair in both lists. Finally, toSet is invoked on the result of xor-ing the chunks together, so now it's either a Set(0) if it had only zeroes, or Set(1) or Set(0,1) if it had ones.

We can check both that this result is Set(0) and that s divides b evenly by comparing that set with == Set(b.size % s * 2). b.size % s * 2 will be 0 if s divides b evenly, but if not, it will be 2 or some higher number, not 1. The result from earlier can only contain a 0 or 1, so it will only match if b.size % s is 0 and the result from earlier is a Set with just a 0, checking both conditions at once.

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

Pip -n, 31 bytes

{!#y%a&!$BX(FB_My<>a)}FI1,--#Ya

Try it online!

Input as a string of 0s and 1s.

Explanation

{!#y%a&!$BX(FB_My<>a)}FI1,--#Ya a → input
                        1,--#Ya range 1..length(a)-1
                             Ya store input in y
{                    }FI        filter each i by the following:
  #y%a                           length(a) mod i
 !                               logical not (is divisor)
      &                          and
                y<>a             input split into chunks of length i
            FB_M                 mapped from binary to decimal
        $BX(        )            folded by bitwise xor
       !                         logical not (checksum validity)
                                 is true?
                                join with newlines(-n flag)
\$\endgroup\$
6
  • \$\begingroup\$ You can remove the FB_M. \$\endgroup\$ – A. Rex Dec 9 '20 at 15:04
  • \$\begingroup\$ nice, didn't know that'd work. \$\endgroup\$ – Razetime Dec 9 '20 at 15:12
  • 1
    \$\begingroup\$ @A.Rex No, that now fails for 1100100001000000 (just like it would with my answer). \$\endgroup\$ – Arnauld Dec 9 '20 at 15:12
  • \$\begingroup\$ @Arnauld: in both your answer and here, it's because of a "leading zero means octal" being triggered, right? I'm just trying to avoid binary/decimal conversions because you should just be able to XOR the decimal numbers together ... as long as leading zeroes are interpreted in decimal. \$\endgroup\$ – A. Rex Dec 9 '20 at 15:24
  • 1
    \$\begingroup\$ @A.Rex No, it would work in octal but doesn't work in decimal (1100 xor 1000 xor 100 is 1984). \$\endgroup\$ – Arnauld Dec 9 '20 at 15:26
2
\$\begingroup\$

JavaScript (ES10), 94 bytes

Expects a string.

s=>(g=k=>s[++k]?[(h=i=>(t=s.substr(i,k))?t[k-1]?'0b'+t^h(i+k):~0:0)(0)?[]:k,g(k)].flat():[])``

Try it online!

Commented

s => (                         // s = input string
  g = k =>                     // g is a recursive function taking a block size k
    s[++k] ?                   //   increment k; if s[k] is defined:
      [                        //     begin an array:
        ( h = i =>             //       h is a recursive function taking a counter i
          (t = s.substr(i, k)) //         t is the next substring of maximum size k
          ?                    //         if it's non-empty:
            t[k - 1] ?         //           if the size of t is k:
              '0b' + t         //             convert it from binary to decimal
              ^                //             and XOR it with
              h(i + k)         //             the result of a recursive call to h
            :                  //           else:
              ~0               //             stop and invalidate the final result
                               //             (the length of s is not a multiple of k)
          :                    //         else:
            0                  //           stop
        )(0)                   //       initial call to h with i = 0
        ?                      //       if the result is not 0:
          []                   //         append an empty array (removed by flat())
        :                      //       else:
          k,                   //         append k
        g(k)                   //       append the result of a recursive call to g
      ].flat()                 //     end of array; flatten it
    :                          //   else:
      []                       //     stop
)``                            // initial call to g with k zero'ish
\$\endgroup\$
6
  • \$\begingroup\$ You can remove the '0b'+. \$\endgroup\$ – A. Rex Dec 9 '20 at 15:02
  • 1
    \$\begingroup\$ @A.Rex It just happens to work for all existing test cases but would fail on 1100100001000000, for instance. \$\endgroup\$ – Arnauld Dec 9 '20 at 15:09
  • \$\begingroup\$ Ah, but you could use '0'+ in an older version of JavaScript? \$\endgroup\$ – A. Rex Dec 9 '20 at 15:17
  • 1
    \$\begingroup\$ @A.Rex A leading 0 is for a literal octal value. The XOR could be done in octal, but a string with a leading 0 (such as "0110") is coerced to a number in base 10 anyway. \$\endgroup\$ – Arnauld Dec 9 '20 at 15:23
  • 1
    \$\begingroup\$ @A.Rex One thing that would work is eval('0'+t) to force a literal octal -- but that's 5 bytes longer. \$\endgroup\$ – Arnauld Dec 9 '20 at 15:40
2
\$\begingroup\$

R, 93 bytes

function(x,l=sum(x|1))which(!sapply(seq(l=l-1),function(n)l%%n|any(rowSums(matrix(x,n))%%2)))

Try it online!

For each n up to the length of the input minus 1, rearranges the input bits into a matrix with n rows: the checksum is valid if the sum of every row is an even number.

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

Julia, 71 bytes

a->filter(i->L%i<1&&!any(xor(a[j:i:L]...) for j=1:i),1:(L=length(a))-1)

expects an Array{Bool}

Try it online!

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

Haskell, 109 bytes

f s=[x|x<-[1..l s-1],rem(l s)x==0,not.or.foldr1(zipWith(/=))$x#map(=='1')s]
l=length
_#[]=[]
n#x=x:n#drop n x

Try it online!

If taking the input as a list of booleans counts as a reasonable manner it would go down to 99 (not sure if it does, though):

Haskell, 99 bytes

f s=[x|x<-[1..l s-1],rem(l s)x==0,not.or.foldr1(zipWith(/=))$x#s]
l=length
_#[]=[]
n#x=x:n#drop n x

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.