Frogs on lily pads want to make a party

Question

Consider binary strings (reading from left to right) starting with a '1' as ponds of lily pads. A '1' signifies a frog sitting on the lily pad, and a '0' represents an empty lily pad.

Here, we see a pond with 7 lily pads on which 4 frogs are sitting:

1101001

The frogs want to all party together. This means that, ultimately, they all want to sit on a single lily pad. However, there are rules as to how to achieve this:

• All of the frogs on a single lily pad jump at once.
• If there are k frogs jumping they jump k spaces to the right or left. (they must all jump in the same direction.)
• Frogs are not allowed to jump onto an empty lily pad.

Examples

1
11       -> 02
111      -> 021      -> 030
1011     -> 1020     -> 3000 
1101001  -> 0201001  -> 0003001  -> 0000004 
10001111 -> 10002011 -> 10002020 -> 10004000 -> 50000000
10110111 -> 10020111 -> 10000311 -> 10000302 -> 10000500 -> 60000000

Challenge

Given n, show all ponds as binary strings, which allow the n frogs to gather to a party. But disregard ponds, which are only a left-right reversal of another one. The output can be given as a comma-separated list or line by line.

For example, for 4 frogs, the output is

[1111, 11101, 11011, 111001, 1101001]

These sequences of jumps lead to the party:

1111 -> 0211 -> 0013 -> 0004
11101 -> 02101 -> 03001 -> 00004
11011 -> 02011 -> 02020 -> 04000
111001 -> 201001 -> 003001 -> 000004
1101001 -> 0201001 -> 0003001 -> 0000004

As a test case show the 12 solutions for 5 frogs. The order is not fixed!

11111      
111011     
111101     
1101011    
1110011    
1111001    
11010011   
11011001   
11110001   
111010001  
1110010001 
11010010001

This is code-golf, so each language's shortest code in bytes wins.

Credits

Gordon Hamilton, Jumping Frogs

Gordon Hamilton and Brady Haran, Frog Jumping, Numberphile video.

Glen Whitney, OEIS A378004 (counting the number of solutions).

Answer 1

JavaScript (V8), 214 bytes

-1 thanks to @l4m2

Quite long, but fast (to some extent).

n=>(F=(a,g=a[n*n]=n,i=-1,k=a.find(x=>x>!!++i))=>k?(g=j=>--j+k&&g(j,a[i+j]||F(b=[...a],b[b[i+j]=j*=j>0||-1,i]-=j)))(k):F[s=/1.*1|1/.exec(a.join``)[0]]||print(F[s]=F[[...s].reverse().join``]=s))(Array(n*n*2).fill(0))

Try it online!

Check the number of solutions up to n=10

Method

As illustrated on the OEIS page, we start with all frogs in a single place and make a tree of all possible reverse moves with a breadth-first search:

                     _____________4____
                    /             |    \
               ___3001___        202    13
              /   |  |   \      /   \    |
        201001 12001 2101 1021 1102 112 121
       /   |     |         |    |
1101001 111001 11101      1111 11011

Implementation

We start with an array of size \$2n^2\$ filled with 0's, except the entry at position \$n^2\$ (0-indexed) which is set to \$n\$.

At each iteration, we look for the first value \$k>1\$ in the array and try to move \$1\$ to \$k-1\$ frogs from there to empty lily pads, in both directions. Each move is a recursive call to the function \$F\$ with an updated copy of the array.

Once there are only 0's and 1's remaining in the array, we trim the leading and trailing 0's and check whether the resulting pattern was already encountered. If not, we print the pattern and save it along with its reversed counterpart, so that neither is printed again.

Answer 2

Python 3, 216 204 196 bytes

-8 bytes thanks to @Unrelated String

g=lambda*y:{z for i in range(len(y))for v in(y,y[::-1])for n in range(1,v[i])for z in g(*(i<n or 1>v[i-n])*(*v[:i][:-n],n,*(n+~i)*[0],*v[:i][1-n or i:],v[i]-n,*v[i+1:]))}-{y[1:]}or{min(y,y[::-1])}

