kmyk-jikka/jikka

an automated solver for problems of competitive programming

jikka's Issues

入出力部分も生成する

選択肢は以下のふたつ。いまのところは入力コードの self-contained のために (1.) を推したい

1. a = int(input()) みたいな入力取得コードを解釈して変換する
2. コメントなどで N A_1 A_2 ... A_N みたいなのを書かせて生成する

TODO: 型について

構文解析はだいたいできたので、型が付いていない λ 項が入力されていると見ることができる。したいのは式木を組み換えての最適化処理。なのでとりあえずいい感じに型再構築が必要。

メモ: 評価用の問題のリスト

• https://atcoder.jp/contests/abc127/tasks/abc127_e
• https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_e
• https://atcoder.jp/contests/code-festival-2015-final-open/tasks/codefestival_2015_final_d

テストの coverage を上げる

どこかで機会を取って coverage を上げておきたい

`print(*ans)` と書けるようにする

Allow C++ as an input language

• C++ の構文解析をする
• core への変換を書く

出力される C++ から fmap や scanl を消去する

core -> C++ の変換時に ad-hoc をやるのがよさそう

FFT

REP (i, n) REP (j, n) c[i + j] += a[i] * b[j] があったら c = fft(a, b) にするやつ

• core 言語に新しい組み込み関数 FFT InverseFFT みたいなやつを足す (あるいは Convolution という組み込み関数を足す？) (Jikka.Core.Language.Expr)
  • それらが $ jikka execute ... で実行できるようにする (Jikka.Core.Execute)
  • それらが C++ に変換されるようにする (Jikka.CPlusPlus.Convert.FromCore)
  • 必要なら runtime/include/jikka/convoluion.hpp を足して実装する
  • それらが C++ で使われていたら自動で #include "jikka/convolution.hpp" とか #include <atcoder/convolution> されるようにする (Jikka.CPlusPlus.Format)
  • その他必要なもろもろをやる (コンパイルエラーや警告が出なくなれば OK)
• core 言語に、foldl (fun c i -> foldl (fun c j -> setAt c (i + j) a[i] b[j]) c (range n)) c (range n) やあるいはこれと等価な部分式があれば、それを FFT を使って書き直すような rewrite rule を足す (Jikka.Core.Convert.FFT みたいなのを足して Jikka.Core.Convert の中から呼び出す)

Report the time complexity

テストにも使えるのであるとよい
再帰があると見積り不可能だけど、どうしよう

quasi quote についてのドキュメントを足す

#133 で quasi quote を使って簡単に rewrite rule が書ける仕組みを追加したけど、これについてのドキュメントを書いておく必要がある

表層 Python に足した追加の builtin 関数を別の名前空間内に移す

• fact とか choose とかは jikka.fact や jikka.choose に rename してしまっていいと思う
• ceildiv とか ceilmod とかも global で ceildiv = jikka.ceildiv ってやってもらえばよいはず

assert を core や C++ で利用する

assert n == len(a) を利用して map(lambda i: a[i], range(n)) を a に変換するなどしたい
いまは restricted Python → core の変換時に無視してしまってる

Use affine types internally

C++ には計算量を考えたときに contraction が可能な型と不可能な型とがある。たとえば vector<int> xs; のとき vector<int> ys = xs; ys.push_back(1); return f(ys, ys); なら move を使って O(1) だが、vector<int> ys = xs; ys.push_back(1); return f(xs, ys); ならば copy になって O(n) である。
この区別を中間言語あるいは Python の上でも持ちたい。contraction 不可能な型についての contraction を検出してエラーにし、そのような contraction をする rewrite rules を禁止して防ぎたい。

このために affine 型を利用したい。
依存型などは悪手だと考えているが、affine 型や線形型なら分かりやすいのでありだと思う。Rust での実績もある。

rewrite rule をもっと簡単に書けるようにする

GHC の RULES pragma みたいに手軽に書きたい

