オフラインリアルタイムどう書く E29 の回答 (Golang)

yhpg.doorkeeper.jp

問題 : 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 使ってるとそれの子供が釣れるみたいだけど気にしない。


完全にせやな、であった

読了: 『ドラゴンクエスト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

書いたやつ

github.com

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

めちゃ面白いイベントなのに参加者すくなくて寂しいので参加者募集です!!!次回のイベントももう公開済みなのでぜひ。

yhpg.doorkeeper.jp

負けました。正確には時間切れから発表中デバッグでバグを落としたけど計算量減らしてないので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

くっそどうでもいいが出力結果がおかしい。実装してみたのが以下。

github.com

chap4.1 全体 あんまりよくわからなかった

p.123

同じ型の2値を戻すとき、名前付き戻り値を _ で受けることによって型を2回書かずに済むというテクを覚えた(おそらく使わない)。

scope 切って一回変数にうけてから chan 型変数を nil 代入して処理済みを表す、というテクを覚えた。これは使うかもしれない。

p.132

リトルの法則について、総和をとってよいのかはあまり自明ではないのでは?と思った。各パイプラインは、直前の例のように重なり合うことが可能なので単純な足し算にしてよいのか、という点が疑問として残る。リトルの法則自体はある程度独立したトピックなので後で調べるかも。

p.207

「プログラムがゴルーチン内の関数に実行してもらいたいと思うのはよくあることでしょう」の文意がとれなかった。前後の流れから、「作ったゴルーチンをすぐに実行してもらいたいと思うのはよくあることでしょう」という感じだろうか。


20181028 19時過ぎ

誤字脱字系は本家サポートレポジトリで issue 化したので読書メモから消した

github.com


  1. google 日本語入力はいつになったら レキシカル を一発で変換できるようになるのか。

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 で判定しているのがダサいので別の手法を試したい。


  1. 本当は decimal がほしいので10進数表現の文字列がほしいのだが