Jikka-5.6.0.0: README.md
# Jikka
[](https://github.com/kmyk/Jikka/actions/workflows/test.yml)
Jikka is an automated solver for problems of competitive programming.
In competitive programming, there are some problems that can be solved just by _repeating formula transformations_ or by _pasting snippets of famous data structures_.
Jikka solves such problems automatically.
Jikka takes problems as input in the form of programs of a very restricted subset of Python, optimizes the codes to reduce their computational complexity, and converts them to implementations of C++ for output.
/
競技プログラミングにおいて「ただ式変形をするだけで解ける」「ただデータ構造のライブラリを貼るだけで解ける」問題は実は少なくありません。
Jikka はそのような問題を自動で解いてくれます。
Jikka は問題をとても制限された Python のサブセット言語のコードの形で入力として受け取り、計算量を落とすような最適化を行い、C++ の実装に変換して出力します。
## Try on Web
Go <https://kmyk.github.io/Jikka/playground>.
## Usage
```console
$ jikka convert PYTHON_FILE
```
## How to Install
### Using prebuilt binaries (recommended)
Go [Releases page](https://github.com/kmyk/Jikka/releases) and download `jikka-vA.B.C.D-Linux`, `jikka-vA.B.C.D-maxOS` or `jikka-vA.B.C.D-Windows.exe`.
### Using Stack
[Stack](https://www.haskellstack.org/) is required. If you are using Ubuntu, you can install Stack with `$ sudo apt install haskell-stack`.
```console
$ git clone https://github.com/kmyk/Jikka.git
$ cd Jikka
$ stack install
```
### Using Cabal
[Cabal](https://www.haskell.org/cabal/) is required. This is bundled [Haskell Platform](https://www.haskell.org/platform/). If you are using Ubuntu, you can install Stack with `$ sudo apt install haskell-platform`.
```console
$ cabal update
$ cabal install Jikka
```
## Discussions
Please feel free to use our [GitHub Discussions](https://github.com/kmyk/Jikka/discussions). / [GitHub Discussions](https://github.com/kmyk/Jikka/discussions) があるので気軽に使ってください。
## Documents
For users:
- [docs/language.md](https://github.com/kmyk/Jikka/blob/master/docs/language.md)
- The language specification of our restricted Python / Jikka で使われる制限された Python の言語仕様
- [docs/optimization.md](https://github.com/kmyk/Jikka/blob/master/docs/optimization.md)
- A list of optimizations which Jikka does / Jikka が行なってくれる最適化の一覧
- [examples/](https://github.com/kmyk/Jikka/blob/master/examples)
- [gallery](https://kmyk.github.io/Jikka/gallery)
- [playground](https://kmyk.github.io/Jikka/playground)
- [CHANGELOG.md](https://github.com/kmyk/Jikka/blob/master/CHANGELOG.md)
For developpers:
- [CONTRIBUTING.md](https://github.com/kmyk/Jikka/blob/master/CONTRIBUTING.md)
- My blog article [競技プログラミングの問題を自動で解きたい - うさぎ小屋](https://kimiyuki.net/blog/2020/12/09/automated-solvers-of-competitive-programming/) (Japanese)
- On what it means to automatically solve problems of competitive programming / 競技プログラミングの問題を自動で解くとはどういうことなのかについて
- [docs/how-it-works.pdf](https://github.com/kmyk/Jikka/blob/master/docs/how-it-works.pdf) (Japanese)
- How it works and related theories / 動作原理や関連する理論
- [docs/DESIGN.md](https://github.com/kmyk/Jikka/blob/master/docs/DESIGN.md)
- The policy of designs / 実装方針
- [docs/internal.md](https://github.com/kmyk/Jikka/blob/master/docs/internal.md)
- The overview of internal processes / 内部の処理の流れ
- [docs/core.md](https://github.com/kmyk/Jikka/blob/master/docs/core.md)
- The specification of core language / core 言語の仕様
- [Haddock](https://hackage.haskell.org/package/Jikka)
- [Haddock (master)](https://kmyk.github.io/Jikka/haddock)
## Examples
### `examples/fib.py` (`v5.0.5.0`)
Input, O(N):
```python
def f(n: int) -> int:
a = 0
b = 1
for _ in range(n):
c = a + b
a = b
b = c
return a
def solve(n: int) -> int:
return f(n) % 1000000007
```
Output, O(log N):
```c++
#include "jikka/all.hpp"
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>
int64_t solve(int64_t n_317) {
return jikka::modmatap<2, 2>(
jikka::modmatpow<2>(jikka::make_array<std::array<int64_t, 2>>(
jikka::make_array<int64_t>(1, 1),
jikka::make_array<int64_t>(1, 0)),
n_317, 1000000007),
jikka::make_array<int64_t>(1, 0), 1000000007)[1];
}
int main() {
int64_t x318;
std::cin >> x318;
int64_t x319 = solve(x318);
std::cout << x319;
std::cout << '\n';
}
```
### `examples/static_range_sum.py` (`v5.0.10.0`)
Input, O(N^2):
```python
# https://judge.yosupo.jp/problem/static_range_sum
from typing import *
def solve(n: int, q: int, a: List[int], l: List[int], r: List[int]) -> List[int]:
ans = [-1 for _ in range(q)]
for i in range(q):
ans[i] = sum(a[l[i]:r[i]])
return ans
def main() -> None:
n, q = map(int, input().split())
a = list(map(int, input().split()))
assert len(a) == n
l = list(range(q))
r = list(range(q))
for i in range(q):
l[i], r[i] = map(int, input().split())
ans = solve(n, q, a, l, r)
for i in range(q):
print(ans[i])
if __name__ == '__main__':
main()
```
Output, O(N):
```c++
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>
std::vector<int64_t> solve(int64_t n_0, int64_t q_1, std::vector<int64_t> a_2,
std::vector<int64_t> l_3, std::vector<int64_t> r_4) {
std::vector<int64_t> x6 = std::vector<int64_t>(a_2.size() + 1);
x6[0] = 0;
for (int32_t i7 = 0; i7 < int32_t(a_2.size()); ++i7) {
x6[(i7 + 1)] = x6[i7] + a_2[i7];
}
std::vector<int64_t> x5 = x6;
std::vector<int64_t> x10 = std::vector<int64_t>(q_1);
for (int32_t i11 = 0; i11 < int32_t(q_1); ++i11) {
x10[i11] = -x5[l_3[i11]] + x5[r_4[i11]];
}
return x10;
}
int main() {
int64_t n_13 = -1;
int64_t q_14 = -1;
std::cin >> n_13;
std::vector<int64_t> a_15 = std::vector<int64_t>(n_13, -1);
std::cin >> q_14;
std::vector<int64_t> l_16 = std::vector<int64_t>(q_14, -1);
std::vector<int64_t> r_17 = std::vector<int64_t>(q_14, -1);
for (int32_t i18 = 0; i18 < n_13; ++i18) {
std::cin >> a_15[i18];
}
for (int32_t i_19 = 0; i_19 < q_14; ++i_19) {
std::cin >> l_16[i_19];
std::cin >> r_17[i_19];
}
for (int32_t i_20 = 0; i_20 < q_14; ++i_20) {
}
auto ans_21 = solve(n_13, q_14, a_15, l_16, r_17);
for (int32_t i_22 = 0; i_22 < q_14; ++i_22) {
}
for (int32_t i_23 = 0; i_23 < q_14; ++i_23) {
std::cout << ans_21[i_23] << ' ';
std::cout << '\n' << ' ';
}
}
```
## License
Appache License 2.0