simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

今年作った gem の紹介 (2017)

この記事は Okinawa.rb Advent Calendar 2017 4日目の記事です。

自分は思いついたアイデアをすぐ gem にするようにしているのですが、今年は結構作った気がしたのでそれを紹介したいと思います。

spellcheck

主に技術系の単語にフォーカスしたスペルチェッカー、スペルミス候補を全部 Hash データで管理していてそれを増やすのが面倒になって放置。

サンプル (aplication がタイポしている

hello world.
I create aplication now.
good bye
$ spellcheck example.md
+----------+--------------------------+------------+-------------+
| Location | Text                     | Pattern    | Expected    |
+----------+--------------------------+------------+-------------+
| 2        | I create aplication now. | aplication | application |
+----------+--------------------------+------------+-------------+

result: 1 typo found.

typogen

英語の typo を生成するコマンド。

前に qiita で紹介したことがあるので詳しくはこちら。

https://qiita.com/siman/items/e3c8dfb72e37142b0b86

spellcheck の辞書データを作っていた時に、typo したときの単語一覧を手入力するのが面倒になった作成した。

$ typogen install
nstall
istall
intall
insall
instll
instal
nistall
isntall
intsall
insatll
instlal
instale

ripper_tree

rubyRipper.sexp の表示を tree コマンド風で表示させる。

$ rtree -e "1+2*3"
:program
 └──── :binary
         ├──── :@int ["1"] 1:0
         ├──── :+
         └──── :binary
                 ├──── :@int ["2"] 1:2
                 ├──── :*
                 └──── :@int ["3"] 1:4

今年作った gem の中では一番使っている。

tspec

TracePoint を使って Ruby で型チェックが出来るようにした gem。

require 'tspec'

def echo(str)
  puts str
end.receive(str: String)

echo('hello world') #=> ok
echo(123)           #=> TSpec::ArgumentTypeError
require 'tspec'

def echo(val)
  puts val
end.receive(val: [String, Float])

echo('hello')  #=> ok
echo(3.14)     #=> ok
echo(123)      #=> TSpec::ArgumentTypeError

ただ、挙動がちょっと怪しいので自分でも使うのをためらっている。

jt

JSON を tree コマンドっぽく表示させる gem

https://qiita.com/siman/items/a59a7ac80fba3e71ed38

rrpn

逆ポーランド記法の計算機と変換器

https://qiita.com/siman/items/d72854c4c4aaaf452868

rpn名前空間ほしかったけど取られていた。(残念

hrm

ヒューマンリソースマシーンに出てくる命令を実装したもの。メモリの初期状態を設定するコードは実装していないかも。

ヒューマンリソースマシンは完全クリアした(ドヤァ

rodir

Ruby のオブジェクト継承ツリーをディレクトリっぽく扱うもの

$ rodir
Ruby@2.4.0 /BasicObject$ ls
<M>   #<Module:0x007fb11a911388>
<M>   Kernel
Ruby@2.4.0 /BasicObject$ cd Kernel
Ruby@2.4.0 /BasicObject/Kernel$ ls
<C>   Object
Ruby@2.4.0 /BasicObject/Kernel$ cd Object
Ruby@2.4.0 /BasicObject/Kernel/Object$ pwd
BasicObject/Kernel/Object

実際に触ってみて 5分で飽きた。

open_class_alarm

オープンクラスに警告を出す gem

https://qiita.com/siman/items/cbc7b85ff45eb5fc58d5

いらない

proc_source

Proc オブジェクトのソースを表示する。

https://qiita.com/siman/items/9ad676cbb4f8afbd15ac

a = -> { 'hi' }
puts a.proc_source
-> { 'hi' }

lier

? で終わるメソッドの返り値を全て逆にする

https://qiita.com/siman/items/475d355fe22e34659149

エイプリルフールネタで作った。テストするときに rspec が壊れてやばかった。(Refinements で影響範囲を限定させた

rtg

Ruby で作ったタイピングゲーム

f:id:simanman:20171204191426g:plain

自分のコンソールの画面に合わせた配色にしたので、場合によっては文字が見づらいかも。

keyevent

keyevent を取得する gem。(Windows では試していない)

require "keyevent"

while input = getkey
  break if input == "Q"

  p input
end

rtg を作っていた時に分離できそうだったので分離した。

まとめ

結構 gem を作ってた。(使ってるとは言ってない

北大日立マラソン参加記

参加してました。

https://hokudai-hitachi2017-1.contest.atcoder.jp/

やったこと

とりあえず submit (52935)

左上から丁寧に並べる

f:id:simanman:20171128215945p:plain:w300

焼きなましする (52935 -> 149624)

近傍は ランダムな2点の位置を交換する

温度管理を調整 (149624 -> 155183)

雑に設定していたパラメータをちょっと調整

遷移させるかどうかの閾値を設ける (155183 -> 156319)

確率的に遷移させるけど、あまりにもスコアが下がっていたら遷移を却下する。

近傍を変える (156319 -> 159568)

ランダムな2点の位置を交換する から ランダムな辺を選び終点の周辺マスを1つ選択する。既に点がある場合は交換、ない場合はそこに点を移動させる に変更。

これだと、必ずスコアに影響がある近傍になるので効率が良い。

f:id:simanman:20171128220004p:plain:w300

初期解を変える (159568 -> 160152)

最初から中央に配置しておくことで移動のバリエーションが増える (気がする)

f:id:simanman:20171128220015p:plain:w300

諸々高速化 (160152 -> 160950)

盤外判定を削除したりとか

if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

高速化 (160950 -> 161572)

辺の重みを int で管理してたのを char にしたら速くなった

細かく確認してないけど、この時点での試行回数は 2億5千万前後ぐらいだったと思う。(3億は目指したかった)

パラメータ調整 (161572 -> 163024)

ひたすらパラメータ調整。(このときはまだ、システムテストとか無かったから適当に submit しながら調整してた)

辺の一部のみを採用する (163024 -> 163653)

全部の辺を使ってたけど、各頂点から生えている辺を重さ順で並べて、その上位だけを使用するようにした。

コード

https://github.com/siman-man/hokudai-hitachi2017

PoisonedWine 参加録

問題

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16944&pm=14636

複数のワインの中から、毒に反応する試験紙を使って「毒入りのワイン」を見つけ出し「毒入りではないワイン」をいかに多く集めることが出来るかという問題でした。(試験紙は毒に反応すると、次回以降に利用できなくなります)

方針

今回の方針です。

1. ワインを一通り検査する

まずは、各ワインを1回ずつ検査していきます。1回のラウンドで検査する範囲についてですが、以下の計算式で出していました。

n * (残っている試験紙の数 / 残っている毒の数) * (未チェックのワインの数 / 残りラウンド数) # nは任意の係数

そして、計算した範囲を試験紙の枚数で分割して、それぞれ検査を行います。

検査中に「試験紙が反応した数 == 毒の数」になった場合は、そこで検査を止めて、未検査のワインを全て保持するようにします。

また、毒に反応した範囲は 毒入りワインリスト に追加します。(毒入りワインリスト は範囲の大きいサイズから取り出す優先度付きキューです)

struct PoisonBarrel {
    vector<int> wineList;

    bool operator>(const PoisonBarrel &pb) const {
        return wineList.size() < pb.wineList.size();
    }
};

2. 追加のチェック

手順1で出した検査範囲だと「試験紙の数 < 毒の数」の場合はそもそも全部検査しきれずに終わることが多いです。逆に「試験紙の数 > 毒の数」の場合は全てのワインの検査後にラウンドが余るケースが発生するので、その場合は追加の検査を行っていきます。

追加の検査は試験紙が反応した範囲のワインに対して行います。

2.1 試験紙が反応した数 == 毒の数の場合

このケースでは「試験紙で検査した範囲に必ず毒が1個ある」という状態が確定しているので 毒入りワインリスト から試験紙が反応した範囲を取り出して、それを分割して検査します。m枚の試験紙を使って検査する場合はその範囲を m + 1 で分割します。m + 1 で分割している理由は、m枚の検査の結果から残りのワインの状態を確定させることが出来るからです。(いずれかの試験紙に反応すれば残りはOK、試験紙が反応無しだとOUT)

f:id:simanman:20170724082122p:plain

そして、毒が入っている範囲のワインを再度 毒入りワインリスト に追加します。

これをラウンドか試験紙がなくなるまで続けます。

2.2 試験紙が反応した数 != 毒の数の場合

このケースでは「試験紙で検査した範囲に複数の毒がある」という可能性があります。なので、この場合は m + 1 で分割しても、試験紙の結果から残りの状態を確定出来ません。

(もしかしたら毒かもしれないので確定できない)

f:id:simanman:20170724083512p:plain

このため、確定できなかったワインリストについては とりあえず保存領域 に置いておきます。

f:id:simanman:20170724083935p:plain

とりあえず保存領域 は、後の試験結果で毒が存在する箇所が全て確定した時にキープするワインのリストを置く場所です。

例えば「試験紙が反応した数 = 9, 毒の数 = 10」だとして、毒入りワインリスト から取り出した範囲から2個以上の試験紙の反応が出た場合。全ての毒の存在箇所が確定するので とりあえず保存領域 にあるワインを保存します。

f:id:simanman:20170724084855p:plain

このケースの場合はなるべく早い段階で複数の毒を検出したいので、試験紙の割り振り方を「m > 1」になるように調整しています。(例: [1, 1, 1, 1, 1] とあったら [3, 2, 0, 0, 0] となるように調整)

Examples

Example scores:
0) 0.01323285993742249
1) 0.20518911960377745
2) 0.009050017313019389
3) 1.0
4) 0.05072227596728843
5) 0.00401218710446807
6) 0.04226661200602016
7) 0.07289292284542803
8) 0.001466688380179619
9) 0.6574141709276845

