ふるつき

私は素直に思ったことを書いてるけど、上から目線だって言われる

プログラミング言語を作りました

元記事

のばなしうさぎ

このように、お友達のいらいざくんが「cottonなる言語を作ったよ〜見て〜」と言って自慢してきて、「すげーーっ!!」となったので、これは負けていられないと思い、 silk というプログラミング言語を作りました。

GitHub - theoldmoon0602/silk

僕も勉強がてら Haskell + LLVM で処理系書いてみるか、と思っていたですが、 cotton のソースを見たところ、レキサもパーサもまるで読めなかったので心折られて、OCaml + LLVM で書くことにしました。 silk 自体の目標としては、 cotton の追従です。 残念ながら全く同じというわけではないのですが。

ところで silk の何よりイケイケなポイントはその小ささで、試しに cat *ml* | wc -l としたら 284 と出ました。いろんなものを省いた結果ですね。

ざっくりした処理の流れ

  • Tokenize
  • Parse
  • α変換
  • 型検査
  • K正規化
  • Closure変換
  • LLVM IR 生成

以上です、 cotton はLLVM builderを使わずに手でIRを吐いていたようですが、ちゃんと cotton のソースコードを読まなかったので、 silk では LLVMOCaml バインドを利用しています。なので多分速度には問題がないです。

データ型はInt32しかない上に関数はオブジェクトとして認めていないので型の概念が今は必要ないので型検査がありません。α変換とか Closure変換とかは必要になったら入れようと思っていたのですが気がついたら cotton と同じところまでは動いたのでまだありません。*1

LLVMは初めて触りましたが関数のインターフェースが勉強になります。どの関数がどんな役割の値を返すのか、といったことはコード生成を自分で書こうとしたらいくらでも悩めるところだったと思うので。一方で、 llbuilder 型の扱いはちょっと気に食わない感じがします。多分これ引数が変更されてますよね?*2 違いますかね。違ったらまるでわからん。

LLVMに任せるとメモリレジスタの管理が不要になるのは本当に偉大ですね。

使ったライブラリとか

いらいざが Lexer とか Parser Generatorを使っていたのでこちらも定番の ocamllex menhir 体制で望みました。レキサパーサを書かなくて良くなるだけでものすごく開発が楽になりますね。

ビルドは OMake を使っていましたが、作業環境その2でいくら menhir を入れてもないと怒られる事案が発生して、回避のために build.sh というファイルに ocamlbuild を用いたビルドスクリプトも書きました。

みていたものとか

どんな構文にするかは cotton ベースで決めていました。LLVM まわりは

https://llvm.moe/ocaml/Llvm.html

Blox/codegen.ml at master · sgtb3/Blox · GitHub

cminus/codegen.ml at master · douggard/cminus · GitHub

を引っ張ってきたりです。なんでこいつら関数の引数に func なんてものがあるんだろうと思っていたのですが、 append_block の引数に必要だったんですよね、なんでこんなことになってるんだろうというのはよくわからないまま、 silk でも eval_exp の引数には func がいます。

おわりに

cotton が更新されたら silk も更新していきたいと思っています。OCaml way も LLVM way もまるで知らないのでもう少し綺麗に書きたいとも思っています。

モチベーションを与えてくれたいらいざと cotton に感謝を込めて。

*1:このあたりってLLVMがやってくれているということなんですか、それともこの程度のプログラムならひつようないということですか

*2:OCamlってそういうことできましたっけ?

20歳になった

 こういう記事を書いてる人がいたら僕は「ほーん」と思ってそのブログを閉じそうなものです。先駆者がいて僕も自分語りをしたくなったので書きます。

yamasy1549.hateblo.jp

 成仏したくねぇなぁ……。成人もしたくない。死が怖い。不死になりたい。

#1 直近の進路

 奈良工業高等専門学校専攻科システム創生工学専攻情報システムコース に推薦合格しました。名称に間違いがあるかも知んないけどこんな名前です。というわけでもう二年、高専ボーナスステージをやります。

 専攻科には行きたかったどころか行きたくなかったくらい(とっても折り合えない教員がいるのが良くないのと、高専では視野が狭すぎると感じてるのと、女の子が存在しうる環境に行きたい)なのですが、第一志望は少し前まで 筑波大学 情報学群 情報科学類 だったくらいなのですが、少しだけ(半月程度)受験勉強なるものをやった結果、完全に心を折られたので、受験勉強の必要がない、推薦で合格できる、(学費が安い、比較的近いので家をでなくて済む)などの理由から専攻科を選択しました。

 受験勉強に心折られたのはそれが難しかったからというわけではなく(確かに難しかったが)、それに取り組む人々が例えば一日に六時間やそれ以上の時間を費やしていて、「ああ、僕にはそれはできない」ということを悟ったということです。数学の問題を解くのは楽しいと感じることがありますが、それもせいぜい1時間までです。受験勉強に取り組んでいる各位にはその努力が実ることを祈念するばかりです。

 高専の残された一年と専攻科の二年間での研究は「型デバッガ」をやっていきたいという気持ちがあります。言語の処理系には大変興味があるので触ることができれば重畳と思っています。私の所属研究室は「サイバーセキュリティ研究室」なる称号も持っているので、なにかしらこじつけて、セキュリティ周りにも手を出していけたらな、と。こんなものは予定ですらなくて空想の域ですが。

 余談ですが、研究室に配属されてまだ一ヶ月と半分程度の、論文もまともに読めない学生に対して面接で研究内容を詰めていくのはどうかと思います。というよりも研究室への配属がおそすぎるのがどうかと思います。受け身だからだめなんですね。

