電話帳作成問題の解答

前回に引き続き、こちらの記事を見てみて、面白そうな問題がいくつかあったので、プログラミング初心者ではないですが解きました。

blog.jnito.com

電話帳作成問題

カタカナ文字列の配列を渡すと、ア段の音別にグループ分けした配列を返すプログラムを作成する問題です。

# INPUT
['キシモト', 'イトウ', 'ババ', 'カネダ', 'ワダ', 'ハマダ']

# OUTPUT 
[ ['ア', ['イトウ']], ['カ', ['カネダ', 'キシモト']], ['ハ', ['ハマダ', 'ババ']], ['ワ', ['ワダ']] ]

詳しい仕様はこちらにあります。

https://github.com/JunichiIto/name-index

解答

class NameIndex
  NAME_INDEX_HASH = {
      '' => %w(ア イ ウ エ オ ヴ),
      '' => %w(カ キ ク ケ コ ガ ギ グ ゲ ゴ),
      '' => %w(サ シ ス セ ソ ザ ジ ズ ゼ ゾ),
      '' => %w(タ チ ツ テ ト ダ ヂ ヅ デ ド),
      '' => %w(ナ ニ ヌ ネ ノ),
      '' => %w(ハ ヒ フ ヘ ホ バ ビ ブ ベ ボ パ ピ プ ペ ポ),
      '' => %w(マ ミ ム メ モ),
      '' => %w(ヤ ユ ヨ),
      '' => %w(ラ リ ル レ ロ),
      '' => %w(ワ ヲ ン)
  }.freeze

  def self.create_index(names)
    names.sort.group_by {|name|
      index_kana = NAME_INDEX_HASH.find(['Others']) {|_, value| value.include?(name[0])}
      index_kana[0]
    }.to_a
  end
end

テストです。

describe NameIndex do
  describe '#create_index' do
    specify {expect(NameIndex.create_index([])).to eq []}
    specify {expect(NameIndex.create_index(['キシモト', 'イトウ', 'ババ', 'カネダ', 'ワダ', 'ハマダ'])).to eq [['', ['イトウ']], ['', ['カネダ', 'キシモト']], ['', ['ハマダ', 'ババ']], ['', ['ワダ']]]}
    specify {expect(NameIndex.create_index(['サトウ', 'スズキ', 'タカハシ', 'イケガミ', 'アラキ', 'デグチ', 'ヌマタ'])).to eq [['', ['アラキ', 'イケガミ']], ['', ['サトウ', 'スズキ']], ['', ['タカハシ', 'デグチ']], ['', ['ヌマタ']]]}
  end
end

元記事では、解答を見ないで解くこととなっていましたが、ある程度自分で考えた後に解答を見てから解きました。それでもオリジナルなコードになったと思います。

解説

問題を見たときに以下の4つを考えました。

  • 名前の先頭のカタカナを取り出す
  • カタカナが属する行のア段のカタカナを求める(ただし濁音、半濁音は清音にする)(例: キ → カ, バ →ハ)
  • ア段のカタカナでグループ化する
  • ソートする

これらをクリアにしていけば解けそうです。

  • 名前の先頭のカタカナを取り出すにはname[0]のように、[0]を使用します。
  • カタカナが属する行のア段のカタカナを求める を行う標準のメソッドは存在しないので、自身で実装する必要があります。
  • ア段のカタカナでグループ化する はArray.group_by( group_by (Enumerable) - Rubyリファレンス )を使用します。
  • ソートする はArray.sort( sort (Enumerable) - Rubyリファレンス )が使用できます。

まず先頭のカタカナを取り出すところまで実装しましょう。

class NameIndex
  def self.create_index(names)
    names.map { |name|
      name[0]
    }
  end
end

テストは一旦以下の2ケースのみ書いておくことにします。また、以下実行結果として書くのは2つ目のテストケースについてです。

describe NameIndex do
  describe '#create_index' do
    specify { expect(NameIndex.create_index([])).to eq [] }
    specify { expect(NameIndex.create_index(['キシモト', 'イトウ', 'ババ', 'カネダ', 'ワダ', 'ハマダ'])).to eq [ ['', ['イトウ']], ['', ['カネダ', 'キシモト']], ['', ['ハマダ', 'ババ']], ['', ['ワダ']] ] }
  end
end

実行結果です。先頭の文字列を取り出すことができました。

["", "", "", "", "", ""]

次にア段の音に変換していきます。範囲オブジェクトを使用する方法もありますが、 50音表の順番で並んでいるわけではないので、注意して使用する必要があります。( 片仮名 (Unicodeのブロック) - Wikipedia ) (カキクケコガギグゲゴと並ぶわけでなく、カガキギクグケゲコゴと並んでいます。)

今回はわかりやすさのため、名前の先頭に使用できるカタカナを全て書き出しました。(ヲ ンから始まる名前があるかどうか微妙ですが)

どのカタカナがどのア段のカタカナに対応するか求めます。まず全てのカタカナをキー、対応するア段のカタカナを値とする方法が思いつきます。

NAME_INDEX_HASH = {'' => '', '' => '', '' => '', ..., }

これは確実な方法ですが、コードが長くなるため今回は採用しませんでした。

代わりに、ア段のカタカナをキー、そのア段のカタカナが含むカタカナを値とするハッシュを定義しました。この場合だとハッシュの逆引きが必要なのですが、コードがわかりやすくなります。

  NAME_INDEX_HASH = {
      '' => %w(ア イ ウ エ オ ヴ),
      '' => %w(カ キ ク ケ コ ガ ギ グ ゲ ゴ),
      '' => %w(サ シ ス セ ソ ザ ジ ズ ゼ ゾ),
      '' => %w(タ チ ツ テ ト ダ ヂ ヅ デ ド),
      '' => %w(ナ ニ ヌ ネ ノ),
      '' => %w(ハ ヒ フ ヘ ホ バ ビ ブ ベ ボ パ ピ プ ペ ポ),
      '' => %w(マ ミ ム メ モ),
      '' => %w(ヤ ユ ヨ),
      '' => %w(ラ リ ル レ ロ),
      '' => %w(ワ ヲ ン)
  }.freeze

