Crossing a Lily Pond

Question

The Narrative

You are a frog who is at the edge of a pond with waterlilies. You would like to cross the pond without getting wet, so you plan to jump from lily to lily. There is, however, one problem: you are a rare species of frog which can only jump one specific distance, and so you might not be able to cross the pond no matter what you do.

The Objective

Determine if the frog can cross the pond without getting wet.
Your program should take two inputs:

• A string or list of lily-y/watery values to represent the lilies in the pond
• A positive integer which tells how far the frog jumps

Your program should output a truthy/falsy value to indicate whether the pond is crossable

The frog can start any distance behind the edge of the pond, but may not start on a lily or in the water. Additionally, the frog may finish any distance beyond the far edge of the pond, but not on a lily or in the water. Note that the frog cannot move at any interval other than that which is specified in the input (i.e. With a jumping distance of 3, the pond 001100 is not crossable, even though it appears that the frog could walk from the first waterlily to the second)
Examples:

(lily=1, water=0)

Inputs: "001101001111001", "3"
Output: "Yes"

Inputs: "101001", "2"
Output: "No"

Inputs: "010000001", "7"
Output: "Yes"

Inputs: "00000", "6"
Output: "Yes"

Inputs: "00000", "5"
Output: "No"

Inputs: "00100100", "4"
Output: "No"

Inputs: "001100", "3"
Output: "No"

Inputs: "", "1"
Output: "Yes"

(note that output does not have to be "Yes" or "No", but any truthy/falsy values)

This is code-golf, so the shortest code in bytes wins.

Answer 1

BitCycle, 329 bytes

BitCycle is certainly not an easy language to solve this in, despite the fact that its only form of data (streams of bits), easily represents the pattern of the lilypond in this challenge.

None of the mathematical solutions used in the other answers here would be at all easy to implement in BitCycle, so the basic algorithm for this program is as follows: given the jump length N and the pond string P, take every Nth bit of P, AND those bits together to determine if this pond is crossable, and repeat this for every possible starting distance from the pond, ORing the results from each variation together to determine if any are crossable.

This program takes the bitstring representing the lilypond as its first input (with 1s as lilies and 0s as water), and the jump length in unary (bitcycles normal way of representing integers) as the second input.

v      <
   v       ~^  v  <  <>  v F>\^Hv
  Gv            E^   ^~   + > + !
1>Gv>v  ^=~      >    ^v+vF^  H>/
  ?B^>   ^    Cv^\=/^^v~ v
  v ~ ^   >    D  ^   >
   ?~     v~^^<v~D/Bvv   <
  0AG\ ^^= ~>  \^^  < >
  B      ^ >^ ~<?~    =
>  B^ >1B^  v /v~<0C^E^
 ^   ~~   Gv0C>D>    E^
  ^        < ^~    ~
      Bv
       >      ~

More in-depth explanation

(will come later, when I feel like digging through this code to figure out how each piece of it works again)

Try it online! or Dlosc's online visualizer (To test inputs on TIO, they must be put into the arguments section, rather than the input section.)

Answer 2

Jelly, 5 bytes

T%QL<

Try it online!

Look ma, no Unicode!

Takes a list of 0 for lilies and 1 for water on the left, and the stride on the right.

   L     The number of
  Q      unique
T        indices of water
 %       modulo the stride
    <    is less than the stride.

The frog must traverse every index with some chosen residue modulo the stride; this checks if there's any residue which does not at any point correspond to water.

Jelly, 6 bytes

s׃R}Ẹ

Try it online!

Takes a list of 1 for lilies and 0 for water on the left, and the stride on the right. (Without having to handle strides longer than the pond itself, could just be sPẸ.)

s         Split the pond into stride-sized slices.
  ƒ       Reduce the list of slices by
 ×        vectorizing multiplication
   R}     starting with [1..stride] (all-truthy and the appropriate length).
     Ẹ    Is any value truthy?

Answer 3

R, 64 bytes

function(x,y)length(table(which(strsplit(x,'')[[1]]=='0')%%y))<y