1.5 直近以降の進路

 また余談ですが、この n.5 という表記、ラノベの外伝でよく見ますが 普通のナンバリングで出してくれても良いんだよと思いますね。

 無事専攻科を卒業したあとのことは考えていません。高専本科を卒業したあと就職の道を選ばなかったのは、これまでお世話になってきたインターンやらで私の力不足を実感し、「このままでは戦えない、あと数年力を溜めておきたい」と思ったからですが、果たして専攻科を卒業したときに今の自分よりも優れた自分になっているのか、大いに不安があります。

 この記事

lacolaco.hatenablog.com

にも影響を受けました。たとえば私が専攻科にすすまずにどこかIT系の企業に就職できたとして、その場合やはり私もこうやって不安を抱えることになるのだと思います(それはそれとしてこの記事書いてるような、活躍活躍の方でもこのように不安を抱えるのだったら何に希望を持てばよいのか)

 何も考えなければ、親に負担を強いて、NAISTなどに進めるのかもしれません(弊学専攻科はNAISTへの進学に有利という話を聞かないでもないので)。しかしそれになんの意味があるのか、情報工学徒だから修士くらいは、という動機で進んだ先で何を得られるのかと考えると今から憂鬱です。なによりこれ以上受験や就職のための活動を増やしたくない。

 そんな感じで進路に悩んでいます。

#2 19歳のときにやったこと

 何もやってないですが……?

  • エスペラントに触れ始めた

    • エスペラントを扱った「ことのはアムリラート」なるゲームがある!→色モノに違いないしやってみよう
    • としたら「百合じゃん! 買い!」としていたクラスメートがいてちょくちょくエスペラントをやっていた
    • 大阪でエスペラント大会が開かれ学力検定もあるからやろうぜ、と言われ、勉強をした
    • この間、3級と4級を受けてきました。合否がわからないのでドキドキ(落ちてる)
  • インターン

  • セキュリティキャンプ

    • 応募したら通る御旗のもとに応募したら通った
    • 貴重な経験をさせてもらえたのは良かったけど、せっかくの機会を棒に振ったような後味が残っていて後悔しています。
  • シェル芸bot

    • https://twitter.com/minyoruminyon/
    • なんで作ったのか忘れたけど作りました
    • 最近フォロワー数を抜かれた
    • よろしくお願いします
    • でも多分 Streaming API の死とともに死にます
  • SECCON 高専プロコン

    • 略。成果でないし

 お前ラストティーンがこれでええんか

#3 20歳がんばりたいこと

 もう頑張るって言葉に疲れてしまいましたが……?

  • 身体を動かす

    • 本当に身体を動かす機会がなくなってしまって、背中やら顎やらに謎のふゆふゆしたものが憑依しています。楽しく運動できる機会をください。
  • 身だしなみに気を使う

    • 無理では……?
    • 興味がないんですが、女の子と接点を作るには普通レベルの見た目を作っていかないとだめだと思っているので
  • 教養を身につける

    • 本を読む、ということです。漫画でもラノベでも、とにかく読む。
    • おすすめを教えてください。唐突に https://twitter.com/theoldmoon0602 にリプライを送りつけてくれるのがよいですね。
    • 本を買うために稼ぎます。
  • kosen14s の人たちと云々

    • 一体何をすればいいんでしょうね。
    • kosen14s は 2014 年度入学というそれだけの絆で成り立っているごらく部です。2014年度に高専/高校に入学したという方と楽しくおしゃべりしたい。

 もう少し若さが欲しいですね。

#4 いつもの

 いつものではない。ほしいものリストに入ってないものも貰えらたら嬉しいですね。言語処理系周りの本を手元に置いておきたい。

http://amzn.asia/3ONSFHk

 おすすめのお酒を教えていただけるとお金に余裕があるときに飲みたいです。呑兵衛になるつもりはないけどお酒は楽しそう。

bairstow法に負けないで

 今日は数値計算法の授業があったのだが、そこで bairstow 法なる手法が紹介された。これは多項式の解を複素数解まで含めてすべて近似的に求めることができる手法である。授業では「多項式を二次式で因数分解していく」「ニュートン法でいい感じにすると二次式の係数が求まる」ということを述べたのみで、後は写経の時間になった。

 なるほど写経は概念を習得していない場合に有効だと思うけど私は概念を習得して自分で考えてプログラムを書きたかったので頭をひねったのだけど理解できなかった。プログラム系の授業で敗北したのは初めてだと思う。ちっぽけなプライドに傷をつけられたまま引き下がることはできないのできちんと理解してやる。


 まず、対象にするのは n次の多項式だ。これの解をすべて求めることを目標にする。

 a_nx^{n}+a_{n-1}x^{n-1}+...+a_1x+a_0 = 0 \tag{1}

 この式(1) を適当な係数を持つ二次式  x^{2} + px + q で割るとこうなる。

 (b_{n-2}x^{n-2} + b_{n-3}x^{n-3} + ... + b_1x + b_0) (x^{2} + px + q)  +  (\alpha x + \beta) = 0 \tag{2}

こうすると  x^{2} + px + q の解は解の公式から求められる。n-2次の多項式は同じように2次ずつ次元を減らしていけば解けることになる、というのが bairstow 法のコンセプトだ。

ここで問題にするのは2つだ。一つは、どのような p, q を選べば余り( \alpha x + \beta )がないように割れるかということ。もう一つは、商の項の係数  b_{n-2}, b_{n-1}, ... の値は何になるのかということ。

