Can the 🐸 visit all the 🪷?

Question

In this challenge you will be simulating a frog jumping from lily-pad to lily-pad in a pond. A frog's jump distance is uniquely determined by the size of the lily pad it jumps from. So for example there are lily-pads that let a frog jump 1 unit, lily-pads that let a frog jump 2 units etc. A frog can never jump more or less than the allowed amount, nor can it jump out of the pond, but it can jump in either direction.

So we will represent a lily-pad by the number of units it allows a frog to jump. This number is always positive. We will then represent a pond as a list of lily-pads.

Our question is then: If a frog starts on the first lily-pad can they visit every lily-pad in the pond by following the jumping rules?

For example if we have the following pond the answer is yes

[2, 3, 1, 4, 1]
 🐸

[2, 3, 1, 4, 1]
       🐸

[2, 3, 1, 4, 1]
    🐸

[2, 3, 1, 4, 1]
             🐸

[2, 3, 1, 4, 1]
          🐸

However for the following pond the answer is no:

[3,2,1,2,1,2]

The frog can never reach any lily-pad labeled with a 1.

The frog is allowed to visit the same lily-pad more than once. The following example requires it:

[2, 1, 1, 1]
 🐸

[2, 1, 1, 1]
       🐸

[2, 1, 1, 1]
    🐸

[2, 1, 1, 1]
       🐸

[2, 1, 1, 1]
          🐸

Some lily-pads are dead ends and need to be visited last for example:

[2,3,1,1]

Here there is nowhere to go from 3 so that has to be the final pad.

Task

For this task you will take as input a non-empty list of positive integers. You should output one of two distinct values, the first if it a frog can reach every lily-pad the second if not.

This is code-golf so your goal is to minimize the size of your source code as measured in bytes.

Test cases

Possible

[10]
[2,1,1,1]
[3,1,4,2,2,1]
[6,1,1,1,1,1,3]
[2,3,1,1]
[2,2,1,2]
[8,9,1,5,2,5,1,7,4]

Impossible

[2,1]
[3,2,1,2,1,2]
[3,2,2,2,2,2]
[3,4,1,2,1,1]
[2,9,1,9]
[3,3,3,1,3,3]

Answer 1

Python3, 151 bytes:

f=lambda n,s=[0],p=[]:len({*s})==len(n)or any(f(n,s+[t],p+[j])for i in[n[s[-1]],-1*n[s[-1]]]if-1<(t:=(s[-1]+i))<len(n)and p.count(j:=(s[-1],t))<len(n))

Try it online!

Answer 2

05AB1E, 40 37 bytes

ā<©+®I-øε®Ã}.āćU©æε®«œεXšü2εR`нsθå]Pà

05AB1E lacks recursive methods unfortunately, so we'll have to use a brute-force approach by first generating all possible results before validating them. Unfortunately, this is both extremely slow and pretty long - although it's probably golfable here and there.

Try it online or verify some smaller test cases.

Explanation:

Step 1: For each Lilly-pad index, check which other Lilly-pads the frog can jump to (which will always be 0, 1, or 2 other Lilly-pads):

ā        # Push a list in the range [1, (implicit) input-length]
 <       # Decrease each by 1 to the range [0, length)
  ©      # Store it in variable `®` (without popping)
   +     # Add it to the input-values at the same positions
®        # Push list `®` again
 I-      # Subtract the input-list at the same positions
    ø    # Create pairs of these two lists
     ε   # Map each pair to:
      ®Ã #  Only keep the values present in list `®`, removing any out-of-bounds
         # indices that are negative or >= the length)
     }.ā # After the map: enumerate the list, pairing each list with its index

Try just step 1 online.

Step 2: Using the powerset and permutations builtins, create all possible lists that contain either 1 or 2 of these list-index pairs, and also start with the first Lilly-pad:

ć        # Extract head; pop and push remainder-list and first item separately
 U       # Pop this first item, and store it in variable `X`
 ©       # Store the remainder-list as new variable `®` (without popping)
  æ      # Pop and push the powerset of this list
ε        # Map over each powerset-list:
 ®«      #  Merge list `®` to it
   œ     #  Get all permutations of this list
    ε    #  Map over each permutation:
     Xš  #   Prepend item `X` to each

Try the first two steps online.

Step 3: Check if there is any inner list for which all overlapping pairs of list-index pairs are valid jumps for the frog:

 ü2      #   Pop the list and push its overlapping pairs
   ε     #   Map each pair to:
    R    #    Reverse the pair
     `   #    Pop and push both inner pairs separated to the stack
      н  #    Pop and and only leave the list
     s   #    Swap so the other pair is at the top of the stack
      θ  #    Pop and only leave the index
       å #    Check if this index is in the list
]        # Close all three open maps
 P       # Product to check for each inner-most list if ALL are truthy
  à      # Flattened-max to check if ANY is truthy
         # (which is output implicitly as result)

Answer 3

JavaScript (ES6), 83 bytes

Returns \$0\$ or \$1\$.

Given a list of \$N\$ entries, this recursively tries all possible paths where each lily-pad may be visited up to \$N\$ times.

f=(a,i=0,[...b]=a.map(_=>0))=>b.every(v=>v)||a[b[i]++]&&f(a,i+a[i],b)|f(a,i-a[i],b)

Try it online!

Or 81 bytes for this slower version suggested by @tsh:

f=(a,i=0,[...b]=a.map(_=>0))=>a[b[i]++]?f(a,i+a[i],b)|f(a,i-a[i],b):b.every(v=>v)

Try it online!

Commented

f = (               // f is a recursive function taking:
  a,                //   a[] = input list
  i = 0,            //   i   = current position
  [...b] =          //   b[] = a list keeping track of how many times each
    a.map(_ => 0)   //         lily-pad was visited, initially all 0's
) =>                //
b.every(v => v)     // success if all lily-pads were visited at least once
||                  // otherwise:
a[b[i]++]           //   failed if a[b[i]] is not defined (either if we've
                    //   visited this position too many times, or we're out
                    //   of bounds and b[i] itself is undefined)
                    //   if applicable, increment b[i] afterwards
&&                  // otherwise:
f(a, i + a[i], b) | //   do a recursive call where we go to the right
f(a, i - a[i], b)   //   do a recursive call where we go to the left

Answer 4

Charcoal, 49 bytes

⊞υ⟦…¹Ｌθ⁰⟧ＦυＦΦＥθ⟦⁻§ι⁰⟦λ⟧λ⟧›⁼§θ§ι¹↔⁻λ§ι¹№υκ⊞υ꬧⌊υ⁰

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if possible, nothing if not. Explanation:

⊞υ⟦…¹Ｌθ⁰⟧Ｆυ

Start a breadth-first search having visited the first lily pad while the remaining lily pads are unvisited.

ＦΦＥθ⟦⁻§ι⁰⟦λ⟧λ⟧

Calculate the result of jumping to each lily pad...

›⁼§θ§ι¹↔⁻λ§ι¹№υκ

... filtering out those jumps that were the wrong distance or have been seen before, ...

⊞υκ

... save the resulting position.

¬§⌊υ⁰

Check whether any of the positions have no unvisited lily pads left.

Answer 5

Python 3, 96 bytes

f=lambda k,x=0,*s:len({*s})==len(k)or-1<x<len(k)>s.count(x)and f(k,x-k[x],x,*s)|f(k,x+k[x],x,*s)

Try it online!

Port of my answer to 1D Hopping Array Maze