Try it online!

If allowed to take a boolean list instead:

R, 42 bytes

function(x,y)length(table(which(!x)%%y))<y

Try it online!

Can cut that down to 41 if I can flip the lily-y and watery states, losing the ! in the process.

1 byte reduced because table is one byte shorter than unique.

Basic idea: look at values mod the jump length, any residue that has a 0 is not a residue you can completely jump across, if not all of them have 0 then you can jump across. Some residues may be empty (and thus fine), e.g. if you have 6 pads and can jump across 7 then there are no pads at 0 mod 7 and you can jump straight across the pond.

This is equivalent to the solutions of https://codegolf.stackexchange.com/users/73593/matteo-c.

Answer 4

Vyxal r, 6 bytes

T%UL⁰>

Try it Online!

Port of Jelly answer.

How?

T%UL⁰>
T      # Truthy (water) indices of the (implicit) first input 
 %     # Modulo each by the (implicit) second input (the stride)
  U    # Uniquify
   L   # Length
    ⁰> # Is the second input (the stride) greater than this?

Answer 5

Python, 62 47 46 bytes

thanks to @Unrelated String for the idea of alternative input format

-1 byte thanks to @dingledooper

f=lambda p,n:0in(0in p[i::n]for i in range(n))

Attempt This Online!

C (gcc), 118 110 bytes

-8 bytes thanks to @ceilingcat

d,i,j,n,l,c;main(c,v)char**v;{for(n=atoi(v++[2]);c=i<n;d+=c)for(j=i++;j<strlen(*v);j+=n)c&=j[*v]-48;return d;}

Try it online!

Haskell, 50 48 bytes

-2 bytes thanks to @Unrelated String

p#n=any(\i->all(p!!)[i,i+n..length p-1])[0..n-1]

Try it online!

All the solutions do basically the same thing.

Answer 6

R, 37 36 34 bytes

Edit: -2 bytes thanks to Giuseppe

function(x,y)(y:0)[1:y*-!c(x,1:y)]

Try it online!

Outputs zero for falsy, and a vector with non-zero first element (which is truthy in R) for truthy.

