[Question]
  [
In this challenge, you're given a list of overlapping waves. Each wave is a finite list with `n` truthy values, then `n` falsy values, then `n` truthy and so on, where `n` is the wavelength (or half the wavelength I guess, but it really doesn't matter in this challenge). The values of a wave may have an offset, so a wave of wavelength 3 could be something like `001110001110001`.
The overlapping waves all have the same length, and the result of an overlap is the exclusive or operator applied to both other waves. Applying the exclusive or operator to more than two booleans returns true if and only if the number of truthy values is odd. Example:
```
1000111000111 +
0101010101010 +
0001111000011 =
1100010101110
```
The values of a list without any waves are all falsy.
Your task is to create a program or function that, given a list of truthy and falsy values, returns the smallest number of waves that can be used to create that list.
## Test cases
```
101010101 =
101010101
-> 1 wave
10100001 =
10011001 +
00111000
-> 2 waves
110101110 =
001100110 +
111000111 +
000001111
-> 3 waves
00100101011011100100 =
10101010101010101010 +
10001110001110001110 +
00000001111111000000
-> 3 waves
1 =
(any wave)
-> 1 wave
0 =
(any or no wave(s))
-> 0 waves
(empty list of booleans) =
(any or no wave(s))
-> 0 waves
```
This is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest submission in bytes wins!
  
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), ~~41~~ 39 bytes
```
K]QWshK=hZ=KSmxMCd*Ksm.:*lQS*hdU2lQlQ;Z
```
[Try it online!](https://tio.run/##K6gsyfj/3zs2MLw4w9s2I8rWOzi3wtc5Rcu7OFfPSisnMFgrIyXUKCcwJ9A66v//aEMdAx0QhkDDWAA "Pyth – Try It Online")
### Explanation
```
                                           # implicitly assign Q = eval(input())
K]Q                                        # assign K to a list containing Q
   WshK                                    # while the first element of K is not all zeros
       =hZ                                 #   increment Z (which is auto-initialized to 0)
          =K                               #   assign K to
                  *K                       #   cartesian product of K and
                    sm.:*lQS*hdU2lQlQ      #   all possible waves
             mxMCd                         #   xor'ed together
            S                              #   sort so the all zeros element will be at the start if present
                                     ;Z    # outside of loop, print Z
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~40~~ 37 bytes
```
⊞υＳＷΣ⌊υ«≔ΣＥυΣＥκＥ⊗⊕ν⭆κ﹪⁺Ｉρ÷⁻ςξ⊕ν²υ→»Ｉⅈ
```
[Attempt This Online!](https://ato.pxeger.com/run?1=VU8xjsJADKzJK1apbClIhOp0VAgaCqToaJDQFSFZktVtdlF2HZAQL6GhuNPxJX7AM3AIFLixPbbHM6dLVqZ1ZlN9Pv-R3_Q_rreEXAkUiZnZkl_4WpkCEEfBrlRaClhQBXNlVMWZEFEcgt7YOVWYbpRu2-NX-ROJNk0trbXMYWayWlbSeK4NIu89-F-bNidtIdHkYJI6DzW2MvxUNSqX7VceNJHYP-A3JkaG2EUkiNX25raR8PmlitJzewwSfuQ72iX7wdGvW2fu6fp_FfYbHX5f4kE84Ig7-A4) Link is to verbose version of code. Explanation:
```
⊞υＳ
```
Start with the input string.
```
ＷΣ⌊υ«
```
Repeat until the input has been cancelled by the waves.
```
≔ΣＥυΣＥκＥ⊗⊕ν⭆κ﹪⁺Ｉρ÷⁻ςξ⊕ν²υ
```
Calculate the effect of at least all possible single waves on all of the waves calculated so far, and collect all of the results. (The code is pathological and generates far too many duplicates but it would cost too many bytes to uniquify them.)
```
→
```
Increment the count of waves, using the X-position to keep track.
```
»Ｉⅈ
```
Output the final count.
[Answer]
# [Python 2](https://docs.python.org/2/), 141 bytes
```
lambda s:g([int("0"+s,2)],len(s))
g=lambda l,n:min(l)and-~g([x^(1<<n+j)/-~(1<<i)%(1<<n)for i in range(1,n+1)for j in range(i*2)for x in l],n)
```
[Try it online!](https://tio.run/##ZY5NCoMwEIX3niIECpkaaeJS9CTWQoo/jcRR1IXdePU0CaWtdGYWbz7ePGZ6ro8RU9sWV2vUcK8VWbKOlRpXRgWNF55CxU2DbAGIuuLtMRyzQSMzoLBOdnew3ZjMc4x7uCS7lxpOgUA7zkQTjWRW2DVMcoxlgP0X6nMa0OaRqTiCnWb3A2kZpRB9tPhd5GERUrj6Y6EPEd4YqJ@gXap9AQ "Python 2 – Try It Online") Link includes test cases. Explanation: Uses bit-twiddling to calculate the effect of at least all possible single waves on the input, recursing until a set of waves that cancels the input wave out is found.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~38~~ 31 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
āεÅ1D_«Ig·∍ŒIgù}€`æé.ΔIš.«^O_}g
```
Input as a list.  
Brute-force, and extremely slow (times out for test cases of length \$n>4\$).
[Try it online](https://tio.run/##AUAAv/9vc2FiaWX//8SBzrXDhTFEX8KrSWfCt@KIjcWSSWfDuX3igqxgw6bDqS7OlEnFoS7Cq15PX31n//9bMCwxLDFd) or [verify most lists of lengths 0 to 4..](https://tio.run/##AVEArv9vc2FiaWX/NMaSMcOdTsOjdnk/IiDihpIgIj95RFX/xIHOtcOFMURfwqtYZ8K34oiNxZJYZ8O5feKCrGDDpsOpLs6UWMWhLsKrXk9ffWf/LP8)
**Original 37 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage) answer:**  
(which doesn't time out for the test cases..)
```
OĀiāεÅ1D_«Ig·∍ŒIgù}€`[¼D¾ãÅΔ.«^IQ}d#]¾
```
Input as a list.  
Brute-force, and also pretty slow (but it's able to complete all test cases at once nonetheless).
[Try it online](https://tio.run/##yy9OTMpM/f/f/0hD5pHGc1sPtxq6xB9a7Zl@aPujjt6jkzzTD@@sfdS0JiH60B6XQ/sOLz7cem6K3qHVcZ6BtSnKsYf2/f8fbahjqGMAhoZwDBaLBQA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeXhCaFK//2PNGQeaTy39XCroUv8odUR6Ye2P@roPTopIv3wztpHTWsSog/tcTm07/Diw63npugdWh0XEVibohx7aN9/Jb0wHb1DW/9HRxvqGOoYgKEhHIPFYnWiDVFEgRhJDKoHLIJFJxCDaBAF14CsDK4YJgtWCRSJjQUA).
**Explanation:**
```
āεÅ1D_«Ig·∍ŒIgù}€`    # Generate a list of all valid waves of the input-length:
ā                     #  Push a list in the range [1, (implicit) input-length]
 ε                    #  Map over each of those integers
  Å1                  #   Convert the integer to a list of that many 1s
    D_«               #   Merge an inverted copy (that many 0s)
       Ig             #   Push the input-length
         ·            #   Double it
          ∍           #   Extend the list of 1s/0s to that list's length
           Œ          #   Get all sublists of this list
            Igù       #   Only keep all sublists of a length equal to the input-list
               }€`    #  After the map: flatten it one level down
æ                     # Get the powerset of this list of lists
 é                    # Sort it by length
  .Δ                  # Find the first that's truthy for:
    Iš                #  Prepend the input-list to the list of lists
      .«              #  Reduce the list of lists by:
        ^             #   Vectorized bitwise-XOR the values in the lists together
         O            #  Then check if the sum of the resulting list
          _           #  is equal to 0
   }g                 # After the find_first loop: pop and push the length of the found
                      # list of lists
                      # (which is output implicitly as result)
```
```
OĀi                   # If the sum of the (implicit) input-list is NOT 0:
   āεÅ1D_«Ig·∍ŒIgù}€` #  Generate a list of all valid waves same as above
   [                  #  Start an infinite loop:
    ¼                 #   Increase the counter variable `¾` by 1 (0 by default)
    D                 #   Duplicate the current list of lists
     ¾ã               #   Get the `¾` cartesian power, to create all possible `¾`-sized
                      #   tuples of the list of lists
       ÅΔ             #   Pop and get the first index that's truthy for,
                      #   or -1 if none are truthy:
         .«           #    Reduce the current list of lists by:
           ^          #     Vectorized bitwise-XOR the values in the lists together
         IQ           #    Check if this list is equal to the input-list
       }d             #   Check if the found index is non-negative (aka NOT -1)
         #            #   If it is: stop the infinite loop
  ]                   # Close both the infinite loop and if-statement
   ¾                  # Push the counter variable
                      # (which is output implicitly as result)
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), ~~26~~ 22 bytes
```
a:[λ?żD›v+$Ẋvƒḭ↔Ṡ∷?c;Ṅ
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCIiLCJhOlvOuz/FvETigLp2KyThuop2xpLhuK3ihpThuaDiiLc/YzvhuYQiLCIiLCJbMF0iXQ==)
Surprisingly it only times out for the longest test case despite using a brute force method.
```
a:[                     # if the input doesn't contain a 1 return 0
   λ                ;Ṅ  # find the first n where the following is truthy:
    ?żD›v+$Ẋvƒḭ         #   get all waves as lists of numbers 
                             where odd numbers represent 1 and even 0
    ?ż                  #   range [1, len(input)]
      D                 #   triplicate
       ›                #   increment
        v+              #   addition vectorised over the left operand
          $             #   swap top two items on the stack
           Ẋ            #   cartesian product
            vƒḭ         #   reduce each by integer division
               ↔        #   all combinations with replacement of length n
                Ṡ       #   vectorising sum
                 ∷      #   mod 2
                  ?c    #   does it contain input?
```
[Answer]
# [Haskell](https://www.haskell.org), ~~177~~ 161 bytes
*-16 bytes thanks to [@Unrelated String](https://codegolf.stackexchange.com/users/85334/unrelated-string)*
```
(#)=replicate
f n|l<-length n=until(\x->any((==n).foldl(zipWith$(fromEnum.).(/=))(l#0))$sequence(x#[take l$drop o$(k#)=<<cycle[0,1]|k<-[1..l],o<-[1..2*k]]))(+1)0
```
[Attempt This Online!](https://ato.pxeger.com/run?1=VVGxboMwEFVXf8UpYTi3QCFdqgiydajUrZU6EA8WMcHCGApGClX-pEs6VP2m9mtqIKkSW7LevffufPZ9fOe8LYRSh8NXZzLv_ucT5zRuRK1kyo0gGei9ijwl9NbkoONOG6lwvfNWXPeIcaypn1Vqo_Bd1q_S5A5mTVU-6K70qY-3MaWo5gGlTiveOqFTgbt5YnghQDmbpqqhcrCwV0ZR2qdKJIEbsn0ReUno-4q51YQW1wVjttRNSIOp0d8raE0j9falepKtgeUSnscYvBUkj9owcqHHUPIacJ0OeiP4BpKUUUKMaE1r1YQA4CwMjnvmQkjdf86ugVqcqNFjT8vdHblgsE38KA3hmXxeceCDIx4hI6QfesAMnMtnSRcqCnvACUQejA0zUnKpbUptvcYmcaUAO512TdODHQul0E8fdZrsHw)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 23 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
...but Golf-SlowTM! :)
```
LḤ+€J:ⱮJẎḂŒPḊ^/⁼¥Ƈ⁸ẈṂ×Ṁ
```
A monadic Link that accepts a, potentially empty, list of zeros and ones and yields the minimal number of waves required.
Don't [Try it online!](https://tio.run/##AUwAs/9qZWxsef//SlLhuaA7wqzhuZlKJMay4oKs4bqO4bmB4oKs4oG4xZJQ4biKXi/igbzCpcaH4oG44bqI4bmCw5fhuYD///9bMCwxLDFd "Jelly – Try It Online") it will time out even at length three!
Modifying a little will allow length four [TIO](https://tio.run/##AUMAvP9qZWxsef//Sl/isa5M4oCYJDrisa5K4bqO4biCxZJQ4biKXi/igbzCpcaH4oG44bqI4bmCw5fhuYD///9bMCwxLDFd) (considers a window of only one greater than the length rather than double the length and also deduplicate the waves prior to getting the powerset).
It would, however, take many more bytes to make this memoised and recursive!
### How
Builds a set of "sea-position" lists that cover having position zero at every index of the input and another that would have zero at one end if extended by one (the code produces more than required). Integer divide the results by each of one through to the length of the list and modulo each result by two to get all possible single waves that could cover the input (with repeats). Take the powerset to get all combinations of waves. Filter these sets to those that become the input when reduced with a vectorising XOR. Get the minimum length of the remaining sets. Handle empty and all-zero input lists by multiplying the result by the maximum value in the input or zero if there are none.
```
LḤ+€J:ⱮJẎḂŒPḊ^/⁼¥Ƈ⁸ẈṂ×Ṁ - Link: list, A
L                       - length (A)
 Ḥ                      - double
    J                   - range of length (A)
   €                    - for each (i in [1..2*length(A)]):
  +                     -   (i) add (range of length (A)) (vectorises)
       J                - range of length (A)
      Ɱ                 - map with:
     :                  -   integer division (vectorises)
        Ẏ               - tighten  -> all waves (with loads of duplicates :p)
         Ḃ              - modulo two (vectorises)
          ŒP            - powerset
            Ḋ           - dequeue -- since we cannot reduce an empty list
                  ⁸     - chain's left argument -> A
                 Ƈ      - filter (the dequeued powerset) keeping those for which:
                ¥       -   last two links as a dyad - f(set of waves, A):
              /         -     reduce (the set of waves) by:
             ^          -       logical XOR (vectorises)
               ⁼        -     equals (A)?
                   Ẉ    - length of each
                    Ṃ   - minimium
                      Ṁ - maximum (A) -- given an empty list Ṁ yields zero
                     ×  - multiply -- this forces the `1` to a `0` when A=[] or is all zeros
```
[Answer]
# JavaScript (ES6), 119 bytes
```
f=(a,n=0)=>(F=(a,k=n)=>a.join``<1||k--&&a.some((_,n)=>(g=o=>o--&&g(o)||F(a.map(v=>v^o++/n&1),k))(++n*2)))(a)?n:f(a,n+1)
```
[Try it online!](https://tio.run/##lY/NDoIwEITvPgUnsmsLtHozFm@@hPGnQSCKdo0YTrw7Uox/qKjbbDLJ5JvZbnWh8@i4OZw8Q@u4qhIFmhslUIUwtTpTptba39LGrFZjWZaZ57mu9nPaxwBLbm1IFamQrJECYVlOQft7fYBChcWCGAuMK5FniMCY6Q@wFhonZpTYNiaxisjktIv9HaWQwExywZ92jui8nyBwZO8DfnkdcIMPXvF7d6M724dtXNzaH2NuYVfXhr7DO8/9/nfxFy7a@O90g1dn "JavaScript (Node.js) – Try It Online")
]