アルゴリズムパズル 2-4 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』という本の問題を解いてる．
初級編なので無限に簡単すぎてあまり面白みを感じられてない．
プログラムも短いのでまとめて問題2-4の実装例を貼っておく．

2. 実装例

この本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本なので，ブログにパズルの内容について書くのは引用に収まるのか？という疑問があるので問題文は書かないです．

2.1. 手袋選び

最悪のケースだけ考えれば良いということに気づかなかったのは痛いが，手袋が左右違うというのは問題文に書いておくべきではと思った．
ヒントにあるとおり(a)はたまたま同じ側の手袋が出まくるケースを，(b)はたまたまたくさんある色が出まくってて，しかも片方の方の手袋が出まくるケースを考えれば良いですね．
そうするともうただ計算式を書くだけという感じなのでプログラムを書く必要ないな……という感じです．

	; アルゴリズムパズル 2
	(defun solve-2-a (xs)
	(1+ (apply #'+ xs)))
	(defun solve-2-b (xs)
	(let*(
	(ys (sort xs #'<))
	(min-val (first ys))
	(rest-ys (rest ys)))
	(+ (* 2 (apply #'+ rest-ys)) 1 min-val)))
	(print (solve-2-a '(2 3 5)))
	(print (solve-2-b '(2 3 5)))

view raw algorithm_puzzle_2.lisp hosted with ❤ by GitHub

2.2. 長方形の分割

数字やテキストの処理で済まないのではみたいな問題だったが再帰的に直角三角形を分割するプログラムをProcessingで書いた．
まぁ無限に分割の仕方はあるので本とは異なる実装にはなった(長方形をまず直角三角形に分割して，それぞれの三角形をint(n/2)個とn-int(n/2)個の直角三角形に分割するのを繰り返してる)．
見た目は本よりも良さそうではあるが初級編なので著者は再帰関数を使わない手法にしたんだろうなぁと思うなどした．

実装のための計算で，ベクトルを幾何のベクトルとして触ったの何年ぶりだよという感じだった(そしてふつうに計算ミスしたりしてた)．

	void setup() {
	size(640, 480);
	}
	void draw() {
	background(0);
	make_triangle(millis()/100);
	}
	void make_triangle(int n) {
	int n1 = n / 2;
	int n2 = n - n1;
	split_triangle(n1, 1, 1, 1, height-1, width-1, height-1);
	split_triangle(n2, 1, 1, width-1, 1, width-1, height-1);
	}
	void split_triangle(
	int n, float x0, float y0, float x1, float y1, float x2, float y2) {
	// 頂点(x1,y1)で直角となている直角三角形を描画
	triangle(x0, y0, x1, y1, x2, y2);
	if (n<=1)return;
	// 次の直角三角形の座標を計算
	float d1 = dist(x0, y0, x1, y1);
	float d3 = dist(x2, y2, x0, y0);
	float k = (d1/d3)*(d1/d3);
	float x3 = k * (x2-x0) + x0;
	float y3 = k * (y2-y0) + y0;
	int n1 = n / 2;
	int n2 = n - n1;
	split_triangle(n1, x0, y0, x3, y3, x1, y1);
	split_triangle(n2, x2, y2, x3, y3, x1, y1);
	}

view raw algorithm_puzzle_3.pde hosted with ❤ by GitHub

2.3. 兵士の輸送

1人のケースについて考えればあとはそれをn人に適用するだけなのでプログラムを書くほどでもない……

	(defun solve-4 (n-soldier n)
	(if (= n-soldier 0)
	(print (format nil "~{~A~}" (list "it takes " (write-to-string n) " steps.")))
	(progn
	(print "2 young man go to left.")
	(print "1 young man go to right")
	(print "1 soldier go to left.")
	(print "1 young man go to right.")
	(solve-4 (1- n-soldier) (+ 4 n)))))
	(solve-4 25 0)

view raw algorithm_puzzle_4.lisp hosted with ❤ by GitHub

3. 所感

こうやってブログに書くことで継続的にやるモチベーションを作ってるのだけど問題が簡単すぎるとモチベダウンがすごい．上級者向けは多分僕が逆立ちしても解けないんだろうけど．