「プログラマ脳を鍛える数学パズルを解こう会」を開催しました

（盛り上がってほとんど写真撮るの忘れてました）

Toyama.rb #05イベントとして、「プログラマ脳を鍛える数学パズルを解こう会」を開催しました。

プログラマ脳を鍛える数学パズル ?

↓こちらの書籍です

www.shoeisha.co.jp

翔泳社主催のITエンジニア本大賞 2016技術書部門大賞にも選ばれました。プログラミングのスキル評価サイト CodeIQに掲載された問題から良問とされる問題が抜粋されており、解き方のサンプルなども掲載されています。

私個人としては、Amazonで翔泳社の技術書籍が半額セールだった時にkindle版を購入しました。

勉強会のテーマに

基本的にToyama.rbは毎回もくもく会を主体に開催していたので、各自が好きなテーマでもくもくとコードを書いていましたが、今回は主催者（というか私）の都合で開催週がズレてしまい、「参加者が少ないかもな〜」→「じゃあ実験的にいつもと違うことやってみよう！」という発想で、この本をテーマに開催することにしました。

チョイスした問題

問題自体は私の独断と偏見で良さそうなもの（できれば現実世界の具体的なモノをイメージしやすそうなもの）をチョイス。比較的本の中でも前半〜中盤に掲載されている易しめの問題にしましたが、実際やってみたら全然易しくなかったという現実。

というより、解こうと思えば解けるけど、パフォーマンスや可読性などを考えると良い感じのコードにならなくて悩むという。易しめのにしたのは正解だったかも。

実際の問題は↓です

Q1. バスの両替機

前提条件

両替で出てくるのは 500/100/50/10円の硬貨のみ
両替で払い出せるのは最大で15枚まで

問題

1000円投入した場合の両替パターンは全部でいくつあるか？

実際解こうと思うと、意外と手が止まっちゃいました。

悩んだ挙句私が叩き出したコード

module Q1
  def self.count
    # プライドを捨ててすべての組み合わせで1000円になるやつを探す
    count = 0
    (0..15).to_a.each { |a|
      (0..15).to_a.each { |b|
        (0..15).to_a.each { |c|
          (0..15).to_a.each { |d|
            if ((a + b + c + d) <= 15 && 500 * a + 100 * b + 50 * c + 10 * d) == 1000
              count += 1
            end
          }
        }
      }
    }
    count
  end
end

puts "answer : #{Q1.count}"

コメントがすべてを物語る。

後輩が書いてきたら「お前本当にこれで良いと思ったのか」って言われるレベル。

(0..15).to_a.each { |a| }の部分をコピペしている時に「絶対これ違うわ！！」と頭をよぎってました。

イメージ的には再帰を使ってスマートに解きたかったんですけど、時間制限を設けたのもあって間に合わず、途中で思考放棄してこんなコードに。

そして後で書籍を見ると、解答サンプルにこれを同じコードが乗っていて

「単純に解くならこんなコードで大丈夫だよ！」
「わぁ、これなら僕でも理解できるや！！」

という扱いを受けていました。屈辱である

他の参加者のコード

他の参加者の方のコードの中で、個人的に「お〜」と思ったのがコチラ

module Q1
  def self.count
    coins = [10, 50, 100, 500]

    result = []
    (2..15).each do |n|
      coins.repeated_combination(n).each do |cs|
        result << cs if cs.inject(:+) == 1000
      end
    end
    result.count
  end
end

puts "answer : #{Q1.count}" #=> answer : 20

私のコードのように無駄な重複がありません。
そして、repeated_combination がポイントですね。

→ リファレンス

呼び出すだけで、重複を許可したすべての組み合わせを列挙してくれます。
こういった機能の充実具合がさすがRubyだな〜といった感じです。

普通に知らなかった・・
（でもこういうとき以外で使うタイミングあるのかな？）

解き方のアプローチの違い

おもしろいな〜と思ったのが、もちろん最終的なコードは違いますが、解くまでのそもそものアプローチが人によって違っていたことでした。

上記の例の場合、根本的な考え方は

使える硬貨を組み合わせて1000円になる組み合わせを探す

となりますが、人によっては

1000円から使える硬貨を引いていき、0になるものを見つけていく

という攻め方をしていました。イメージ的には実際の両替に近いですね。

そして第2問目↓

Q2. ストラックアウト

前提条件

ストラックアウトをイメージ

| 1 | 2 | 3 |  
| 4 | 5 | 6 |
| 7 | 8 | 9 |

ボールを投げると的が抜ける
ボールは必ずいずれかの的にヒットする
5以外の的は2枚抜きができる (1&2, 4&7 などはok / 5&6, 2&5などは不可)

問題

的がすべて抜ける投球パターンはいくつ存在するか？

ポイントは2枚抜き。
というか2枚抜きがなければ階乗を出すだけで一瞬で終わりますね。

1問目以上に（私含め）苦戦していたようです。

なんか明らかに少ない数字になるぞ・・
処理が返ってこないぞ・・

といった声が多数。大変楽しんでいただけたようです。

私がひねり出したコード

