# History

This kata is a sequel of my [Mixbonacci](https://www.codewars.com/kata/mixbonacci/python) kata. Zozonacci is a special integer sequence named after [**ZozoFouchtra**](https://www.codewars.com/users/ZozoFouchtra), who came up with this kata idea in the [Mixbonacci discussion](https://www.codewars.com/kata/mixbonacci/discuss/python). 

This sequence combines the rules for computing the n-th elements of fibonacci, jacobstal, pell, padovan, tribonacci and tetranacci sequences according to a given pattern.

# Task

Compute the first `n` elements of the Zozonacci sequence for a given pattern `p`.

## Rules

1. `n` is given as integer and `p` is given as a list of as abbreviations as strings (e.g. `["fib", "jac", "pad"]`)
2. When `n` is 0 or `p` is empty return an empty list.
3. The first four elements of the sequence are determined by the first abbreviation in the pattern (see the table below).
4. Compute the fifth element using the formula corespoding to the first element of the pattern, the sixth element using the formula for the second element and so on. (see the table below and the examples)
5. If `n` is more than the length of `p` repeat the pattern.


```
+------------+--------------+------------------------------------------+---------------------+
|  sequence  | abbreviation |         formula for n-th element         | first four elements |
+------------|--------------+------------------------------------------|---------------------|
| fibonacci  |     fib      | a[n] = a[n-1] + a[n-2]                   |     0, 0, 0, 1      |
| jacobsthal |     jac      | a[n] = a[n-1] + 2 * a[n-2]               |     0, 0, 0, 1      |
| padovan    |     pad      | a[n] = a[n-2] + a[n-3]                   |     0, 1, 0, 0      |
| pell       |     pel      | a[n] = 2 * a[n-1] + a[n-2]               |     0, 0, 0, 1      |
| tetranacci |     tet      | a[n] = a[n-1] + a[n-2] + a[n-3] + a[n-4] |     0, 0, 0, 1      |
| tribonacci |     tri      | a[n] = a[n-1] + a[n-2] + a[n-3]          |     0, 0, 0, 1      |
+------------+--------------+------------------------------------------+---------------------+
```

## Example

```
zozonacci(["fib", "tri"], 7) == [0, 0, 0, 1, 1, 2, 3]

Explanation: 

          b     d
       /-----\/----\
[0, 0, 0, 1, 1, 2, 3]
 \--------/  
     | \--------/
     a     c

a - [0, 0, 0, 1] as "fib" is the first abbreviation
b - 5th element is 1 as the 1st element of the pattern is "fib": 1 = 0 + 1
c - 6th element is 2 as the 2nd element of the pattern is "tri": 2 = 0 + 1 + 1
d - 7th element is 3 as the 3rd element of the pattern is "fib" (see rule no. 5): 3 = 2 + 1
```

## Sequences

* [fibonacci](https://oeis.org/A000045) : 0, 1, 1, 2, 3 ...
* [padovan](https://oeis.org/A000931): 1, 0, 0, 1, 0 ...
* [jacobsthal](https://oeis.org/A001045): 0, 1, 1, 3, 5 ...
* [pell](https://oeis.org/A000129): 0, 1, 2, 5, 12 ...
* [tribonacci](https://oeis.org/A000073): 0, 0, 1, 1, 2 ...
* [tetranacci](https://oeis.org/A000078): 0, 0, 0, 1, 1 ...

```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 collections import deque\n\nstart = {\n    'fib': [0, 0, 0, 1],\n    'jac': [0, 0, 0, 1],\n    'pad': [0, 1, 0, 0],\n    'pel': [0, 0, 0, 1],\n    'tet': [0, 0, 0, 1],\n    'tri': [0, 0, 0, 1],\n}\n\nsum_idx = {\n    'fib': [-1, -2],\n    'jac': [-1, -2, -2],\n    'pad': [-2, -3],\n    'pel': [-1, -1, -2],\n    'tet': [-1, -2, -3, -4],\n    'tri': [-1, -2, -3],\n}\n\ndef sequence(pattern):\n    pattern, seq = deque(pattern), deque(start[pattern[0]])\n    while 1:\n        seq.append(sum(seq[idx] for idx in sum_idx[pattern[0]]))\n        yield seq.popleft()\n        pattern.rotate(-1)\n\ndef zozonacci(pattern, length):\n    return pattern and [n for _, n in zip(range(length), sequence(pattern))]"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'zozonacci'
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: 6290