Try it online!

The gnarly one liner always wins in the end.

Uses the same backwards search as found on the OEIS page.

Answer 3

Charcoal, 85 bytes

ＮθＦΦＥＸ²Σ…⁰⊕θ↨⊕⊗ι²›⁼θΣι‹ι⮌ι«≔⟦ι⟧υＦυ«≔⌕ＡＸ⁰κ⁰ηＦηＦΦη⁼§κλ↔⁻λμ⊞υＥκ⎇⁻ξμ∧⁻ξλν⁺ν§κλ»¿⊙υ№κθ⟦⪫ιω

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input n.

ＦΦＥＸ²Σ…⁰⊕θ↨⊕⊗ι²›⁼θΣι‹ι⮌ι«

Make bit strings of up to length 1+T(n) (n² would save 2 bytes but take too long on TIO) which both start and end in 1 plus have n bits in total and do not already appear as a reversal.

≔⟦ι⟧υＦυ«

Start a breath-first search for parties.

≔⌕ＡＸ⁰κ⁰η

Find the list of valid sources and destinations.

ＦηＦΦη⁼§κλ↔⁻λμ

Find those sources and destinations that are an exact hop away.

⊞υＥκ⎇⁻ξμ∧⁻ξλν⁺ν§κλ

Calculate the position after the hop and add it to the search list.

»¿⊙υ№κθ

If any position is a party, then...

⟦⪫ιω

... output the original bit string.

Answer 4

Haskell, 240 bytes

g.h.pure
h l|all(<2)l=[show=<<l]|m<-length l-1=[r|(i,k)<-zip[0..]l,k>1,j<-[1..k-1],d<-[i+j,i-j],d<0||d>m||l!!d<1,r<-h[last$0:[l!!x|elem x[0..m]]++[k-j|x==i]++[j|x==d]|x<-[min 0 d..max d m]]]
g(a:r)=a:g(filter(`notElem`[a,reverse a])r)
g e=e

Try it online!

Starts with a party and backtracks to find all possible starting positions.

The h function takes a list of frog counts and returns a list of starting positions that can lead to that position. First we check if all the frogs are alone; if so we simply return the input as binary string in a singleton list. Otherwise we iterate over each position that has k frogs (where k is at least 2) and send j of them j positions left or right (where j is at most k-1 so we always leave at least one frog behind) as long as the landing spot is empty. Then we recur with that new position.

Finally all we have to do is filter out all the repetitions.

Answer 5

Python3, 369 bytes

def f(n):
 q,s,r=[([],n,0)],[],[]
 for a,b,t in q:
  if b:q+=[(a+[1],b-1,0)]
  if t<n-1 and b and a:q+=[(a+[0],b,t+1)]
  if b==0 and a[::-1]not in s:
   s+=[a[::-1],a];Q,S=[a],[a]
   for u in Q:
    if u.count(0)==len(u)-1:r+=[a];break
    for i,j in enumerate(u):
     for I in[-1,1]:
      if 0<=(V:=I*j+i)<len(u)and u[V]:U=[*u];U[i]=0;U[V]+=j;Q+=[U];S+=[U]
 return r

Try it online!

Answer 6

JavaScript (V8), 173 bytes

n=>(g=(a,i=0,A=[...a].reverse(),h=t=>--a[i]&&h(++t,a[t]=a[t]||(a[t]=t-i,g([...a]))))=>1/a[i]?a[i]>1?h(i,A&&g(A,a.length+~i,0)):g(a,i+1):g[a]||print(g[a]=g[A]=a.join``))([n])

Try it online!

Idea of Arnauld, split the first group of ≥2

Handle jump backward, then reverse the array and still handle jump backwards, since it's easier to append at end.

Should be faster than Arnauld's since shorter array. Because of too many execution of reverse it can be slower. g(a,i+1) => g(a,i+1,A) to accelerate