{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Block 2 — Exercises · Space: Reaction–Diffusion & Invasion Fronts\n",
    "### Bridging the Scales · GEFENOL Summer School 2026 · *Noise and Space in Biological Systems*\n",
    "\n",
    "We now let molecules **move**. The one new idea: diffusion is just another reaction, a hop $X_i \\to X_{i\\pm1}$ with rate $d = D/\\Delta x^2$. You will build a Fisher–KPP invasion front **two ways** — a continuous PDE and a discrete stochastic lattice — and measure how discreteness slows the front below the mean-field speed (the **Brunet–Derrida** effect).\n",
    "\n",
    "Complete every **>>> TODO** and run the ✅ self-checks (they should print **PASSED**). *Worked solutions:* **Block2_Space_and_Fronts.ipynb**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "plt.rcParams.update({'figure.figsize':(7,4),'axes.grid':True,'grid.alpha':0.25,'font.size':11})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 1 · The deterministic reference front (Fisher–KPP)\n",
    "$$\\partial_t u = D\\,\\partial_x^2 u + r\\,u(1-u).$$\n",
    "Integrate with **explicit Euler**. The discrete Laplacian is $(u_{i+1}-2u_i+u_{i-1})/\\Delta x^2$; use **no-flux (Neumann)** ends. Fisher–KPP theory predicts a front travelling at the selected speed $v^{*}=2\\sqrt{Dr}$.\n",
    "\n",
    "Complete the update step, then the code measures the front speed and compares it to $v^{*}$.\n",
    "\n",
    "<details><summary>💡 Hint</summary>\n",
    "\n",
    "- Laplacian with periodic roll: `(np.roll(u,-1) - 2*u + np.roll(u,1))/dx**2`.\n",
    "- Euler update: `u = u + dt*(D*lap + r*u*(1-u))`.\n",
    "- No-flux ends: `u[0], u[-1] = u[1], u[-2]`.\n",
    "- Keep `dt <= dx**2/(2*D)` or the explicit scheme blows up.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "D, r = 1.0, 1.0\n",
    "L, nx = 200.0, 1000\n",
    "dx = L/nx; dt = 0.2*dx**2/D            # CFL-stable\n",
    "\n",
    "def fkpp_run(nsteps=4000, record=400):\n",
    "    u = np.zeros(nx); u[:5] = 1.0     # seed the left edge\n",
    "    xf = []\n",
    "    for s in range(nsteps):\n",
    "        # >>> TODO (a): discrete Laplacian of u\n",
    "        # lap = ...\n",
    "        # >>> TODO (b): explicit-Euler update of u\n",
    "        # u = ...\n",
    "        # >>> TODO (c): no-flux boundary conditions at both ends\n",
    "        # u[0], u[-1] = ...\n",
    "        raise NotImplementedError(\"complete TODOs (a)-(c), then delete this line\")\n",
    "        if s % record == 0:\n",
    "            idx = np.where(u >= 0.5)[0]                 # front = where u crosses 1/2\n",
    "            xf.append((s*dt, idx[-1]*dx if len(idx) else 0.0))\n",
    "    return u, np.array(xf)\n",
    "\n",
    "u, xf = fkpp_run()\n",
    "t, pos = xf[:,0], xf[:,1]\n",
    "mask = t > t.max()*0.5\n",
    "v_pde = np.polyfit(t[mask], pos[mask], 1)[0]\n",
    "print(f\"measured PDE front speed = {v_pde:.3f}    (theory v* = {2*np.sqrt(D*r):.3f})\")\n",
    "plt.plot(np.linspace(0,L,nx), u); plt.xlim(0,L)\n",
    "plt.xlabel('x'); plt.ylabel('u'); plt.title('the reference travelling front');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✅ self-check: the measured speed must be close to 2*sqrt(Dr)\n",
    "assert abs(v_pde - 2*np.sqrt(D*r)) < 0.15, \"front speed is off from v* = 2 sqrt(Dr)\"\n",
    "print(\"PASSED \\u2705  the mean-field front travels at v* = 2 sqrt(Dr)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2 · The same front, individual by individual\n",
    "Now the discrete version. Each voxel has capacity $N$; cells grow by logistic birth at rate $r\\,n(1-n/N)$ and **hop** to neighbours at rate $d$. We use fixed-step $\\tau$-leaping so it stays fast.\n",
    "\n",
    "Births are provided. **Your job is the diffusion**: each step, some cells in each voxel become *movers*, split left/right, and land in the neighbouring voxel — with reflecting ends. Complete the redistribution.\n",
    "\n",
    "<details><summary>💡 Hint</summary>\n",
    "\n",
    "- Left-movers from site $i$ land at $i-1$: `n[:-1] += left[1:]`.\n",
    "- Right-movers from site $i$ land at $i+1$: `n[1:] += right[:-1]`.\n",
    "- Reflect at the edges: `n[0] += left[0]` and `n[-1] += right[-1]`.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lattice_front(V=400, N=100, d=1.0, r_=1.0, t_max=250, dt=0.05, seed=0):\n",
    "    rg = np.random.default_rng(seed)\n",
    "    n = np.zeros(V, int); n[:5] = N\n",
    "    front, t = [], 0.0\n",
    "    while t < t_max:\n",
    "        # reactions: logistic birth (non-negative tau-leap)  -- PROVIDED\n",
    "        n = n + rg.poisson(np.clip(r_*n*(1-n/N), 0, None)*dt)\n",
    "        # diffusion: how many cells leave each voxel, and split into L/R  -- PROVIDED\n",
    "        movers = rg.binomial(np.clip(n,0,None), min(d*dt, 1.0))\n",
    "        left   = rg.binomial(movers, 0.5)\n",
    "        right  = movers - left\n",
    "        n = n - movers\n",
    "        # >>> TODO: deposit left-movers into i-1, right-movers into i+1, reflect at ends\n",
    "        raise NotImplementedError\n",
    "        n = np.clip(n, 0, None)\n",
    "        occ = np.where(n > 0)[0]\n",
    "        front.append((t, occ[-1] if len(occ) else 0))\n",
    "        t += dt\n",
    "    return n, np.array(front)\n",
    "\n",
    "n_final, fr = lattice_front(seed=1)\n",
    "t2, pos2 = fr[:,0], fr[:,1]\n",
    "mask2 = t2 > t2.max()*0.5\n",
    "v_ssa = np.polyfit(t2[mask2], pos2[mask2], 1)[0]\n",
    "print(f\"stochastic front speed = {v_ssa:.3f}    (mean-field v* = {2*np.sqrt(1.0):.3f})\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✅ self-check: mass must be conserved by diffusion and the front must LAG the mean field\n",
    "rg = np.random.default_rng(0)\n",
    "probe = np.array([0,0,10,0,0]); tot0 = probe.sum()\n",
    "mv = rg.binomial(probe, 0.5); lf = rg.binomial(mv, 0.5); rt = mv - lf; q = probe - mv\n",
    "q[:-1] += lf[1:]; q[1:] += rt[:-1]; q[0] += lf[0]; q[-1] += rt[-1]\n",
    "assert q.sum() == tot0, \"diffusion is not conserving particles\"\n",
    "assert v_ssa < 2*np.sqrt(1.0), \"the discrete front should be slower than v*\"\n",
    "print(f\"PASSED \\u2705  particles conserved, and v_N = {v_ssa:.2f} < v* = {2*np.sqrt(1.0):.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 3 · Measuring the Brunet–Derrida correction\n",
    "The leading edge is only a handful of individuals, so the true speed falls below $v^{*}$ by a correction that shrinks only **logarithmically** with the per-voxel capacity $N$:\n",
    "$$v_N \\approx v^{*} - \\frac{\\pi^2 D}{2(\\ln N)^2}.$$\n",
    "Sweep $N$, measure $v_N$ for each, and check that $v^{*}-v_N$ **decreases as $N$ grows** and lines up against $(\\ln N)^{-2}$.\n",
    "\n",
    "<details><summary>💡 Hint</summary>\n",
    "\n",
    "Loop over `N`, call `lattice_front(N=N, ...)`, fit the slope over the second half of the run exactly as above. This is heavier — a handful of $N$ values is enough.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Ns = [20, 50, 100, 200, 400]\n",
    "vN = []\n",
    "for Nc in Ns:\n",
    "    # >>> TODO: run the lattice front for capacity Nc and measure its speed (append to vN)\n",
    "    raise NotImplementedError\n",
    "\n",
    "vstar = 2*np.sqrt(1.0)\n",
    "vN = np.array(vN)\n",
    "x = 1/np.log(Ns)**2\n",
    "plt.plot(x, vstar - vN, 'o-')\n",
    "plt.xlabel(r'$(\\ln N)^{-2}$'); plt.ylabel(r'$v^* - v_N$')\n",
    "plt.title('Brunet-Derrida: the gap closes only logarithmically');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✅ self-check: the speed gap should shrink monotonically as N increases\n",
    "gap = vstar - vN\n",
    "assert np.all(np.diff(gap) < 1e-6), \"v* - v_N should decrease as N grows\"\n",
    "print(\"PASSED \\u2705  discreteness at the edge sets the front speed\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Going further\n",
    "- **Test $v^{*}=2\\sqrt{Dr}$** in Part A by varying $D$ and $r$ independently.\n",
    "- **Stepping-stone model:** put the neutral Moran process (Block 1) on the lattice with migration between voxels and watch single-type domains **coarsen**, boundaries perform random walks, and fixation still win — absorbing states, now with geography.\n",
    "- **Next-Subvolume Method** (see the Appendix): make the spatial SSA $\\mathcal{O}(\\log V)$ per event with a priority queue."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.x"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