2つめの問題はかんたんなので先に取り組むことにする。 式(1)、(2) で 各項の係数を比較すれば良い。例えば、(2) 式中で n-2 次の項は   (b_{n-2}q + b_{n-3}p + b_{n-4}) x^{n-2} である。これが、(1)式中での n-2次の項  a_{n-2}x^{n-2} と恒に等しいので、

 b_{n-4} = a_{n-2} - b_{n-3}p - b_{n-2}q

を導ける。添字を修正して

 b_{i} = a_{i+2} - b_{i+1}p - b_{i+2}q \tag{3}

である。p, q がわかれば係数列 b を次数の高い方から求めることができる。ただし、 b_{n} = b_{n-1} = 0 としておく。

続いて、余りを0にするためには何がどうなればよいかを考える。先程のように (1)、 (2) 式からなる恒等式を見れば、  (\alpha + b_0p + b_1q)x = a_1x であり、  \beta + b_0q = a_0である。(3) を用いて

 \alpha = b_{-1} = a_1 - b_0p - b_1q \tag{4}

 \beta =b_{-2} + b_{-1}p  =b_{-2} + b_{-1}p + b_{0}q - b_{0}q = a_0 - b_0q \tag{5}

を得る。 \alpha, \beta を 係数列bの項とp, qを使って表すことができた。係数列bの値も p, qが決まれば決まるので、  \alpha, \beta は二変数 p, q で決まる値である。 \alpha, \beta をそれぞれ0にするような p, qの値を、多変数のニュートン法によって求める。


ニュートン法

少々脱線するがニュートン法についても解説しておく。ニュートン法多項式の解の近似値を一つ求める手法である。

原理は省略するが、手法としては

 f(x) = a_{n}x^{n} + a_{n-1}x^{n-1}  + ... + a_{0} = 0

の解 x' を求めるときには、

 x'_{n} = x'_{n-1} - \frac{f(x'_{n-1})}{df(x'_{n-1})}

とする。nが大きいほど解としての精度はあがる。ちなみに  x'_{0} の値は適当に決めておく。この値によっては異なる解が得られることがある。

二変数のニュートン法

二変数のニュートン法では  f(x,y) = 0, g(x, y) = 0 を満たすような x, y を探す。

これについても原理を省いて手法のみ説明する。偏導関数  f_{x}, f_{y}, g_{x}, g_{y}が求まっていて、適当な  x'_{n}, y'_{n} があるとき、

 x'_{n+1} = x'_{n} -  \frac{fg_{y} - f_{y}g}{f_{x}g_{y} - f_{y}g_{x}}

 y'_{n+1} = y'_{n} -  \frac{f_{x}g - fg_{x}}{f_{x}g_{y} - f_{y}g_{x}}

とする。*1


以上が bairstow 法の理論である。理論がわかったので実装を行う。実装の方針は次の通り

  1. 数値微分を実装する
  2. 二変数のニュートン法を実装する
  3. 二次方程式の解の公式を実装する
  4. bairstow 法を実装する( b_{i}, \alpha, \beta を求める関数を実装してニュートン方にかける )

数値微分の実装

数値微分は、二変数のニュートン法において、偏微分係数を求めるために必要となる。実装は微分の定義式に従えば良い。

 \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}

ただし実装にはより精度の良い三点差分による近似を用いた。導出は面倒そうなので省略するが直感的な理解があるので使って良いことにした。

 \lim_{h \to 0} \frac{f(x + h) - f(x - h) }{2h}

D言語による実装ではこうなる。

auto differential(F)(F f, double h = float.epsilon)
{
    return (double x) {
        return (f(x + h) - f(x - h)) / (h * 2);
    };
}

ここで 変数 hの値を小さくしすぎる( double.epsilon など)と失敗する。細かい理由は追いかけていないがそうなりそうということはわかっているので良いことにした。

二変数のニュートン法の実装

二変数のニュートンはそのまま実装する。関数名が気に食わないのでよりよい名前をご存知という方はお知らせ下さい。

import std.typecons;
Tuple!(double, double) newton2(F)(F f, F g, double x, double y, double epsilon=float.epsilon)
{
  import std.math;

  while (true) {
    auto f_x = differential((double x) => f(x, y));
    auto f_y = differential((double y) => f(x, y));
    auto g_x = differential((double x) => g(x, y));
    auto g_y = differential((double y) => g(x, y));

    auto d = f_x(x) * g_y(y) - f_y(y) * g_x(x);
    auto dx = (f(x, y) * g_y(y) - f_y(y) * g(x, y)) / d;
    auto dy = (f_x(x) * g(x, y) - f(x, y) * g_x(x)) / d;

    x = x - dx;
    y = y - dy;
    if (abs(dx) <= epsilon && abs(dy) <= epsilon) {
      break;
    }
  }

  return tuple(x, y);
}

先程定義した微分関数 differential を用いて偏導関数を導いている。 二変数の偏導関数の定義を書いておくと

 \lim_{h \to 0} \frac{f(x + h, y) - f(x, y)}{h}

である*2

二次方程式の解の公式を実装する

やるだけ。これについても良い名前をご存じの方はお知らせ下さい。

import std.complex;

/// solve ax^2 + bx + c = 0
Complex!double[] solve2d(double a, double b, double c)
{
  import std.math;

  auto d = b * b - 4 * a * c; 
  if (d > 0) {
    auto ans1 = (-b + sqrt(d)) / (2*a);
    auto ans2 = (-b - sqrt(d)) / (2*a);
    return [complex(ans1), complex(ans2)];
  }
  else if (d == 0) {
    auto ans = (-b + sqrt(d)) / (2 * a);
    return [complex(ans)];
  }
  else {
    auto ans1 = complex(-b, sqrt(-d)) / (2 * a); 
    auto ans2 = ans1;
    ans2.im = -ans2.im;
    return [ans1, ans2];
  }
}