MM92 Lighting 参加録

Marathon Match 92の「Lighting」に参加していました。

問題

SxS のセル状空間に光源の強さがDのL個のライトをいい感じに設置して、なるべくたくさんの空間を照らしましょう。

すごいシンプルでした。美術館問題に似た問題だなと思いました。

方針

大きく分けて次の3つを行いました。

  • フィールドの拡大率をいい感じに決める
  • 焼きなましで照明を設置する場所を決める
  • 焼きなまし後にフィールドの拡大率をさらに上げて照明の位置を微調整する

フィールドの拡大率をいい感じに決める

最初に与えられたフィールドをそのまま使うと照明のシミュレーションの精度が粗いので、フィールドをある程度引き伸ばして精度を高めました。テスターの実装では拡大率が f = 100 で定義されていましたが、これをそのまま使うと後の焼きなましパートで試行回数が全然稼げないので、フィールドサイズが「縦 x 横 == 10000」ぐらいになるように値を修正しました。

SCALE = ceil(sqrt(10000 / (S * S))); // 端数は切り上げ

焼きなましで照明を設置する場所を決める

遷移は「照明を1つ選び任意の場所に移動させる(※ただし壁は除く)」を採用し、温度管理は「差分スコア / (任意の定数) * (残り時間)」で管理してました。

