スコーンの開発日記

開発中の学びをまとめていく。

【Go】プルリクエストを一覧表示するCLIツールを作ってみる（1）

仕事でGoを使うことになったので、勉強がてらCLIツールを作ってみる。

プルリクエストを一覧表示するツール

今いるリポジトリのプルリクエスト（以下PR）を一覧表示するツールを作ってみる。 すべてのPRではなく、自分がassigneeもしくはreviewerのものだけ取得する。

# assignee/reviewer両方
$ prs

# assigneeだけ
$ prs --assignee

# reviewer
$ prs --reviewer


# 出力イメージ
[#1234] https://github.com/foo/bar/pull/1234 ユーザー一覧画面のバグ修正 assignee 
[#1235] https://github.com/foo/bar/pull/1235 ユーザー関連テーブルの追加 reviewer

動機: シンプルなJasperが欲しい

PRの管理にはJasperが便利だが、単一リポジトリで作業する場合はtoo muchな感があった。日頃アクセスするPRは自分がassigneeもしくはreviewerのものが大半なので、その2つだけに絞りたい。

cliを使う

ライブラリはcliを使う。 github.com

GoのCLIツール用ライブラリはcliとcobraがメジャーっぽい。cobraの方が多機能な印象を受けたので、Go入門者としてはcliの方がよさそうと判断。

やっていき

諸々決まったので作っていく。

Rubyでスタックを扱う

Ruby algorithm

LeetCodeで面白い問題を見つけたので、理解を深めるために復習する。 スタックを使ったアルゴリズム。

leetcode.com

問題

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.
  • Note that an empty string is also considered valid.

つまり、カッコが適切に閉じられていればtrue、そうでなければfalseを返すようにせよ、という問題。

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true



考えてみよう

LeetCodeのSolutionをたどっていく。


カッコが1種類だったら

まずカッコが1種類()しかないケースを考える。

(((((()))))) -- VALID

()()()()     -- VALID

(((((((()    -- INVALID

((()(())))   -- VALID

この場合は、以下のアルゴリズムで解決できる。

  1. We process the expression one bracket at a time starting from the left.

  2. Suppose we encounter an opening bracket i.e. (, it may or may not be an invalid expression because there can be a matching ending bracket somewhere in the remaining part of the expression. Here, we simply increment the counter keeping track of left parenthesis till now. left += 1

  3. If we encounter a closing bracket, this has two meanings:

    1. One, there was no matching opening bracket for this closing bracket and in that case we have an invalid expression. This is the case when left == 0 i.e. when there are no unmatched left brackets available.
    2. We had some unmatched opening bracket available to match this closing bracket. This is the case when left > 0 i.e. we have unmatched left brackets available.

  4. If we encounter a closing bracket i.e. ) when left == 0, then we have an invalid expression on our hands. Else, we decrement left thus reducing the number of unmatched left parenthesis available.

  5. Continue processing the string until all parenthesis have been processed.

  6. If in the end we still have unmatched left parenthesis available, this implies an invalid expression.


つまり、


  1. 左から1つずつ処理する
  2. opening bracketだけではinvalid判定はできないので、left += 1
  3. closing bracketは、以下のいずれか
    1. マッチするopening bracketがいなかった(left == 0のとき)
    2. 未マッチのopening bracketがいる (left > 0のとき)
  4. left == 0でclosing bracketが出たらinvalid。left -= 1
  5. 以上の処理を最後まで繰り返す
  6. left != 0ならばinvalid

しかし3種類のカッコには対応できない

しかしこの方法では3種類のカッコに対応することはできない。3種類それぞれにleftの変数を用意すればよいのでは？と考えるかもしれないが、それだと以下のケースでもvalidとなってしまう。

[{]
# => 本当はinvalidなのにvalid扱いになる



解法

アルゴリズム

スタックとして処理すればよい。

  1. Initialize a stack S.
  2. Process each bracket of the expression one at a time.
  3. If we encounter an opening bracket, we simply push it onto the stack. This means we will process it later, let us simply move onto the sub-expression ahead.
  4. If we encounter a closing bracket, then we check the element on top of the stack. If the element at the top of the stack is an opening bracket of the same type, then we pop it off the stack and continue processing. Else, this implies an invalid expression.
  5. In the end, if we are left with a stack still having elements, then this implies an invalid expression.


つまり、


  1. スタック型のデータSを初期化する
  2. カッコを1つずつ処理する
  3. opening bracketならばスタックSに入れて、次に進む
  4. closing bracketならばスタックSに入っている一番上のカッコを見て、同じ種類ならばpopして次に進む。同じ種類でなければinvalid
  5. 最後まで処理してもスタックに残っていたらinvalid



Rubyで書いてみる

# @param {String} s
# @return {Boolean}
def is_valid(s)
    stack = []
    
    s.split('').each do |char|
        if MAPPING.key?(char)
            top_element = stack.size > 0 ? stack.pop : '#'
            return false if MAPPING[char] != top_element
        else
            stack.push(char)
        end
    end
    stack.empty?
end

MAPPING = {
          ")" => "(",
          "}" => "{",
          "]" => "["
          }

コメントをつけるとこうなる。

# @param {String} s
# @return {Boolean}
def is_valid(s)
    # opening bracketsを入れていくスタック
    stack = []
    
    s.split('').each do |char|
        if MAPPING.key?(char)
            # closing bracketの場合
            # スタックの中身がある場合は一番上の要素と比較。無い場合はinvalid
            top_element = stack.size > 0 ? stack.pop : '#'
            return false if MAPPING[char] != top_element
        else
            # opening bracketの場合
            # スタックに入れる
            stack.push(char)
        end
    end
    stack.empty?
end

MAPPING = {
          ")" => "(",
          "}" => "{",
          "]" => "["
          }

なるほど、popの返り値が配列から落とした値である理由がわかった。pushとpopは配列をスタックとして扱ってるんやな。



参考

leetcode.com

en.wikibooks.org

RubyでBacktracking

Ruby algorithm

いつものようにLeetCodeをやっていると、解法としてBacktrackingというものが出てきた。アルゴリズムの名前らしい。

leetcode.com

Backtrackingとはなんだろうか。

問題

まず解くべき問題を説明する。

2-9の数字からなる文字列が与えられる。それぞれの数字は、以下の画像のように文字列の組み合わせを持っている。

与えられた数字をそれぞれの文字列に変換した場合にできうる文字列をすべて答えよ、という問題。

f:id:ayacai115:20191116100449p:plain
電話のキー （https://leetcode.com/problems/letter-combinations-of-a-phone-number/ より）

例：

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

※ 例では辞書順の出力になっているが、順序は問わない


ツリー構造

組み合わせを洗い出すと、こんなツリー構造になる。

f:id:ayacai115:20191116101735j:plain
ツリー構造

これらすべての要素を列挙する解法の1つがBacktrackingということらしい。



Backtrackingとはなにか

概念

こちらの説明を読んでみる。

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.


具体的には

backtrack(combination, next_digits)という関数を考える。 combinationは現在の文字列(an ongoing letter combination)で、next_digitsは残りの数字(the next digits to check)である。

f:id:ayacai115:20191116103312p:plain
洗い出しの過程（https://leetcode.com/problems/letter-combinations-of-a-phone-number/solution/ より）

この関数は以下の処理を行う。

  • If there is no more digits to check that means that the current combination is done.
  • If there are still digits to check :
    • Iterate over the letters mapping the next available digit.
      • Append the current letter to the current combination combination = combination + letter.
      • Proceed to check next digits : backtrack(combination + letter, next_digits[1:]).


つまり、

  • next_digitsが空の配列ならば、そのcombinationの処理は終わり
  • next_digitsが空じゃなければ、
    • 次の数字の持つ文字列に対して繰り返し処理を行う
      • 文字列をcombinationに追加する combination = combination + letter
      • 次の数字に進む backtrack(combination + letter, next_digits[1..-1]


Rubyで書いてみる

# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
    return [] if digits.empty?
    @result = []
    @digit_to_letters = {
        '2' => %w[a b c],
        '3' => %w[d e f],
        '4' => %w[g h i],
        '5' => %w[j k l],
        '6' => %w[m n o],
        '7' => %w[p q r s],
        '8' => %w[t u v],
        '9' => %w[w x y z],
    }
    backtrack('', digits)
    @result
end

private

def backtrack(combination, next_digits)
    if next_digits.empty?
        @result << combination
        return
    else 
        @digit_to_letters[next_digits[0]].each do |letter|
            backtrack(combination + letter, next_digits[1..-1])
        end
    end 
end

コメントをつけるとこうなる。

# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
    return [] if digits.empty?
    @result = []
    @digit_to_letters = {
        '2' => %w[a b c],
        '3' => %w[d e f],
        '4' => %w[g h i],
        '5' => %w[j k l],
        '6' => %w[m n o],
        '7' => %w[p q r s],
        '8' => %w[t u v],
        '9' => %w[w x y z],
    }
    backtrack('', digits)
    @result
end

private

def backtrack(combination, next_digits)
    # next_digitsが空の配列ならば、
    if next_digits.empty?
        # もう子要素はないので、現時点での文字列を追加して処理を終える
        @result << combination
        return
    # next_digitsが空じゃなければ、
    else 
        # 次の数字が持つ文字列セットの要素1つずつに対して
        @digit_to_letters[next_digits[0]].each do |letter|
            # backtrack関数を呼び出す
            backtrack(combination + letter, next_digits[1..-1])
        end
    end 
end

こういう再帰系の処理は慣れが必要な感がある。精進あるのみ。

参考

leetcode.com

継続的インテグレーションがなぜ重要なのか

継続的インテグレーション（CI, Continuous Integration）が大事というのはよく聞く話だが、幸運にもそれはあって当たり前のものだったのでなぜ重要なのかが納得できていなかった。『レガシーコードからの脱却』で初めてその理由が腹落ちしたので、ここに書いておく。

レガシーコードからの脱却 ―ソフトウェアの寿命を延ばし価値を高める9つのプラクティス

レガシーコードからの脱却 ―ソフトウェアの寿命を延ばし価値を高める9つのプラクティス


継続的インテグレーションのあるとき/ないとき

継続的インテグレーションとは、リリース直前まで待つのではなく、ソフトウェアをビルドしながら統合することだ。（p. 105）

ということは…

継続的インテグレーションのない状態
=> 本番リリース直前に初めてビルド・統合される。つまり、リリース時に初めてコンパイルエラーやバグが発覚する

継続的インテグレーションのある状態
=> コードに変更を加えるたびに全体のビルド・統合を行う。つまり、リリースのずっと前にコンパイルエラーやバグに気づける。また、変更の規模が少ないので原因を突き止めるのも容易。


自動化して、常に実行される状態にする

ビルド専用のビルドサーバーを用意し、リポジトリに新しいコードが追加されたらシステム全体をリビルドする。そして自動テストを実行して結果を知る。

このサイクルを自動で回し続けることで、リリース直前にエラーやコンフリクトに直面することを避けられる。


継続的インテグレーションがもたらすもの

継続的インテグレーションには以下のメリットがある。

  • 小さい変更に対してフィードバックが得られるので、修正が容易
    • (リリース直前に問題が発覚してしまうと、緊急に対処しなければならないにもかかわらず範囲が大きく修正コストがかかる)


実体験と想像

さきほど「あって当たり前のものだった」と書いたが、そういえば入社1年目に自分ひとりで書いた小さなリポジトリにはCIツールが入っていない。ついでに言うとテストも無い🙃（ちなみに最初のリリース以来更新は入っていない。ほぼ触らないプロダクト）


困っていること、そしてチーム開発になったら困るであろうことを書いてみる。

  • 開発/本番環境に入れてみるまで、壊れていることに気づけない（手元で簡単な動作確認はできるが、カバレッジが低い）
  • チーム開発になった場合（仮定）
    • masterが更新されるたびに取り込む必要があり、取り込み作業に加えてコンフリクト修正の手間もかかる
    • masterを取り込むたびに手動で動作確認をする必要がある
    • masterへのマージが相次いだ場合は、壊れていることが確認できないまま or 十分な動作確認ができないまま本番にリリースされてしまう可能性がある
    • masterへのマージが相次いだあとに壊れた場合、原因の切り分けが難しい


やばすぎ💥💥💥

本を読んだあとに改めて考えてみると、継続的インテグレーションがなぜ重要なのかが納得できた。

参考

レガシーコードからの脱却 ―ソフトウェアの寿命を延ばし価値を高める9つのプラクティス

レガシーコードからの脱却 ―ソフトウェアの寿命を延ばし価値を高める9つのプラクティス

LeetCode復習 (8. String to Integer (atoi))

Ruby

最近LeetCodeをコツコツやっている。

こちらの問題で、自分では数十行書いていた処理が他の人の解答ではたったの6行で感動した。 後学のために、処理内容を1行ずつ見ていく。

leetcode.com

問題

StringをIntegerに変換する。

  • 数値は正負の符号を含む
  • 文字列には数値以外に単語が含まれることもある
  • 文字列は空白を含む
  • 空白を除く最初の文字が数値ではない場合、0を返す
  • 数値は符号付きで32ビットで表現するため、[−2 ** 31, 2 ** 31 − 1]の範囲を超える場合は、INT_MAX (2 ** 31 − 1) or INT_MIN (−2 ** 31)を返す

例1

Input: "42"
Output: 42

例2

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

例3

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

例4

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

例5

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

leetcode.com

解答

6行の解答例（ブロック内の行数）

# @param {String} str
# @return {Integer}
def my_atoi(str)
    arr = str.strip.split(/\s+/)
    if arr[0] =~ /^([+-]?[0-9]+)/
        i = $1.to_i
        return i >= 0 ? [2147483647, i].min : [-2147483648, i].max
    end
   0
end

leetcode.com

1行ずつ見ていく。

1行目

文字列から前後の空白を取り除く→空白で区切って配列に入れる。

# str = "   -42"
arr = str.strip.split(/\s+/)
# => ["-42"]

細かく見る

stripは文字列先頭と末尾の空白文字を全て取り除いた文字列を生成して返す。 instance method String#strip (Ruby 2.6.0)

arr = str.strip
=> "-42"

\sは「タブなどを含む空白文字全般にマッチするメタ文字列」、+は1回以上という意味なので、/\s+/ は空白が1回以上、の正規表現。 つまり、split(/\s+/)は1回以上空白を含むもので区切って配列を作る、という意味。

> "123 45    67 8 9 foo".split(/\s+/)
=> ["123", "45", "67", "8", "9", "foo"]

ちなみにsplit(' ')でも同じ結果だった。（複数の空白がどう扱われるか気になったけど1つと同じ扱い）

> "123 45    67 8 9 foo".split(' ')
=> ["123", "45", "67", "8", "9", "foo"]

2行目

配列の1つ目の値が頭に+-が0回か1回ついており、その後1回以上数字が連なる場合、ブロック内の処理を行う。

if arr[0] =~ /^([+-]?[0-9]+)/
end

細かく見る

  • ^ : 行頭にマッチ
  • [] : 文字クラス
  • ? : 0回もしくは1回
  • [0-9] : 10進数字
    • : 1回以上

=~は、マッチしたらマッチした位置の先頭のインデックス、マッチしなければnilを返す。

p /foo/ =~ "foo"  #=> 0 
p /foo/ =~ "afoo" #=> 1
p /foo/ =~ "bar"  #=> nil

0はtrueになるのでマッチしたらブロック内の処理が行われることになる。

[+-]?は+/-が0回か1回なので、2回あったらマッチしない。

> '-+1' =~ /^([+-]?[0-9]+)/
=> nil

3行目

上の正規表現にマッチした部分を取得して、Integerクラスに変換し、変数に格納。

i = $1.to_i

$1を調べると…

最後に成功したパターンマッチで n 番目の括弧にマッチした値が格納されます。

variable $1 (Ruby 2.6.0)

へーー知らんかった。 つまりこういうこと。

>'12345' =~ /^([+-]?[0-9]+)/
> $1
=> "12345"

4行目

上で格納した値が正の値であればmax値と比較して小さい方、負の値であればmin値と比較して大きい方を返す。

return i >= 0 ? [2147483647, i].min : [-2147483648, i].max

細かく見る

max``min便利。

3つ以上の要素にも対応。

> [1, 433, 254245, 642].max
=> 254245

文字列とは比較不可。

> [1, 433, 'foo', 'bar'].max
ArgumentError: comparison of String with 433 failed
    from (irb):42
    from /Users/okiaya/.rbenv/versions/2.4.6/bin/irb:11:in `<main>'

数値の文字列もダメ。

> [1, 433, '123'].max
ArgumentError: comparison of String with 433 failed
    from (irb):43
    from /Users/okiaya/.rbenv/versions/2.4.6/bin/irb:11:in `<main>'

6行目

配列の1つ目の値が「頭に+-が0回か1回ついており、その後1回以上数字が連なる」という条件に合致しなければ、0を返す。

#   if arr[0] =~ /^([+-]?[0-9]+)/
#        i = $1.to_i
#        return i >= 0 ? [2147483647, i].min : [-2147483648, i].max
#    end
   0

おさらい

# @param {String} str
# @return {Integer}
def my_atoi(str)
    # 文字列から前後の空白を取り除く→空白で区切って配列に入れる
    arr = str.strip.split(/\s+/) 
    # 配列の1つ目の値が頭に+-が0回か1回ついており、その後1回以上数字が連なるか？
    if arr[0] =~ /^([+-]?[0-9]+)/ 
        # マッチした部分を取得して、Integerクラスに変換し、変数に格納。
        i = $1.to_i 
        # 格納した値が正の値であればmax値と比較して小さい方、負の値であればmin値と比較して大きい方を返す
        return i >= 0 ? [2147483647, i].min : [-2147483648, i].max 
    end
   # 一致しなければ0を返す
   0
end

うーん、素晴らしい。

参考

docs.ruby-lang.org

docs.ruby-lang.org

docs.ruby-lang.org

Railsコンソールで、成形されたJSONデータをクリップボードにコピーする

Ruby on Rails

成形されたJSONデータを作成

hash = { foo: 'foo', bar: 'bar' }
json_str = JSON.pretty_generate(hash)

クリップボードにコピー

IO.popen('pbcopy', 'w') { |f| f << json_str }

参考

uxmilk.jp

coderwall.com

ActiveRecordのscopeではfind_byしない方がよい

Ruby on Rails

find_byしてしまうと…

ActiveRecordのscopeでは、クエリの実行結果がnilだとallを返してしまう。

class Order < ActiveRecord::Base
  scope :bar, -> { find_by(foo: 'bar') }
end

Order.find_by(foo: 'bar')と同じ動きだと思ってnilを期待すると、allが返る。

# レコードがあるとき
Order.bar
=> #<Order ...> # ActiveRecord::Relationではなく、インスタンスが返る

# レコードがないとき
Order.bar
=> [#<Order ...>
     #<Order ...>
     #<Order ...>] # Order.all相当の処理

Order.bar.to_sql
=> "SELECT * FROM [orders]"

Order.bar.class
=> Order::Billing::Detail::ActiveRecord_AssociationRelation

(ハイライトおかしい😭)

scopeは通常ActiveRecord_AssociationRelationを返すものだが、find_byにしてしまうと、対象レコードがある場合でもインスタンスがそのまま返ってしまう。ActiveRecord_AssociationRelationが返ると思ってチェインしようとしたらつながらない、なんてこともありそう。(要調査)

さらに、対象レコードがない場合だと、Order.allの結果が返ってしまう。これは困る。

クラスメソッドにするとよい

find_byと同じ動きを期待するならば、クラスメソッドにすべき。

class Order < ActiveRecord::Base
  def self.bar
    find_by(foo: 'bar')
  end
end

※ こうなるとただfind_byをラップしているだけのメソッドなので、そもそもメソッドとして切り出さなくてよいのかも

参考

qiita.com