bairstow法を実装する

実装はこうなる。

import std.complex;
Complex!double[] bairstow(double[] as, double epsilon = float.epsilon)
  in {
    assert(as.length > 1);
  }
do
{
  import std.range;
  import std.typecons : tuple, Tuple;
  import std.meta : AliasSeq;

  auto n = as.length;
  if (n == 2) {
    return [complex(-as[0]/ as[1])];
  }
  if (n == 3) {
    return solve2d(as[2], as[1], as[0]);
  }


  alias memo_key = Tuple!(ulong, double, double);
  double[memo_key] memo;

  double b_i(ulong i, double p, double q) {
    auto key = tuple(i, p, q);
    if (key in memo) { return memo[key]; }
    if (i >= n - 2) { return 0; }
    auto r = as[i+2] - b_i(i+1, p, q) * p - b_i(i+2, p, q) * q;
    memo[key] = r;
    return r;
  }

  auto alpha = (double p, double q) {
    return as[1] - b_i(0, p, q) * p - b_i(1, p, q) * q;
  };
  auto beta = (double p, double q) {
    return as[0] - b_i(0, p, q) * q;
  };


  double p = 1.0, q = 1.0;
  AliasSeq!(p, q) = newton2(alpha, beta, p, q);
  double[] bs = new double[](n-2);
  foreach (i; 0..n-2) {
    bs[i] = b_i(i, p, q);
  } 

  return solve2d(1, p, q) ~ bairstow(bs, epsilon);
}

以下、各部分に分解して解説をはさむ。

一次式、二次式が渡されたときはそれぞれそのまま解を返している。

  auto n = as.length;
  if (n == 2) {
    return [complex(-as[0]/ as[1])];
  }
  if (n == 3) {
    return solve2d(as[2], as[1], as[0]);
  }

係数列 b の各係数を求める関数は以下のとおりである。

  alias memo_key = Tuple!(ulong, double, double);
  double[memo_key] memo;

  double b_i(ulong i, double p, double q) {
    auto key = tuple(i, p, q);
    if (key in memo) { return memo[key]; }
    if (i >= n - 2) { return 0; }
    auto r = as[i+2] - b_i(i+1, p, q) * p - b_i(i+2, p, q) * q;
    memo[key] = r;
    return r;
  }

ニュートン法の中で、何度も呼ばれることになるため、メモ化を行っている。値を求める方法は愚直に (3) 式に従っている。

alpha, beta は b_i を用いて愚直に計算すれば良い。

  auto alpha = (double p, double q) {
    return as[1] - b_i(0, p, q) * p - b_i(1, p, q) * q;
  };
  auto beta = (double p, double q) {
    return as[0] - b_i(0, p, q) * q;
  };

こうして得られた alpha, beta をそれぞれ 0にするような p, qをニュートン法を用いて探索する。その後、  x^{2} + px + q = 0 の解を求め、残りの式を再度 bairstow 法で解くことで解を得る。

  double p = 1.0, q = 1.0;
  AliasSeq!(p, q) = newton2(alpha, beta, p, q);

  double[] bs = new double[](n-2);
  foreach (i; 0..n-2) {
    bs[i] = b_i(i, p, q);
  } 

  return solve2d(1, p, q) ~ bairstow(bs, epsilon);

動作例

試しに適当な多項式を解いてみる。ここでは授業中に課題として出された  x^{4} - 3x + 1 = 0 を解く*3

void main()
{
  writeln(bairstow([1, -3, 0, 0, 1]));
}

実行結果は次の通り

[-0.822576+1.26032i, -0.822576-1.26032i, 1.30749+0i, 0.337667+0i]

Wolfram Alpha に解かせてみると Real Solutions として x = 0.33767, x = 1.3075 、 Complex Solutionsとして x = -0.8226 +- 1.2603i を出してきたので多分正しい。

どうか、人々が bairstow 法に負けないように。

間違いを見つけたら教えてください。

*1:本当かどうか大変怪しい

*2:本当かどうか大変怪しい

*3:2件ほど指摘を受けてわかりにくいようだったので補足。プログラム中では次数が低いほど添え字が小さく、次数が高いほど添え字が大きくなっているので注意。数式とは逆順に書くことになるが、こちらのほうが自然に感じた

私もAtCoderに登録したら解くべき精選過去問10問をD言語で解いた

私は時々D言語AtCoderの問題を解くことがあるので(rating 958のざこざこですが)

qiita.com

D言語でやってみました。 D言語は超絶人気バリバリメジャー言語なので当然先駆者がいます。

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた - よすぽの日記

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた - D言語の構文と標準ライブラリを使い倒す編 - 矮小

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた

D言語では構文や標準ライブラリの選択肢が広く、同じ問題を説いていてもまるで異なったプログラムが生まれます。ちゃんと読んでないけど↑の場合でもそうです。私も別のプログラムになる場合があったので書いておきます。

