Is it a Frog List?

Question

Challenge:

A Frog List is defined by certain rules:

1. Each frog within a Frog List has an unique positive digit [1-9] as id (any 0 in a list is basically an empty spot, which can mostly be ignored).
2. A Frog List will always have exactly one Lazy Frog. A Lazy Frog will remain at its position.
3. Every other frog in a Frog List will jump at least once, and will always jump towards the right from its starting position.
4. When a frog jumps, the distance of its jump is always the same.
5. When a frog jumps, it will continue jumping until it's outside the list's right bound.
6. 0-1 jumping frogs can stand on top of a Lazy Frog, as long as their summed ids is still a single digit. (Jumping frogs cannot stand on top of one another! Which implicitly also means there cannot be two jumping frogs on a Lazy Frog simultaneously.)

Note that the frog-ids within a Frog List describe how a frog has already jumped (past sense). Focusing on an individual frog-id within a Frog List shows how it has jumped, and at what positions within the Frog List it has landed, and jumped onward from - with the exception of the Lazy Frog, which hasn't moved.

Worked out explanation of the Frog List [1,2,1,0,8,2]:

1. The Lazy Frog has id \$\color{green}{7}\$ at position ~~~~7~:

2. The first jumping frog has id \$\color{red}{1}\$ at positions 1~1~1~ with jump distance 2:

3. The second jumping frog has id \$\color{blue}{2}\$ at positions ~2~~~2 with jump distance 4:

All three frogs summed gives the Frog List [1,2,1,0,8,2], so [1,2,1,0,8,2] would be truthy:

All Test cases including explanation:

Input                 Explanation:

Truthy:

[1,2,1,0,8,2]         Lazy Frog 7 doesn't jump                ~~~~7~
                      frog 1 jumps (with jumping distance 2)  1~1~1~
                      frog 2 jumps (with jumping distance 4)  ~2~~~2

[1,0,0,0,0,1,2,7,2,2] Lazy Frog 5 doesn't jump                ~~~~~~~5~~
                      frog 1 jumps (with jumping distance 5)  1~~~~1~~~~
                      frog 2 jumps (with jumping distance 1)  ~~~~~~2222

[9,8,9,1]             Lazy Frog 7 doesn't jump                ~7~~
                      frog 1 jumps (with jumping distance 2)  ~1~1
                      frog 9 jumps (with jumping distance 2)  9~9~

[1,0,1,3,3,3,1]       Lazy Frog 2 doesn't jump                ~~~~2~~
                      frog 1 jumps (with jumping distance 2)  1~1~1~1
                      frog 3 jumps (with jumping distance 2)  ~~~3~3~
(Note that the 3 at ~~~~3~~ is Lazy Frog 2 and jumping frog 1 on top of one another,
 and not jumping frog 3!)

[7]                   A single Lazy Frog 7

[7,0,0,0]             A single Lazy Frog 7~~~

[8,1,1]               Lazy Frog 8 doesn't jump                8~~
                      frog 1 jumps (with jumping distance 1)  ~11
    OR alternatively:
                      Lazy Frog 7 doesn't jump                7~~
                      frog 1 jumps (with jumping distance 1)  111

Falsey:

[1,2,3,0,2,1,3]       (rule 2) there is no Lazy Frog: 1~~~~1~
                                                      ~2~~2~~
                                                      ~~3~~~3
[1,6,1,8,6,1]         (rule 4) frog 1 jumps irregular 1~1~~1 / 1~11~1
                                                      ~6~~6~ / ~6~~6~
                                                      ~~~8~~ / ~~~7~~
[2,8,2,8,0,9]         (rule 5) frog 2 stopped jumping 2~2~~~
                                                      ~~~~~1
                                                      ~8~8~8
[1,2,3,2,7]           (rule 6) two jumping frogs at the last position with: 1~~~1
                                                                            ~2~2~
                                                                            ~~3~3
                                                                      (Lazy)~~~~4
                                                                                ^
                      OR two jumping frogs at the third and last positions with: 1~1~1
                                                                                 ~2222
                                                                           (Lazy)~~~~4
                                                                                   ^ ^
