# Can the 🐸 visit all the 🪷?

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.

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 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]

• 🪷 doesn't render for me on Windows 10.
Jun 13, 2022 at 14:08
• About 🪷: "🚩 Approved in September 2021 as part of Emoji 14.0. Now available on iOS 15.4, Android 12L, Twitter, and Facebook. Coming soon to Windows 11."
Jun 13, 2022 at 14:10
• The broken emoji at the end is a lotus. Some systems don't render it. There is no need to post about this for every combination of browser and OS, so please try to keep the comment section clean and not cluttered. Jun 15, 2022 at 21:05

# 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!

• 1 if len(set(s))==len(n)else  can be len(set(s))==len(n)or  Jun 13, 2022 at 15:12
• if 0<= can also be if-1< for another -1 Jun 13, 2022 at 15:14
• set(s) -> {*s}. And for i in[n[s[-1]],-1*n[s[-1]]]...(t:=(s[-1]+i)) can be for i in[1,-1]...(t:=s[-1]+n[s[-1]]*i) Jun 13, 2022 at 15:30
• You can take advantage of comparison chaining to make the condition if len(n)>(t:=s[-1]+n[s[-1]]*i)>-1<p.count(j:=(s[-1],t))<3 Jun 13, 2022 at 15:33
• I think this can be fixed by replacing <3 with <len(n) (but this needs to be double-checked). Jun 15, 2022 at 11:07

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

Explanation:

ā        # 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)


# 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

• -3 bytes, by currying a out and calling as f(a)() Jun 13, 2022 at 22:30
• @MatthewJensen Last time I checked, there were more downvotes (including mine) than upvotes for this one. Seems like the trend has changed. Thank you for the suggestion, but I still don't like it. :-) Jun 13, 2022 at 22:42
• I don't particularly like it either, it seems 'dirty'. I thought I'd suggest it since it seems more popular now Jun 13, 2022 at 22:52
• 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); shorter, slower.
– tsh
Jun 14, 2022 at 8:11
• @tsh yes, this script generates examples where you have to visit one node at least length/2+1 times: gist.github.com/VisualMelon/50ad520ad47ad58be8cd1e4ba0e36bb9 - code has additional notes, but basically it builds a binary tree where the leaves take you back to the root of the binary tree: this means you have to traverse the tree as many times as there are leaves (and there are length/2+1 leaves). Jun 14, 2022 at 10:43

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

# 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