PracticeA はじめてのあっとこーだー(Welcome to AtCoder

import std.stdio, std.conv, std.string;


void main()
{
    long a,b,c;
    string s;
    readf("%d\n%d %d\n", &a, &b, &c);
    s = readln.chomp;
    writefln("%d %s", a+b+c, s);
}

D言語競技プログラミングをやるなら入力は readlnreadf で受け取ることになりそうです。 readf が割と罠で 手元では readf("%d\n%d %d\n", a, b, c); と書いて動いていたのでずっとこの書き方をしていたのですが、AtCoder上ではこれに Warning がでて CE となります。

このときは chomp で改行文字を落としていますが途中で strip 関数のことを思い出したのでそっちを使うようになります。

ABC086A Product

import std.stdio, std.conv, std.string;


void main()
{
        long a, b;
        readf("%d %d\n", &a, &b);
        if (a*b % 2 == 0) {
                writeln("Even");
        }
        else {
                writeln("Odd");
        }
}

はい

ABC081A Placing Marbles

import std.stdio, std.conv, std.algorithm, std.string;


void main(){
        auto s = readln.chomp;
        writeln(s.count('1'));
}

algorithm に入っている count 関数は便利です。大体何でも数えられます。カウントの条件はデフォルトでは a==b で行われていますが、テンプレート引数を書き換えることによって a > b のような例えば「nより大きい」ものだけを数えることもできます。ちなみに a が配列の要素で b が引数です。

ABC081B Shift only

import std.stdio, std.conv, std.string, std.algorithm;


void main()
{
        long n = readln.strip.to!long;
        long[] xs = readln.split.to!(long[]);

        long cnt = 0;
        while(true) {
                bool flag = true;

                foreach (x; xs) {
                        if (x % 2 != 0) {
                                flag = false;
                                break;
                        }
                }

                if (! flag) {
                        break;
                }

                foreach (ref x; xs) {
                        x /= 2;
                }

                cnt++;
        }
        writeln(cnt);

}

to!(long[]) が便利で文字列の配列をlongの配列に変換できます。これを知らなかった頃は map!(to!long).array をやっていて。

foreach (ref x; xs) はまあできそうだよねと思って書いたらできてびっくりしました。PHPのような罠はないでしょう。

ABC087B Coins

import std.stdio, std.conv, std.algorithm, std.string;


void main() {
        long a,b,c,x;
        readf("%d\n%d\n%d\n%d\n", &a, &b, &c, &x);

        long cnt = 0;

        foreach (i; 0..a+1) {
                foreach (j; 0..b+1) {
                        foreach (k; 0..c+1) {
                                if (i*500 + j*100 + k*50 == x) {
                                    cnt++;
                                }
                        }
                }
        }

        writeln(cnt);
}

入力は縦に

a
b
c
x

と与えられますが、 readf に改行文字も読ませて対応できて楽です。ここで foreach を使うか for を使うかは微妙なところですが、 foreach で困らないときは foreach を使ったほうがコンパイラがよしなにしてくれるという話を聞いた気がします*1

ABC083B Some Sums

import std.stdio, std.string, std.conv, std.algorithm;


void main()
{
        long n, a, b;
        readf("%d %d %d", &n, &a, &b);

        long ans = 0;
        foreach (x; 1..n+1) {
                auto s = x.to!(string).split("").to!(long[]).sum;
                if (a <= s && s <= b) {
                        ans += x;
                }
        }
        writeln(ans);
}

123[1, 2, 3] をやるのに文字列に変換して各文字で区切ってそれぞれ数値に変換というのをやってます。普通ですね。 sum は sum する。当然 reduce もあるのでそちらを使ってもいいですけどsumするときは sum を使うのがわかりやすいと思います。

ABC088B Card Game for Two

import std.stdio, std.algorithm, std.string, std.conv, std.range;


void main()
{
        long n = readln.strip.to!int;
        auto xs = readln.split.to!(long[]);
        sort(xs);
        reverse(xs);

        long alice = xs.stride(2).sum;
        long bob = xs.drop(1).stride(2).sum;

        writeln(alice-bob);
}

D言語は range を頑張って扱いたがっていて stride([1,2,3,4], 2)[1,3] になります。 drop([1,2,3,4], 1)[2,3,4] になりそうですね。

ところで sortreverse は結構罠で、最初は auto xs = readln.split.to!(long[]).sort.reverse; って書いてたんですが、 AtCoder 上では Warning: use std.algorithm.sort instead of .sort property と怒られて CE になります。まじでこの sort どこから生えてきたんだと思いながら sort(xs); って書きました。

ちなみに algorithm に生えてる sort はテンプレート引数で比較関数を変更できて sort!("a < b") とかすれば reverse いらないし property の方と差別化できて CE ならんかったのではと思っているところです。

ABC085B Kagami Mochi

import std.stdio, std.conv, std.algorithm, std.string, std.array;

void main()
{
        long n = readln.strip.to!long;
        long[] xs = [];

        foreach (i; 0..n) {
                xs ~= readln.strip.to!long;
        }
        sort(xs);
        writeln(xs.uniq.array.length);
}

やるだけ。 uniq する前には sort しましょうというのと、 返ってくる UniqResultlength プロパティを持ってないので一回 array で配列に戻します。

ABC085C Otoshidama

import std.stdio, std.conv, std.algorithm, std.string, std.range, std.array;


void main()
{
        long n, y;
        readf("%d %d\n", &n, &y);

        for (long i = 0; i <= n; i++) {
                for (long j = 0; i+j <= n; j++) {
                        long k = n - (i + j);

                        if (i * 10000 + j * 5000 + k * 1000 == y) {
                                writefln("%d %d %d", i, j, k);
                                return;
                        }
                }
        }
        writeln("-1 -1 -1");
}

条件がややこしい気がしたので for を使いましたが 0..(n-i+1) でも良いですね。やっぱりわかりにくいか。

ABC049C 白昼夢 / Daydream

import std.stdio, std.string, std.conv, std.array, std.algorithm;

void main()
{
        string[] ts = ["dream", "dreamer", "erase", "eraser"];
        string s = readln.strip;

        while (true) {
                bool flag = false;
                foreach (t; ts) {
                        if (s.length < t.length) {
                                continue;
                        }

                        if (s[($-t.length)..$] == t) {
                                s = s[0..$-t.length];
                                flag = true;
                                break;
                        }
                }
                if (! flag) {
                        writeln("NO");
                        return;
                }
                
                if (s.length == 0) {
                        writeln("YES");
                        return;
                }
        }
}

これは yosupo さんの回答が優れてたのでそっちを見ましょう。

ABC086C Traveling

import std.stdio, std.string, std.algorithm, std.array, std.range, std.conv, std.math;


void main()
{
        long n = readln.strip.to!long();
        long[] ts = [];
        long[] xs = [];
        long[] ys = [];

        foreach (i; 0..n) {
                long t, x, y;
                readf("%d %d %d\n", &t, &x, &y);
                ts ~= t;
                xs ~= x;
                ys ~= y;
        }

        bool flag = true;
        long x = 0, y = 0, t = 0;
        foreach (i; 0..n) {
                long dx = abs(x - xs[i]);
                long dy = abs(y - ys[i]);
                long dt = ts[i] - t;           

                long v = dt - (dx + dy);
                if (v < 0) {
                        flag = false;
                        break;
                }

                if (v % 2 != 0) {
                        flag = false;
                        break;
                }

                x = xs[i];
                y = ys[i];
                t = ts[i];
        }

        if (flag) {
                writeln("Yes");
        }
        else {
                writeln("No");
        }

}

絶対 dx, dy, dt = ..., ..., ... ってする構文か何かがあると思うんですがよく知らないので愚直に書きました。

おわりに

D言語はCEしなければ良い言語なのでコードテストしましょう。

*1:ほんまか

TalkCafe に参加した

 昨日の弊高専では、 TalkCafe なるオサレイベントが開催されていました。

これは有り体に言いましてただのLT会です。今まで弊学にはjoken LTというjoken民限定の大体monthlyなゆるふわLT会以外にまともなLT会がなかったのですが、 ちげくんと kyumina の粉骨砕身の努力によってこれが成し遂げられました。TalkCafeは「学生間交流の促進」や「外部との積極的交流促進」、「新規知見の獲得」を目的としている様子です。副作用としてLR談話室(現在は地域創生なんとか室になった)が大変良さげなお部屋に変身したにも関わらずまともに使えるような状況じゃない(制度が整っていない)っぽくてこれを殴りにいってたみたいです。

ともあれ、このめでたい第一回TalkCafe に参加し、発表してきました。タイトルは「情報工学三種の神器」で、他学科の人間も来るだろうし下級生もいるだろうから、と思ってちょっと緩めの内容にしました。中身はシェル使おうぜ、Vim使おうぜという布教記事です。

この会の前の晩にふと思い立って、 こんなものを書きました。これはLT中に面白い、良いと思ったら good を、悪いと思ったら bad を押してもらうというだけのツールで、ページごとに押された回数を記録しておくことであとから「ここが良かったのか」「悪かったのか」ということを振り返る目的でした。nodejs というか express というか、とにかくそういうものを使うのは初めてでした。

github.com

f:id:Furutsuki:20180303153954p:plain

これが、画像を見ればわかるようにgoodボタンを押しまくられるDoSを喰らいました。どうやら二人程度が 5000 から10000 回程度のループで good を押す javascript を書いたらしく、発表中にこのツールは処理落ちしました(どうやって処理落ち防ぐんですか)。一応、こういう人たちがいるかと思って、 script のページには適当な flag を埋め込んでCTFに誘導しようとしたのですが、そちらは一切効果を発揮しませんでした。

というのが功を奏したのかどうかわかりませんが、ベスト技術賞をもらいました。光栄です。


私以外にも 1年生から 5年生まで多くの人が発表していました。特に 撮り鉄の一年生の話は技術にフォーカスして列車を撮る楽しみをきれいに伝えていてよかったと思いますし、最後に発表した5年生はコーヒーを淹れる実演をして、文句なし最高のLTでした。私もインスタントコーヒーを卒業したくなったのですが、Amazonでみたらひと揃い揃えると結構することがわかったのでほしいものリストに突っ込むに留めました。

TalkCafeではそれ以外にもチーム対抗大喜利をやって(これは笑点というよりはIPPONに近い形でした)学生間交流をはかっていましたが私はこれはあんまり好みではなかった。好みではなかったけどチームワークで一番評価の高いチームになりました。

その後なんだかんだとおやつ会兼懇親会をやりおわったのですが(私は一切懇親しなかった)、なかなか疲れました。人間が多いところに行くとそれだけで消耗できるの本当に不利ですね。

全体として雰囲気よい会で、次回にも期待が持てそうでした。次回は Wifi が会場に導入されて(なんか許可が降りなかったらしい)、Twitterでの盛り上がりも見せてくれると嬉しいですね。

 

Ponyがいい言語に見える

 最近D言語と倦怠期に突入して(classを引数にとって中身をがんがんいじっていた自分のプログラミングが嫌になり、structを使えばいいのかclassを使えばいいのか考え出して死んだ。そもそもぱっと出てきた変数が値型なのか参照型なのかわからないの辛くないですか? 僕は Rangeはclassだと思ってたよ)、

書いていて楽しいプログラミング言語を探す旅に出たんですが、その中でであったものの一つがPonyでした(他にはElixirとかCommon Lispをみてた。やつらも楽しい感じがありますね)。

github.com

 Ponyは静的型付けのオブジェクト指向コンパイル言語だけど、核にあるのはActor Model な並列プログラミングだと思います。私はActorモデルよく知らないので全然わからないけど、言語仕様を見ていて好きな感じがしました。私はPonyのこんなところがスキっていうのを列挙します。

  • 静的型付け(強そう)である
  • capability って言われる(ほんまか)制約みたいなんがあって格好良い
  • コンパイルする言語でバイナリが結構小さい
  • GCがあるっぽい
  • プログラムの見た目が好き
  • 例外の扱いが好き
  • その他なんとなく哲学が好き(グローバル変数がないとか、stdoutやargsは全部Envというクラスのインスタンスにまとめられてエントリポイントに渡されるとか)
  • ドキュメントを結構たくさん書いてくれてる

まあなんというか、書いていて楽しそうという感じがしました。何故か日本語の情報が少ない*1 のですが GitHub では Syntax Highlight されてるし多分メジャーになってきてるとか、メジャーだとかそういう言語なんだと想います。


ちょっと見て下さい。これはフィボナッチ数列を列挙するプログラム*2です。

primitive Fibonacci
    fun fib[A: Integer[A] val](a: A, b: A, out: OutStream) =>
        out.print(a.string())
        if (a+b) < a then
            None
        else
            fib[A](b, a+b, out)
        end

        
actor Main
    new create(env: Env) =>
        try
            let a = env.args(1)?.u128()?
            let b = env.args(2)?.u128()?
            Fibonacci.fib[U128](a, b, env.out)
        end

プログラムは Main actor のコンストラクタから始まります。コンストラクタは new <constructor name>(args) => <body> という形になっていて、脱線すると自由に名前をつけることができます。実質オーバーロードみたいなものですが。Main と書いたら引数なしの create が呼ばれるけどこれは Main.create() でも同じことです。 もし new with_arg(arg1: U32) みたいなコンストラクタが定義されていたら Main.with_arg(10) みたいな感じでコンストラクタを呼び出すこともできます。なんか好き。

閑話休題で、まあその下に書いてあるのが body だっていうのはわかると思われます。何をしてるかも雰囲気で読めますよね? あと、これはちょっと罠っぽいんですが、インデントはプログラムの挙動には関係ないです。その代わり、フィールドの宣言、コンストラクタの定義、関数の定義、befavior の定義っていう順番に書かないとダメという決まりがあります。なるほどね。

env.args はなんとなく Array[String] みたいな型を持ちそうということは推測できそうですが((実際には val という immutability を表す capability がついて Array[String val] val なんですが))、これにいくつ要素が入ってるかわからないので その () オペレータ (( apply という関数の呼び出しなんで args.apply(1)? とも書ける)) の返り型は A? です。これは A 型の値を返すかあるいは 例外を発生する事を表していて*3Javathrows みたいなもんですね)こういう関数*4は呼び出すときに ? を付けないとだめだし、呼び出している関数も partial function になるか、それとも try...else...then...end 構文で例外を捕捉しに行かないとだめです(おわかりかと思いますが elsecatch 相当、 thenfinally 相当です)。

