| Bytes | Lang | Time | Link |
|---|---|---|---|
| 015 | Vyxal 3 | 240925T215845Z | Joooeey |
| 013 | Japt v1.4.5 | 240925T120106Z | Shaggy |
| 058 | Wolfram Language Mathematica | 201209T192430Z | att |
| 066 | JavaScript Node.js | 240924T220639Z | l4m2 |
| 033 | K ngn/k | 201208T223106Z | coltim |
| 109 | Haskell | 201211T133835Z | david |
| 071 | Julia | 201210T134301Z | MarcMush |
| 086 | Python 3 | 201209T183939Z | ovs |
| 075 | Ruby 2.7 nl | 201209T091337Z | vrintle |
| 008 | 05AB1E | 201208T213959Z | ovs |
| 093 | R | 201209T231612Z | Dominic |
| 110 | Python 3.8 | 201209T102026Z | Noodle9 |
| 104 | SageMath | 201209T174649Z | Robin Ho |
| 094 | JavaScript ES10 | 201208T222717Z | Arnauld |
| 031 | Pip n | 201209T085846Z | Razetime |
| 012 | Husk | 201208T235142Z | Dominic |
| 093 | Scala | 201208T220609Z | user |
| 029 | Charcoal | 201208T225023Z | Neil |
| 068 | Perl 5 lF | 201208T224650Z | Xcali |
| 016 | Brachylog | 201208T223731Z | xash |
| 029 | Add++ | 201208T220710Z | caird co |
| 011 | Jelly | 201208T213509Z | caird co |
Vyxal 3, 15 bytes
LDKΦΩ?ᶲ÷ᵛB/⊻¬}÷
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.
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
Wolfram Language (Mathematica), 62 59 58 bytes
s(i=0;Pick[i,1##&@@Partition[1-2s,UpTo@i++],{1..}]&/@s)
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
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:[])
s.length is automatically filtered out cuz it's not an index
K (ngn/k), 33 31 28 30 33 bytes
{((|/2!+/#[;x]0N,)')_&~(!#x)!'#x}
Takes input as a list of 0s and 1s.
&~(!#x)!'#xdivisors 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?
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
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
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}
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))]
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)
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}
TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, i.e., _1, which saves 2 bytes.
05AB1E, 10 8 bytes
Input is a list of bits.
gѨʒιOÈP
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?
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)))
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.
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)]
Inputs a string of \$1\$s and \$0\$s and returns a list of all possible block sizes where the checksum is valid.
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.
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():[])``
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
Pip -n, 31 bytes
{!#y%a&!$BX(FB_My<>a)}FI1,--#Ya
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)
Husk, 12 bytes
fö¬ΣFz≠C¹hḊL
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
Scala, 95 93 bytes
b=>1.to(b.size/2)filter{s=>b.grouped(s).reduce((_,_).zipped.map(_^_)).toSet==Set(b.size%s*2)}
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.
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
Perl 5 -lF, 68 bytes
map{@a=$i=0;//;map$a[$i++%$']+=$_,@F;@F%$_+(grep$_%2,@a)||say}1..$#F
Brachylog, 16 bytes
⟨{ġ\+ᵐ~×₂ᵐl}ᶠxl⟩
⟨{ġ\+ᵐ~×₂ᵐ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
Add++, 29 bytes
D,g,@@,T2€BbB^
L,bLd1_Rþ%A$þg
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]
Jelly, 11 bytes
LÆḌs@^/ẸɗÐḟ
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 columnsT: Indexes of non-zero elementsḄ: Convert from binaryḌ: Convert from decimalṬ: Generate an array which would yield the original argument underTṀ: Maximum§: Sum of rows