30
\$\begingroup\$

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 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]
\$\endgroup\$
3
  • 27
    \$\begingroup\$ 🪷 doesn't render for me on Windows 10. \$\endgroup\$
    – Adám
    Jun 13, 2022 at 14:08
  • 7
    \$\begingroup\$ 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." \$\endgroup\$
    – Adám
    Jun 13, 2022 at 14:10
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – hyper-neutrino
    Jun 15, 2022 at 21:05

5 Answers 5

7
\$\begingroup\$

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!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 1 if len(set(s))==len(n)else can be len(set(s))==len(n)or \$\endgroup\$ Jun 13, 2022 at 15:12
  • 1
    \$\begingroup\$ if 0<= can also be if-1< for another -1 \$\endgroup\$ Jun 13, 2022 at 15:14
  • \$\begingroup\$ 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) \$\endgroup\$
    – pxeger
    Jun 13, 2022 at 15:30
  • \$\begingroup\$ 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 \$\endgroup\$
    – pxeger
    Jun 13, 2022 at 15:33
  • \$\begingroup\$ I think this can be fixed by replacing <3 with <len(n) (but this needs to be double-checked). \$\endgroup\$
    – Arnauld
    Jun 15, 2022 at 11:07
4
\$\begingroup\$

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

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
\$\endgroup\$
8
  • \$\begingroup\$ -3 bytes, by currying a out and calling as f(a)() \$\endgroup\$ Jun 13, 2022 at 22:30
  • \$\begingroup\$ @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. :-) \$\endgroup\$
    – Arnauld
    Jun 13, 2022 at 22:42
  • \$\begingroup\$ I don't particularly like it either, it seems 'dirty'. I thought I'd suggest it since it seems more popular now \$\endgroup\$ Jun 13, 2022 at 22:52
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – tsh
    Jun 14, 2022 at 8:11
  • 2
    \$\begingroup\$ @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). \$\endgroup\$ Jun 14, 2022 at 10:43
2
\$\begingroup\$

Charcoal, 49 bytes

⊞υ⟦…¹Lθ⁰⟧FυFΦEθ⟦⁻§ι⁰⟦λ⟧λ⟧›⁼§θ§ι¹↔⁻λ§ι¹№υκ⊞υ꬧⌊υ⁰

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

⊞υ⟦…¹Lθ⁰⟧Fυ

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

FΦEθ⟦⁻§ι⁰⟦λ⟧λ⟧

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.

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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