13
\$\begingroup\$

In this challenge we considered a frog hopping around a lily pond. To recap the lily pond was represented as a finite list of positive integers. The frog can only jump forward or backwards by a distance equal to the number at its current location. So for example:

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

Here the frog is on a 1 so it can move forward 1 to the 4 or backwards 1 to the 3. In the last challenge the frog had a specific starting location, but in this one we don't care about that. We just care what jumps a frog can make from a particular lily pad.

We can represent these as a directed graph, where each pad is a vertex and the edges represent hops the frog can make. Thus each vertex can have at most 2 children (forward and backwards), vertices can have fewer children if jumping in a certain direction would put them out of bounds. And indeed at least two vertices in every lily pond have fewer than two children.

As an example the pond shown above [2,3,1,4,1] can be represented as the graph:

{ 0 : [ 2 ]
, 1 : [ 4 ]
, 2 : [ 1, 3]
, 3 : []
, 4 : [ 3 ]
}

Graph 1

Of course not all graphs where each node has fewer than 2 children represents a lily pond. For example, the complete graph of order 3:

{ 0 : [ 1, 2 ]
, 1 : [ 0, 2 ]
, 2 : [ 0, 1 ]
}

Each node has two children, but the first element of the list can have at most 1 child (can't go backwards from the start). So none of the elements can go first, thus this can't be a lily pond.

Task

Your answer should take as input a directed graph which satisfies the following properties:

  • it doesn't have a vertex with more than 2 outgoing edges (children).
  • it doesn't have a self loop (an edge from a vertex to itself).
  • it doesn't have two edges with the same origin and destination vertices (the graph is simple).

Graph nodes are unlabeled and unordered.

Your answer should output one of two consistent values. The first if the input represents some lily pond, the second if it does not. What the two values are are up to you to decide.

This is the goal is to minimize your source code as measured in bytes.

Test cases

Test cases are given where each element is a list of indices that are children. Note that since graph nodes are unlabeled and unordered the order given in the input in the case below does not represent positioning of the potential solution. The second test case should demonstrate this.

Represents a lily pond

Here each input is provided with a potential solution. The solution does not need to be output it is just there to help you.

[[2],[4],[1,3],[],[3]] ~ [2, 3, 1, 4, 1]
[[],[2],[0],[4],[0,1]] ~ [2, 3, 1, 4, 1]

Represents no lily ponds

[[1,2],[0,2],[0,1]]
[[1,2],[],[],[0,1]]
[[1,2],[],[],[],[1,2]]
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ @KevinCruijssen There is no starting place here, it's not a part of the challenge. The left most and right most items can only have 0 or 1 children. 0 if their value exceeds the total size of the list and 1 otherwise. \$\endgroup\$ Commented Jun 27, 2022 at 13:53
  • 1
    \$\begingroup\$ Yeah, I know now. But since I also did the previous challenge, where the frog always started at the first/left lily-pad, it might be good to explicitly mention there isn't any starting place in this related challenge. \$\endgroup\$ Commented Jun 27, 2022 at 13:57
  • \$\begingroup\$ In the truthy examples, I understand the first one and why it corresponds to 2 3 1 4 1. But it seems to me that the lilypond induces the adjacency graphy, so I don't understand the 2nd example, where we have the same lilypond but a different adjacency graph. \$\endgroup\$ Commented Jun 28, 2022 at 5:13
  • \$\begingroup\$ @Jonah the second one is actually the same adjacency graph. \$\endgroup\$ Commented Jun 28, 2022 at 6:27

1 Answer 1

Reset to default
1
\$\begingroup\$

Python3, 264 bytes:

def f(g):
 for i in permutations(g,len(g)):
  G=dict(enumerate(i))
  for p in c(G):
   if len(G[p[0]])==1and len(G[p[-1]])<2and p:return 1
def c(g,s=0,k=[0]):
 if not g[s]:yield k;return
 for i in g[s]:
  if(i in k)^1:yield from c(g,i,k+[i])
from itertools import*

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ This is 267 because you have a trailing space at the very end. Here's 264 tho \$\endgroup\$ Commented Jun 27, 2022 at 18:07
  • \$\begingroup\$ @Steffan Thanks, updated \$\endgroup\$ Commented Jun 27, 2022 at 18:11
  • \$\begingroup\$ 256 bytes \$\endgroup\$ Commented Aug 10, 2025 at 6:20

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.