[2,1]                 (rule 2+3) There are two Lazy Frogs without jumping frogs: ~1
                                                                                 2~
                      OR (rule 1) The Lazy and jumping frog would both have id=1: 11
                                                                                  1~

Here are all Frog Lists (as integers) of 3 or less digits:

[1,2,3,4,5,6,7,8,9,10,13,14,15,16,17,18,19,20,23,25,26,27,28,29,30,31,32,34,35,37,38,39,40,41,43,45,46,47,49,50,51,52,53,54,56,57,58,59,60,61,62,64,65,67,68,69,70,71,72,73,74,75,76,78,79,80,81,82,83,85,86,87,89,90,91,92,93,94,95,96,97,98,100,103,104,105,106,107,108,109,113,114,115,116,117,118,119,121,122,131,133,141,144,151,155,161,166,171,177,181,188,191,199,200,203,205,206,207,208,209,211,212,223,225,226,227,228,229,232,233,242,244,252,255,262,266,272,277,282,288,292,299,300,301,302,304,305,307,308,309,311,313,322,323,334,335,337,338,339,343,344,353,355,363,366,373,377,383,388,393,399,400,401,403,405,406,407,409,411,414,422,424,433,434,445,446,447,449,454,455,464,466,474,477,484,488,494,499,500,501,502,503,504,506,507,508,509,511,515,522,525,533,535,544,545,556,557,558,559,565,566,575,577,585,588,595,599,600,601,602,604,605,607,608,609,611,616,622,626,633,636,644,646,655,656,667,668,669,676,677,686,688,696,699,700,701,702,703,704,705,706,708,709,711,717,722,727,733,737,744,747,755,757,766,767,778,779,787,788,797,799,800,801,802,803,805,806,807,809,811,818,822,828,833,838,844,848,855,858,866,868,877,878,889,898,899,900,901,902,903,904,905,906,907,908,911,919,922,929,933,939,944,949,955,959,966,969,977,979,988,989]

Challenge rules:

• The integers in the input-list are guaranteed to be \$0\leq n\leq9\$ (aka single digits).
• Any single-value inputs are Frog List, since they'll contain a single Lazy Frog and no jumping frogs.
• I/O is flexible. You may take the input as a list/array/stream of digits, an integer, a string, etc. You may output any two values or type of values (not necessarily distinct) to indicate truthy/falsey respectively.
• You can assume a Frog List will never start with a 0 (doesn't matter too much for list I/O, but can be for integer I/O).

General Rules:

• This is code-golf, so the shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (e.g. TIO).
• Also, adding an explanation for your answer is highly recommended.

Answer 1

Python3, 498 bytes:

E=enumerate
def V(x,l):r=len(K:=set({x[i+1]-a for i,a in E(x)if i+1<len(x)}));return r==1and max(x)+max(K)>=len(l)
T=lambda x:[*filter(None,x)]
P=sorted
def f(l):
 if len(T(l))==1:return 1
 q=[(l,T({*l[:i]+l[i+1:]}),i,a,[])for i,a in E(l)if a>1]
 while q:
  L,s,I,o,C=q.pop(0)
  if[]==s and o-sum(C)not in l and o-sum(C)and C:return 1
  if[]==s:continue
  S,*s=s
  U=[i for i,a in E(l)if a==S and i!=I]
  if len(U)>1and V(P(U),l):q+=[(L,s,I,o,C)]
  if V(P(U+[I]),l)and len(C)<1:q+=[(L,s,I,o,C+[S])]

Try it online!

Answer 2

Haskell + hgl, 141 bytes

g k(x:y)=lq x<>mL1 x<>k?<fo y
f x=or[fo[ay(g k<tx<fue(dW(k/=)y)<sA)$dpH y|k<-y,k>0]|y<-[i++q:k|(i,j:k)<-fsA**<dph$x,q<-e0$j-1,(j-q)?<x||1>q]]

Attempt This Online!

Euch, this seems long. There's probably a better way to do this, and there's probably a lot of little things here I could tweak to improve it. But the spec turned out to be a lot more intricate and have a lot more edge cases than I had thought and I'm just glad to be done.

Explanation

First we find all the ways to split the list into two chunks

(i,j:k)<-fsA**<dph$x

We filter out cases where the element we are splitting is 0

j>0

Then we get all number strictly less than j. This will give us the id number for the lazy frog.

q<-e0$j-1

Now we replace the lazy frog with q.

i++q:k

Now we confirm that one of the possible combinations of lazy frog and replacement yields a solution. To check solutions we are going to check that every frog in the list can jump to the right.

So we enumerate every frog in the list:

k<-y,k>0

This has duplicates, but I don't care. For each frog we drop everything off the front of the list until that frog is at the front itself.

dW(k/=)y

Then for each number \$n\$ from one to the length of the list, we split the trimmed list into chunks of size \$n\$.

fue(dW(k/=)y)<sA)$dpH y