(test setup stolen from Cong Chen's R answer...)

Answer 7

Desmos, 85 62 bytes

f(l,s)=max(0,sign(s-mod([1...l.length][l=0],s).unique.length))

-23 bytes thanks to Aiden Chow

Try it on Desmos!

Answer 8

Pip -xp, 9 bytes

$|$&*aUWb

Attempt This Online! Or, verify all test cases.

Explanation

$|$&*aUWb
     a     First command-line input (list of 1s and 0s)
      UW   Unweave into this many strands:
        b  Second command-line input (jump distance)
  $&*      Fold each of those strands on logical AND
$|         Fold the list of results on logical OR

That is, there must be at least one strand which contains only 1s.

Answer 9

Java (JDK), 67 bytes

(j,l,s)->{int r=1<<j;for(l|=--r>>s%j<<s;l>0;l>>=j)r&=l;return r>0;}

Try it online!

Takes input as three ints: the jump size, the lily pond as an integer and the size of the pond

Explanations

(j,l,s)->{                     // 3 parameters: jump size, lilies positions, pond size
 int r=(1<<j)-1;               // Result. By default all entries are crossable
 for(
   l|=r>>s%j<<s;               // Ensure the banks of the pond are jumpables.
   l>0;                        // Stop when all jumps are done
   l>>=j)                      // Prepare the next jump
  r&=l;                        // Do all tests for the n-th jump at once.
 return r>0;                   // Return whether any jump line fully succeeded.
}

Credits

• -2 bytes thanks to ceilingcat

Answer 10

05AB1E, 5 bytes

ι€ßĀà

First input is the jump-distance, second the string of water/lilies with 0/1 similar as the challenge description.

Try it online or verify all test cases.

5 instead of 6 bytes by taking advantage of a bug in 05AB1E that causes Ā to be truthy for empty strings "". The 6 byter without bug-abuse would have been ι€ß_ß_. (It could have been 4 bytes ι€ßà if the length of water/lilies string was \$\geq\$ the jump-distance, which isn't the case for test case 6,"00000".)

Explanation:

ι      # Uninterleave the (implicit) second input-string to the (implicit)
       # first input-integer amount of parts
 ۧ    # Get the minimum of each part
   Ā   # Transform empty strings to 1s with a bugged Python-style truthify
    à  # Get the maximum of this list
       # (which is output implicitly as result)

Answer 11

C(GCC), 105 99 bytes

-6 bytes thanks to @ceilingcat, but I want to keep the inside while

j(a,b)char*a;{char*c=a,*d=a,m=1,o=0;for(;c-a<b;o|=m++,d=c++)while(*++d)m&=*d-48||(d-c)%b;return o;}

Try it online The idea is to try all possible starting points and then go through the whole string and do something only when on a place the frog lands. If frog's jumping power would be limited to 32 max, it would be possible to golf more (88 bytes), like:

j(a,b)char*a;{char*d=a;unsigned m=(1<<b)-1;while(*++d)m&=-1u^49-*d<<(d-a)%b;return !!m;}

Try it online Here I would simply have a bitflag for each possible start, and use !! to normalize the result.

Answer 12

Minecraft Command Blocks, 403 bytes

The commands in the command blocks from left to right:

scoreboard objectives add o dummy
execute store result score d o run data get storage a d
data modify storage a c set from storage a b[0]
execute if data storage a {c:0} run scoreboard players add c o 1
execute if data storage a {c:1} run scoreboard players reset c
data remove storage a b[0]
execute if score c o = d o run say 0
setblock 0 0 0 air
execute unless data storage a b[0] run say 1
setblock 0 0 0 air

Input is given with the command /data merge storage a {d:2,b:[0,1,0,1...]} where d is the frog's jump length and b is an array representing the lily pads.

Explanation

When the lever is pressed, the repeating command block (purple) executes every gametick, with the chain command blocks (green) executing after it in sequence. The third-last and last command blocks are conditional, which means they will only execute if the previous command block was successful.

scoreboard objectives add o dummy                                   Create scoreboard objective to store variables in
execute store result score d o run data get storage a d             Store the jump distance in d
data modify storage a c set from storage a b[0]                     Get the first value of the lily pad array
execute if data storage a {c:0} run scoreboard players add c o 1    If the value is zero increment the jump counter by 1
execute if data storage a {c:1} run scoreboard players reset c      If the value is one reset the jump counter
data remove storage a b[0]                                          Delete the first value of the array
execute if score c o = d o run say 0                                If the jump counter is equal to the jump distance print 0 (fail)
setblock 0 0 0 air                                                  (conditional) Delete the lever to stop the loop
execute unless data storage a b[0] run say 1                        If the array is empty print 1 (success)
setblock 0 0 0 air                                                  (conditional) Delete the lever to stop the loop

Answer 13

HBL, 19 bytes

?('?,)1(1,)('?.(2.,
+(*(),(<2(*-(0,)).

Takes two arguments: a list of 1s and 0s, and an integer. Returns 0 for falsey and a nonzero integer for truthy. Try it at HBL online!

Explanation

The first line is a recursive helper function that takes the number as its first argument and a partial list as its second argument:

?('?,)1(1,)('?.(2.,
?                    If
    ,                 the second argument
 ('? )                is empty, then:
      1                Return 1 (we've reached the other side of the pond)
                     Else, if
       (1 )           the first item in
         ,            the second argument
                      is truthy (nonzero), then:
           ('?         Recur
              .        with same first argument
                       and second argument equal to
               (2       drop
                 .      (first argument) many items
                  ,     from the front of second argument
                     Else, return the falsey value from the last test (0)

The result will be 1 if the pond can be crossed by starting with the first lily, 0 otherwise.

Then the main function trims off between 0 and N-1 elements from the start of the list, applies the helper function to each trimmed list, and sums the results:

+(*(),(<2(*-(0,)).
              ,     Second argument (jump distance)
            (0 )    Inclusive range from 1 to that number
         (*     )   Map
           -         decrement
        2           Drop that many
      (<             for each of those numbers
                 .   from first argument (list of lily pads)
 (*                 For each of those lists
   ()                call the helper function
     ,               with main function's second argument as first argument
                     and the trimmed list as second argument
+                   Sum

Answer 14

JavaScript (ES6), 52 bytes

Expects (distance)(string).

(n,k=n)=>g=s=>k--&&[...s].every((x,i)=>i%n|x)|g(1+s)

Try it online!

Answer 15

Factor, 52 bytes

[| s n | n 1 s indices [ n mod ] map cardinality > ]

Try it online!

Port of Unrelated String's first Jelly answer.

               ! s = { 1 1 0 0 1 0 1 1 0 0 0 0 1 1 0 }, n = 3
n              ! 3
1              ! 3 1
s              ! 3 1 { 1 1 0 0 1 0 1 1 0 0 0 0 1 1 0 }
indices        ! 3 V{ 0 1 4 6 7 12 13 }
[ n mod ] map  ! 3 V{ 0 1 1 0 1 0 1 }
cardinality    ! 3 2
>              ! t

Answer 16

J, ¹⁹ 16 bytes

[>#@~.@(|[:I.-.)

Try it online!

-3 taking the approach from Unrelated String's jelly answer

original answer J, 19 bytes

+./@((|#\)*//.]),&1

Try it online!

Consider 3 f 0 0 1 1 0 1 0 0 1 1 1 1 0 0 1:

• ,&1 Append a 1:

  0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1
  

• (|#\) Label each 1..n and then mod by 3:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  1 2 0 1 2 0 1 2 0 1  2  0  1  2  0  1   <-- mod 3
  

• *//.] Use the last row to group the original input, and take the product of each group:

  0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1
  1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1   <-- mod 3
  
  
  0 1 0 1 0 1│0 0 0 1 0│1 1 1 1 1
       ^          ^         ^
    1-group    2-group    0-group
  
       0     │    0    │    1    
       ^          ^         ^
    1-group    2-group    0-group
    product    product    product
  

• +./@ Is there a 1 among them? That indicates a valid path.

  1
  

Answer 17

Retina, 48 bytes

~(L$`.+$
*
C`\B
.+
^(^.{0,$&}1|$&*.1)$*.{0,$&}\n

Try it online! Takes pond and jump size on separate lines but link is to test suite that splits on comma for convenience. Explanation:

~(

After running the rest of the program, treat the result as its own Retina program, and execute that on the original input.

L$`.+$
*
C`\B

Delete the pond and decrement the jump size.

.+
^(^.{0,$&}1|$&*.1)$*.{0,$&}\n

Replace the decremented jump size with a regular expression that matches crossable ponds. Example: If the jump size is 7, then the following expression is produced:

^(^.{0,6}1|......1)*.{0,6}\n

This optionally matches up to six digits and a 1 followed by multiple matches of six digits and a 1, finishing with up to six digits and the newline that separates the pond from the jump size.

Answer 18

C++ (clang), 91 bytes

[](auto p,int s){int i=s,j,a,r=0;for(;a=i;r|=a)for(j=--i;j<p.size();j+=s)a&=p[j];return r;}

Try it online!

input: lily = -1, water = 0

gcc-specific (abusing UB):

C++ (GCC), 89 bytes

int f(auto p,int s){int i=s,j,a,r=0;for(;a=i;r|=a)for(j=--i;j<p.size();j+=s)a&=p[j];s=r;}

Attempt This Online!

Answer 19

Charcoal, 14 bytes

Ｎθ¬⌊Ｅθ№✂ηιＬηθ0

Try it online! Link is to verbose version of code. Takes the jump size as the first parameter and the pond as the second parameter and outputs a 1 if the pond can be crossed, 0 if not. Explanation: Based on @MatteoC's Python answer.

Ｎθ              First input as a number
     θ          First input
    Ｅ           Map over implicit range
      №         Count of
             0  Literal string `0` in
        η       Second input
       ✂        Sliced from
         ι      Current index to
           η    Second input
          Ｌ     Length
            θ   In steps of first input
   ⌊            Take the minimum
  ¬             Logical Not i.e. is zero
                Implicitly print

I tried porting @UnrelatedString's Jelly answer but the best I could do was also 14 bytes:

Ｎθ‹υ⁻…⁰θ﹪⌕Ａη0θ

Try it online! Link is to verbose version of code. Takes the jump size as the first parameter and the pond as the second parameter and outputs a Charcoal boolean, i.e. 1 if the pond can be crossed, nothing if not. Explanation:

Ｎθ              First input as a number
   υ            Predefined empty list
  ‹             Is less than
     …          Range from
      ⁰         Literal integer `0` to
       θ        First input
    ⁻           Remove elements from
         ⌕Ａ     Find all occurrences of
            0   Literal string `0`
           η    In second input
        ﹪       Vectorised modulo
             θ  First input

Answer 20

Perl 5 -pl, 49 bytes

$l=<>-1;$_=/^.{0,$l}(.{$l}1)+.{0,$l}$/||$l>=y///c

Try it online!

Answer 21

Wolfram Language (Mathematica), 44 bytes

Length[{}⋃Flatten@#~Position~0~Mod~#2]<#2&

Try it online!

Answer 22

Retina 0.8.2, 62 bytes

.+$
$*
^(?=.*¶1(1)*)(?<-1>.)*((?(3)^)1(?=.*¶1(1)*)(?<-3>.)*)*¶

Try it online! Takes pond and jump size on separate lines but link is to test suite that splits on comma for convenience. Explanation:

.+$
$*

Convert the jump size to unary.

^(?=.*¶1(1)*)(?<-1>.)*

At the start of the pond, match up to (but not including) the jump size number of digits, then...

((?(3)^)1(?=.*¶1(1)*)(?<-3>.)*)*¶

... repeatedly match a 1 plus up to the jump size number of digits for the last repeat before the end of the pond, except that the condition at the beginning of the repeat means that the maximum number of digits must have been matched on all the previous repetitions.

Answer 23

Desmos, some bytes

t(V)=V.length
R(V)=[sign(t(V)-i+.2)/2+.5fori=[1...t(V)+100]]
X(V)=[1-R(V)[j]+R(V)[j]V[jR(V)[j]+1-R(V)[j]]forj=[1...t(V)+100]]
f(V,z)=∑_{y=1}^z∏_{v=1}^{floor((t(V)-y+z)/z)}[X(V)[y+kz]fork=[0...(t(V)-z+10-y)/z]][v]

Answer 24

Scala, 89 bytes

Golfed version. Try it online!

def f(n:Int,p:String)=(0 until n).exists(i=>(i until p.length by n).forall(j=>p(j)=='1'))

Ungolfed version. Try it online!

object Main {
  def pHash(n: Int, p: String): Boolean = {
    (0 until n).exists(i => (i until p.length by n).forall(j => p(j) == '1'))
  }

  def main(args: Array[String]): Unit = {
    val testCases = List(("001101001111001", 3), ("101001", 2), ("010000001", 7), ("00000", 6), ("00100100", 4))

    for ((p, n) <- testCases) {
      println(pHash(n, p))
    }
  }
}

Answer 25

Uiua ^SBCS, 6 bytes

>⧻◴◿,⊚

Try it!

Port of UnrelatedString's Jelly answer.

Answer 26

JavaScript (Node.js), 47 bytes

n=>k=>eval(`/^((.|^){${n-1}}(1|$))*$/`).test(k)

Try it online!

Answer 27

Rust, 80 bytes

|p:&[_],j|(0..j).map(|i|(0..).zip(p).filter(|x|x.0%j==i).all(|f|*f.1)).any(|f|f)

Attempt This Online!

Feels like there's still room for lots of improvements.