ス→サのような変換を行うには、"ス"が含まれる配列を見つけ、それのキーを取得することで実現できます。 Enumerable#find( find, detect (Enumerable) - Rubyリファレンス ) を使用すると、ブロックが最初に真になったときのキーと値を返します。名前の始めの文字が見つからなかったときの挙動は特に問題には示されていなかったので、"Other"というキーを返すようにしました。

class NameIndex
  NAME_INDEX_HASH = {
      '' => %w(ア イ ウ エ オ ヴ),
      '' => %w(カ キ ク ケ コ ガ ギ グ ゲ ゴ),
      '' => %w(サ シ ス セ ソ ザ ジ ズ ゼ ゾ),
      '' => %w(タ チ ツ テ ト ダ ヂ ヅ デ ド),
      '' => %w(ナ ニ ヌ ネ ノ),
      '' => %w(ハ ヒ フ ヘ ホ バ ビ ブ ベ ボ パ ピ プ ペ ポ),
      '' => %w(マ ミ ム メ モ),
      '' => %w(ヤ ユ ヨ),
      '' => %w(ラ リ ル レ ロ),
      '' => %w(ワ ヲ ン)
  }.freeze

  def self.create_index(names)
    names.map { |name|
      NAME_INDEX_HASH.find(['Others']) {|_, value| value.include?(name[0])}  # 変更
    }
  end
end

実行結果です。名前の最初のカタカナが含まれている配列と対応するキーが取り出せています。

[
  ["", ["", "", "", "", "", "", "", "", "", ""]],
  ["", ["", "", "", "", "", ""]],
  ["", ["", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]],
  ["", ["", "", "", "", "", "", "", "", "", ""]],
  ["", ["", "", ""]],
  ["", ["", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]]
]

必要なのはキーだけなんで、配列の0番目を取り出します。読みやすさのために一旦index_kanaに見つかったキーと値のペアを格納しています。

class NameIndex
  NAME_INDEX_HASH = {
      '' => %w(ア イ ウ エ オ ヴ),
      '' => %w(カ キ ク ケ コ ガ ギ グ ゲ ゴ),
      '' => %w(サ シ ス セ ソ ザ ジ ズ ゼ ゾ),
      '' => %w(タ チ ツ テ ト ダ ヂ ヅ デ ド),
      '' => %w(ナ ニ ヌ ネ ノ),
      '' => %w(ハ ヒ フ ヘ ホ バ ビ ブ ベ ボ パ ピ プ ペ ポ),
      '' => %w(マ ミ ム メ モ),
      '' => %w(ヤ ユ ヨ),
      '' => %w(ラ リ ル レ ロ),
      '' => %w(ワ ヲ ン)
  }.freeze

  def self.create_index(names)
    names.map { |name|
      index_kana = NAME_INDEX_HASH.find(['Others']) {|_, value| value.include?(name[0])}  # 変更 
      index_kana[0] # 追加
    }
  end
end

実行結果です。ア段のカタカナを取り出すことができました。

["", "", "", "", "", ""]

次に、ア段のカタカナごとに名前をグループ化します。Array#group_byを使うのでした。

class NameIndex
  # 中略

  def self.create_index(names)
    names.group_by { |name|  # 変更
      index_kana = NAME_INDEX_HASH.find(['Others']) {|_, value| value.include?(name[0])}
      index_kana[0]
    }
  end
end

実行結果です。ア段ごとにグループ化されました。

{
  ""=>["キシモト", "カネダ"],
  ""=>["イトウ"],
  ""=>["ババ", "ハマダ"],
  ""=>["ワダ"]
}

個人的には、データ形式は上記のように{ア段のカタカナ => 含まれる名前の配列}がよいと思うのですが、問題ではア段のカタカナを0番目の要素、名前の配列を1番目の要素とする配列の配列を作成することになっているので変換します。この変換はHash#to_a( to_a (Hash) - Rubyリファレンス )で行うことができます。

class NameIndex
  # 中略

  def self.create_index(names)
    names.group_by { |name|
      index_kana = NAME_INDEX_HASH.find(['Others']) {|_, value| value.include?(name[0])}
      index_kana[0]
    }.to_a  # 変更
  end
end

実行結果です。配列に変更できました。

[
  ["", ["キシモト", "カネダ"]],
  ["", ["イトウ"]],
  ["", ["ババ", "ハマダ"]],
  ["", ["ワダ"]]
]

最後にソートをかけます。ア段のカタカナ、それに対応する名前の配列それぞれにソートをかける必要があります。今回は最後にソートかけるのではなく、最初にソートをかけるように変更します。それによって自然に最終的な配列もソートされます。

1つ気にしておくべきことは、Rubyの(というよりほぼ全てのプログラミング言語での)ソートは文字コード順に並ぶということです。例えば、['ゴトウ', 'コニシ', 'コバヤシ']は、国語辞典ではこの順に並びますが、Rubyでは['コニシ', 'コバヤシ', 'ゴトウ']の順に並びます。もし国語辞典と同じ順番で並べたい場合はArray#sortに比較を行うブロックを渡し独自のソートを行う必要があります。 今回は問題文中の例として示されているケース(['ハ', ['ハマダ', 'ババ']])から、文字コード順で並び替えることが類推できます(あと初心者向けと銘打っていることからも)。コードは以下になります。

class NameIndex
  # 中略

  def self.create_index(names)
    names.sort.group_by { |name|  # 変更
      index_kana = NAME_INDEX_HASH.find(['Others']) {|_, value| value.include?(name[0])}
      index_kana[0]
    }.to_a
  end
end

実行結果です。期待通りの結果が得られました。

[
  ["", ["イトウ"]],
  ["", ["カネダ", "キシモト"]],
  ["", ["ハマダ", "ババ"]],
  ["", ["ワダ"]]
]

あとがき

こちらも意外と考えることの多い問題でした。自分が初心者の時に解けただろうか。全てのことを一度にやろうとするのではなく、問題を細かいステップに分けるのがカギなのですが、初心者の頃は全てのことを一度にやりがちでした。