また脱線すると例外の扱いがすごい好きで、いわゆる raise とか throw に当たるのは error という構文なんですが、これの面白いのが値を一緒に渡せないし型がないところで、つまり一切の例外を識別できないんですね。これはパフォーマンス的な理由からと書いてあるような気がするんですが、私はこれかなり好きです。例外ハンドリング嫌いなので(でもこれDBのカラム名間違ってましたみたいなエラーの原因特定するの難しそう)。

まあそんな感じで、もし引数があれば、それは String なので u128 関数で U128 型の値として取り出します。当然これも失敗しうる。ちなみに整数型は U8 U16 ... U128I8 ... I128 に加えて {U,I}{Size,Long} があります。

次は fib の呼び出しなんですが先に定義の方を解説します。

primitive はいろいろな使われ方をしていて enum のように使うときと 「メソッドまとめ」のように使うときとあります。今回は後者。 Main の関数でも良かったといえばそうだけど。

なんか雰囲気ありますがこれは Generics を使っていて ちょっとどういう書き方でこうなってるのかわかってないんですが、 「Integer に属していて読み取り専用」 の型Aを引数に取っている気持ちです。やってることは単純なのでわかるとおもいます。あ、末尾最適化があります。

定義がわかると呼び出しもわかります。いい感じの言語に見えませんか?

