go のパッケージで特定の型のメンバをもった構造体が定義されていないことを確認したい
モチベ
swagger 定義から go client を生成するときに、 type: "number" はデフォルトでは float32 型として定義される。これは type: "number", format: "double" とすることにより float64 型に変更可能である。
該当プロジェクトでは精度的な観点から float64 を使うことが望ましかった1。定義ファイルの変更は完了したが、生成したクライアントライブラリが float32 型を含まないことを確認したくなったので静的に解析することにした。
制約
swagger による go client は構造体のメンバの型に alias された型を使わないのでその前提とする。すなわち type f32 float32 のようなことは起きないものとする。
また構造体のメンバのみに限定し、関数のシグネチャや定数・変数の類も気にしないことにする。
実装
以下のようなコードになる
func TestType(t *testing.T) { subPackage := "pkgname" set := token.NewFileSet() packs, err := parser.ParseDir(set, subPackage, nil, 0) if err != nil { t.Fatal("Failed to parse package:", err) } for _, pack := range packs { for path, f := range pack.Files { tokenFile := set.File(f.Pos()) bs, err := ioutil.ReadFile(path) if err != nil { t.Fatal(err) } for _, d := range f.Decls { if g, ok := d.(*ast.GenDecl); ok { if g.Tok == token.TYPE { for _, v := range g.Specs { if ts, ok := v.(*ast.TypeSpec); ok { if st, ok := ts.Type.(*ast.StructType); ok { for _, f := range st.Fields.List { bp := tokenFile.Position(f.Pos()) ep := tokenFile.Position(f.End()) s := string(bs[bp.Offset:ep.Offset]) if strings.Index(s, "float32") >= 0 { t.Errorf("should not contain float32 type at %s:%d", tokenFile.Name(), bp.Line) } } } } } } } } } } }
今後の課題
ioutil.ReadFile は必要になるまで呼び出しを遅延したほうがよいのだろうが面倒なので必ず読むようにしている。これはまあやたらファイル数が多くなければ問題にならないだろう。
最終的に strings.Index で判定しているのがダサいので別の手法を試したい。
-
本当は decimal がほしいので10進数表現の文字列がほしいのだが↩
Ruby でリファクタリングをした際にテスト要否を判断したい
TL; DR
- rubocop の自動修正とかが正しいのか不安になる
- Ruby なら ISeq に差分があるか調べればよい
- line number, column number 問題は本体に手をいれておけばある程度乗り越えられる
前提
$ ruby -v ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin17] $ bundle exec rubocop -V 0.59.2 (using Parser 2.5.1.2, running on ruby 2.5.1 x86_64-darwin17)
モチベ
rubocop には自動修正機能がついているわけですが、実際に rubocop のソースを読んでいない身としては盲信するわけにもいかない、というつらいところがあります。日々活発に追加される cop の中にはもしかしたらバグっているのもあるかもしれません。そうするとプロダクションコードにえいやでいれるにはちょっと気がひけるところがあったりなかったりします1。
ですので上で紹介した記事のように、言語処理系がどのようにソースコードを捉えているのかという観点から auto correct による変更の安全性を確かめたいと思います。
コンセプト
Ruby script を実行する場合には ソースコード -> AST -> ISeq ( instruction sequence ) と変換されてから YARV が ISeq 実行するようになっています2。
ruby コマンドには --dump=insns という便利なオプションがあり ISeq を(比較的)人間に読みやすい表現で確認することができます。今回はこの --dump=insns の結果をもとに安全性を担保します。
$ ruby -e 'puts 1' 1 $ ruby -e 'puts 1' --dump=insns == disasm: #<ISeq:<main>@-e:1 (1,0)-(1,6)>============================== 0000 putself ( 1)[Li] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave
実践
簡単なケース
まずは以下のような簡単な例からいきます。
# frozen_string_literal: true class Foo def foo puts 1 end end
puts と 1 の間に2スペース入ってますね。さて、この状態の --dump=insns の結果は以下になります。
== disasm: #<ISeq:<main>@sample1.rb:1 (1,0)-(7,3)>====================== 0000 putspecialobject 3 ( 3)[Li] 0002 putnil 0003 defineclass :Foo, <class:Foo>, 0 0007 leave == disasm: #<ISeq:<class:Foo>@sample1.rb:3 (3,0)-(7,3)>================= 0000 putspecialobject 1 ( 4)[LiCl] 0002 putobject :foo 0004 putiseq foo 0006 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache> 0009 leave ( 7)[En] == disasm: #<ISeq:foo@sample1.rb:4 (4,2)-(6,5)>========================= 0000 putself ( 5)[LiCa] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave ( 6)[Re]
今回の本旨とは外れるので内容は飛ばします。 ruby --dump=insns sample1.rb | md5とかして md5 hash をとっておくと eac204585dcd059cbf333c3f6681d59e でした。
さて、rubocop に autocorrect してもらうとどうなるでしょうか。
$ bundle exec rubocop -a (snip)
diff --git a/iseq-diff/sample1.rb b/iseq-diff/sample1.rb index 97256e1..f847a3d 100644 --- a/iseq-diff/sample1.rb +++ b/iseq-diff/sample1.rb @@ -2,6 +2,6 @@ class Foo def foo - puts 1 + puts 1 end end
スクリプトの中身は変わっていますが、前後でハッシュ値が変わってないので YARV に渡される AST は変わらないことがわかります。
$ ruby --dump=insns sample1.rb | md5 eac204585dcd059cbf333c3f6681d59e
このケースはこれでおk
難しいケース
先程掲載された insns を見ていると謎の数値がいくつかでてきます。
sample1.rb:1 (1,0)-(7,3)
0000 putspecialobject 3 ( 3)[Li]
このうちいくつかはソースファイルにおける行番号・列番号を示しています。
そのため、以下のようなファイルでは --dump=insns の結果が変わってしまいます。
# frozen_string_literal: true puts 1
$ ruby --dump=insns sample2.rb == disasm: #<ISeq:<main>@sample2.rb:1 (1,0)-(3,7)>====================== 0000 putself ( 3)[Li] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave $ bundle exec rubocop -a (snip) $ git diff sample2.rb diff --git a/iseq-diff/sample2.rb b/iseq-diff/sample2.rb index 851def2..946ef90 100644 --- a/iseq-diff/sample2.rb +++ b/iseq-diff/sample2.rb @@ -1,3 +1,3 @@ # frozen_string_literal: true -puts 1 +puts 1 $ ruby --dump=insns sample2.rb == disasm: #<ISeq:<main>@sample2.rb:1 (1,0)-(3,6)>====================== 0000 putself ( 3)[Li] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave
(1,0)-(3,7) と (1,0)-(3,6) で差異があります。これは (lineno,colno) の組み合わせです。評価したブロックを構成する token について、の最初の token の開始位置と最後の token の終了位置が示されているので、こういった最後の token の終了位置がずれる変更については差分が出てしまいます。
また改行があったときには ( lineno)[LI] のような表記が現れます。しかし行の変更はほとんどのケースにおいて意味がないので検知したくありません(後述)。そこで ruby コマンドによって --dump=insns で表示される情報から lineno, colno の情報を抜いてしまうことにします。
以下コードリーディングしたときの雑な流れです。
- 起動時のオプションを判断して分岐がありそうなので
insnsで grep してDUMP_BIT(insns)がそのフラグっぽいことを突き止める - ruby.c の中で
rb_io_write(rb_stdout, rb_iseq_disasm((const rb_iseq_t *)iseq));がDUMP_BIT(insns)を使った分岐の中にあるのでrb_iseq_disasmが出力を形作る本体であろうと予想をつける rb_iseq_disasm_X系の中でなんとなくそれっぽいところを変えていく。
実際の diff としてはこうなります。不要な [Li] あたりのコメントアウトと、(lineno, colno) を全部 (1, 1) に置き換えの2点。
diff --git a/iseq.c b/iseq.c index 831a9e8109..a25b179178 100644 --- a/iseq.c +++ b/iseq.c @@ -1895,15 +1895,15 @@ rb_iseq_disasm_insn(VALUE ret, const VALUE *code, size_t pos, } } - { - unsigned int line_no = rb_iseq_line_no(iseq, pos); - unsigned int prev = pos == 0 ? 0 : rb_iseq_line_no(iseq, pos - 1); - if (line_no && line_no != prev) { - long slen = RSTRING_LEN(str); - slen = (slen > 70) ? 0 : (70 - slen); - str = rb_str_catf(str, "%*s(%4d)", (int)slen, "", line_no); - } - } +// { +// unsigned int line_no = rb_iseq_line_no(iseq, pos); +// unsigned int prev = pos == 0 ? 0 : rb_iseq_line_no(iseq, pos - 1); +// if (line_no && line_no != prev) { +// long slen = RSTRING_LEN(str); +// slen = (slen > 70) ? 0 : (70 - slen); +// str = rb_str_catf(str, "%*s(%4d)", (int)slen, "", line_no); +// } +// } { rb_event_flag_t events = rb_iseq_event_flags(iseq, pos); @@ -1965,11 +1965,11 @@ iseq_inspect(const rb_iseq_t *iseq) const rb_code_location_t *loc = &body->location.code_location; return rb_sprintf("#<ISeq:%"PRIsVALUE"@%"PRIsVALUE":%d (%d,%d)-(%d,%d)>", body->location.label, rb_iseq_path(iseq), - loc->beg_pos.lineno, - loc->beg_pos.lineno, - loc->beg_pos.column, - loc->end_pos.lineno, - loc->end_pos.column); + 1, // loc->beg_pos.lineno, + 1, // loc->beg_pos.lineno, + 1, // loc->beg_pos.column, + 1, // loc->end_pos.lineno, + 1); //loc->end_pos.column); } }
実行しないならば外部ライブラリは不要なので miniruby で十分です。 make miniruby してできたバイナリを用いて比較していきます。
$ path/to/miniruby --dump=insns sample2.rb | md5 3d80188a91c6d6c6c84f2520b77a43f0 $ rubocop -a (snip) $ git diff sample2.rb diff --git a/iseq-diff/sample2.rb b/iseq-diff/sample2.rb index 851def2..946ef90 100644 --- a/iseq-diff/sample2.rb +++ b/iseq-diff/sample2.rb @@ -1,3 +1,3 @@ # frozen_string_literal: true -puts 1 +puts 1 $ path/to/miniruby --dump=insns sample2.rb | md5 3d80188a91c6d6c6c84f2520b77a43f0
一致しましたね！一応手元ではもう少し難しそうな以下のようなファイルでも差分が出ないことを確認しています。
class Foo # todo: nya-n def no_body end def show(_mode) if _mode; puts :a else puts 1 || 2; end end end module Main end def Main.exec Foo.new.show(false) end Main::exec
diff --git a/iseq-diff/sample3.rb b/iseq-diff/sample3.rb index 1cd1af4..6b946e1 100644 --- a/iseq-diff/sample3.rb +++ b/iseq-diff/sample3.rb @@ -1,10 +1,11 @@ +# frozen_string_literal: true + class Foo - # todo: nya-n - def no_body - end + # TODO: nya-n + def no_body; end def show(_mode) - if _mode; puts :a else puts 1 || 2; end + _mode ? (puts :a) : (puts 1 || 2) end end @@ -14,4 +15,4 @@ def Main.exec Foo.new.show(false) end -Main::exec +Main.exec
課題
このアプローチにはいくつかの問題点があります。まず、Ruby スクリプトにおいて行番号は、意味のない情報ではありません。例えばみなさんが大好きな Tracepoint の line イベントに影響があります。まあ Tracepoint をプロダクションコードで使うケースは稀だとは思いますが3。
しかし、ぱっと思いついたものでも __LINE__ についての影響は実際のアプリケーションにも影響がありそうです。
$ cat a.rb __LINE__ $ cat b.rb __LINE__ $ path/to/miniruby --dump=insns a.rb == disasm: #<ISeq:<main>@a.rb:1 (1,1)-(1,1)> (catch: FALSE) 0000 putobject 2[Li] 0002 leave $ path/to/miniruby --dump=insns b.rb == disasm: #<ISeq:<main>@b.rb:1 (1,1)-(1,1)> (catch: FALSE) 0000 putobject 3[Li] 0002 leave
__LINE__ は行番号に変換されますが、これはなんとASTの時点で NODE_LIT に変換されています4。そのためディスアセンブルした結果を表示する箇所をいかにいじろうとも無力です。しかも実際にメタプロの現場では __LINE__ を使う書き方は頻出です。下記の記事が仕様と __LINE__ を使うメリットについてよくまとまっています。
また、実行時のバイナリと違うバイナリで比較して意味あんのか、という観点でも課題があります。
これから
ISeq を比較するという手法である限り、__LINE__ などの課題に対して有効な解決策はなさそうです。
一方でバイナリ違う問題については、 RubyVM::AST を用いることで ruby コマンドに手を入れなくても評価可能なのではないか？と思っています。未着手ですけど。「Ruby 本体で AST の等値性を保証してくんねーかなー」という気持ちもありますが、「等値性」がこの場合においては一般的ではないので、自分で 「 lexical な差異には目をつむって、ほかはなんとなくあってそうなの」という評価をするしかなさそうですね。
-
ゆーて大丈夫だとは思っていますが。現実的に払えるコストなら払っていいんじゃないの、という気持ち↩
-
このへんは『Rubyのしくみ Ruby Under a Microscope』 などをどうぞ。↩
-
事例があったら知りたいのでささよろです↩
-
--dump=paで確認可↩
オフラインリアルタイムどう書く E27 の解答例
問題 : http://nabetani.sakura.ne.jp/hena/orde27cardgame/
実装リンク集 : https://qiita.com/Nabetani/items/cdc102d186faaf542574
久々に勝ちました。
割と素直な実装です。計算量的に大丈夫かかなり不安だったけど結構すぐだった。
8枚のうち、ストーリーとカインドは2個のまとまりが必要なので枚数でいうとパターンが少ない。列挙すると以下の通り。
patterns = [ [8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2], ]
この枚数にたいしてストーリーあるいはカインドをつくって抜いて、と再帰すればよい。
初期実装は再帰じゃなくて if の羅列になってて結構汚いです。
リファクタリングしたほう
TaPL読書録 #6
前回:
今回は7章、8章。
7章は実装章である。個人的には小ステップの実装をするところまでで終わり。大ステップには変換しなかった。もうひとり書いてきた人のと小ステップ・大ステップでの差異をかるく比較して終わり。実装したのは2人だったが、「実装したからといって理解したとは限らない」のであった。
8章からは「型つき算術式」ということでようやく型がついた。長く苦しい戦いだった(マジ)
以前は「行き詰まり状態」というものを導入して評価をとめていたが、それらを実行前に静的に解釈して行き詰まり状態であることを検査したい。そのため型 Nat, Bool を導入する。
検査は「保守的」に行われることに注意。すなわち if 項 if t1 then t2 else t3 において、 t1 が「明らかに」真である場合にも t3 の型情報も用いる、という話である。ここでは t2 と t3 についてユニオンしたような型の導入は行わない1
補題8.2.2.「型付け関係の逆転」
逆転が成り立つのは、ある値が複数の型に解釈される可能性がないからである。すなわち 1 が型 Nat であり、かつ型 Rational でもあるような値が今の所存在しないことが前提となっている。これは定理 8.2.4. 「型の一意性」にて言及されている。
演習8.2.3.
「正しく片付けされた項」の「正しく」ってなんだっけ、というメモがあったが定義 8.2.1 に「項 t にたいしてある型 T が存在して t: T となるとき t は型付け可能(または正しく型付けされている)という」と書いてあった。
解答してはだいたい自明で、筆者のメモでは「規則に従ってるので規則が正しく型付けされていること・保守的に評価することを考えたら自明」とある。はい。おそらく正式に書く場合には逆転補題についてそれぞれ追えばよい。
定理8.2.4「型の一意性」
余談として部分型(で合ってたか少し自信がないが)についての話が出てきた。以下のようなクラス、関数を考える。記法は独自文法であるが意味はおそらくとれるとおもう2。
class A x: int end class B x: int y: int end func f(a: A) -> int return a.x * 2 end
上記の関数 f について、仮引数 a として B のインスタンスをいれることが可能なのか、という話。この場合 B ⊂ A なので、使えてもいいよね、という話をした。
ここでダイヤモンド継承の話もした。ダイヤモンド継承をして同名メソッドがあったときには、シグネチャさえ同じならば型システム的にはおkになりそうだよねー、実装的にはどっちにとぶか決められなくてつらそうだよねーなど。
8.3.
型の安全性とは進行と保存である。
演習 8.3.4. スキップ
演習 8.3.5.
俺のメモでは pred 0 で行き詰まるので pred nv の nv は「0 ではない numeric value」という型情報をもたないと型システムが健全じゃなくなるので無理、と書いてあった。
演習 8.3.6.
良問では？という話になった。
メモでは「型付けされていて、型が2つしかないから保存の定理の対偶から明らか」とあるが、実際のところは if true then 0 else false みたいな項が反例となる。
演習 8.3.7.
大ステップにおける「最終的に値になる」という制約が強いのだなあ、ということを確認して終わり。
次回 chap9 全部。
読了: Clean Architecture 達人に学ぶソフトウェアの構造と設計
『Clean Architecture 達人に学ぶソフトウェアの構造と設計』を読み終えたので感想です。
なにか新しいことが書いているというわけではなく、ちゃんと依存関係について考えようねという本だと捉えている。ソフトウェア設計の原則を、クラスなどの細かい粒度からもっと粗いパッケージ・サービスの粒度まで適用して俯瞰することができた。
悪書だとは思わないが、特にめちゃくちゃよい本だとも思わなかった。普通のことを「丁寧に」書いているような印象。個人的には逆にくどく感じられ、ざっと流し読み、というスピードで読了した。
さて、本書では「依存関係を整理しろ」ということを具体例を挙げて話していた。しかし普段は Ruby で書くことが多く、パッケージ・あるいはクラスに対する依存が不明確になりがちである。例えば require した場合に定数はグローバルにロードされるため、あるファイル内で何に依存しているのかということは人間としても機械としても(ツールを用いても)不明瞭になりがちである。
require 'foo' require 'bar' Baz.new
例えば上記スクリプトでは Baz について fooで require したのか、 bar で require したのか、あるいはこのファイルを実行する側で require / 定義されたのかわからない。そもそも Baz がオープンクラスされている可能性もあり、上記すべてで定義されている可能性もある。
一方で Go などであれば、別パッケージで定義されたものはパッケージ名から引かなければならず、依存は明示される。ツールにやさしい1。
package main import "fmt" func main() { fmt.Println("Hello") // fmt パッケージへの依存が明確 }
これを考えると Ruby において依存関係の整理をやろうとするのは難しいような気がする。RoR がそういったフレームワークでないという話もあるが。なお、本書の中では「アーキテクチャまで決めるようなフレームワークに依存するな」という趣旨の主張も記載されていた2。
また、別の大きな主張として「システムとしての詳細に依存するな」というのも挙げられる。具体的にはDBとかである。これに関しても「せやな〜」という気持ちはある一方でDBやミドルウェアの特性にひどく依存したシステムというのもあるような気がしていて、それをパッケージとしてまとめて覆い隠すのは少しむずかしいような気もした。これに関してはちょうど go でなんやかんや書く機会があるので実践してみようと思う。
他には、マイクロサービスへの言及もあり「サービスとして切り出しただけで依存が切れると思ったら大間違いだぞ」という話があってほっこりした。一方で「週次ビルド」についての言及もあり、時代を感じさせるものでもあった。
Rails におけるパフォーマンス検証パターン: action 抜けた後が遅いケース
TL; DR
- アクション抜けたあとは action の callback, rendering, rack middleware の世界
- おもそうなものを特定して抜こう
- bullet は重いぞ
事象
新機能開発中に、大量データ突っ込むか〜と思って突っ込んで開いたらまあ全然返ってこない。
はあ、まあそういうこともありますわよねと思って見ていたら、実はアクションから抜けるところまではそこそこの速度で終わることがわかった。1
調査
とゆーことは action 後に呼ばれる処理があやしい。 after_action はざっと確認した感じあんまりなさそうだった。2
ていうかそもそも rails log でも rendering xx sec と出ているのでレンダリングも終わっていることがわかった。
というわけでレスポンスを書き終わったはずなのにまだナニカをする層、つまり middleware があやしいということがわかる。
以下を参考に middleware ごとの経過時間を見ておく
http://blog.mirakui.com/entry/2012/04/03/slow-middleware
元コードは alias_method_chain を使っているので prepend に書き直してみた
増加時間が長いやつを探す。今回は bullet が悪そうだった。業務アプリなのでログは載せないでおく。
とりあえず disable すればいいかなと思って設定変更したらはやくなったことを確認。
bullet は本番ではオフになるので特に問題にならないはずだなーというところまで考えて調査終了。
オフラインリアルタイムどう書くE27の参考問題の実装例(Rust)
オフラインリアルタイムどう書くE27の参考問題「灯りと鏡」の実装例です。オフサイトだし Rust やるかあとおもって書きました。
問題 : http://nabetani.sakura.ne.jp/hena/orde27ligmir/
実装リンク集 : https://qiita.com/Nabetani/items/0b2f459ec128c89948f4
10/6 のイベント : https://yhpg.doorkeeper.jp/events/79705
NOTE: コードは末尾にも載せています。
問題自体はそんなに難しくなくて、素直にやれば素直に解けると思います……といいつつハマった点を2つ。
1つは、反射したらなんか、時計回りにまわるもんだと思っててあれー？ってなってました。これはただのアホでたぶん俺だけだと思う。
もう1つは、無限ループですね。どう示すか迷って、とりあえず座標 + 方角で HashSet つくって、入ってるか確認して、とやりました。一回通した後に「いや、これ各マスについてbitでフラグ立てればええやん」と思い直して今の実装に。おかげで sort する手間が省けていいです。
完全に Rust に不慣れなせいでいくつか困っています。
- char どうやって変換するのがいいんだろ( from_digit でやってる
- usize こんなに使ってていいんか？ index 指定するために使ってるけど
- consume 扱いになるとめんどいから参照で取得してるところがあるんだけどそれでいいのかわからない
- 参照でもったあとリテラルの参照と比較するような書き方をするハメになっていてほんまか？という気持ちが
あと書いてて思ったんですが borrow 難しいですね……。なんかの struct にメソッドはやして破壊的にーとかやるとだいたい死ぬ。俺が悪い気はしている。Rust においてどういうふうに書くのがきれいなのかよくわからないなあと思いながらやっています。
最初に通すまで 2.5h くらいかかってますが Rust のリファレンスめっちゃ見てたのでRuby でやったら勝てた気がする。オンサイト時はおとなしく Ruby を使います。
use std::fmt; use std::char; use std::iter::FromIterator; struct Field { f: [[Cell; 5]; 5], y_idx: (usize, usize), } #[derive(Eq, PartialEq, Debug, Clone)] enum Direction { N, E, S, W, } impl Direction { fn dir_flag(d: &Direction) -> i32 { match d { Direction::N => 1, Direction::E => 2, Direction::S => 4, Direction::W => 8, } } } struct RayResult { from: (usize, usize), dir: Direction, stopped: bool, passed: [[i32; 5]; 5], } fn coor_to_char(coor: (usize, usize)) -> char { let idx = coor.0 + coor.1 * 5; match char::from_digit(10 + idx as u32, 36) { Some(s) => return s, None => panic!("Cannot convert coor: ({}, {})", coor.0, coor.1), } } impl Field { fn set(&mut self, cell: Cell, x: usize, y: usize) { if cell == Cell::Y { self.y_idx = (x, y); } self.f[y][x] = cell; } fn start(&self) -> Vec<char> { let mut res = RayResult { from: self.y_idx, dir: Direction::N, stopped: false, passed: [ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], ], }; res.passed[self.y_idx.1][self.y_idx.0] = res.passed[self.y_idx.1][self.y_idx.0] | Direction::dir_flag(&Direction::N); let mut f = res.stopped; while !f { // println!("now: ({}, {})", res.from.0, res.from.1); res = self.process(res); f = res.stopped; } let mut vec = Vec::new(); for (y, r) in res.passed.iter().enumerate() { for (x, f) in r.iter().enumerate() { if f != &0 { let c = coor_to_char((x, y)); vec.push(c) } } } return vec } fn process(&self, mut res: RayResult) -> RayResult { let coor = match res.dir { Direction::N => (res.from.0 as i32, res.from.1 as i32 - 1), Direction::E => (res.from.0 as i32 + 1, res.from.1 as i32), Direction::S => (res.from.0 as i32, res.from.1 as i32 + 1), Direction::W => (res.from.0 as i32 - 1, res.from.1 as i32), }; let oc = self.pick(coor.0, coor.1); if oc.is_none() { return RayResult { from: res.from, dir: res.dir, stopped: true, passed: res.passed, } } let c = oc.unwrap(); let new_dir = Cell::reflect(c, res.dir); let new_x = coor.0 as usize; let new_y = coor.1 as usize; let flag = Direction::dir_flag(&new_dir); if res.passed[new_y][new_x] & flag != 0 { return RayResult { from: (new_x, new_y), dir: new_dir, stopped: true, passed: res.passed, } } if c != &Cell::X { res.passed[new_y][new_x] = res.passed[new_y][new_x] | flag; } return RayResult { from: (new_x, new_y), dir: new_dir, stopped: c == &Cell::X, passed: res.passed, } } fn pick(&self, x: i32, y: i32) -> Option<&Cell> { if x >= 0 && x < 5 && y >= 0 && y < 5 { return Some(&self.f[y as usize][x as usize]) } return None } } #[derive(PartialEq, Debug)] enum Cell { X, // x: 光を吸収するマス。 D, // .: なにもないマス。光を通す。 R, // 1: 「╱」という向きの鏡。 L, // 0: 「╲」という向きの鏡。 Y, // Y: あなた。 } impl fmt::Display for Cell { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { match self { Cell::X => write!(f, "X"), Cell::D => write!(f, "D"), Cell::R => write!(f, "R"), Cell::L => write!(f, "L"), Cell::Y => write!(f, "Y"), } } } impl Cell { fn reflect(c: &Cell, dir: Direction) -> Direction { if c == &Cell::R { // println!("reflect by {}", c); // R == / return match dir { Direction::N => Direction::E, Direction::E => Direction::N, Direction::S => Direction::W, Direction::W => Direction::S, } } else if c == &Cell::L { // println!("reflect by {}", c); // L == \ return match dir { Direction::N => Direction::W, Direction::E => Direction::S, Direction::S => Direction::E, Direction::W => Direction::N, } } else { dir } } } fn new_field() -> Field { Field { f: [ [Cell::Y, Cell::X, Cell::X, Cell::X, Cell::X], [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X], [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X], [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X], [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X], ], y_idx: (0, 0) } } fn solve(input: &str) -> String { let row_strs = input.split("/"); let mut field = new_field(); for (y, row_str) in row_strs.enumerate() { for (x, c) in row_str.chars().enumerate() { let cell = match c { 'x' => Cell::X, '.' => Cell::D, '1' => Cell::R, '0' => Cell::L, 'Y' => Cell::Y, _ => panic!("Invalid input: {}", input), }; field.set(cell, x, y); }; } let tmp = field.start(); return String::from_iter(tmp) } fn test(input: &str, expected: &str) { let actual = solve(input); if actual != expected { println!("ng\n actual: {} \nexpected: {}", actual, expected); } else { println!("ok!"); } } fn main() { test( "x...x/.1.0./..0../.Y.../0..x.", "ghilnqs" ); test( "..Y../...../...../...../.....", "c" ); test( "..x../..Y../...../...../.....", "h" ); test( "..Y.x/..1x0/11.../....0/1..1.", "c" ); test( "....1/....Y/...../...../.....", "ej" ); test( ".10../x.1../x.1x./.Y.1./...0.", "bcghlq" ); test( "0.x10/00..x/x0x.0/....0/...Y1", "deinsx" ); test( "1.01./01Y.1/..1.1/..10./0.0..", "abcfgh" ); test( "x..../x1x../0...0/....Y/.1..0", "klmnot" ); test( "...../..10./.1Y1./.01../.....", "hilmnqr" ); test( "...../..10./x.11./...../..Y..", "hilmnrw" ); test( "...../x.10x/...../x.Y1x/.....", "himnqrs" ); test( "..010/...Y1/..0../0.x../.....", "defghij" ); test( "1.0../...../.0x../Y.1x./..1..", "abcfhkp" ); test( "...../101../0.0../..Y../.....", "fgklmqrv" ); test( "1.0../00.../.x..0/0.Y1./...10", "abcfghmr" ); test( "x101./1..../.Y.x./..01./.00.1", "bcghlmrs" ); test( "x11../x.x../.0.01/..x../...Y.", "bcglmnsx" ); test( "..1.0/x0.x./0.0../x...Y/.10.1", "cdehjmnot" ); test( "..x.0/.0.../1..0x/1..1./Y.00.", "klmnpqrsu" ); test( "0.1.0/.0.xY/0...0/01..1/x00.x", "cdehjmrwx" ); test( "...0./.0.0./..101/...10/..01Y", "mnpqrstwxy" ); test( "10..0/.Y.0./0..1./....x/000..", "abfghiklmn" ); test( "10..1/...../.1010/110.1/x..Yx", "lmnopqrstx" ); test( "110../....1/x1..x/0.0.0/....Y", "bcghlmrsty" ); test( "x.101/1..../..001/010Yx/..1.1", "cdehijmnos" ); test( "x.111/x10../...0./00.1x/x.Y.1", "ghklmnqrsw" ); test( "11.../....0/11..1/1.1../.Y..1", "fghijlmnoqv" ); test( "...x1/.1.0./11.1./.01../Y..x.", "cghiklmnpqru" ); test( ".0.../110x./11..0/01.x./..Y.x", "ghklmnopqrtw" ); test( ".01.0/.110x/0...0/.01Y./x.1x.", "cdeghilmnqrs" ); test( ".1100/..1.0/1.11Y/0..1./.0..0", "hijklmnopqrs" ); test( "1..00/..11./.100./1..Y1/.....", "abcdfhikmnps" ); test( "1.0../.11x0/.00.x/Y.10./.10x0", "abcfghklmpqr" ); test( "11110/11.../.x.../.0111/0.Y0.", "deijnorstwxy" ); test( "...1./.1.0x/10..0/0Y.11/.0.x0", "ghiklmnopqrst" ); test( "...10/x111./0x.11/.0.../0.0Y.", "dehijmnorswxy" ); test( ".1x../.x1.0/0x.x./x11.1/x0Y.1", "hijmoqrstvwxy" ); test( "x.x../x110./1.1.0/0.Y.1/0.00x", "hiklmnopqrstx" ); test( "...0./11.00/10..x/..0.1/Y0.10", "ghiklmnpqsuvwx" ); test( ".110./....0/x..../.0001/11.Y.", "cdfghijmnorstx" ); test( "1.00./....1/.1.../0...0/0..1Y", "abcfhkmpqrstwy" ); test( ".1.01/..x../..100/..Y../...01", "bcdgilmnoqrstvxy" ); test( "1...0/Y..../...../...../0...1", "abcdefjkoptuvwxy" ); test( "x1..0/1..0./.Yx../0...1/.0.1.", "bcdefghijklnopqrstvwx" ); test( "1...0/.1.0./..1../..01./Y0..1", "abcdefghijklmnopqrstuvwxy" ); }
