オフラインリアルタイムどう書く E29 の回答 (Golang)
問題 : http://nabetani.sakura.ne.jp/hena/orde29unes/
実装リンク集 : https://qiita.com/Nabetani/items/f2db9b916c0a301b744f
勝ちました。珍しく Golang で。
なんかかっこいいやり方あんのかなーと思ったけど、1文字ずつ素直に読んでけばいいやって感じに。こういうの1文字ずつ読んでなんかの区切りで返すのって lexer だよねって思ってそんな名前にしております。TaPLの言語を実装している経験が役にたっている。
l.cur += 2
のところは slash
の mode を用意すればいいということを他の人の回答から学んだ。なるほど。
byte リテラルの書き方がわからなくてなんかアレな感じになっている。
package e29 import ( "errors" "fmt" "strings" ) type lexer struct { cur int text string mode lexerMode } type lexerMode int32 const ( normal lexerMode = iota singleQuote doubleQuote ) var slashByte, dQuoteByte, sQuoteByte byte var validChars = []byte("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\"'/") const noAnswer = "-" type result struct { output string err error } func init() { tmp := "/\"'" slashByte = tmp[0] dQuoteByte = tmp[1] sQuoteByte = tmp[2] } func solve(input string) result { l := lexer{text: input} var tokens []string for l.Next() { token, err := l.NextToken() if err != nil { return result{output: noAnswer, err: err} } tokens = append(tokens, token) } if l.mode != normal { return result{output: noAnswer, err: errors.New("unterminated quote")} } if len(tokens) == 0 { return result{output: noAnswer, err: errors.New("no entries")} } output := strings.Join(tokens, ",") return result{output: output, err: nil} } func (l *lexer) Next() bool { if l.cur == len(l.text) { return false } return true } func isValidByte(b byte) bool { for _, bb := range validChars { if b == bb { return true } } return false } func (l *lexer) NextToken() (string, error) { var ret []byte beg := l.cur loop: for { if l.cur >= len(l.text) { return "", errors.New("idx") } c := l.text[l.cur] if !isValidByte(c) { return "", fmt.Errorf("invalid char: %v", string(c)) } switch c { case slashByte: if l.mode == normal { if l.cur+1 == len(l.text) { // 終わり return "", errors.New("should not end with /") } if l.text[l.cur+1] == slashByte { // スラッシュ2個のパターン ret = append(ret, c) l.cur += 2 } else { l.cur++ break loop } } else { // quote 中は / として扱う l.cur++ ret = append(ret, c) } case dQuoteByte: if l.mode == normal { l.mode = doubleQuote l.cur++ } else if l.mode == doubleQuote { l.mode = normal l.cur++ } else if l.mode == singleQuote { l.cur++ ret = append(ret, c) } case sQuoteByte: if l.mode == normal { l.mode = singleQuote l.cur++ } else if l.mode == doubleQuote { l.cur++ ret = append(ret, c) } else if l.mode == singleQuote { l.mode = normal l.cur++ } default: l.cur++ ret = append(ret, c) } if l.cur == len(l.text) { break loop } } entry := string(ret) if entry == "" { return "", fmt.Errorf("entry should not be blank %d-%d", beg, l.cur) } return entry, nil }
Rails で全部のモデルについて何かの処理をしたい
eager_load = true にした上で ↓ のスクリプトを bundle exec rails r
する
ar_classes = [] ObjectSpace.each_object do |obj| next if obj.class.name.to_s != 'Class' if obj.ancestors.include?(ActiveRecord::Base) && obj != ActiveRecord::Base ar_classes << obj end end # 本体の処理
今回は実際にはテーブル名がほしかったのでこんな処理を。
table_names = ar_classes.map do |klass| klass.respond_to?(:table_name) && klass.table_name end puts table_names.compact.sort
SwitchPoint
使ってるとそれの子供が釣れるみたいだけど気にしない。
Rails だったら descendants 使う方が良さそう
— たにみち (@ttanimichi) 2018年11月29日
完全にせやな、であった
読了: 『ドラゴンクエストXを支える技術ーー 大規模オンラインRPGの舞台裏』
読み終えました。ざっと俯瞰する感じで面白かった。とても深いところがあったりとかめっちゃ参考になる〜みたいな本ではないです。タイトルどおり、まさに舞台裏を教えてくれる本という感想でした。
自分のバックグラウンドとしてはweb系の業務システムをやってきていて、webで継続的にサービスを提供することについてはある程度理解がある。一方でゲーム系は全くやっていないので全然わからない。本書ではコンシューマーゲームの売り切りをやってきた人が多い中でMMORPGをサービスとして提供していくことについて描かれている点が多かったように感じた。そういった対比は、サービス提供するということの特徴の再確認と、売り切りゲームの特徴を学ぶという点でなかなかおもしろかった。
3Dの計算などの負荷量はあまりよくわからないのだが、負荷系ではスレッドは活用しないという判断をした点、全部永続化はきついのでKVSを併用してる点などが記憶に残っている。といってもそうだろうねえというくらいの感想でしかないが。
ゲームをつくっていくという点については Lua のスクリプトとの二段構成というのが実際どういうもんなのかというのがなんとなく理解できてよかった。大規模ゲームを支えているだけあってツール類が手厚いのもなるほど、という感じがあった。
macOS Mojave + nasm の Hello world
nasm の Hello world 記事はそこそこあるもののコピペで動かなかったのでメモ。
TL;DR
- エントリポイントは
start
ではなくて_main
という名前にしておく - ld コマンドに
-lSystem
と-macosx_version_min 10.13
を指定しておく
前提
- macOS Mojave 10.14.1
uname -m
->x86_64
書いたやつ
GLOBAL _main SECTION .text _main: mov rax, 0x2000004; mov rdi, 1; mov rsi, hello_world; mov rdx, 13; syscall; mov rax, 0x2000001; mov rdi, 0; syscall; SECTION .data; hello_world db "Hello World", 0x0a;
hello.out: hello.o ld -lSystem -o hello.out -macosx_version_min 10.13 hello.o hello.o: hello.asm nasm -f macho64 -o hello.o hello.asm
インターネット上にいろいろ落ちてるサンプルとの変更点は1つだけ。GLOBAL でアクセス可能にしているシンボル名が start
になっているのが多かったのだが、_main
にした。
これは ld
コマンド実行時にシンボルが見つからないんだが?と怒られたので変更。たぶん macOS 側の仕様が変わった?のかな?
Undefined symbols for architecture x86_64: "_main", referenced from: implicit entry/start for main executable ld: symbol(s) not found for inferred architecture x86_64
また make コマンドにも -lSystem
と -macosx_version_min 10.13
を追加。これもわからなくてググったのだが以下のSOにたどり着いた。そしたらこいっちでも「 start
から _main
に変えてみたがまだだめなんだが」とのこと。start って名前はどこから来てるんですかねえ。
https://stackoverflow.com/questions/52830484/nasm-cant-link-object-file-with-ld-on-macos-mojave
$ ./hello.out Hello World
オフラインリアルタイムどう書くE28の実装例 ( Ruby )
オフラインリアルタイムどう書くE28の問題「増築の果ての隣室」の実装例を、Ruby で。
問題 : http://nabetani.sakura.ne.jp/hena/orde28sqst/
実装リンク集 : https://qiita.com/Nabetani/items/4e3fac2746ca05a93165
イベント : https://yhpg.doorkeeper.jp/events/81346
めちゃ面白いイベントなのに参加者すくなくて寂しいので参加者募集です!!!次回のイベントももう公開済みなのでぜひ。
負けました。正確には時間切れから発表中デバッグでバグを落としたけど計算量減らしてないのでNo30くらいまでしか通せず。家帰ってちょこちょこ直していまは通ってます。以下、ざっくり方針。
なんか計算で番号求められるんじゃね?って思ったんだけど、増築されていくごとに分割数が増えていくことにより、1辺の長さを割っていったもの(あるいはかけていったもの)が膨らんでいって、どうもさくっとは計算できなさそうだった。なので真面目に増築することにする。
Ruby なので有理数が扱えて最初の正方形の1辺を1としたときに4分割なら 1/4 、そのあと7分割なら 4/28 みたいな感じで考えていくと楽かも、と思った。ただどうも隣接の判定をミスりそうな気がしたので4分割したら最初の正方形の1辺を4、さらに7分割なら28と増やしていくことにした。Rubyなら扱いきれるだろ、みたいな雑な予想込みで。
んで、そうやってかけていった値をもとにすると、すべての部屋の辺の長さが整数で扱えるようになる。じゃあそのあとどうするのっていうと、 Hash{Integer => Hash{ Integer => Integer}}
みたいな型で盤面を用意してほんとに正方形を塗っていくことにした。配列にしてないのはSあるいはW方向への増築をすると x, y がマイナス側にいくかもだから。全く塗る必要はないのだが脳内デバッグが下手すぎて実際に塗ってたらなんかわかるようになってきた。実際発表中に debug モードで見せたりしてウケた1。
ただこれがとんでもなく遅い。そりゃ当然だということで全部塗るわけじゃなくて辺だけ塗るようにした。
でもこれも遅い。辺すら塗る必要ないよね、といって部屋の情報を貯め込むようにした。
これもまた遅い。これがなんで遅いのかというと隣接判定のところで r1.to_a & r2.to_a
的なことをやってたせいだった。そりゃそうだ。隣接判定のため、x座標的にあるいはy座標的に同じところにいるかどうか、みたいな判定。
def neighbor?(other) if h_match?(other) x2 == other.x1 || x1 == other.x2 elsif v_match?(other) y2 == other.y1 || y1 == other.y2 end end def v_match?(other) !((x1...x2).to_a & (other.x1...other.x2).to_a).empty? end def h_match?(other) !((y1...y2).to_a & (other.y1...other.y2).to_a).empty? end
重なりがあること、というのがうまく言語化できなかったのだが両手をピースにしてごにょごにょ動かしてたら、一方の始点がもう一方の終点より大きいケースがだめであることがわかった。というわけで最終形は以下。これは普通に返ってくる。 x1, x2, y1, y2 の計算あたりは正方形なので全然いらない情報なのだが一旦通ってるのでこのままで。
class Solver Instruction = Struct.new(:dir, :size) Sq = Struct.new(:num, :x1, :x2, :y1, :y2) do def cover?(x, y) x1 <= x && x <= x2 && y1 <= y && y <= y2 end def neighbor?(other) if h_match?(other) x2 == other.x1 || x1 == other.x2 elsif v_match?(other) y2 == other.y1 || y1 == other.y2 end end def v_match?(other) !((x2 - 1) < other.x1 || (other.x2 - 1) < x1) end def h_match?(other) !((y2 - 1) < other.y1 || (other.y2 - 1) < y1) end end class Board attr_reader :min_w, :max_w, :min_h, :max_h def initialize @min_w = 0 @max_w = 0 @min_h = 0 @max_h = 0 @sqs = [] end def fetch(x, y) @sqs.find { |e| e.cover?(x, y) }&.num end def neighbors(num) t = @sqs.find { |e| e.num == num } @sqs.select { |e| t.neighbor?(e) }.sort_by(&:num) end def rect(num, x1, x2, y1, y2) @min_w = x1 if x1 < min_w @max_w = x2 if x2 > max_w @min_h = y1 if y1 < min_h @max_h = y2 if y2 > max_h @sqs << Sq.new(num, x1, x2, y1, y2) end end def initialize @base = 1 # base_size end def solve(input) a, b = input.split('/', 2) @target = b.to_i @insns = a.chars.each_slice(2).map do |s| Instruction.new(s[0].to_sym, s[1].to_i) end @insns.each do |insn| @base *= insn.size end board = Board.new board.rect(1, 0, @base, 0, @base) n = 1 @insns.each.with_index do |insn, i| minw = board.min_w maxw = board.max_w minh = board.min_h maxh = board.max_h case insn.dir when :N, :S tmp_base = (maxw - minw) / insn.size else tmp_base = (maxh - minh) / insn.size end 1.upto(insn.size) do |d| case insn.dir when :N x2 = minw + (tmp_base * d) x1 = x2 - tmp_base y1 = maxh y2 = maxh + tmp_base when :S x2 = minw + (tmp_base * d) x1 = x2 - tmp_base y2 = minh y1 = minh - tmp_base when :E y1 = maxh - (tmp_base * d) y2 = y1 + tmp_base x1 = maxw x2 = maxw + tmp_base when :W y1 = maxh - (tmp_base * d) y2 = y1 + tmp_base x2 = minw x1 = minw - tmp_base end board.rect(n+d, x1, x2, y1, y2) end n += insn.size end board.neighbors(@target).map(&:num).join(',') end end
読了: 『Go言語による並行処理』
読みました。ちょっと駆け足気味だけど。
全体的に良書でこういったことが知りたかったんだということが書いてあってよかったです。一方で悪い点もほんのちょっとありました。先に悪いと思っている点について書いておこうと思います。
悪かったと思った点
まず、interface{}
型の利用は、うーん、やめたほうがいいんじゃないの、という感じです。まあこれは補遺Bにより訳者の方による go generate の利用の推奨などもありまあええやろって思いました。
また、 done
チャネルの利用は、context がある程度普及している昨今ではかえって混乱を招いたのではないかと思います。最初の1例は「お、これ context の本質を捉えてていいな」と思ったのですが。エラー処理も pkg/errors でよくね?と最初は思ったのですが、そちらはいろいろ学びがあったので、逆に done についての煩雑さが目についたというのもあります。
まあこれらはどちらも個人の趣味の範疇かもしれません。そんなに目くじら立てるようなことでもないでしょう。
これは本文とは関係ないのですが、DLしたPDFファイルの outline が iOS 上の GoodNotes というアプリでは部分的にしか解釈できてなかったようです。これはアプリ側の問題の可能性もありますが。ちょっと読書体験が悪かったです。
良かったと思った点
まず「並行」「並列」について。僕はこの本で出てきた説明が一番しっくりきました。曰く「並行性はコードの性質を指し、並列性は動作しているプログラムの性質を指」すとのことです。以前にはおそらく Rebuild.fm でささださん達が説明されていた回で聞いていたのですがその後あまり意識することがなくうろ覚えになっていました。今回のこの説明は結構すんなり納得できました。
エラー処理や流量制限については現在 go でなにかを書いてる身としては参考になりました。実際運用するとこういうことありそうだなーとか不安になったりしてね……。はい。「ゴルーチンの生成コストとか気にすんな」という話はもともと繰り返し出ていて「いやでも無限に生成できると、DB詰まったりとか考えるとそこの生成数とかに制限かけないと安定しなくね?」みたいなことを思っていましたのが流量制限に集約していたのだなーと気づきました。
チャネルの所有権を曖昧にしないことや正しくリソース管理する点についてのイディオムというか、お作法について明に暗に示されていたのもよかったです。構造体のメンバにするなとか、レキシカル1に縛っておけとか。
p.32 からはじまる「チャネルを使うかどうか」という決定木や4章の各種パターンは有用そうなので忘れた頃に確認したほうが良さそうですね。チームでの読み合わせなどをしたほうが良いかもしれません。
読書メモ
コピらずメモったので原文と表記が違うかもしれません。
p.39
結果としてゴルーチンは、暗黙的には並行処理の構成要素ですが、並行性というのはコルーチンの性質ではありません。
各コルーチンを逐次実行するような処理系もありうるから、かな?
ゴルーチンはグリーンスレッドにスケジュールされます
へー。これ知らなかった。6章で解説あり。
p.53 あたり
Cond いまいちよくわからない
p.68
無名ゴルーチンが終了するとき
言語仕様的には無名ゴルーチンが終了するのと stringStream
からの読み込みでブロックするのはどっちが先かわからないのではないか、と思った。些細な点だけど。
p.74
くっそどうでもいいが出力結果がおかしい。実装してみたのが以下。
chap4.1 全体 あんまりよくわからなかった
p.123
同じ型の2値を戻すとき、名前付き戻り値を _
で受けることによって型を2回書かずに済むというテクを覚えた(おそらく使わない)。
scope 切って一回変数にうけてから chan 型変数を nil 代入して処理済みを表す、というテクを覚えた。これは使うかもしれない。
p.132
リトルの法則について、総和をとってよいのかはあまり自明ではないのでは?と思った。各パイプラインは、直前の例のように重なり合うことが可能なので単純な足し算にしてよいのか、という点が疑問として残る。リトルの法則自体はある程度独立したトピックなので後で調べるかも。
p.207
「プログラムがゴルーチン内の関数に実行してもらいたいと思うのはよくあることでしょう」の文意がとれなかった。前後の流れから、「作ったゴルーチンをすぐに実行してもらいたいと思うのはよくあることでしょう」という感じだろうか。
20181028 19時過ぎ
誤字脱字系は本家サポートレポジトリで issue 化したので読書メモから消した
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進数表現の文字列がほしいのだが↩