そう言えばコンパイルも面白くて、特定のディレクトリ以下で ponyc とすると勝手にソースコードを探索する仕組みになっています。便利と言えば便利だけど慣れないのでキモいですね。 make してる気持ちに慣ればいいんでしょう。できるバイナリはディレクトリ名をしてます。


もういっこサンプルを。折角Actorモデルがつかえるので書きたかったんですがわからなかったやつ。

use "collections"
use "itertools"

actor Worker
    be calculatePiFor(receiver: Main, start: U32, stop: U32) =>
        let iterator: Iterator[U32] = Range[U32](start, stop)
        let x: F32 = Iter[U32](iterator)
            .map[F32]({(x: U32) => x.f32()})
            .map[F32]({(x: F32) => 4.0 * ((1-((x%2)*2)) / ((2*x)+1))})
            .fold[F32](0.0, {(sum: F32, x: F32) => sum + x})
        receiver.receive(x)
        
actor Main
    var _pi: F32 = 0.0
    let _range: U32 = 10000
    let _actor_nums: U32 = 1000
    let _out: OutStream
    new create(env: Env) =>
        var start: U32 = 0
        for i in Range[U32](0, _actor_nums) do
            Worker.create().calculatePiFor(this, start, start + _range)
            start = start + _range
        end
        _out = env.out


    be receive(x: F32) => 
        _pi = _pi + x
        _out.print(_pi.string())
        

これは、 ライプニッツの公式による円周率の導出です。 1000個の actor に計算を投げてそれの集約をしてる……んですが、うまく create の中で actor の計算終了を待って出力みたいなことができませんでした。どうやるんだろ。