名前の先頭のカタカナからア段のカタカナを求める部分がキモなのですが、その部分は今回はわりと読みやすいコードになったかとは思います。

テストが書きにくかったです。数ケースはコードが書いた人が書けばよいと思いますが、チームで働いてる場合はテストケースは他の人が追加で書いた方がよい気がします(特に今回の場合は)。考慮漏れが発生しやすいプログラミング問題だと感じました。

テストケースの名字は名字由来netを参考にしました。


国民の祝日.csv パースプログラムの解答

前回に引き続き、こちらの記事を見てみて、面白そうな問題がいくつかあったので、プログラミング初心者ではないですが解きました。

blog.jnito.com

国民の祝日.csv パースプログラム

その昔、「国民の祝日.csv」という扱いづらいCSVが話題になっていました。
具体的にはこんなCSVファイルです↓

平成28年(2016年),,平成29年(2017年),,平成30年(2018年),
名称,月日,名称,月日,名称,月日
元日,2016/1/1,元日,2017/1/1,元日,2018/1/1
成人の日,2016/1/11,成人の日,2017/1/9,成人の日,2018/1/8
建国記念の日,2016/2/11,建国記念の日,2017/2/11,建国記念の日,2018/2/11
春分の日,2016/3/20,春分の日,2017/3/20,春分の日,2018/3/21
# 中略
文化の日,2016/11/3,文化の日,2017/11/3,文化の日,2018/11/3
勤労感謝の日,2016/11/23,勤労感謝の日,2017/11/23,勤労感謝の日,2018/11/23
天皇誕生日,2016/12/23,天皇誕生日,2017/12/23,天皇誕生日,2018/12/23
,,,,,
月日は表示するアプリケーションによって形式が異なる場合があります。,,,,,

これをいい感じにパースして、以下のようなデータ構造(Rubyのハッシュオブジェクト)に変換しよう、というプログラミング問題です。

{
  2016 => {
    # 実際のキーは文字列ではなくDateオブジェクト
    '2016/01/01' => '元日',
    '2016/01/11' => '成人の日',
    # ...
    '2016/11/23' => '勤労感謝の日',
    '2016/12/23' => '天皇誕生日',
  },
  2017 => {
    '2017/01/01' => '元日',
    '2017/01/09' => '成人の日',
    # ...
    '2017/11/23' => '勤労感謝の日',
    '2017/12/23' => '天皇誕生日',
  },
  2018 => {
    '2018/01/01' => '元日',
    '2018/01/08' => '成人の日',
    # ...
    '2018/11/23' => '勤労感謝の日',
    '2018/12/23' => '天皇誕生日',
  },
}

解答

class SyukujitsuParser
  CSV_PATH = File.expand_path('../../resource/syukujitsu.csv', __FILE__)

  def self.parse(csv_path = CSV_PATH)
    self.new.parse(csv_path)
  end

  def parse(csv_path)
    IO.readlines(csv_path, chomp: true, encoding: 'Shift_JIS:UTF-8')
          .join(',')
          .scan(%r!([^,]+),([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})!)
          .group_by{|_, year| year.to_i}
          .map { |year, holiday_arr|
            holiday_hash = holiday_arr.map {|holiday, *date|
              [Date.new(*date.map(&:to_i)), holiday]
            }.to_h
            [year, holiday_hash]
          }.to_h
  end
end

RSpecは本家のgithubに記載されているので割愛します。 https://github.com/JunichiIto/parse-syukujitsu/blob/master/test/syukujitsu_parser_test.rb

解説

RubyCSVファイルを読み込むには、CSVクラスを使用するのが定石のようですが、CSVクラスを知らなかったので、通常のファイルとして読み込みました。

まず、どのように祝日名と日付部分を取り出すか考えます。公式ドキュメントのString#scan( scan (String) - Rubyリファレンス )の例に以下のようなものがあるので、同様の処理を行います。

s = "Hokkaido:Sapporo, Aomori:Aomori, Iwate:Morioka"
p s.scan(/(\w+):(\w+)/)
# => [["Hokkaido", "Sapporo"], ["Aomori", "Aomori"], ["Iwate", "Morioka"]]

祝日名と日付の部分は、

(平仮名か漢字),(年/月/日)

というペアになっており、上記のscanの例と同じようになっています。

正規表現にしていきます。まず、(平仮名か漢字)の部分ですが、これを満たす正規表現が無くはないようですが、一筋縄ではいかないようなので今回は別の方法にします。カンマより前のすべての(カンマでない)文字を取れば良いので、[^,]+という正規表現で表します。

日付部分の正規表現

[0-9]{4}/[0-9]{1,2}/[0-9]{1,2}

にします。ここまでで、マッチさせる正規表現は以下のようになります。

([^,]),([0-9]{4}/[0-9]{1,2}/[0-9]{1,2})

先々の過程で、日付の年月日が一つの変数に入っているよりも、年・月・日で別々の方が扱いやすいので、カッコでのキャプチャの位置を変更します。

([^,]+),([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})

それでは、ファイルを読み込んでString#scanで一致した部分を抜き出していきます。 ファイルは1行ごとに読むことが多いのですが、今回は一度にすべての行を読み込みます。IO.readlinesは指定されたファイルを全て読み込んで、その各行を要素としてもつ配列を返すメソッドです。 ( singleton method IO.readlines (Ruby 2.6.0) )

class SyukujitsuParser
  CSV_PATH = File.expand_path('../../resource/syukujitsu.csv', __FILE__)

  def self.parse(csv_path = CSV_PATH)
    self.new.parse(csv_path)
  end

  def parse(csv_path)
    IO.readlines(csv_path, chomp: true, encoding: "Shift_JIS:UTF-8")
  end
end

readlinesの引数のchomp: trueは各行の末尾の改行を取り除くオプションです。今回の場合、指定しなくても出力は変わらないのですが、あると将来的なバグの温床になるので取り除いておきます。読み込むCSVファイルのエンコーディングがShift-JIS、内部的にはUTFで扱いたいので、encoding: "Shift_JIS:UTF-8"を指定しています。