1つのセルを16分割して細かく移動出来るようにしています。

f:id:simanman:20170119163941p:plain

   ↓

f:id:simanman:20170119163947p:plain

高速化

一度照明のシミュレーションをした座標については「照らすことが出来るセルの位置情報」をキャッシュして、次回以降はそれを取り出すようにしました。

照明の位置を微調整

焼きなましパートで照明の位置を決めた後に位置を微調整を行いました。処理的には任意の照明を1つ選んでちょっとだけ動かしてスコアが改善していたら採用という感じで山登り的に行いました。シミュレーションの精度を上げるために事前にフィールドを焼きなましパートのときより少し拡大しています。

f:id:simanman:20170119013248p:plain

それぞれのパートの時間の割り振りは

  • 焼きなまし(15秒)
  • 微調整(5秒)

としました。

感想

0.1%のスコア範囲で争ったのは初めてかもしれない。みんな大体同じ戦略になってそう。

Example scores:
0) 0.9987473684210526
1) 0.8922939051918736
2) 0.7014297413793104
3) 0.382128527607362
4) 0.15465865921787708
5) 0.13367932926829268
6) 0.98818025477707
7) 0.9328539007092198
8) 0.7149500729927007
9) 0.7206551724137931

ソースコード

RubyのEnglish.rbソース読み

Rubyの標準ライブラリを読んでいく、前回は3年前に ostruct を読んだ

今回は English.rb を読んでいく。

English.rbとは何か

English.rbはRubyの特殊変数に対してわかりやすい別の名前を付与するライブラリである。Rubyの特殊変数は通常 $ + 記号 の形で与えられており大変読みにくい。そこでこの English.rb を取り込むことで読みやすい別名を使用することが出来るようになる。