ところでこれも気持ちがあると読めると思うんですが、 beactor 特有のアレで、 behavior の略です。なんでこんな略し方をしたのか。 Rust の fn みたいな反感の買い方をしそう。まああの、 be は partial にできなかったり返り値を返せなかったりしますが*5、そのかわり勝手に並列になります(一つのActorインスタンス内で並列になることはないので安心)。

あーあとすっごい不思議なんですが、すべての演算子には 括弧がついていて順序付けされている必要があります。 1 + 2 * 3は許可されて無くて (1 + 2) * 31 + (2 * 3) じゃないとだめ(でもなぜか 1 + 2 + 3 のように同じ演算子の連続はOKらしい)。これ鬱陶しい。ついでに U32 + F32 とか U32 + U128 みたいな演算は定義されてないので悪しからず。さらに言えば 加算代入演算子っていうんでしたっけ、 こういうの += も存在しません。この辺なんでだろ……。

まあこんな感じの言語があって良さげだし、もうちょっと勉強したいですね。今回は capability にも言及できなかったので(わかってないから。良さそうに見えるけど)、そこもどうにかしていきたいです。

*1:矢二郎の顔ばかり出てくる

*2:本当にどうでもいい話だけど math package が最高に面白い

https://github.com/ponylang/ponyc/tree/8a8ee28f8dec1f5336f9c6e3176e41d133e5b68b/packages/math

*3:型としてはA or None を表している

*4:partial functionと呼ばれる

*5:つねにNoneが返ることになってる

SECCON2017 国内決勝に出た

KOSENSECで優勝したので theoldmoon0602、thrust2799、kyumina8376、miwpayou0808 からなる insecure というチームで SECCON 国内決勝に出ました。 結果は 300pt で 24チーム中 19 位でした。私は300pt をSubmit したので一応WriteUpを書きます。はあ〜〜〜〜負けた。

https://i.gyazo.com/c73c95915dee890e2a2d8ffe15b1985f.png

梅田

画像Uploaderの問題です。King of the Hill なので flag を書き込むべきページみたいなのがあって、そこにでかでかと SECCON{hogehoge} が鎮座していました。他のチームはこれを速攻で見つけていたっぽくて開始と同時に AC がN回行われていました。クソ焦る。私は 船橋を検討して無理だな! と結論付けた後にこれを見つけてSubmitした。梅田に取り組んでいるチームメイトもいたんですがね。 100pt

幕張

golang 製のバイナリが二つ渡されます。まずはAだけが配られていたのでAについて話す。最初は「えっなにこれ即終了するじゃ〜ん。私の環境では動かねぇのかよ」とか思って放置していましたが、 miwpayou0808 がちょっと解析して 適当に command line arguments を渡すと usage を吐いてくれることを教えてくれてやる気が出たのでもうちょっとやることにしました。

よくわかんないけどバイナリを IDA でみていたら END PRIVATE KEY みたいな文字列に遭遇して「おっ秘密鍵ジャーン」と思ってコピー&ペーストしてvim で整形しました。鍵があるということは通信しているとあたりをつけて、 wireshark でパケットを監視しながらもう一度起動しました。秘密鍵もってるし秘密通信を解読できるね! と思っていたら解読できなかったんですが、鍵交換アルゴリズムの中にフラグっぽい文字を見つけました。

後から調べたら、このバイナリはもう二つ、公開鍵証明書みたいなものを持っていて、それの mail address の欄がそうなっていたっぽいです。

この頃にはこのバイナリが MQTT みたいなプロトコルで通信していることがわかりました。 もう一つのBのバイナリも MQTT で通信するプログラムっぽかった。

けどいろいろよくわからなくて時間を無限に溶かしていましたが、 無限に溶かした時間のうち少しが有意義だったっぽくて、 MQTT には topic なる概念があって、まあ IRC で言う channel みたいなものだと思うんですけど、まあそういうものがあるということがわかりました。

で、このバイナリが何ていうchannel で通信してるかを調べたら、サービス内に飛んでるメッセージを拾えると思ったので、 クライアントはここから https://qiita.com/n-yamanaka/items/91dbd7bd9fed5b3fbed4 頂戴してきて、バイナリの中から topic っぽい文字列を探そうとしたのですが、 IDA でも gdb でも全然わからず、 miwpayou0808 が探してきていた delve という go binary 用の gdb みたいなやつを使いました。 b Subscribe→c→si→args でSubscribeしてるときの引数を見られたんですが、ここに /mkhr/v/1/unlock/1 のような名前があって、 「これじゃーん!」となりました。でもこれに対して subscribe してみても全然飛んできませんでしたどういうことだよ。

miwpayou0808 がもう一個のバイナリもおんなじように調べたら今度は 別のtopic 名があって、そっちを subscribe したらいろいろ飛んできて「うーわこれじゃん」ってなりました。その中にしれっと FLAG も飛んできてた。

多分これで subscribe の代わりに defense キーワードを publish すると defense ポイントが入るような気がしたんですが↑の時点で残り時間が 5分もなかったので意味なし!!!!!

追記

さいこうですね


これで 300 点でした。 miwpayou0808 は基本的に 幕張の rev をやってて、残りの二人は府中梅田船橋を横断していたっぽいですけどよくわからなかった。完全に食いの残る競技と言うかはーつらい。つらいなー。insecureは弱いということです。


どうでもいいことですが懇親会みたいなやつ、完全に電池が切れて端っこで座ったり寝たりしていました。人間がたくさんいて喋ってるのが本当に苦手っぽい。友達を作り損ねた。

来年はもう参加できないと思うけど参加できたら師匠に出てもらってもうちょっとまともに戦えてる風を演出したいです