実行結果です。

[
  "平成28年(2016年),,平成29年(2017年),,平成30年(2018年),", 
  "名称,月日,名称,月日,名称,月日", 
  "元日,2016/1/1,元日,2017/1/1,元日,2018/1/1", 
  "成人の日,2016/1/11,成人の日,2017/1/9,成人の日,2018/1/8", 
  "建国記念の日,2016/2/11,建国記念の日,2017/2/11,建国記念の日,2018/2/11", 
  "春分の日,2016/3/20,春分の日,2017/3/20,春分の日,2018/3/21", 
  "昭和の日,2016/4/29,昭和の日,2017/4/29,昭和の日,2018/4/29", 
  # 中略
  "秋分の日,2016/9/22,秋分の日,2017/9/23,秋分の日,2018/9/23", 
  "体育の日,2016/10/10,体育の日,2017/10/9,体育の日,2018/10/8", 
  "文化の日,2016/11/3,文化の日,2017/11/3,文化の日,2018/11/3", 
  "勤労感謝の日,2016/11/23,勤労感謝の日,2017/11/23,勤労感謝の日,2018/11/23", 
  "天皇誕生日,2016/12/23,天皇誕生日,2017/12/23,天皇誕生日,2018/12/23", 
  ",,,,,", 
  "月日は表示するアプリケーションによって形式が異なる場合があります。,,,,,"
]

この各配列の要素に対してscanをかけてもよいのですが、今回は簡単のためすべての行をカンマで結合してからscanをかけます。CSVの各行を1行にまとめるのは普通はやらないのですが、今回は元となるデータの形式がイマイチなのでこのようなことをしてもしょうがないという気持ちです。配列の各要素をjoinで連結します。引数にカンマを与えて、カンマ区切りで結合します。結果的に1行のCSVが出力されます。

class SyukujitsuParser
  # 中略

  def parse(csv_path)
    IO.readlines(csv_path, chomp: true, encoding: "Shift_JIS:UTF-8")
          .join(',')  # 追加
  end
end

実行結果です。1行にまとまりました。

"平成28年(2016年),,平成29年(2017年),,平成30年(2018年),,名称,月日,名称,月日,名称,月日,元日,2016/1/1,元日,2017/1/1,元日,2018/1/1,成人の日,2016/1/11,成人の日,2017/1/9,成人の日,2018/1/8,建国記念の日,2016/2/11,建国記念の日,2017/2/11,建国記念の日,2018/2/11,春分の日,2016/3/20,春分の日,2017/3/20,春分の日,2018/3/21,昭和の日,2016/4/29,昭和の日,2017/4/29,昭和の日,2018/4/29,(中略)2018/9/17,秋分の日,2016/9/22,秋分の日,2017/9/23,秋分の日,2018/9/23,体育の日,2016/10/10,体育の日,2017/10/9,体育の日,2018/10/8,文化の日,2016/11/3,文化の日,2017/11/3,文化の日,2018/11/3,勤労感謝の日,2016/11/23,勤労感謝の日,2017/11/23,勤労感謝の日,2018/11/23,天皇誕生日,2016/12/23,天皇誕生日,2017/12/23,天皇誕生日,2018/12/23,,,,,,,月日は表示するアプリケーションによって形式が異なる場合があります。,,,,,"

これに対して、上で作成した正規表現で祝日名と日付を抽出します。scanの引数には正規表現オブジェクトを渡します。今回は%rを使用して正規表現オブジェクトを作成します。マッチしたい部分に記号がたくさん含まれるので!正規表現を囲みます。

class SyukujitsuParser
  # 中略

  def parse(csv_path)
    IO.readlines(csv_path, chomp: true, encoding: "Shift_JIS:UTF-8")
          .join(',')
          .scan(%r!([^,]+),([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})!)  # 追加
  end
end

実行結果です。[祝日名, 年, 月, 日]の配列が作成されました。

[
  ["元日", "2016", "1", "1"], 
  ["元日", "2017", "1", "1"], 
  ["元日", "2018", "1", "1"], 
  ["成人の日", "2016", "1", "11"], 
  ["成人の日", "2017", "1", "9"], 
  ["成人の日", "2018", "1", "8"], 
  ["建国記念の日", "2016", "2", "11"], 
  ["建国記念の日", "2017", "2", "11"], 
  # 中略
  ["文化の日", "2017", "11", "3"], 
  ["文化の日", "2018", "11", "3"], 
  ["勤労感謝の日", "2016", "11", "23"], 
  ["勤労感謝の日", "2017", "11", "23"], 
  ["勤労感謝の日", "2018", "11", "23"], 
  ["天皇誕生日", "2016", "12", "23"], 
  ["天皇誕生日", "2017", "12", "23"], 
  ["天皇誕生日", "2018", "12", "23"]
]

ここから年でグルーピングしてみましょう。group_byを使えば簡単です。年は配列の2番目なので、それを整数に変換したものでグルーピングします。

class SyukujitsuParser
  # 中略

  def parse(csv_path)
    IO.readlines(csv_path, chomp: true, encoding: 'Shift_JIS:UTF-8')
          .join(',')
          .scan(%r!([^,]+),([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})!)
          .group_by{|_, year| year.to_i}  # 追加
  end
end

実行結果です。

{
  2016=>[
    ["元日", "2016", "1", "1"], 
    ["成人の日", "2016", "1", "11"],
    # 中略
    ["勤労感謝の日", "2016", "11", "23"], 
    ["天皇誕生日", "2016", "12", "23"]
  ], 
  2017=>[
    ["元日", "2017", "1", "1"], 
    ["成人の日", "2017", "1", "9"], 
    # 中略
    ["勤労感謝の日", "2017", "11", "23"], 
    ["天皇誕生日", "2017", "12", "23"]
  ], 
  2018=>[
    ["元日", "2018", "1", "1"], ["成人の日", "2018", "1", "8"], 
    ["建国記念の日", "2018", "2", "11"],
    # 中略
    ["勤労感謝の日", "2018", "11", "23"],
    ["天皇誕生日", "2018", "12", "23"]
  ]
}