{-# RULES
  "map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs
    #-}

Template Haskell を使って準クオートで書けるようにするのがよい気がする

mapMapReduce :: Monad m => RewriteRule m
mapMapReduce = [rule| "map/map"  forall f g xs.  map f (map g xs) = map (f.g) xs |]

Python での list 操作の可能な範囲を広げる

xs.count() とか xs.append(x) とかを書きたい。現在は Python パーサが method 呼び出しに対応していないので、そこから初める必要がある

Refactoring for v5.0.2.0

とりあえず動かすことを優先で書いたものが v5.0.1.0 ですが、この上にものを積むには汚すぎてしんどいので仕様の再検討と実装の書き直しが必要そう。

• 本物の Python をそのままパースできるようにする
  • 構文解析だけなら簡単だということが分かってきたので
• Python のサブセット言語の仕様を修正し簡単化する
  • 「非負である」「要素数は n である」みたいな情報を無理矢理に型システムに押し込む利点はあまりない気がしてきたので
• できるだけ広い範囲の AST により詳細な位置情報を乗せる
  • エラー報告は実用上かなり重要だし後から付け加えるのはしんどいので早めにやるべき
• 一貫性のあるエラー処理機構を用意する
  • Either String a で頑張っているが、つらい
• rewrite rules を簡単に定義できる DSL を用意する
  • 現状では、記述が面倒。しかも AST に対する型検査は走らないのでバグが埋まりやすい
• modules の構造を転置する
  • Jikka.Converter.Core を Jikka.Core.Converter にするなど

convex hull trick をする

`Jikka.Core.Convert.*` の modules にドキュメントが足りてないので書く

他は多少は省略していいとしても、Jikka.Core.Convert の中は手厚く書いておいた方がよい

C++ コードの最適化をする

不要な copy がたくさん挟まるせいで計算量が上がってしまっている

具体的には core の SetAt 関数がやばい。現在は Jikka.CPlusPlus.Convert.FromCore で core から C++ への変換と諸々の inlining を同時に雑にやってしまっているが、できるだけ多くの情報を残したまま C++ に変換してさらにそこでもう一度いくらかの最適化をかけるようにする必要がありそう。「この変数が参照されるのはここが最後だから move してしまってよい」みたいなのを判断して最適化に使ったりしたい。

Knuth-Yao speedup

Knuth-Yao speedup - 週刊 spaghetti_source - TopCoder部

Monge 性の機械判定ってどうすればいいですか？ HELP!

標準 Python と非互換な書き方をしていたらコンパイルエラーにする

• lambda 式の中で参照されている変数を書き換えるやつ
• 関数の引数として受けとったリストを書き換えるやつ

現状だと以下はすべて正しく動かない。そもそもそんな書き方をするのが悪いので、コンパイル時にエラーにしてしまいたい

c = 0
f = lambda x: x + c
c = 1
f(0) # => 1

f = lambda x: x + 1
f = lambda x: f(f(x))
f(0) # => 停止しない

def f(xs):
    xs.append(0)
xs = []
f(xs)
xs # => [0]

Hackage への upload

アカウントの activation はしてもらった

• メールで教えてもらった箇所 (依存に bounds を足す + .cabal は checkin した方がいい) を直す
• upload する
• 追加: GitHub Actions から upload する

変な型の比較をコンパイルエラーにする

現状だとたとえば以下のようなコードが書けてしまう。そして奥の方で分かりにくいエラーになるはず。これをちゃんと明示的に検出して分かりやすいエラーとして報告するようにしたい。

(lambda x: abs(x)) == (lambda y: y + 3)
(lambda x: abs(x)) < (lambda y: y + 3)
min(lambda x: abs(x)), (lambda y: y + 3))

Erase if-exprs in loops

邪魔なので消去したいのだけど、一般的な方法で消去するのが難しすぎて困っています。
ad-hoc に処理することはできるけどしんどいし役立つのか不明だしなのでできれば避けたい。

やること:

1. 追加の具体例を収集する
2. いい感じの方法を考える

例 1

# https://atcoder.jp/contests/abc127/tasks/abc127_e

MOD: int = 10 ** 9 + 7

def solve(h: int, w: int, k: int) -> int:
    ans = 0
    for y1 in range(h):
        for x1 in range(w):
            for y2 in range(h):
                for x2 in range(w):
                    if (y1, x1) < (y2, x2):
                        ans += choose(h * w - 2, k - 2) * (abs(y2 - y1) + abs(x2 - x1))
    return ans % MOD

例 2

# https://atcoder.jp/contests/abc134/tasks/abc134_c
from typing import *

def solve(N: int, A: List[int]) -> List[int]:
    assert 2 <= N <= 200000
    assert len(A) == N
    assert all(0 <= A_i <= 200000 for A_i in A)

    ans = [-1 for _ in range(N)]
    for i in range(N):
        ans[i] = max((0 if j == i else A[j]) for j in range(N))
    return ans

等式を解くことを試みる

• 一般
  • 構文木として a と b が等しいなら a == b を true にする
• 整数について
  • 右辺を 0 にする。つまり a == b を a - b == 0 にする
    • 両辺に分かれていたものがひとつの式になれば、別の最適化器 Jikka.Core.Convert.ArithmeticalExpr が頑張ってくれます
  • 組み込み関数 f であって単射なものについて f(a) - f(b) == 0 を a - b == 0 にする
