| Bytes | Lang | Time | Link |
|---|---|---|---|
| 179 | R | 241209T004300Z | Eonema |
| 057 | Charcoal | 241127T133301Z | Neil |
| 103 | JavaScript Node.js | 241127T192216Z | l4m2 |
| 119 | JavaScript Node.js | 241127T032524Z | tsh |
| 023 | Jelly | 241127T195630Z | Jonathan |
| 324 | Python3 | 241127T034326Z | Ajax1234 |
R, 179 bytes
\(i,f,s=1:length(i))any(apply(expand.grid(lapply(i,seq,f=0)),1,\(g,n=sum(g))any(sapply(c(-1,1),\(d)all(sapply(s,\(x)i[x]-g[x]+`if`((x+d*n)%in%s,g[x+d*n],0))==f)))))&sum(i)==sum(f)
Commented:
# takes initial positions i and final positions f, calculates vector of poles s
function(i, f, s = 1:length(i)) {
# iterates over all possible flocks and returns true if any are valid
any(apply(
expand.grid(lapply(i, seq, first = 0)), # all possible flocks (beginning position)
1,
function(g, n = sum(g)) { # n = size of flock
# true for either direction -1 or 1:
any(sapply(c(-1,1), function(d) {
# true if new counts are same as final counts on every pole
all(sapply(s, function(x) {
# initial count minus flock count on that pole
i[x] - g[x] +
# plus new birds, if that doesn't go outside the listed poles
if ((x+d*n) %in% s) g[x+d*n] else 0
}) == f)
}))
}
)) &
# check that the number of birds stays the same
# necessary to make sure no birds flew outside of the listed poles
sum(i)==sum(f)
}
Charcoal, 57 bytes
≔Σ⊕⁺⌊θ⌈θη≔↔↨Eθ↨ιη±¹ζ⬤Eη⊖Xηι⎇κ∨﹪ζι∨⁻κΣ↨÷ζιη⊙⮌↨÷ζιη›λ§⮌⌊θμζ
Try it online! Link is to verbose version of code. Takes input as an array of two arrays and outputs an inverted Charcoal boolean, i.e. nothing if a single movement exists, - if not. Explanation:
≔Σ⊕⁺⌊θ⌈θη
Charcoal has no polynomials, so these are simulated by performing operations with an arbitrarily large base b, here computed as the sum of the incremented values in the input arrays.
≔↔↨Eθ↨ιη±¹ζ
Calculate the difference between the two arrays in base b.
⬤Eη⊖Xηι⎇κ∨﹪ζι∨⁻κΣ↨÷ζιη⊙⮌↨÷ζιη›λ§⮌⌊θμζ
If the difference is not zero, and no integer exists such that the difference is divisible by bⁿ-1, the result of the division being represented in base b with digits whose sum is n, and those digits do not exceed the corresponding value in the smaller of the two input arrays (e.g. in the last test case, a flock of size 2 cannot move since there are no birds in the middle of the array), then output a -.
45 42 bytes if I ever get around to implementing Cartesian product on ATO:
⊙Π⁺E⌈θ…·⁰ιE⌈θ⁰›⁼⌊θE⌈θ⁺⁻λ§ιμ§ι⁻μΣι⌊✂ι⁻L⌈θΣι
Attempt This Online? Link is to verbose version of code. Takes input as an array of two arrays and outputs a Charcoal boolean, i.e. - if a single movement exists, nothing if not. Explanation: For each possible flock, calculates whether it can legally move by its size k and if so whether that results in the other state.
JavaScript (Node.js), 103 bytes
f=(a,b,i=0)=>1/a[i]&&f(b,a,i+(a<=b))|![...a].map((t,j,a)=>s+=!(t-=b[j])||t<0&(a[i+j]+=t)>=0?t:f,s=i)==s
-1B Shaggy
Try all is and all (a,b) orders
JavaScript (Node.js), 119 bytes
a=>g=(b,r=n=(a.map((v,i)=>m+=(v-b[i])*i,m=0),m*m)**.25)=>a.some(u=>u<b[++i],i=-1)?b[i]--*a[i+m/n]--*g(b,r-1)>0:r+a==0+b
Although following algorithm passes all testcases, I have no idea if it actually works... (So use at your own risk)
Given \$\vec{a},\vec{b}\in\mathbb{Z}_{\ge 0}^{n}\$ for number of birds After and Before. Let’s define \$\vec{u}=[0,1,\dots,n-1]^\top\$ and we need to move \$n\$ birds with \$d\$ cells where $$ \begin{aligned} m&=\left(\vec{a}-\vec{b}\right)\cdot\vec{u}\\ n&=\sqrt{\left|m\right|}\\ d&=\frac{m}{n} \end{aligned} $$ In each move, we find first \$i\$ such that \$a_i<b_i\$, and move one bird by \$b_{i}'=b_i-1\$, \$a_{i+d}'=a_{i+d}-1\$. The moving may fail if \$i+d\notin\{0,\dots,n-1\}\$ or \$a_{i+d}=0\$.
We would report false if either \$n\$ is not integer, or we failed to attempt \$n\$ moves, or \$\vec{a}'\neq\vec{b}'\$ after \$n\$ moves. Or true if we successfully make \$\vec{a}'=\vec{b}'\$ after \$n\$ moves.
The algorithm has \$\mathcal{O}\left(n^2\right)\$ time complexity. However, since the function is symmetric, you may swap \$\vec{a}\$ and \$\vec{b}\$ so \$d\ge 0\$. Then a improved implementation could do the process in \$\mathcal{O}\left(n\right)\$ time.
Jelly, 23 bytes
ṫS‘$+NS¬ȧƊ
ṂŻ€ŒpÇ€+Ʋe@Ṁ
A monadic Link that accepts a pair of lists of birds per pole and yields 1 if a flock of \$k \ge 0\$ birds could have moved in tandem by \$k\$ steps each to transition from one state to the other.
Try it online! Or see the test-suite.
How?
If a flock could have moved then it could have moved left from the minimum of the two states to the maximum of the two states.
If any flock movement would take any birds farther left than any of the poles that state change should not be considered.
ṫS‘$+NS¬ȧƊ - Link 1, Get Delta: Flock (same format as a State)
$ - last two links as a monad - f(Flock):
S - sum {Flock} -> FlockSize
‘ - increment
ṫ - tail {Flock} from {that} index
N - negate {Flock}
+ - add these together -> PoleDeltas
Ɗ - last three links as a monad - f(PoleDeltas):
S - sum {PoleDeltas} -> 0 if birds stayed within range
¬ - logical NOT
ȧ - logical AND {PoleDeltas}
ṂŻ€ŒpÇ€+Ʋe@Ṁ - Main Link: States
Ṃ - minimum {States} -> MinState
Ʋ - last four links as a monad - f(MinState):
Ż€ - zero-range each
Œp - Cartesian product
-> all potential flocks (including [0,0,...])
Ç€ - call Link 1 for each -> ValidDeltas
+ - add {MinState} (vectorises)
-> PossibleNewStates
Ṁ - maximum {States} -> MaxState
e@ - {MaxState} exists in {PossibleNewStates}
Python3, 324 bytes
from itertools import*
R=range
def f(a,b):
v=[*R(len(a))]
for i in v:
for j in combinations(v,i):
for t in product(*[R(1,a[u]+1)for u in j]):
for D in[1,-1]:
F,O=1,[*a]
for u,k in zip(j,t):
if 0<=(T:=u+sum(t)*D)<len(O)and u<len(a)and O[u]:O[u]-=k;O[T]+=k
else:F=0
if F and O==b:return 1