Jikka: A transpiler from Python to C++ for competitive programming

[ compilers-interpreters, library, program ] [ Propose Tags ]

Please see the README on GitHub at https://github.com/kmyk/Jikka


[Skip to Readme]
Versions [RSS] [faq] 5.0.11.1, 5.0.11.2, 5.1.0.0, 5.2.0.0, 5.3.0.0, 5.4.0.0, 5.5.0.0, 5.6.0.0
Change log CHANGELOG.md
Dependencies ansi-terminal (==0.11.*), array (>=0.5.3 && <0.6), base (>=4.12 && <5), containers (>=0.6.0 && <0.7), deepseq (>=1.4.4 && <1.5), directory (>=1.3.3 && <1.4), Jikka, mtl (>=2.2.2 && <2.3), template-haskell (>=2.15.0 && <2.17), text (>=1.2.3 && <1.3), transformers (>=0.5.6 && <0.6), vector (>=0.12.3 && <0.13) [details]
License LicenseRef-Apache
Copyright 2021 Kimiyuki Onaka
Author Kimiyuki Onaka
Maintainer kimiyuk95@gmail.com
Category Compilers/Interpreters
Home page https://github.com/kmyk/Jikka#readme
Bug tracker https://github.com/kmyk/Jikka/issues
Source repo head: git clone https://github.com/kmyk/Jikka
Uploaded by kimiyuki at 2021-09-25T15:17:06Z
Distributions NixOS:5.5.0.0
Executables jikka
Downloads 603 total (21 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2021-09-25 [all 1 reports]

Modules

[Index] [Quick Jump]

Manual Flags

NameDescriptionDefault
embed-runtime

Embed files under runtimeinclude to the compiled binary.

Disabled
Automatic Flags
NameDescriptionDefault

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Candidates


Readme for Jikka-5.6.0.0

[back to package description]

Jikka

test

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_FILE

How to Install

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 install

Using 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 Jikka

Discussions

Please feel free to use our GitHub Discussions. / GitHub Discussions があるので気軽に使ってください。

Documents

For users:

For developpers:

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) % 1000000007

Output, 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