| Bytes | Lang | Time | Link |
|---|---|---|---|
| 173 | JavaScript V8 | 241202T163152Z | l4m2 |
| 214 | JavaScript V8 | 241126T143307Z | Arnauld |
| 196 | Python 3 | 241126T194249Z | CursorCo |
| 240 | Haskell | 241126T154839Z | colossus |
| 369 | Python3 | 241126T143701Z | Ajax1234 |
| 085 | Charcoal | 241126T135018Z | Neil |
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])
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
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))
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.
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])}
The gnarly one liner always wins in the end.
Uses the same backwards search as found on the OEIS page.
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
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.
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
Charcoal, 85 bytes
NθFΦEX²Σ…⁰⊕θ↨⊕⊗ι²›⁼θΣι‹ι⮌ι«≔⟦ι⟧υFυ«≔⌕AX⁰κ⁰ηFηFΦη⁼§κλ↔⁻λμ⊞υEκ⎇⁻ξμ∧⁻ξλν⁺ν§κλ»¿⊙υ№κθ⟦⪫ιω
Try it online! Link is to verbose version of code. Explanation:
Nθ
Input n.
FΦEX²Σ…⁰⊕θ↨⊕⊗ι²›⁼θΣι‹ι⮌ι«
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.
≔⟦ι⟧υFυ«
Start a breath-first search for parties.
≔⌕AX⁰κ⁰η
Find the list of valid sources and destinations.
FηFΦη⁼§κλ↔⁻λμ
Find those sources and destinations that are an exact hop away.
⊞υEκ⎇⁻ξμ∧⁻ξλν⁺ν§κλ
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.