【Project EulerにRubyで挑戦シリーズ】問15:Lattice paths

スポンサーリンク

今回の問題

Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.

書いた内容

懐かしき高校数学の格子最短経路の問題です。

2×2の格子であれば、
異なる 4 個(右・下)の選択肢から 2 個の(右)を選ぶ組み合わせなので
4C2 = 4*3/2*1 = 6通り

それが20×20の格子であれば、
40C20を計算するだけです。

puts [*21..40].inject(:*) / [*1..20].inject(:*)

Cの計算をメソッド化して終わりにしました。

def lattice_path_roots(lattice_number:)
  total = lattice_number * 2
  n = ((total - lattice_number + 1)..total).inject(:*)
  r = (1..lattice_number).inject(:*)
  return n / r
end

puts lattice_path_roots(lattice_number: 20)

※Project Eulerのリポジトリ

          
    

スポンサーリンク

  
Scroll Up