• リストについて
  • nil == cons(x, xs) を false に
  • cons(x, xs) == cons(y, ys) を x == y && xs == ys に展開する
• 真偽値について
  • a == true を a に
  • a == false を not a に

Convert recursions to loops

再帰よりループの方が最適化しやすいのでほしい。

末尾再帰最適化というよりも停止性自動証明をやることになる。
ad-hoc に induction measure (つまり DP table の埋める順番) を総当たりして潰すことになりそう。

例

たとえば

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

が

def fact(n):
    dp = [-1 for _ in range(n + 1)]
    dp[0] = 1
    for i in range(n):
        dp[n + 1] = (n + 1) * dp[n]
    return dp[n]

になってほしい。

Dual Segment Tree

segment tree を貼る

累積和を取ってある箇所を検出して、その累積和に対する更新が発生しているなら大域的に segment tree に書き換える、とかがよいかと思われる

epsilon calculus

メモ: 哲学について

方向付けのために胡乱なことを書いていたが、人目に付くところに置いておいても混乱を招くだけでよくなさそうなので消した。しかし重要なものでもあると考えているので、 Issue として残しておく。
4d6e5c3

Slope Trick

slope trick の C++ 実装であってライセンスがはっきりしたもの (Apache 2.0 あるいはできれば CC0) を探しています。持ってる人がいればください

CI が頻繁に失敗するのでなんとかする

time limit 20 sec を使い切って落ちるのは何かがよくない。Ubuntu だと安定して通っていて特に macOS で遅い。詳しい理由は不明

やること

言語機能

• liquid types を実装
  • 添字の境界検査とかを自動でしたいと思うとこの手のものは避けられなさそう
  • #2 を参照
• 実装を進めて機能不足を埋める
• 最適化の際に使いやすい構文木を設計する
• Haskell 系の文法の方が数式ぽくてよさそうなので修正する
  • 現在は型システムの資料の多さのために一度ML に戻してある状態

最適化

• 最適化のルールを追加しやすいような枠組みを作る
• 定数畳み込みや式変形などの実装を進める
• データ構造を貼るやつを実装
• 再帰的定義を分析してループに直したり依存関係を判断したりするやつを実装
• 普段の精進の中で「あー こういう考察は機械的にできそうだなあ」みたいなやつを見つけて集める

出力

• C++ のものの実装を進める
• 計算量解析をする
  • 補助として使うなら「ここをこう変えると計算量どうなる？」みたいな質問ができるとうれしいはず
  • C++ から ML への変換器と併わせて、エディタのプラグインにして常に現在のコードの計算量が表示されるようになったらうれしい

周辺ツール

• C++ から ML 形式への変換器を書く
  • エンドユーザは C++ しか書けないだろうのであるとよい
• 入出力パートの自動生成をする
  • kyuridenamida/atcoder-tools や過去の kmyk/online-judge-tools がやってるやつ + 出力部分
  • 解法生成にこれが加わるとそのまま提出できるコードになるのでうれしい
  • kyuridenamida/atcoder-tools に機能をうまく切り出して整理してもらうのがよさそう
• (自然言語の問題文を形式言語に落とす変換器を書く)
  • これは完全に別プロジェクトぽいけどいつかはできてほしい

QuickCheck を導入する

property-based なテストを足したい

生成される C++ で値のコピーを減らして参照を使う

int func(const std::vector<int> &a) { return [=]() { return a[0]; }(); } ってやったときに O(n) になってそう。だめ

標準 Python をテストに使う

def main があったら標準 Python に食わせて入出力を確認するのがよい

list.append や list.extend を使えるようにする

副作用を伴なうので厄介

stack build fails on macOS because of cabal's bug

Summary

The same with haskell/cabal#4739

Steps to reproduce

Just execute the following on the environment mentioned below

stack build

environments:

$ stack --version
Version 2.7.1, Git revision 8afe0c2932716b0441cf4440d6942c59568b6b19 x86_64 hpack-0.34.4

macOS Catalina Version 10.15.5

Expected behavior

build succeeds

Actual behavior

$ stack build
Jikka> configure (lib + exe)
Configuring Jikka-5.0.5.0...
Jikka> build (lib + exe)
Preprocessing library for Jikka-5.0.5.0..
Building library for Jikka-5.0.5.0..
Preprocessing executable 'jikka' for Jikka-5.0.5.0..
Building executable 'jikka' for Jikka-5.0.5.0..

/Users/koki/programming/others/Jikka/<built-in>:15:10: error:
     error: non-portable path to file '".stack-work/dist/x86_64-osx/Cabal-3.2.1.0/build/Jikka/autogen/cabal_macros.h"'; specified path differs in case from file name on disk [-Werror,-Wnonportable-include-path]