module Q2
  PATTERN = [
    [1], [2], [3], [4], [5], [6], [7], [8], [9],
    [1, 2],
    [2, 3],
    [3, 6],
    [6, 9],
    [9, 8],
    [8, 7],
    [7, 4],
    [4, 1]
  ]

  def self.hit(board, target)
    # いずれかが存在しなければ不正な投球
    target.each { |n| return 0 unless board.include?(n) }

    hit_board = board - target

    # 空になったら終わり
    return 1 if hit_board.empty?

    # 残りのパターンを網羅
    return PATTERN.map { |target| self.hit(hit_board, target) }.inject(:+)
  end

  def self.strike
    PATTERN.map { |target| self.hit((1..9).to_a, target) }.inject(:+)
  end
end

puts "answer : #{Q2.strike}"

今回は何を思ったか「今回は再帰で解きます！」と宣言してスタートしたので、明らかに自分の首を締めてしまったのですが、なんとか宣言通りのコードになりました。

「投げられるパターンが決まってるなら、全部投げていけばいいじゃない！」というスタンス。

コードの綺麗さというか、すっきりしてる感じでは悪くないのでは？と思います。

が・・・今回の問題では、答えを出す以外にも、さらに隠れ課題が。

処理速度

上記のコードでも答えは出るのですが、実行すると私のマシンでは約20秒程度かかります。

別に1回限りだしいいじゃん、という考えもありだとは思います。

でもほら、なんというか、速くできるなら速くしたいじゃないですか！！そこに深い意味はないんですよ！

他の参加者のコード

まずは私と同じく再帰を使っていた方の解答です

module Q2
  NUMS = (1..9).to_a
  PAIRS = [[1, 2], [1, 4], [2, 3], [3, 6], [4, 7], [6, 9], [7, 8], [8, 9]]

  module_function

  def hit seq, left = NUMS.dup
    if left.empty?
      [seq]
    else
      [
        *left.map do |i|
          hit [*seq, i], (a = left.dup; a.delete(i); a)
        end.inject(:+),
        *PAIRS.select { |pair| pair.all? { |i| left.include? i } }.map do |pair|
          hit [*seq, pair], left - pair
        end.inject(:+)
      ]
    end
  end

  def strike
    (@sequences = hit([])).count
  end

  def sequences
    @sequences
  end
end

以下がポイントなのかな〜と思いました。

実際の投球パターンを網羅したリストが作成される
不必要な投球を削ることで処理速度が向上されている

無駄が省かれているため、私のコードより2倍ほど高速に。

同じ再帰なのにこうも違うコードになるのか・・と感心してしまいました。

最速だったコード

そして全員のコードで最速だったコードが以下でした。

module Q2
  def self.strike
    board = *(1..9)
    count = factorial(board.count)

    two_numbers = (board.zip(board.rotate) + board.zip(board.rotate(3))). #=> [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 1], [1, 4], [2, 5], [3, 6], [4, 7], [5, 8], [6, 9], [7, 1], [8, 2], [9, 3]]
                   select {|ns| ns[0] < ns[1] }.
                   reject {|ns| ns.include?(5) }.
                   reject {|n| [[3, 4], [6, 7]].include?(n) }

    (1..4).each do |n|
      two_numbers.combination(n).each do |nums|
        next if nums.flatten.size != nums.flatten.uniq.size

        numbers = nums + board.select {|b| !nums.flatten.include?(b) }
        count += factorial(numbers.count)
      end
    end

    count
  end

  def self.factorial(number)
    (1..number).inject(1,:*)
  end
end

おそらくこのコード、書籍に載っていたサンプルより速いのではないでしょうか。
マシンスペックにもよりますが、おおよそ1ms〜2msで終了するようです。（爆速）

ポイントは、「そもそも網羅的に捜査はしていない」ということかもしれません。

処理的には

まず、投球のユニークな組み合わせを列挙する
組み合わせごとに階乗値 = 投球パターンを算出する
2の合計を算出する

という流れのようで、結果的に処理の大半が単純な数値の演算となるため、非常に高速に動作するようです。

実際に自分でコードを書いたときには、「いかに網羅して調べるか」ということばかり考えていたため、そもそも階乗すればいいじゃない、という発想がありませんでした。

根本の部分で自分の発想を疑ってみるのも大事ですね〜・・

ちなみに

今回は「よくやったで賞」という小学校のお楽しみ会でありそうな賞を用意しました。

具体的に何をしたか、というより

この人今日よくやったな

という人を投票で決めよう！というもの。

副賞として1,500円分のAmazonギフトカードを贈呈。(もちろん私の自腹で！)

結果的には上記の最速コードの作者に贈呈されました。おめでとうございます！

終わってみて

思いつきで開催した企画だったのですが、個人的にはかなり面白い内容だったと思います。同じテーマでコードを書いたこともあり、会話も活発でした。

そして、人のコードを見るのは本当に参考になりますね〜

そもそも自分じゃ思いつかない発想に触れられるのはそれだけで貴重。

普段の業務で求められるコードなど、バックグラウンドとなる部分が人によって異なるからこういう結果になるのでしょうね。こういうのはコミュニティならではかもしれません。

また機会があれば全員で同じテーマでコードを書くイベントをやってみたいな〜