require 'English'

"hogefugapiyo" =~ /fuga/

p $PREMATCH   #=> "hoge"
p $MATCH      #=> "fuga"
p $POSTMATCH  #=> "piyo"

中身を見てみる

基本的に alias を使って別名を割り当てているだけ

# The exception object passed to +raise+.
alias $ERROR_INFO              $!

# The stack backtrace generated by the last
# exception. <tt>See Kernel.caller</tt> for details. Thread local.
alias $ERROR_POSITION          $@

# The default separator pattern used by <tt>String.split</tt>.  May be
# set from the command line using the <tt>-F</tt> flag.
alias $FS                      $;

1つ気になるところ

読んでいて1個所気になったのはこの部分

module English end if false

絶対に実行されない謎のコードが入っていたので「なんだこれは」と思っていたのだがどうやらRDocのparseのために追加しているらしい。

参考URL

TCO 16 Round3参戦記録 - TerrainCrossing -

TCOMMの最終ラウンドが終わりました。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283


問題文

縦横長さが S あるフィールドがあります。フィールド上にはN個のアイテムとN個の目的地が存在しています。あなたは全てのアイテムを各目的地に運ぶ必要があります。この時、各目的地には1つのアイテムしか届けることが出来ません。(複数のアイテムを同じ目的地に置くことは不可)

フィールドの移動についてですが、現在いるセルから隣接するセルへ移動が可能です。また、各セルにはコストが割り振られており、そのセル内での移動では「移動した距離 x セルのコスト」のコストがかかります。さらにセル間の移動については以下の計算式によって追加コストが発生します。

セル(x, y) -> セル(nx, ny) への移動
addCost = pow(fieldCost[x][y] - fieldCost[nx][ny], 2)

アイテムの回収についてですが、プレイヤーがアイテムの座標から距離0.001以内のフィールドに到達すると自動的に回収されます。アイテムの保持数については上限があり、上限を超えてアイテムを保持することは出来ません。また、アイテムの設置については回収と同様に目的に0.001以内のフィールドに到達すると自動的に配置されます。アイテムを保持していない場合は設置は行われないので注意してください。

また、経路の開始地点と終了地点についてですが、開始時は任意のマップの端から0.001以内の距離にある座標から開始し終了地点も同様にマップの端から0.001以内の距離を指定してください。なお、連続している経路の間隔は0.001より大きく、かつ座標が存在しているセルのマンハッタン距離が1以下になるようにしてください。さらに始点と終点を除いた各経路の座標はセルの端から0.001より離れた場所を指定してください。

最終的にコストの消費を少なく全てのアイテムを目的地に届けて下さい。

今回の問題、細かい制約のせいでたくさんのバグを埋め込みました。 あと参加した中で一番疲れました。

戦略

今回は「各オブジェクト間のコストを計算」「巡回セールスマン問題を解く」「山登りで経路を修正」と大きく分けて3つのフェーズに分けて処理を行いました。

各オブジェクト間のコストを計算

まず最初にフィールドに散らばっている「アイテム」と「目的地」それぞれの経路間のコストを求めます。基本的には各オブジェクトからダイクストラ法で経路を生成しました。

f:id:simanman:20160706224555p:plain

なるべくコストが小さくなるように移動。

f:id:simanman:20160706225209p:plain

今回はこのコストをどう計算するかでかなり頭を悩ませました。というのも、下の図のようなフィールドが存在し

f:id:simanman:20160706231156p:plain

このフィールドを次のように移動した時に、図の経路だと「1 + 1 = 2」と計算するのですが、実際には

f:id:simanman:20160706231409p:plain

この移動が可能なので1.41ぐらいのコストにしたい、かといってこの状態でさらに右に進んだ場合

f:id:simanman:20160706231748p:plain

今度は赤線の経路が最短になり、前回時点での最短を固定してしまうとロスが発生してしまう。

f:id:simanman:20160706232113p:plain

このロスは経路を進めれば進めるほど発生するので、このロスをいかに減らすかが難しかったです。