#include ".stack-work/dist/x86_64-osx/Cabal-3.2.1.0/build/jikka/autogen/cabal_macros.h"
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         ".stack-work/dist/x86_64-osx/Cabal-3.2.1.0/build/Jikka/autogen/cabal_macros.h"
1 error generated.

/Users/koki/programming/others/Jikka/.stack-work/dist/x86_64-osx/Cabal-3.2.1.0/build/jikka/autogen/Paths_Jikka.hs:1:1: error:
    `gcc' failed in phase `C pre-processor'. (Exit code: 1)
  |
1 | {-# LANGUAGE CPP #-}
  | ^


--  While building package Jikka-5.0.5.0 (scroll up to its section to see the error) using:
      /Users/koki/.stack/setup-exe-cache/x86_64-osx/Cabal-simple_mPHDZzAJ_3.2.1.0_ghc-8.10.4 --builddir=.stack-work/dist/x86_64-osx/Cabal-3.2.1.0 build lib:Jikka exe:jikka --ghc-options " -fdiagnostics-color=always"
    Process exited with code: ExitFailure 1

TODO: 配布について

https://github.com/cannorin/FsCalc/blob/d6b0513f3c7c181a2051ca4497044387355ae4fb/FsCalc.fsproj#L6-L18 このようにえいっと書くと $ dotnet tool -g install hogehoge [--add-source <custom-nuget-repo-url>] のようにインストールできて $ hogehoge で実行できるようになってよい

添字の中の演算子に無駄な括弧が付いてる

h_1[(i3 + 1)] でなくて h3[i3 + 1] ってなっててほしい

現状:

          std::min<int64_t>(
              x2[i3][1] + std::max<int64_t>(-h_1[(i3 + 1)] + h_1[(i3 + 2)],
                                            h_1[(i3 + 1)] - h_1[(i3 + 2)]),
              x2[i3][0] + std::max<int64_t>(-h_1[i3] + h_1[(i3 + 2)],
                                            h_1[i3] - h_1[(i3 + 2)]))};

配るもらう変換

配る DP ともらう DP とを相互に変換する処理を書く。優先順位が高いのは配る形からもらう形へだけど、逆向きもあるとよい。普通のセグ木とか CHT とかだともらう形がうれしくて、双対セグ木だと配る形がうれしいので

同種の let があればまとめる

Description / 説明

もし

let x = e(...)
in let y = e(...)
in f(x, y)

があったら

let x = e(...)
in f(x, x)

にする

Motivation / 動機

定数倍しか変わらないけど、違うループの中で別々に作られた同じ累積和とかはまとめたい

for i in range(n):
   ans += sum(a[:i])
for i in range(n):
   ans += sum(a[:i])

機械的に解けそうな問題を収集する

集めています。テストに使います。見つけたら教えてください。可能なら Python の愚直解やテストケースをプルリクしてくれるとよりうれしいです。

---

• 自動で解けたらチェックを入れていきたい

core の if 関数の扱いを明確にする

if(a, b, c) って書いたときに正格評価するのか遅延評価するのかが曖昧なのでよくない

data Builtin から data Type への依存をなくす

GHC Core みたいに「型は項」をして高階型を足すのがよい

Binary Indexed Tree (Fenwick Tree)

Currently we always use segment trees, but we replace them with binary indexed trees if possible because they have a little bit smaller constant-time factor.

四則演算などの式を整理する

-1 + a + b - a + 2 が b + 1 になってほしい
Jikka.Core.Language.ArithmeticalExpr をするだけなのだけど、局所的な書き換えでは済まないから rewrite rule には落ちなさそう

設計について

現状 (v3.1.0)

1. ML 風言語の構文解析をする
   • lex + yacc で教科書通りにやった
2. 構文木を変形し最適化をする
   • 定数畳み込み (x + 0 → x とか if true then x else y → x とか)
   • 大型演算子の分配 (sum (fun i -> A i + B i) → sum (fun i -> A i) + sum (fun j -> B j) とか)
   • 大型演算子の消去 (max l r (fun i -> A i) で l が定数のときに累積和に書き直すとか)
     • このとき toplevel に新しい関数を追加することも
3. C++ に変換する
   • C++ は高級言語なのでいい感じにやるとできる

`xs = xs + [x]` などとも書けるようにする

xs.append(x) だけでなく xs += [x] や xs = xs + [x] とも書けるようにしたい。特に xs = xs + [x] は参照を破壊しないので互換性のために重要

Segment Trees with Lazy Propagation