Now we transpose the list with tx. With the transposed list we want to check the following conditions:

• The first piece contains only one type of element (must be the frog we are looking at since it is the first element of the trimmed list) lq x
• The first piece contains at least two elements (so the frog jumps at least twice) mL1 x
• The frog cannot occur in other pieces k?<fo y

If the split list satisfies these conditions for any way to divide it, then that frog is good. If all frogs in the modified list satisfy this then the substitution is good. If any substitution of the lazy frog for a non-lazy frog is good, then the whole list is valid.

Reflection

There are a lot of things here that could be improved. A few come to mind immediately but I will probably add to this list as I ruminate on this.

• I shouldn't have to do ic[j]. I really thought I had already made a function which intercalates elements with lists. But it seems either I didn't or I can't find it.
• There should be a way to replace every instance of one element with another element.
• I could swear there used to be a "is x a prefix of y" function. But I cannot find it. It would be useful here
• There should be a way to get all partitions of a specific size. And there should be a function which gives all ways to split a list in two (as tuples).
• tx could be a pattern here. It would be one of the rare times in which a pattern would actually save bytes
• There should be a built in for breaking a list into chunks of a certain size. uue<sA is short, but it could be much shorter.
• I discovered eL is broken. I didn't need to use it but it should be fixed. Also there should be some pre-composed functions here with eL2, eL3 etc.

Answer 3

Jelly, 39 35 bytes

Ḷ⁹¦Ẏ€ŒpɗⱮTẎḟƑ_ƒ¥ƇSẹⱮ¹ƇfƑJmÐƤ`ẎIƇƲƲƇ

Try it online!

Takes an integer list as input, and outputs a list of all valid ways to ignore the Lazy Frog--falsy if empty.

Generate every candidate:

Ḷ⁹¦Ẏ€ŒpɗⱮTẎḟƑ_ƒ¥ƇS
       ɗⱮT            For every index with any frogs:
Ḷ⁹¦                   Replace the frog(s) at that index with [0 .. id),
   Ẏ€                 wrap all other elements in singleton lists,
     Œp               and compute the Cartesian product of all of them.
          Ẏ           Join the results into a single list of candidates.
                Ƈ     Filter the candidates to those which
           ḟƑ         do not contain
             _Ĵ      the difference between their sum and
                 S    the input's sum
             _Ĵ S    (i.e., the Lazy Frog's ID).

Filter (ƲƇ) to those with valid jumping frogs:

ẹⱮ¹ƇfƑJmÐƤ`ẎIƇƲ
      J ÐƤ         For every suffix of [1 .. len(input)],
       m           drop all but every n'th element, where n is
      J   `        each of [1 .. len(input)].
           Ẏ       Join the results,
            IƇ     and filter to those with multiple elements.
 Ɱ¹Ƈ               For every frog in the candidate,
ẹ                  get the list of all of its indices in the candidate.
    fƑ        Ʋ    Is every element of that list an element of the other list?

This took me an hour and a half to write on my phone and it didn't even work lmao

Answer 4

05AB1E, 68 67 bytes

εLã€êDOyQÏ}JŻ‘}θ€€SʒU9LεXQ€à0ÛDVεYNÅ0«Ćƶ0K¥Ë}à}þ`y˜0KD¢ΘOy€g2¢!P

