はじめに
誰もやってなさそうな言語で競プロをやるシリーズ第5弾1、AtCoder Beginners Selection の問題2を、プロトタイプベースオブジェクト指向プログラミング言語「Io」で解いてみました。
競プロを知っている方向けのIoの布教記事となります。
現在のところ Io はAtCoderで使用可能な言語に含まれていないのでローカル環境でテストだけしています。
使用環境はUbuntu 18.04 LTS on WSL。環境構築については以前記事にしたので**こちら**をご覧ください3。
Ioの解説
Ioは純粋なプロトタイプベースオブジェクト指向言語です。Ioの基礎的な文法は非常に単純なので、同様にプロトタイプベースで動作するJavascriptやLuaなどの言語の理解に役立つのではないかと思います。
Ioはすべての動作が「オブジェクトへのメッセージ4送信」だけで成りたっています。
オブジェクトはメッセージを受け取るとメッセージと名前の一致する「スロット」を検索します。該当するスロットが見つかればそのスロットに対応するメソッドを実行、戻り値があれば値を返します。
オブジェクトを実質的に {スロット名→その値} というハッシュテーブルだとみなすとわかりやすいでしょう。
各オブジェクトにはそのオブジェクトの「プロトタイプ」が設定されており、受け取ったメッセージに該当するスロットが存在しなければ自身のプロトタイプにメッセージをたらい回しします。
例として"Hello, world!" printという文を見てみましょう。
"Hello, world!"は文字列リテラルですが、これはSequenceというオブジェクトをプロトタイプに持ち、スロットは何もないオブジェクトです。
Io> "Hello, world!" slotNames
==> list()
// slotNamesでスロットの一覧が取得される
これにprintというメーッセージが送られていますが、printというスロットは無いのでプロトタイプのSequenceにprintを送ります。
Sequenceは
Sequence slotNames
==> list(asJson, linePrint, duplicateIndexes, pathComponent, urlDecoded, removeSeq, bitwiseAnd, asCapitalized, log, uppercase, findSeq, replaceSeq, logicalOr, +, beginsWithSeq, containsAnyCaseSeq, square, sizeInBytes, cos, byteAt, asIoPath, removeEvenIndexes, <=, endsWithSeq, validEncodings, between, preallocateToSize, asBinarySignedInteger, sqrt, asDecodedList, size, repeated, isSymbol, interpolate, setSize, copy, removeSlice, beforeSeq, cloneAppendSeq, asLowercase, alignLeftInPlace, bitCount, afterSeq, findNthSeq, abs, lstrip, asBuffer, log10, max, slice, z, print, replaceFirstSeq, translate, cPrint, <, at, reverseFindSeq, appendSeq, encoding, acos, product, atPut, setItemsToDouble, asOSPath, Max, foreach, -, stringByExpandingTilde, setItemType, asSymbol, sinh, removeAt, set, sum, betweenSeq, /=, inclusiveSlice, clipAfterSeq, addEquals, atan, reverse, unpack, splitAt, setZ, asNumber, withStruct, removeOddIndexes, alignLeft, ceil, bitwiseNot, setItemsToLong, itemCopy, orderedSplit, tanh, asList, asFixedSizeType, removeSuffix, unescape, with, removeLast, >=, asBase64, validItemTypes, asMutable, normalize, exclusiveSlice, replaceMap, inSlice, asUCS4, x, floor, clipBeforeSeq, isUppercase, percentEncoded, lowercase, rootMeanSquare, asUppercase, alignCenter, sort, convertToFixedSizeType, asFile, append, isZero, empty, +=, toBase, rangeFill, cloneAppendPath, asin, sequenceSets, asStruct, zero, lastPathComponent, setEncoding, min, occurancesOfSeq, convertToItemType, split, itemSize, Min, capitalize, y, asSimpleString, strip, pack, findSeqs, percentDecoded, isEmpty, setY, *=, >, -=, asBinaryNumber, contains, /, splitNoEmpties, asBinaryUnsignedInteger, .., asUTF8, itemType, justSerialized, cosh, makeFirstCharacterLowercase, atInsertSeq, fromBase, clipBeforeEndOfSeq, sin, bitAt, meanSquare, negate, mean, prependSeq, containsSeq, slicesBetween, removePrefix, *, reverseInPlace, asString, isEqualAnyCase, whiteSpaceStrings, escape, bitwiseXor, alignRight, tan, urlEncoded, leaveThenRemove, interpolateInPlace, fileName, isLowercase, isMutable, fromBase64, distanceTo, insertSeqEvery, clipAfterStartOfSeq, hash, appendPathSeq, pathExtension, asHex, asMessage, makeFirstCharacterUppercase, exSlice, dotProduct, bitwiseOr, asUCS2, rstrip, setX)
のように文字列の様々な機能が実装されたスロットが存在します。ここにprintスロットも存在し、自身を標準出力に出力するメソッドが対応していますので、Hello, world!が出力されます。
メソッドによって値が返されればそのオブジェクトに更にメッセージを送ることでメソッドチェーンが実現可能です。例：9. ABC 049 C - Daydream
文字列にtypeというメッセージを送ると"Sequence"と帰ってきます。つまり文字列のtypeは「Sequence」なのですが、これはSequenceクラスがあるわけではありません。Ioに「クラス」と「インスタンス」の区別はなく、全て等しく「プロトタイプ」です。
Io>"Hello, world!" type
==> Sequence
では何故"Hello, world!" typeは"Sequence"なのかというとSequenceがスロットtypeを持っていてその値が"Sequence"だからです。Ioでは大文字で始まるオブジェクトを作成すると自動でその変数名を持ったtypeスロットが作成されます。これであるオブジェクトのクローン(そのオブジェクトをプロトタイプに持つ新たなオブジェクト)を小文字で作れば「子」は同じtypeを持つようになるので「種類」が規定され、大文字でクローンすればメソッドを継承した新しい「種類」ができるという意味をつけ、判別しやすくしていますが、結局操作の方法は同じです。
ジャッジ方法
可能な限り公式のdropboxに公開されているものを使用しますが、見つけられなかったものは考えられるコーナーケースを含んだテストケースを作成し判定します5。
$ EXE="hoge"
$ PTH="fuga"
$ (/usr/bin/time -f "${EXE} ${PTH}: %U s, %M kB" io ${EXE}.io < ../testcases/${EXE}/in/${PTH}.txt) 2>> ./resultout.txt | diff - ../testcases/${EXE}/out/${PTH}.txt
のようにdiffで正答と比較し、timeで実行時間と使用メモリをチェックしていきます。timeの出力は標準エラー出力に出るので、うまいことdiffの結果はコンソールに、timeの結果は./res/"${EXE}-${PTH}_out.txt"に
0 ex1: 0.01s, 5000 kB
のように出力されます。diffの出力なし、かつtimeの結果が制約以内ならばACとみなします。（一部答えが複数存在するものがあるのでこれは適宜対応）
解法
0. practice contest A - Welcome to AtCoder
readln := method(
File standardInput readLine
)
a := readln asNumber
l := readln split
b := l at(0) asNumber
c := l at(1) asNumber
s := readln
writeln(a + b + c, " ", s)
まずは出入力の確認ということで0番。ちょっと長いので一行読み込みのメソッドを作成しました。
トップレベルに定義した変数は実はプロトタイプチェーンの一番根本のオブジェクトである「Objectのプロトタイプ」のスロットとして定義されています。:=はスロット作成の演算子です。
Io> Object proto
==> Object_0x68c6d0:
Lobby = Object_0x68c6d0
Protos = Object_0x68c470
_ = Object_0x68c6d0
exit = method(...)
forward = method(...)
set_ = method(...)
だったのがプログラムの実行後は
Io> Object proto
==> Object_0x68c6d0:
Lobby = Object_0x68c6d0
Protos = Object_0x68c6d0
_ = Object_0x68c6d0
a = 1
b = 2
c = 3
exit = method(...)
forward = method(...)
l = list(2, 3)
readln = method(...)
s = "test"
set_ = method(...)
のようにプログラム中で定義した変数がスロットに加わっていることがわかります。6
引数0の関数呼び出しではメンバ変数のようにカッコが要らないのが特徴的ですね。
配列のインデックスアクセスにはat(1引数メソッド)、文字列の結合は..(2項演算子7)を使います。
結果： AC / 0.04s, 5984 kB
個別ケース結果
1. ABC 086 A - Product
l := File standardInput readLine split
a := l at(0) asNumber
b := l at(1) asNumber
if(a * b % 2 == 0) then(
"Even" println
) else(
"Odd" println
)
もちろん標準入力読み込みのメソッドを作らず1行で書くこともできます。
条件分岐はこんな感じに書きます。
ifもObjectのスロットに定義されているメソッドです。徹底していますね。
標準出力は#0ではwriteln(hoge)と書きましたが、<Object> printlnのようにオブジェクトが持っているprintlnメソッドを呼び出すことでも可能です。
結果： AC / 0.06 s, 5996 kB
個別ケース結果
2. ABC 081 A - Placing Marbles
s := File standardInput readLine
r := 0
for(i, 0, s size - 1,
r = r + if(s at(i) == "1" at(0), 1, 0)
)
r println
繰り返しはこんな感じ。
ifは3つ引数を与えると第1,2引数の値を返す、つまりif式として使うことができます。
ちなみにforも式で、繰り返し最後の文の値を返します。
結果： AC / 0.03 s, 5988 kB
個別ケース結果
3. ABC 081 B - Shift Only
readln := method(
File standardInput readLine
)
n := readln asNumber
l := readln split
a := list()
m := 100
for(i, 0, n - 1,
a := l at(i) asNumber; c := 0;
while(a % 2 == 0,
a = a / 2 floor; c = c + 1
);
m = m min(c)
)
m println
forの第4引数のところのように、式を複数続けて実行するときは;で繋ぎます。
結果： AC / 0.06 s, 6016 kB
個別ケース結果
4. ABC 087 B - Coins
readln := method(
File standardInput readLine
)
a := readln asNumber
b := readln asNumber
c := readln asNumber
x := readln asNumber / 50
result := 0
for(i, 0, a,
for(j, 0, b,
if(0 <= x - i * 10 - j * 2 and x - i * 10 - j * 2 <= c, result = result + 1)
)
)
result println
結果： AC / 0.06 s, 5988 kB
個別ケース結果
5. ABC 083 B - Some Sums
ketawa := method(num,
num asString asList map(asNumber) sum
)
l := File standardInput readLine split
n := l at(0) asNumber
a := l at(1) asNumber
b := l at(2) asNumber
result := 0
for(i, 1, n,
w := ketawa(i)
if(a <= w and w <= b, result = result + i)
)
result println
ketawaは数字の各桁の和を求めるメソッドです。いい感じにメソッドチェーンがつながって気持ちいいですね。
結果： AC / 0.59 s, 6296 kB
個別ケース結果
6. ABC 088 B - Card Game for Two
readln := method(
File standardInput readLine
)
n := readln asNumber
lst := readln split map(asNumber) sort reverse
alice := 0
bob := 0
for(i, 0, n - 1,
if(i % 2 == 0,
alice = alice + lst at(i),
bob = bob + lst at(i)
)
)
(alice - bob) println
listの各要素に処理を加え、戻り値のリストを得ることができる"高階関数"8、mapも存在します。
結果： AC / 0.06 s, 6012 kB
個別ケース結果
7. ABC 085 B - Kagami Mochi
readln := method(
File standardInput readLine
)
n := readln asNumber
lst := list()
for(i, 0, n - 1,
lst push(readln asNumber)
)
lst unique size println
listオブジェクトのuniqueメソッドは重複を取り除いたリストを返します。
結果： AC / 0.04 s, 5992 kB
個別ケース結果
8. ABC 085 C - Otoshidama
l := File standardInput readLine split
n := l at(0) asNumber
y := l at(1) asNumber
result := "-1 -1 -1"
for(i, 0, n,
for(j, 0, n - i,
if(10 * i + 5 * j + n - i - j == y / 1000,
result = i asString .. " " .. j asString .. " " .. (n - i - j) asString
)
)
)
result println
$O(N^2)$なので間に合う想定の解なのですが、Io自体の速度の問題でsample4では12秒もかかってしまいました。
結果： TLE / 11.79 s, 5992 kB
個別ケース結果
仕方がないので$O(1)$の解法で解きました。参考
l := File standardInput readLine split
n := l at(0) asNumber
y := l at(1) asNumber
t := (y - 1000 * n) / 1000
a := t % 4
b := (t - 9 * (t % 4)) / 4
kmin := list((- a / 4) ceil, ((a + b - n) / 5) ceil) max
kmax := (b / 9) floor
if(kmin <= kmax,
(4 * kmin + a) asString .. " " .. (-9 * kmin + b) asString .. " " .. (n - 4 * kmin - a + 9 * kmin - b) asString,
"-1 -1 -1") println
結果： AC / 0.04 s, 6012 kB
個別ケース結果
9. ABC 049 C - Daydream
この問題では eraser→erase→dreamer→dream の順で置換しすると判定ができます。置換があれば一番簡単なのでまずはこれで解いてみます。
if(File standardInput readLine asMutable replaceSeq("eraser", "!") replaceSeq("erase", "!") replaceSeq("dreamer", "!") replaceSeq("dream", "!") replaceSeq("!", "") == "", "YES", "NO") println
そのままの文字列はImmutableSequenceなのでreplaceSeqが使えません。asMutableでMutableば文字列に変換します。
結果： AC / 0.18 s, 6088 kB
個別ケース結果
公式解説の通りに、後ろから順に判定していく解法もあります。
s := File standardInput readLine
len := s size
i := len
flag := true
while(i > 0,
if("erase" == s exSlice(i - 5, i)) then(
i = i - 5
) elseif("eraser" == s exSlice(i - 6, i)) then(
i = i - 6
) elseif("dream" == s exSlice(i - 5, i)) then(
i = i - 5
) elseif("dreamer" == s exSlice(i - 7, i)) then(
i = i - 7
) else(
flag = false;
break
)
)
if(flag, "YES", "NO") println
部分文字列はexSliceで取得します。sliceも存在しますがdeprecatedだそうです。
結果： AC / 0.07 s, 6248 kB
個別ケース結果
10. ABC 086 C - Traveling
readln := method(
File standardInput readLine
)
n := readln asNumber
preT := 0
preX := 0
preY := 0
flag := true
for(i, 1, n,
l := readln split;
t := l at(0) asNumber;
x := l at(1) asNumber;
y := l at(2) asNumber;
dt := t - preT;
dl := (x - preX) abs + (y - preY) abs;
if(dl > dt or dl % 2 != dt % 2, flag = false)
)
if(flag, "Yes", "No") println
この問題でも制約を超えてしまいました。
頑張って並列化すれば速くなるんじゃないかとも思ったんですが、どうも入力の読み込みにほとんどの時間がかかっているようです。IoなのにIOが遅い こればっかりはちょっと手がつけられないので諦めました……
結果： TLE / 3.06 s, 6184 kB
個別ケース結果
まとめ
ちょっと遅いですがなかなかおもしろい言語です。
競プロではなかなか使う機会がありませんが、Ioは非同期処理がとても得意です。（例えばメッセージに@をつけるだけでFutureオブジェクトを生成し、オブジェクトをアクターとするのでとても簡単に書けます。）
プログラミングの基礎を学ぶ言語としては大変ポテンシャルのある言語なんじゃないかと思います。
惜しむらくは異常にググラビリティが低いこと、そして流行ったのがそこそこ昔（2000年代初頭）なため、当時あった日本語文献もほぼ散逸してしまい調べるのがとても大変なことです。
本記事も 『7つの言語 7つの世界』（オーム社、B. A. Tate著、まつもとゆきひろ 監訳、田和勝 訳）と「Rubyist のための他言語探訪 【第 3 回】 Io」を頼りに公式ドキュメントをひーこら読みながら書きました（公式ドキュメントもそんなに詳しくない）。
AtCoderには無いけどAnarGolfにはジャッジがあるのでやってみてください。
-
過去の記事は 「AtCoderに登録したら解くべき精選過去問10をTeXで解いてみた」、「〃JSFuck」、「〃プロデル」、「〃LabVIEW」となっています ↩
-
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～(@drken さん) にて紹介されている過去問題 ↩
-
環境構築記事の通り、プロジェクトをクローンしてきてmakeする方法だと一部パッケージが正常に読み込めないため「#バイナリからのインストール」の項に従ってインストールしています。 ↩
-
以下太字はテクニカルタームとしての語を意味します。 ↩
-
使用したテストケースデータは https://github.com/Yukishita26/abs-solve/tree/master/testcases にまとめました。 ↩
-
つまりビルトインのオブジェクトに変更を加えられるということです。Rubyのオープンクラスのようなメタプログラミングが可能です。 ↩
-
「2項演算子」は1引数メソッドのシュガーシンタックスです。 ↩
-
実際の処理としては各要素に、引数に与えた「メッセージ」を送っているだけなので関数型言語のように関数オブジェクトを扱っているわけではありません。 ↩