## Euler's Method

We want to calculate the shape of an unknown curve which starts at a given point 
with a given slope. This curve satisfies an ordinary differential equation (ODE):

```math
\frac{dy}{dx} = f(x, y);\\
y(x_0) = y_0
```

The starting point `$ A_0 (x_0, y_0) $` is known as well as the slope to the curve 
at `$ A_0 $` and then the tangent line at `$ A_0 $` .

Take a small step along that tangent line up to a point `$ A_1 $`. Along this small step, 
the slope does not change too much, so `$ A_1 $` will be close to the curve. 
If we suppose that `$ A_1 $` is close enough to the curve, the same reasoning 
as for the point `$ A_1 $` above can be used for other points. 
After several steps, a polygonal curve `$ A_0, A_1, ..., A_n $` is computed. 
The error between the two curves will be small if the step is small.

We define points `$ A_0, A_1, A_2, ..., A_n $`
whose x-coordinates are `$ x_0, x_1, ..., x_n $`
and y-coordinates are such that `$ y_{k+1} = y_k + f(x_k, y_k) \times h $` 
where `$ h $` is the common step. If `$ T $` is the length `$ x_n - x_0 $` we have `$ h = T/n $`.

## Task

For this kata we will focus on the following differential equation:

```math
\frac{dy}{dx} = 2 - e^{-4x} - 2y; \\
A_0 = (0,1)
```
with `$ x ∈ [0, 1] $`. We will then take a uniform partition of the region of `$ x $` between `$ 0 $` and `$ 1 $` and split it into `$ n $` + 1 sections. `$ n $` will be the input to the function `ex_euler(n)` and since `$ T $` is always 1, `$ h = 1/n $`.

We know that an exact solution is
```math
y = 1 + 0.5e^{-4x} - 0.5e^{-2x}.
```
For each `$ x_k $` we are able to calculate the `$ y_k $` as well as the values `$ z_k $` of the exact solution.

Our task is, for a given number `$ n $` of steps, to return the mean (*truncated* to 6 decimal places)
of the relative errors between the `$ y_k $` (our aproximation) and the `$ z_k $` (the exact solution). 
For that we can use:

error in `$ A_k = abs(y_k - z_k) / z_k $` and then the mean is sum(errors in `$ A_k $`)/ (`$ n $` + 1)

## Examples

```python
ex_euler(10) should return: 0.026314 (truncated from 0.026314433214799246)
with
Y = [1.0,0.9..., 0.85..., 0.83..., 0.83..., 0.85..., 0.86..., 0.88..., 0.90..., 0.91..., 0.93...]
Z = [1.0, 0.9..., 0.88..., 0.87..., 0.87..., 0.88..., 0.89..., 0.90..., 0.91..., 0.93..., 0.94...]
Relative errors = [0.0, 0.02..., 0.04..., 0.04..., 0.04..., 0.03..., 0.03..., 0.02..., 0.01..., 0.01..., 0.01...]
```
`ex_euler(17)` should return: `0.015193 (truncated from 0.015193336263370796)`.
As expected, as `$ n $` increases, our error reduces.
### Links and graphs

Wiki article

![alternative text](http://i.imgur.com/vjK7edl.png)

Below comparison between approximation (red curve) and exact solution(blue curve) for n=100:
![alternative text](http://i.imgur.com/KufSkYEm.png)

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from math import *\nimport numpy as np\nfrom decimal import *\n\ndef f(xk,yk):\n    return 2 - exp(-4*xk) - 2*yk\ndef Y(t):\n    return 1 + 0.5*exp(-4*t) - 0.5*exp(-2*t)\n    \ndef ex_euler(n):\n        x = 0\n        y0 = 1\n        T = 1\n        h = 1/n\n        y = np.zeros(n+1)\n        z = np.zeros(n+1)\n        y[0] = y0        \n        for i in range(n):\n            y[i+1] = y[i] + f(x,y[i])*h\n            z[i] = Y(x)\n            x+=h\n        z[len(z)-1] = Y(x)\n        A = [abs(y[i] - z[i])/z[i] for i in range(n+1)]\n        return round(1e-6 * trunc(1e6*(np.mean(A, dtype=np.float32))),6)    \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'ex_euler'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: