Jikka
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
$ jikka convert PYTHON_FILEHow to Install
Using prebuilt binaries (recommended)
Go Releases page 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 is required. If you are using Ubuntu, you can install Stack with $ sudo apt install haskell-stack.
$ git clone https://github.com/kmyk/Jikka.git
$ cd Jikka
$ stack installUsing Cabal
Cabal is required. This is bundled Haskell Platform. If you are using Ubuntu, you can install Stack with $ sudo apt install haskell-platform.
$ cabal update
$ cabal install JikkaDiscussions
Please feel free to use our GitHub Discussions. / GitHub Discussions ใใใใฎใงๆฐ่ปฝใซไฝฟใฃใฆใใ ใใใ
Documents
For users:
- docs/language.md
- The language specification of our restricted Python / Jikka ใงไฝฟใใใๅถ้ใใใ Python ใฎ่จ่ชไปๆง
- docs/optimization.md
- A list of optimizations which Jikka does / Jikka ใ่กใชใฃใฆใใใๆ้ฉๅใฎไธ่ฆง
- examples/
- CHANGELOG.md
For developpers:
- CONTRIBUTING.md
- docs/how-it-works.pdf / docs/how-it-works.ja.pdf
- How it works and related theories / ๅไฝๅ็ใ้ข้ฃใใ็่ซ
- docs/DESIGN.md
- The policy of designs / ๅฎ่ฃ ๆน้
- docs/internal.md
- The overview of internal processes / ๅ ้จใฎๅฆ็ใฎๆตใ
- docs/core.md
- The specification of core language / core ่จ่ชใฎไปๆง
- Haddock
Blog articles:
- ็ซถๆใใญใฐใฉใใณใฐใฎๅ้กใ่ชๅใง่งฃใใใ - ใใใๅฐๅฑ (Japanese)
- Jikka, a transpiler/solver for competitive programming - Codeforces
Examples
examples/fib.py (v5.0.5.0)
Input, O(N):
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) % 1000000007Output, O(log N):
#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):
# 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):
#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