だいぶ完成に近くなってきました。完成形と違うところは、ハッシュの各値が配列になっていることです。

まず、ハッシュの値(value)を変換する方法として、以下のイディオムがあります。

hash.map {|key, value|
  [key, convert(value)]
}.to_h

こちらを適用します。中の実装は仮のものにしておきます。

class SyukujitsuParser
  # 中略

  def parse(csv_path)
    IO.readlines(csv_path, chomp: true, encoding: 'Shift_JIS:UTF-8')
          .join(',')
          .scan(%r!([^,]+),([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})!)
          .group_by{|_, year| year.to_i}
          .map { |year, holiday_arr|  # 追加
            [year, holiday_arr]  # 仮実装
          }.to_h  # 追加
  end
end

実行すると1つ前で実行したのと同じものになります。

次に

[
  ["元日", "2016", "1", "1"], 
  ["成人の日", "2016", "1", "11"],
  # 中略
  ["勤労感謝の日", "2016", "11", "23"], 
  ["天皇誕生日", "2016", "12", "23"]
]

{
  Date.parse('2016/01/01') => '元日',
  Date.parse('2016/01/11') => '成人の日',
  # 中略
  Date.parse('2016/11/23') => '勤労感謝の日',
  Date.parse('2016/12/23') => '天皇誕生日',
}

