Project Eular 15: 正方形の道筋は幾つあるの? について

はじめに

数学の問題をプログラミングで解こう! という趣旨の、プログラミング問題集であるところのProject Eularというサイトがあって、非常に初歩的なんだけど、解くのを面倒臭がって放置していた問題として、20 x 20の正方形の道筋はいくつあるの?という問題がある。久しぶりにやってみたら、スムーズに解けたので、嬉しくなったので、その辺りの話をメモしておこうと思う。処理系は以前と同じRacketで。

非効率な方法: 単純な再帰でやってみよう

もちろん、この手の問題はしらみつぶしに調べていけば、その数の総数を調べることができる。考え方としては、問題の性質上、「右か下か」に行くことができる。そして、「問題の正方形の幅を超えてしまったら移動できない」という風な考え方ができるだろう。汚い図にすると下のような感じ:

これを素朴に実装すると、下のようになる:

(define X 3)
(define Y 3)

(define (can-walk x y)
  (append (if (< x X) '(x) null)
          (if (< y Y) '(y) null))) 

(define (walk x y)
  (if (and (= x X) (= y Y)) 'G
      (map (lambda (go-to)
             (cond [(and (symbol=? 'x go-to) (< x X)) (walk (+ x 1) y)]
                   [(and (symbol=? 'y go-to) (< y Y)) (walk x (+ y 1))]))
           (can-walk x y))))

(define (goal-length x)
  (length (flatten x)))

確かに、これだと少ない道筋だったりするといいんだけど、今回のように20x20だと圧倒的にメモリが足りなくなってしまうので良くない。

ほんの少しだけ効率的な方法: パスカルの三角形を利用する

これでダメだとすると、もう少し効率的な方法があるはずだ。例えば2x2の四角形の道筋の出し方を考えて見る:

ここでよく見てみると、Fという点への向かい方は3通りなのだけれど、これはCの時点での向かい方の数+Eの時点での向かい方の数、ということの組み合わせだということだ。そして、Eの時点の組み合わせは、Bを経路する方法と、Dを経路する方法の二つある組み合わせであることがわかる。そして、点線で斜めに弾いてるのものがあるけれど、この半分下の部分はパスカルの三角形になっている。つまり:

  1
 1 1
1 2 1 

という形になっていて、この最後の段を、今度は逆に隣同士でマージしていけばいいということになる。この場合なら

(1 + 2) + (2 + 1) = 6

となる。また3x3だと、最後の列は

   1
  1 1
 1 2 1
1 3 3 1

となり、

(1 + 3), (3 + 3), (1 + 3)
=> 4, 6, 4
=> (4 + 6), (6 + 4)
=> 10, 10
=> (10 + 10)
=> 20

となり、組み合わせは20通りということになる。

したがって、このようにパスカルの三角形を生成する関数と、それを逆にマージしていくような関数を定義してあげればいいことになる:

(define (pascal x)
  (pascal-p x 1 '()))

(define (pascal-p x point dan)
  (let ([next-point (+ point 1)])
    (cond [(= point 1) (pascal-p x next-point '(1))]
          [(> point x) dan]
          [else (let ([up-dan (cons 0 dan)])
                (pascal-p x next-point
                          (map (lambda (elem) (apply + elem))
                               (for/list ([up-elem up-dan]
                                          [down-elem (reverse up-dan)])
                                 (list up-elem down-elem)))))])))

(define (reverse-pascal now-list)
  (cond [(= (length now-list) 1) now-list]
        [else (reverse-pascal (press-dan now-list '()))]))

(define (press-dan now-list create-list)
  (cond [(= (length now-list) 1) create-list]
        [else (press-dan (cdr now-list) (cons (+ (car now-list) (cadr now-list)) create-list))]))

基本的にパスカルの三角形は、過去のブログから再掲するけれど、現在の段を下のように組み合わせるような関数を定義してあげればいいことになる:

マージ方法についてだけれど、基本的にはどんどんスライドさせてあげればいいだけなので、そういう風な関数を書いている。

まとめ

手書きで解説画像を書くのは楽なので、今後はブログにどんどん書いていきたい。

あと、Project Eularは、単純なプログラミング問題というよりも(その手の問題もあるんだけど)、どちらかというと上みたいなちょっとした数学的なコツも試されたりする部分もあるっぽいので、まだ初歩的な解けない問題もあるけれど、焦らず、気が向いたらちょくちょく解いていきたいなと思う。