| Bytes | Lang | Time | Link |
|---|---|---|---|
| 517 | Python3 | 250520T015923Z | Ajax1234 |
| 022 | Vyxal | 230329T193222Z | AndrovT |
| 119 | JavaScript ES6 | 230328T152414Z | Arnauld |
| 023 | Jelly | 230329T205641Z | Jonathan |
| 031 | 05AB1E | 230328T074618Z | Kevin Cr |
| 161 | Haskell | 230328T160927Z | matteo_c |
| 039 | Pyth | 230327T170542Z | CursorCo |
| 141 | Python 2 | 230328T003901Z | Neil |
| 037 | Charcoal | 230328T001257Z | Neil |
Python3, 517 bytes
Long, but fast. Computes all the test cases in ~0.19 seconds.
from itertools import*
def C(n,w):
q=['1'*i for i in range(1,w+1)]
for i in q:
if(T:=len(i)==n)and'1'*w in i:yield from[i,''.join(str(int(not int(k)))for k in i)]
if T:continue
q+=[i+'10'[int(i[-1])]*min(w,n-len(i))]
def f(w):
if not any(map(int,w)):return 0
p=[j for i in range(1,len(w)+1)for j in C(len(w),i)]
if w in p:return 1
for j in range(1,len(p)+1):
for J in combinations(p,j):
if''.join(str((V:=lambda x:int(x[0])if 1==len(x)else int(int(x[0])!=V(x[1:])))(i))for i in zip(*J))==w:return j
Vyxal, 26 22 bytes
a:[λ?żD›v+$Ẋvƒḭ↔Ṡ∷?c;Ṅ
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?
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)
Jelly, 23 bytes
...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! it will time out even at length three!
Modifying a little will allow length four TIO (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
05AB1E, 38 31 bytes
āεÅ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 or verify most lists of lengths 0 to 4..
Original 37 bytes 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 or verify all test cases.
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)
Haskell, 177 161 bytes
-16 bytes thanks to @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
Pyth, 41 39 bytes
K]QWshK=hZ=KSmxMCd*Ksm.:*lQS*hdU2lQlQ;Z
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
Python 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! 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.
Charcoal, 40 37 bytes
⊞υSWΣ⌊υ«≔ΣEυΣEκE⊗⊕ν⭆κ﹪⁺Iρ÷⁻ςξ⊕ν²υ→»Iⅈ
Attempt This Online! Link is to verbose version of code. Explanation:
⊞υS
Start with the input string.
WΣ⌊υ«
Repeat until the input has been cancelled by the waves.
≔ΣEυΣEκE⊗⊕ν⭆κ﹪⁺Iρ÷⁻ςξ⊕ν²υ
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.
»Iⅈ
Output the final count.