Twice as long as the Jelly answer, but figured I'd post my own (now mostly golfed) reference implementation. A different approach is likely much shorter, though.

-1 byte by including duplicates in the truthy outputs.

Input as an integer; output as a list of list of ids for truthy cases (may contain duplicates) and an empty list for falsey cases.

Try it online or verify all test cases.

Explanation:

Step 1: Convert each digit of the input to a list of potential 1 or 2 frogs:

ε                  # Map over each digit of the (implicit) input-integer:
 L                 #  Convert it to a list in the range [1,digit]
  ã                #  Get the cartesian power of itself to create pairs
   €               #  Inner map over each pair:
    ê              #   Uniquify and sort each pair
     D             #  Duplicate this list
      O            #  Sum each inner list
       yQ          #  Check which are equal to the current digit
     D   Ï         #  Keep the singulars/pairs which sum to the digit
}                  # Close the map

Try just the first step.

Step 2: Reduce it by the cartesian product to create all possible result-lists (for which 05AB1E unfortunately lacks a builtin):

J                  # Join each inner singular/pair together
 Å»                # Left-reduce it by (unfortunately keeping all intermediate results)
   â               #  Take the cartesian product of the current two lists to create pairs
    €˜             #  Flatten each inner list
      }θ           # After the reduce (with intermediate results), keep the last
        €          # Map over each inner list:
         €         #  Inner map over each integer:
          S        #   Convert it back to a singular digit/pair of digits

Try the first two steps.

Step 3: Filter and output the result:

ʒ                  # Start filtering this list by:

Step 3a: Verify rules 4 (the jump distance of jumping frogs is always the same) and 5 (will go outside the list's right bound):

 U                 #  Pop and store the current list in variable `X`
 9L                #  Push a list in the range [1,9]
   ε               #  Map over this list of potential frog-ids:
    X              #   Push list `X`
     Q             #   Check which inner digits are equal to the current potential frog-id
      ۈ           #   Any on each (for the pairs)
        0Û         #   Trim all leading 0s
    DVεY           #   Duplicate this list its length amount of times as list
      ε            #   Inner map over each of these lists:
        NÅ0        #    Push a list with the 0-based index amount of 0s
           «       #    Append it to the list
            Ć      #    Enclose; append its own head
             ƶ     #    Multiply each inner 0/1 by its 1-based index
              0K   #    Remove all 0s
                ¥  #    Get the deltas/forward-differences
                 Ë #    Check if all of them are equal
       }à          #   After the inner map: check if any was truthy
    }þ             #  After the outer map: remove all empty strings (for the non-occurring frog-ids)
      `            #  Pop and push all checks to the stack

Step 3b: Verify rule 2 (there is exactly one Lazy Frog):

 y                 #  Push the current list we're filtering again
  ˜                #  Flatten it to a single list of digits
   0K              #  Remove all 0s
     D¢            #  For each digit, count how many times it occurs
       Θ           #  Check for each count whether it's equal to 1
        O          #  Sum them together to get the amount of Lazy Frogs

Step 3c: Verify rule 6 (there cannot be two jumping frogs on top of one another):

 y                 #  Push the current list we're filtering for a third time
  €g               #  Get the length of each inner list
    2¢             #  Count the amount of 2s (amount of pairs of frog-ids)
      !            #  Faculty to check it's either 0 or 1

Step 3d: Combine all checks, and output the result:

 P                 #  Get the product of all values on the stack
                   #  (note: only 1 is truthy in 05AB1E)
                   # (output the filtered result)