18
\$\begingroup\$

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 , so the shortest code in bytes wins.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ It would be interesting to see a solution written in LilyPond (although it’s quite improbable that it’d be the winning contribution), lilypond.org/doc/v2.22/Documentation/extending/index \$\endgroup\$
    – Boldewyn
    May 16 at 11:59
  • \$\begingroup\$ Missing test case: "00000", "5" -> "No". \$\endgroup\$ May 19 at 9:18
  • \$\begingroup\$ @OlivierGrégoire Thanks for letting me know! \$\endgroup\$
    – Nilster
    May 19 at 16:39
  • \$\begingroup\$ Heres a question: is the case of an empty string for the pond (i.e. there is no pond) a valid input? Presumably (if allowed) this would be a truthy case, as if the pond has a width of zero, any frog can easily jump over it \$\endgroup\$
    – des54321
    May 20 at 20:20
  • \$\begingroup\$ @des54321 A zero-length pond is valid as input. I'll add this as a test case! \$\endgroup\$
    – Nilster
    May 21 at 2:47

23 Answers 23

13
+200
\$\begingroup\$

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.)

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Yo dang when I said that someone should solve this in BitCycle, I meant that as a joke lmao. Didn't expect someone to actually do it. \$\endgroup\$
    – Aiden Chow
    May 20 at 7:48
  • \$\begingroup\$ @AidenChow well it was a fun challenge :P I couldnt resist actually doing it \$\endgroup\$
    – des54321
    May 20 at 17:05
11
\$\begingroup\$

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?
\$\endgroup\$
1
  • \$\begingroup\$ Very concise! I'm marking this as the winner for now, as I imagine it will take a while before it is beaten. (that is, if it is beaten) \$\endgroup\$
    – Nilster
    May 14 at 23:54
7
\$\begingroup\$

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.

\$\endgroup\$
3
5
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ I'd assume "string of lily-y/watery values" does not forbid taking, say, a list of booleans. \$\endgroup\$ May 14 at 22:53
  • 1
    \$\begingroup\$ @UnrelatedString That is affirmative, you can take booleans as input \$\endgroup\$
    – Nilster
    May 14 at 23:04
  • 1
    \$\begingroup\$ I did not think so! nice, - some bytes! \$\endgroup\$
    – matteo_c
    May 14 at 23:05
  • 3
    \$\begingroup\$ The f= isn't necessary since the function isn't recursive. Also, you can abuse 0in to save another byte: lambda p,n:0in[0in p[i::n]for i in range(n)]. \$\endgroup\$ May 14 at 23:14
  • 1
    \$\begingroup\$ 48 on the Haskell with infix \$\endgroup\$ May 15 at 0:18
5
\$\begingroup\$

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...)

\$\endgroup\$
4
  • \$\begingroup\$ Very nice! Er, your link is to my answer? \$\endgroup\$
    – Cong Chen
    May 17 at 11:56
  • 1
    \$\begingroup\$ @CongChen - Oops! Sorry! Fixed now! \$\endgroup\$ May 17 at 12:14
  • 1
    \$\begingroup\$ 35 bytes - I think 1:y*-!c(x,1:y) should work for 34 as well but I'm less sure about that. \$\endgroup\$
    – Giuseppe
    May 17 at 13:16
  • \$\begingroup\$ @Giuseppe - Ah, very nice, thanks, and - yes - I think the 34-byter works (at least I can't think of a counterexample either)... \$\endgroup\$ May 17 at 14:11
5
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Woops, I didn't see you \$\endgroup\$ May 19 at 3:18
  • \$\begingroup\$ g[g.y=0].x can be replaced by [1...l.length][l=0], and you can take out the initialization of g completely. \$\endgroup\$
    – Aiden Chow
    May 19 at 7:31
4
\$\begingroup\$

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

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

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ May 15 at 17:37
  • \$\begingroup\$ The challenge says that you can use any value as "lillypond" and any other value as "water". Try using an array of 0 and 1 to reflect that instead of a string, and you should be able to golf a bit. \$\endgroup\$ May 17 at 15:22
  • \$\begingroup\$ you can remove the space between return and !!m in your second solution for -1 byte \$\endgroup\$
    – c--
    Jun 15 at 1:28
4
\$\begingroup\$

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

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.

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

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

\$\endgroup\$
0
3
\$\begingroup\$

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

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

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.

\$\endgroup\$
3
\$\begingroup\$

Minecraft Command Blocks, 403 bytes

stack of command blocks 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
\$\endgroup\$
1
  • \$\begingroup\$ is your scoring of 403 bytes based on a .nbt structure file of the command blocks (generally this sites agreed-upon scoring mechanism for minecraft redstone)? If so, would it be possible to post a hexdump or download link of said .nbt? \$\endgroup\$
    – des54321
    May 19 at 19:27
3
\$\begingroup\$

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!

\$\endgroup\$
0
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 14 bytes

Nθ¬⌊Eθ№✂ηιLηθ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.

Nθ              First input as a number
     θ          First input
    E           Map over implicit range
      №         Count of
             0  Literal string `0` in
        η       Second input
       ✂        Sliced from
         ι      Current index to
           η    Second input
          L     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:

Nθ‹υ⁻…⁰θ﹪⌕Aη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:

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

Perl 5 -pl, 49 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

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

Try it online!

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

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.

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

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]
\$\endgroup\$
6
  • \$\begingroup\$ By the way, I don't know how to explain why it works \$\endgroup\$ May 19 at 3:07
  • \$\begingroup\$ Link: desmos.com/calculator/vyd3ir5j3x \$\endgroup\$ May 19 at 3:08
  • \$\begingroup\$ The final equation returns a value, 0 is falsey, anything else is truthy \$\endgroup\$ May 19 at 3:09
  • 1
    \$\begingroup\$ First of all, input cannot be hardcoded into a variable (in your case, it's variable V). You need to obtain input through a function (like f(V)=...). Also, all those ÷ can be replaced with / which saves quite a few bytes. Additionally, \sum can be replaced with and \prod can be replaced with which also save a few bytes. Lastly, length can be called using a dot call to save a byte: length(V) can be replaced with V.length. There are most likely more golfs but these are the really obvious ones that I see at the moment. \$\endgroup\$
    – Aiden Chow
    May 19 at 7:37
  • 1
    \$\begingroup\$ I also see that z is an input as well, so you would need to do f(V,z)=... in the last line. \$\endgroup\$
    – Aiden Chow
    May 19 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.