25
\$\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)
Improve this question
\$\endgroup\$
3
  • 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
    Commented Dec 9, 2020 at 15:29
  • \$\begingroup\$ @Arnauld ​Added \$\endgroup\$
    – rydwolf
    Commented Dec 9, 2020 at 15:33
  • \$\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
    Commented Dec 10, 2020 at 16:44

22 Answers 22

Reset to default
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?
Improve this answer
\$\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
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 at 15:31
  • 1
    \$\begingroup\$ @A.Rex Ah, too bad :( But thanks for notifying me \$\endgroup\$
    – ovs
    Commented Dec 9, 2020 at 16:59
8
\$\begingroup\$

K (ngn/k), 33 31 28 30 33 bytes

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

Try it online!

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

  • &~(!#x)!'#x divisors of the length of the input
  • ((...)')_... drop records from the right side (divisors) if the left side (run on each divisor) is truthy
  • #[;x]0N, split the input into equal pieces, each of length corresponding to the current divisor
  • |/2!+/ are there an odd number of 1's in any "column" of the split-out input?
Improve this answer
\$\endgroup\$
0
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]
Improve this answer
\$\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
Improve this answer
\$\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
Improve this answer
\$\endgroup\$
5
\$\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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ @Dingus - I'd just forgot about ~/$/ + didn't knew about eval in ruby! \$\endgroup\$
    – vrintle
    Commented Dec 10, 2020 at 5:01
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.

Improve this answer
\$\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
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 at 19:25
4
\$\begingroup\$

Vyxal 3, 15 bytes

LDKΦΩ?ᶲ÷ᵛB/⊻¬}÷

Vyxal It Online!

LDKΦΩ?ᶲ÷ᵛB/⊻¬}÷  :Get the list of valid block sizes (from largest to smallest).
LD               :Get the length of the input and push it to the stack three times.
L K              :Get all integer factors of the length as a list. These are all the possible block counts.
L  Φ             :Drop the first element (block count 1) from this list.
    Ω?ᶲ÷ᵛB/⊻¬}   :Select only block counts where the XOR sum is zero from that list.
    Ω........}   :Select block counts where ........ is truthy.
     ?           :Fetch the input.
      ᶲ          :Convert that number to a string.
       ÷         :Split that string into <block count> substrings.
        ᵛB       :Interpret each substring as a binary number.
          /⊻     :Compute the XOR sum of these numbers.
            ¬    :Negate the result to get truth for zero.
L             ÷  :Divide input length by filtered block counts to get filtered block sizes.
Improve this answer
\$\endgroup\$
3
\$\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
Improve this answer
\$\endgroup\$
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!

Improve this answer
\$\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.

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 62 59 58 bytes

s(i=0;Pick[i,1##&@@Partition[1-2s,UpTo@i++],{1..}]&/@s)

Try it online!

Input a list of bits.

Mathematica's Listable functions only evaluate when arguments are all scalars or lists of matching lengths. As a result, if the block size does not evenly divide the total length, Times[...] does not evaluate further and cannot be matched by {1..}.

i=0;                                 i++        &/@s    for sizes 0,...,len-1:
           1##&@@Partition[1-2s,UpTo@i  ]                 checksum by multiplying with 0,1 -> 1,-1
    Pick[i,                              ,{1..}]          output length if valid
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 29 bytes

ＩΦＬθ∧ι¬∨﹪Ｌθι⌈﹪↨ΣＥ⪪θι⍘λ⊕Ｌθ⊕Ｌθ²

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

Improve this answer
\$\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)
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ You can remove the FB_M. \$\endgroup\$
    – A. Rex
    Commented Dec 9, 2020 at 15:04
  • \$\begingroup\$ nice, didn't know that'd work. \$\endgroup\$
    – Razetime
    Commented Dec 9, 2020 at 15:12
  • 1
    \$\begingroup\$ @A.Rex No, that now fails for 1100100001000000 (just like it would with my answer). \$\endgroup\$
    – Arnauld
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 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
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ You can remove the '0b'+. \$\endgroup\$
    – A. Rex
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 at 15:09
  • \$\begingroup\$ Ah, but you could use '0'+ in an older version of JavaScript? \$\endgroup\$
    – A. Rex
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 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
    Commented Dec 9, 2020 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.

Improve this answer
\$\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!

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt v1.4.5, 13 bytes

Takes input as a binary digit array.

Êâ¬f@òX yx ev

Try it (includes all test cases, header converts binary strings to arrays)

Êâ¬f@òX yx ev     :Implicit input of array U
Ê                 :Length
 ⬠              :Proper divisors
   f              :Filter by
    @             :Passing each X through the following function
     òX           :  Partitions of U of length X
        y         :  Transpose
         x        :  Reduce each by addition
           e      :  All?
            v     :    Divisible by 2
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 72 66 bytes

s=>[...s].flatMap((k,i,v)=>!v.map(c=>v^=c<<k++%i,k=0)==k%i+v?i:[])

Try it online!

s.length is automatically filtered out cuz it's not an index

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.