に変換します。配列からハッシュを作成するには、Array.to_hを使用します。( instance method Array#to_h (Ruby 2.6.0) ) このメソッドは[key, value]のペアの配列を、{key => value}のハッシュに変換します。

to_hで変換する前の配列は

[
  [Date.parse('2016/01/01'), '元日'],
  [Date.parse('2016/01/11'), '成人の日'],
  # 中略
  [Date.parse('2016/11/23'), '勤労感謝の日'],
  [Date.parse('2016/12/23'), '天皇誕生日'],
]

となっている必要があります。

年ごとの配列に対してmapを使用します。mapで受け取る引数は、["元日", "2016", "1", "1"]の形式です。多重代入を使用して、holiday, *date = ["元日", "2016", "1", "1"]のように受け取っています。 この場合だと、holiday = "元日", date = ["2016", "1", "1"]のように代入されます。

dateをDate( class Date (Ruby 2.6.0) ) オブジェクトに変換します。Date.newで作成するので、 はじめにdateの各日付を数値に変換します(date.map(&:to_i))これをDate.newの引数にします。配列展開を使います。Date.new(*[2016, 1, 1])と書くと、Date.new(2016, 1, 1)と書いたのと同じになります。

class SyukujitsuParser
  # 中略

  def parse(csv_path)
    IO.readlines(csv_path, chomp: true, encoding: 'Shift_JIS:UTF-8')
          .join(',')
          .scan(%r!([^,]+),([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})!)
          .group_by{|_, year| year.to_i}
          .map { |year, holiday_arr|
            holiday_hash = holiday_arr.map {|holiday, *date|  # 追加
              [Date.new(*date.map(&:to_i)), holiday]  # 追加
            }.to_h  # 追加
            [year, holiday_hash]  # 変更
          }.to_h
  end
end

これで完成です。書いている最中はプログラムの意図を理解していますが、1週間くらいすると各変数やメソッドの使用意図を忘れそうなので、適宜コメントを入れた方がよさそうです。

あとがき

元のCSVがひどいのでコードも力技になったなあと思います。

初心者向けの問題と書かれていながら、なかなか考えることの多い問題でした。

★前回の記事

yucatio.hatenablog.com


ボーナスドリンク問題の解答

こちらの記事を見てみて、面白そうな問題がいくつかあったので、プログラミング初心者ではないですが解きました。

blog.jnito.com

ボーナスドリンク問題

「ある駄菓子屋で飲み物を買うと、空き瓶3本で新しい飲み物を1本プレゼントしてくれる。最初に100本購入した場合、トータルで何本飲めるか」

解答

コード

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    last_amount = (amount - 1) % 2 + 1
    (3 * amount - last_amount) / 2
  end
end

テストコードはこちら。

require 'rspec'
require File.expand_path(File.dirname(__FILE__) + '/../bonus_drink')

describe BonusDrink do
  specify { expect(BonusDrink.total_count_for(0)).to eq 0 }
  specify { expect(BonusDrink.total_count_for(1)).to eq 1 }
  specify { expect(BonusDrink.total_count_for(2)).to eq 2 }
  specify { expect(BonusDrink.total_count_for(3)).to eq 4 }
  specify { expect(BonusDrink.total_count_for(11)).to eq 16 }
end

解説

最初にN本買ってきたときに、最終的に飲める本数をf(N)とします。

f(1) = 1
f(2) = 2
f(3) = 4
f(11) = 16

です。

例として問題にある通り、今回はN=100の場合を考えます。

f(100) = 最初に100本買ってきたときに最終的に飲める本数

まず、100本の中身が入っているジュースがあります。

f:id:yucatio:20190509234327p:plain

3本飲んでください。

f:id:yucatio:20190509234406p:plain

さっそく3本だけ取り替えに行きましょう。1本もらいました。

手元にあるジュースの本数を確認しましょう。 残ってる97本と取り替えた1本で98本ですね。 98本で飲める量はf(98)で表されるのでした。

f:id:yucatio:20190509234512p:plain

すでに3本のジュースを飲んでいるので、 100本のジュースで飲める量は、

f(100) = 3 + f(98)

で表すことができます。

同様に98本のうち3本を飲んで新しいジュース1本と交換します。

f:id:yucatio:20190509234751p:plain

手元には96本のジュースがあります。すでに6本のジュースを飲んでいるので100本で最終的に飲める本数は以下の式で表すことができます。

f(100) = 3 + 3 + f(96)

お気付きのように、ジュースを3本飲むごとに手持ちのジュースが2本減ります。

繰り返していきましょう。

f(100) = 3 + 3 + 3 + f(94)
f(100) = 3 + 3 + 3 + 3 + f(92)
f(100) = 3 + 3 + 3 + 3 + 3 + f(90)
# 中略
f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + f(6)
f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + f(4)
f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + f(2)

ここで手持ちのジュースが2本になってしまいました。 最後にこれを飲みましょう。

f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + 2

では、上の式で3を何個足したか数えましょう。 100から2まで、2ずつ引いていったので、

(100 - 2)/2 = 49

49個の3を足しています。

なので、上記の式は以下のように書き換えられます。

f(100) = 3 * 49 + 2
       = 149

最初に100本買った場合に最終的に飲める本数は149本であることがわかりました。(プログラムで算出するはずなのに、算数的に解いてしまった)

本数がNの時は上記と同様に

f(N) = 3 * (N-2)/2 + 2

となります。しかし、2本ずつ引いていって最後に2本になるのは偶数の時のみです。 奇数の場合を考えてみましょう。例として97本の場合を考えます。

考え方は同様で、3本飲むと、2本手持ちが減ります。これを数式にしていきます。

f(97) = 3 + f(95)
f(97) = 3 + 3 + f(91)
f(97) = 3 + 3 + 3 + f(89)
f(97) = 3 + 3 + 3 + 3 + f(87)
# 中略
f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + f(5)
f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + f(3)
f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + f(1)

このようになり、最後に手持ちの1本を飲んで終わりです。

f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + 1

97から1まで2ずつ引いたので、足した3の数は、

(97 - 1)/2 = 48

48個の3を足したので、

f(97) = 3 * 48 + 1
      = 145

最初に97本買った場合に最終的に飲める本数は145本であることがわかりました。

本数がNかつNが奇数の時、最終的に飲めるジュースの本数は

f(N) = 3 * (N-1)/2 + 1

になります。

ここまでをまとめると、

f(N) = 3 * (N-2)/2 + 2 (Nが偶数のとき)
       3 * (N-1)/2 + 1 (Nが奇数のとき)

です。

コードにしてみましょう。メソッドの最初にamountが0の時に0を返す処理を書いています。 amount % 2はamountを2で割ったときの余りという意味です。

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    case amount % 2
    when 0
      3 * (amount - 2) / 2 + 2
    when 1
      3 * (amount - 1) / 2 + 1
    end
  end
end

2つの式は似ているので、工夫すればまとめられそうです。 2つの式の違いは、amountから引いている数と最後に足している数です。この数は最後に手元に残る瓶の本数でした。

奇数と偶数で値が異なるので、

last_amount = amount % 2 === 0 ? 2 : 1
3 * (amount - last_amount) / 2 + last_amount

のようなコードを書きたくなりますが、あまりよい方法とは言えません。"3本で1本プレゼント"が"4本で1本プレゼント"になったときに対応できなくなってしまいます。

基本的には剰余(割り算の余り)を考えればよいのですが、割り切れる時には2にします。

last_amount = amount % 2 === 0 ? 2 : amount % 2
3 * (amount - last_amount) / 2 + last_amount

3項演算子を使わなくても、一旦1を引いて剰余を求めてから1を足すと同様の結果が得られます。

last_amount = (amount - 1 ) % 2 + 1
3 * (amount - last_amount) / 2 + last_amount

式を整理して、最終的にこちらのコードになります。

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    last_amount = (amount - 1 ) % 2 + 1
    (3 * amount - last_amount) / 2
  end
end

完成です!

あとがき

最初に再帰アルゴリズムを思いついたのですが、最終的に四則演算と剰余だけで求めることができました。 試行錯誤できて楽しい問題でした。

ちなみに5本で1本交換の場合は、以下のようになります。

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    last_amount = (amount - 1 ) % 4 + 1
    (5 * amount - last_amount) / 4
  end
end

算数としてはこれで答えは出るのですが、プログラミングとしては整除を使用すればもう少し短く書けるかもと思いました。

こちらもどうぞ

yucatio.hatenablog.com

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

面白くて眠れなくなる数学 (PHP文庫) [ 桜井進 ]
価格:691円(税込、送料無料) (2019/2/8時点)


JavaScriptのnew Array(n)をmapしたいとき fillをはさむ理由

経緯

配列をオブジェクトで初期化したい場合、

new Array(3).fill({foo: "ふう", bar:"ばあ"})

というコードだと、全てのインデックスが同じオブジェクトを指してしまうので、 調べたら

new Array(3).fill().map(() => ({foo: "ふう", bar: "ばあ"}))

という方法が出てきたので試したらうまく行きました。

疑問

このfill()要らなくない?new Array(3).map(() => ({foo: "ふう", bar: "ばあ"})) って書けばよさそうな気がします。

答え

fill()は必要。

理由はここに書いてありますが、英語なので日本語で&自分で実行しながら書いていきます。

itnext.io

まず、JavaScriptの配列は、実質的には数値をキーとしたオブジェクトです。

例えば、以下のように配列を初期化します。

const array = ['りんご', 'みかん', 'バナナ']

console.log("array", array)

これを実行すると以下のようになります。

f:id:yucatio:20190407105938p:plain

{
  0: "りんご"
,
  1: "みかん"
,
  2: "バナナ"
,
  length: 3

}

上記配列はこのオブジェクトを宣言したのと同じになります。

さて、今度は今度はArrayのコンストラクタを使った場合をみてみます。

const array = new Array(3)

console.log("array", array)

実行結果です。

f:id:yucatio:20190407110103p:plain

{
  length: 3

}

この場合はlengthのみ含まれているオブジェクトになっています。数値のキーはありません。

コンストラクタで作成された配列に対して、map()を呼び出してみます。

const array = new Array(3).map(() => ({foo: "ふう", bar: "ばあ"}))

console.log("array", array)

実行結果です。

f:id:yucatio:20190407110103p:plain

{
  length: 3

}

何も設定されていません。mapに渡したコールバックが呼ばれていないことがわかります。

公式ドキュメントのArray.prototype.map()のページには、下記のように書いてあります。

callback は、値が代入されている配列のインデックスに対してのみ呼び出されます(undefined が代入されているものも含みます)。すでに削除されたインデックスや、まだ値が代入されていないインデックスに対しては呼び出されません。

https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/map

つまり、new Array(3)だけした状態でmapを呼び出しても、インデックス(オブジェクトのキー)がないので1度もコールバックが呼ばれないのです。 この挙動はforEachやreduce、filterなども同様です。

そこで、先人の教えの通り、一旦fill()します

const array = new Array(3).fill()

console.log("array", array)

実行結果です。

f:id:yucatio:20190407110128p:plain

{
  0: undefined
,
  1: undefined,

  2: undefined,
  length: 3
}

インデックスのキーが作成されました。fillに引数を渡していないので、各値はundefinedです。

この状態でmap()をすれば、各キーに対してコールバックが呼ばれそうです。

const array = new Array(3).fill().map(() => ({foo: "ふう", bar: "ばあ"}))

console.log("array", array)

実行結果です。

f:id:yucatio:20190407110144p:plain

{
  0: {foo: "ふう", bar: "ばあ"},
  1: {foo: "ふう", bar: "ばあ"},
  2: {foo: "ふう", bar: "ばあ"},
  length: 3
}

配列に初期値を設定できました。

あとがき

オブジェクトで配列の初期化をする方法は複数ありますが、どれも初心者にとって直感的ではないのでなんとかならないかなと思います。


「5と8を使った和で表すことができない最大の整数を求めよ」を解いてみる

小2が「5と8を使った和で表すことができない最大の整数を求めよ」という大学入試レベルの算数を教えてと聞いてきた

togetter.com

この問題が面白いなと思って自分なりに解いて見たので書いてみます。数学は専門ではないので厳密さに欠けることは先に記しておきます。

問題を書き直すと、

8x + 5y (xとyは0以上の整数) で表される数で、表現できない最大の数はいくつか

になります。

問題文から、ある程度大きい数字であれば5と8の和で表すことができるので、適当な数で確かめます。 49にでもしましょうか。

49から8を順に引いていきます。

f:id:yucatio:20190209142054p:plain
49から8を引いていく

さらに5で割った余りを下に書いていきます。

f:id:yucatio:20190209142142p:plain
5で割った余りを書く

25が5で割り切れますね。25までは49から3回8を引いていますので、

49 = 8 × 3 + 5 × 5

で表すことができます。別の数でもやってみましょう。8を引いていった数字と、それぞれ5で割った数字を書きます。

f:id:yucatio:20190209142813p:plain
48から8を引いていく

40が5で割り切れます。40まで1回8を引いているので、

48 = 8 × 1 + 5 × 8
(もちろん、48 = 8 × 6 でもよいです)

f:id:yucatio:20190209143221p:plain
47から8を引いていく

15が5で割り切れます。15まで4回8を引いているので、

47 = 8 × 4 + 5 × 3

長くなるので、たくさんのパターンは書けませんが、ある数から8を引いて、それを5で割った余りは、

f:id:yucatio:20190209151022p:plain
0 -> 2 -> 4 -> 1 -> 3 の繰り返し

この順番で現れることがわかります。もう少し大きい数でも確かめてみましょう。97でやってみます。

f:id:yucatio:20190209152509p:plain

なりますね。実際に定理になってると思うのですが、何の定理か忘れました。

ある数から8ずつ引いていくと、5回に1回は、5で割った余りが0になる(=5で割り切れる=5の倍数である)ということがわかりました。

ということは、ある数から4回以上8が引ければ、元の数と合わせて5個の数字が並び、その中の1つは5で割り切れます。4回以上8が引ける数の最小は33 (= 8 * 4 + 1 ) です。確かめてみると、

f:id:yucatio:20190209152956p:plain
33から8を引いていく

33 = 8 × 1 + 5 × 5

で表すことができます。

32のときは

f:id:yucatio:20190209154140p:plain
32から8を引いていく

5で割り切れる数は出てきませんが、8で割り切れるので、

32 = 8 × 4

です。1つずつみていきましょう。

31のときは、

f:id:yucatio:20190209154204p:plain
31から8を引いていく

31 = 8 × 2 + 5 × 3

30のときは、

f:id:yucatio:20190209154224p:plain
30から8を引いていく

30 = 5 × 6

29のときは、

f:id:yucatio:20190209154252p:plain
29から8を引いていく

29 = 8 × 3 + 5 × 1

28のときは、

f:id:yucatio:20190209154400p:plain
28から8を引いていく

28 = 8 × 1 + 5 × 4

27のときは、

f:id:yucatio:20190209154420p:plain
27から8を引いていく

27から8を引いていっても5の倍数にならないので、27が 8x + 5y で表すことのできない最大の数ということがわかります。

実は、32から1つずつみていかなくても、規則性を見ていけば計算で答えを求められます。

f:id:yucatio:20190209151022p:plain

32から25までは8が3回引けるので、元の数と合わせて4つの数が並びます。4つの場合、上の図で、2から始まると 2 → 4 → 1 → 3になり、0が出てこない(=5で割り切れない)ことが分かります。

5で割った余りが2になる33より小さい数は、32ですが、これは8の倍数(32 = 8*4)なので、次に大きい27(=32-5)が答えになります。

あとがき

小学校2年生まで習う知識ではとても解けなさそうでした。

ネット上に同じ解法が載っているかもしれませんが、見つけられませんでした。

この問題自体はフロベニウスの硬貨交換問題として知られているそうです。

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

面白くて眠れなくなる数学 (PHP文庫) [ 桜井進 ]
価格:691円(税込、送料無料) (2019/2/8時点)


RSpecでsubjectを使用して配列を検査時、配列の長さを取得する

RSpecでsubjectを使用して、配列を

subject { user.errors[:name] }  # user.errors[:name] は配列

このように検査時、配列の長さを取得する方法が分からなかったので調べました。

結論

rspec-itsitsを使用する。

its(:size) { is_expected.to eq 3 }

のように書くとsubjectの検査対象の配列の長さを取得できます。

経緯

モデルのテストを書きました。

modelのコード↓

class User < ApplicationRecord
  validates :nickname, presence: true, length: { maximum: 32 },
                       format: { with: /\A[-0-9a-zA-Z#$%&()._]*\z/,
                                 message: 'には半角英数字と#$%&()-._のみ使用できます。' }
end

テストは以下のようになります。(全て書くと長いので一部のみ抜粋)

require 'rails_helper'

RSpec.describe User, type: :model do
  describe '#nickname' do
    context '空白のとき'do
      it 'エラーが出ること' do
        user = User.new(nickname: '')
        user.valid?
        expect(user.errors[:nickname]).to include("can't be blank")
      end
    end

    context '許可される文字の場合' do
      context '英大文字小文字数字#$%&()-._' do
        it 'エラーが出ないこと' do
          user = User.new(nickname: 'ARZatz809(_#-$%.&)')
          user.valid?
          expect(user.errors[:nickname]).to be_blank
        end
      end
    end

    context '許可されない文字の場合' do
      context '許可されていない文字"?"が含まれている場合' do
        it 'エラーが出ること' do
          user = User.new(nickname: 'correct?')
          user.valid?
          expect(user.errors[:nickname]).to include('には半角英数字と#$%&()-._のみ使用できます。')
        end
      end
    end
  end
end

これを綺麗にすると以下のようになります。(参考: 使えるRSpec入門・その1「RSpecの基本的な構文や便利な機能を理解する」 - Qiita )

require 'rails_helper'

RSpec.describe User, type: :model do
  describe '#nickname' do
    subject { user.errors[:nickname] }

    let(:user) { User.new(params) }
    let(:params) { {nickname: nickname} }

    before do
      user.valid?
    end

    context '空白のとき'do
      let(:nickname) { '' }
      it { is_expected.to include("can't be blank") }
    end

    context '許可される文字の場合' do
      context '英大文字小文字数字#$%&()-._' do
        let(:nickname) { 'ARZatz809(_#-$%.&)' }
        it { is_expected.to be_blank }
      end
    end

    context '許可されない文字の場合' do
      context '許可されていない文字"?"が含まれている場合' do
        let(:nickname) { 'correct?' }
        it { is_expected.to include('には半角英数字と#$%&()-._のみ使用できます。') }
      end
    end
  end
end

繰り返しがなくなってすっきりしました。

ここでふと思いました。 このテストコード、対象のエラーが含まれることはチェックできるけど、想定外のエラーが(間違って)含まれることはテストできていないじゃん、と。

ここでの方針としては、

  • includeでなく配列同士の比較を行う
  • エラーの数をチェックする

などが思いつきます。今回は

  • エラーの数をチェックする

方法にします。この方法をとることで、

  • エラーの順番は問わず
  • 想定外のエラーが間違って入っていることを防ぐ

ことができます。

さて、テストの対象はsubjectに書かれています。これのサイズを取得したい。 これにはitsを使用します。

RSpec3からitsはgemに分離されているのでインストールします。

Gemfile

group :development, :test do
  # Call 'byebug' anywhere in the code to stop execution and get a debugger console
  gem 'byebug', platforms: [:mri, :mingw, :x64_mingw]
  gem 'rspec-rails'
  gem 'rspec-its'  # この行を追加
end

bundle installします。

テストを追加します。

its(:size) { is_expected.to eq 1 }のように書くとuser.errors[:nickname].sizeが1かどうかをテストすることができます。

RSpec.describe User, type: :model do
  describe '#nickname' do
    subject {user.errors[:nickname]}

    # 略

    context '空白のとき'do
      let(:nickname) { '' }
      it { is_expected.to include("can't be blank") }
      its(:size) { is_expected.to eq 1 }  # 追加
    end

    context '許可される文字の場合' do
      context '英大文字小文字数字#$%&()-._' do
        let(:nickname) {'ARZatz809(_#-$%.&)'}
        it { is_expected.to be_blank}
      end
    end

    context '許可されない文字の場合' do
      context '許可されていない文字"?"が含まれている場合' do
        let(:nickname) {'correct?'}
        it { is_expected.to include('には半角英数字と#$%&()-._のみ使用できます。')}
        its(:size) { is_expected.to eq 1 }  # 追加
      end
    end
  end
end

以上でsubjectに指定した配列のサイズ(長さ)をテストすることができました。

環境

参考


正規表現間違い探しクイズ その3

正規表現間違い探しクイズシリーズです。

正規表現単体テストを書いている場合でもバグを発見しづらいものです。そのため、自身での検証が欠かせません。 今回は仕事中に見つけたものでなく、個人開発中にネットで見つけた間違いのうち印象的だったものを少し変えて紹介します。

問題編

仕様

  • 行頭及び行末の#記号を取り除くString#strip_hashを定義する
  • #記号は連続している可能性がある
  • #記号がない場合もある

動作イメージ

  • ###本文本文
  • #大切#大切
  • 普通普通

ソースコード

ソースコードです。 今回はRubyで実装します。

class String
  def strip_hash
    sub(/^#*([^#]+)#*$/, '\1')
  end
end

正規表現^#*([^#]+)#*$は、行頭に続き#の0回以上の繰り返し、続いて#以外の文字の繰り返し、#の0回以上の繰り返し、行末、を意味します。subメソッドを使用して、1つ目のグループ([^#]+)を抜き出しています。

f:id:yucatio:20190107194148p:plain

さて、この正規表現には明らかな間違いがあります。どのような間違いでしょうか。また、どのように修正するべきでしょうか。

テスト

以下のテストはパスしています。RSpecで書いています。

describe '#strip_hash' do
  subject { str.strip_hash }

  context '#が含まれているとき' do
    context '行頭に#がある場合' do
      let(:str) { '###文字列' }
      it { is_expected.to eq '文字列' }
    end

    context '行末に#がある場合' do
      let(:str) { '文字列###' }
      it { is_expected.to eq '文字列' }
    end

    context '行頭と行末に#がある場合' do
      let(:str) { '###文字列###' }
      it { is_expected.to eq '文字列' }
    end
  end

  context '#が含まれていないとき' do
    let(:str) { '文字列' }
    it { is_expected.to eq '文字列' }
  end
end

解答編

少し考えてから解答編を見てください

続きを読む