21
\$\begingroup\$

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 , so the shortest submission in bytes wins!

\$\endgroup\$
6
  • 5
    \$\begingroup\$ Can't test case 010000011000 can be done in 2 waves instead of 3: 110000011111 (wave length 5) + 100000000111 (wave length 8)? \$\endgroup\$ Commented Mar 27, 2023 at 16:03
  • 2
    \$\begingroup\$ You're right ... I'll change the test case :) \$\endgroup\$
    – Peter
    Commented Mar 27, 2023 at 17:21
  • 2
    \$\begingroup\$ Just to be clear; looking at your samples, a wave does not wrap around according to its offset? I mean a sequence of any odd number of 1s other than 1 itself would not be possible otherwise. And if the above is true, would that mean 0000000000000000000001 is considered a possible wave? \$\endgroup\$
    – JvdV
    Commented Mar 28, 2023 at 8:19
  • 4
    \$\begingroup\$ @JvdV No, the waves do not wrap around. As someone replied a while ago but deleted for some reason (I assume you've already seen that reply, but others might have the same question as you), you can look at the waves as a sublist of an infinite list. Therefore, 0000000000000000000001 is a valid wave, since it may be a sublist of a wave of length 21 or longer. \$\endgroup\$
    – Peter
    Commented Mar 28, 2023 at 14:42
  • 3
    \$\begingroup\$ @Kaia Part of me regrets not making this a challenge for the fastest algorithm. I honestly have no idea if there's a better method than brute force or not. \$\endgroup\$
    – Peter
    Commented Mar 30, 2023 at 5:37

8 Answers 8

8
\$\begingroup\$

Pyth, 41 39 bytes

K]QWshK=hZ=KSmxMCd*Ksm.:*lQS*hdU2lQlQ;Z

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
\$\endgroup\$
3
  • \$\begingroup\$ If you started with K as a list of a single null wave then you wouldn't need that as a special-case, although I don't know whether that would cost more bytes than it saves. \$\endgroup\$
    – Neil
    Commented Mar 28, 2023 at 0:15
  • \$\begingroup\$ The lowest I can seem to get that is two bytes more expensive. But when I combine it with the method in your charcoal answer, it saves two bytes :) \$\endgroup\$ Commented Mar 28, 2023 at 15:09
  • \$\begingroup\$ I came up with that saving after writing my previous comment, although it only saved me three bytes, so I was surprised that it saved you four, until I noticed that I had actually outgolfed you even before that saving, and in fact I'm actually tying with 05AB1E somehow. \$\endgroup\$
    – Neil
    Commented Mar 28, 2023 at 17:01
7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ [0,1,1] should be 1 but returns 2 \$\endgroup\$
    – AndrovT
    Commented Mar 29, 2023 at 18:39
  • \$\begingroup\$ @AndrovT Thanks for noticing. Should be fixed (at the cost of 1 byte). \$\endgroup\$ Commented Mar 29, 2023 at 20:17
4
\$\begingroup\$

Vyxal, 26 22 bytes

a:[λ?żD›v+$Ẋvƒḭ↔Ṡ∷?c;Ṅ

Try it Online!

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?
\$\endgroup\$
0
4
\$\begingroup\$

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

Attempt This Online!

\$\endgroup\$
1
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\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.