自分は通常のコストの計算時に追加コストを通常の2倍で計算を行いました。(これは評価値としては微妙な気がしなくもないですが

また、Sが小さい場合は、1つ進める毎に今までの経路に対して後述する山登り法を適用して経路のコストをその都度再計算していました。

巡回セールスマン問題を解く

求めたオブジェクト間のコストを元に巡回セールスマン問題を解きます。経路には以下の制限をつけました

  • アイテムが0個の状態で「目的地」に到達してはいけない
  • アイテムの所持数が上限の状態で「アイテム」に到達してはいけない

巡回セールスマン問題を解いた内容については前回の予選の感想ブログで書いた内容とほぼ一緒なのでそちらをどうぞ

simanman.hatenablog.com

簡単に説明すると、現在の経路に対して以下の操作のいずれかを選択します。

  • 2点間のオブジェクトを入れ替える
  • 2点間の交差を削除する
  • 1点を取り出し任意の場所に追加する
  • 連続した2点を取り出し任意の場所に追加する

また、仮に経路のコストが増加しても一定の確率でその経路を採用します(焼きなまし法

山登りで経路を修正

最終的な経路が確定したら、経路の座標をランダムに選択し、ランダムに動かしてスコアが改善されたらそれを採用する、という処理を行いました。

この様な経路が存在している時に

f:id:simanman:20160706233252p:plain

始点と終点とアイテムと目的地を除いた座標をランダムに1つ選び動かします

f:id:simanman:20160706233859p:plain

スコアが改善された場合はそちらを採用します。

セルを飛び越える移動も有効にしています

f:id:simanman:20160706235123p:plain

f:id:simanman:20160706235132p:plain

感想

まさか同じ予選で巡回セールスマン問題を2回も出題されるとは思いませんでした。点をばらまいてそれをくっつけたり切り離したり移動させたりする案もあったのですが、時間が無くて断念しました。序盤の「オブジェクト間のコストを算出」する部分が精確に出せなかったのが心残りです。

Example

Example scores:
0) 8.106127476192645
1) 85.36355804638156
2) 384.75769417466637
3) 5627.9464135616445
4) 551.6884483017363
5) 311.8191310808154
6) 313.3568643271177
7) 921.3633059194917
8) 1493.4400096579031
9) 664.7891337391771

OnlineExam 参戦記録

Codeforcesで開催されていたマラソンマッチに参加してました。

codeforces.com


問題文

オンラインの試験があります。問題は全部で5000問あり、各問題は「YES」または「NO」で解答を行います。採点については各問題ごとに正解不正解を判別し不正解の数が2000に達するまで採点が行われます。最終的な点数は採点が終了した時点の問題番号となります(正解数ではないので注意)。試験には最大100回までチャレンジできます、その間に問題の解答が変化することはありません。なるべく多くの点数を取れるように頑張ってください。

戦略

まず、大きな手がかりとして「採点したスコアの問題番号は不正解」というのがあります。例えば問題数が10で1問でも間違ったら採点終了の場合において、スコアが7だった場合は8問目は不正解ということになります。

f:id:simanman:20160622062424p:plain

まずこれで最大100問は不正解を正解に直すことが出来ます。

特定の範囲を指定して解答をひっくり返す

5000個の問題の中から一部を抜粋して、その部分の解答を反転させてそのスコアの増減を確認してました。

一部を抜き出して
f:id:simanman:20160622063351p:plain

解答を反転させる
f:id:simanman:20160622063427p:plain

初期の頃はこれを範囲40ぐらいで行って68000点ぐらいでした。

変化が少ない部分は分割して再調査

分割して調査していくと、特定の個所ではスコアの変動がかなり少ないところがあります。これは正解数と不正解数がその区間ではほぼ同一なことを示しているのですが、実際には図のように片方に正解が偏って、もう片方に不正解が偏っている場合があります。

f:id:simanman:20160622064122p:plain

その場合にはその区間を再度分割し片方の解答を反転させて再度スコアを計算します。

分割して
f:id:simanman:20160622064350p:plain

片方を反転させて再計算
f:id:simanman:20160622064552p:plain

図ではスコアが上昇したのでもう片方の領域については何も行いませんが、もし、スコアが低下した場合はもう片方の領域を反転させます。(その場合は正確なスコアの取得は行わず予測スコアを計算します

感想

シンプルな問題でしたが色々考察しがいのある問題でした。問題の環境としてtesterがもうちょっと充実していると良かったです。あと、提出間隔に制限が無いのはいいですね。