アルゴリズムパズル 6-7 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の6, 7番目の問題「行と列の入れ替え」の実装例です．

2. 解

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

2.1. 問題6 指数え

本の解説のとおりなのでまぁ実装する必要はない

	; 6. 指数え
	(defparameter *fingers*
	(list
	"index finger" "thumb" "index finger" "middle finger"
	"ring finger" "little finger" "ring finger" "middle finger"))
	(defun solve-6 (n)
	(nth (mod n 8) *fingers*))

view raw algorithm_puzzle_6.cl hosted with ❤ by GitHub

2.2. 問題7 真夜中の橋渡り

1分の男を何回も酷使すればいけるのではと思ったら駄目だったので少し考えることになった問題．良問だと思うが一般的に解く方法は全探索しか思いつかない．
解説にあるが「橋とトーチ問題」という有名な問題でそこそこ研究されてるらしいが特に調べてないのでわからない．
なお今回のような「歩くのが遅いやつ二人をどこかで一緒に連れてく」という方法では最適解を得られない場合もある(例：5分 6分 6分 7分のひとがいる条件では一番渡るのが早いやつが懐中電灯を持ってひたすら往復するのが一番早い)

	// アルゴリズムパズル 7. 真夜中の橋渡り
	use std::io;
	use std::cmp::{max,min};
	use std::collections::BinaryHeap;
	fn read_line() -> String{
	let mut s = String::new();
	io::stdin().read_line(&mut s).unwrap();
	s.trim().to_string()
	}
	fn read_ints() -> Vec<i64>{
	let s = read_line();
	let split:Vec<&str> = s.split(" ").collect();
	split.iter().map(|&x| x.to_string().parse().unwrap()).collect()
	}
	fn take_2_pattern(xs:&Vec<i64>) -> Vec<(usize,usize)>{
	let mut ret = vec![];
	for i in 0..xs.len(){
	for j in i+1..xs.len(){
	ret.push((i,j));
	}
	}
	ret
	}
	fn solve(from:Vec<i64>,dest:BinaryHeap<i64>)->i64{
	if from.is_empty(){
	return 0;
	}else if from.len() <= 2{
	return max(from[0],from[1]);
	}
	let pattern = take_2_pattern(&from);
	let mut min_val = 9999999999;
	for (i,j) in pattern{
	let mut from = from.clone();
	// 小さい順のbinaryheapがわからないので符号を反転して使う(良くないが)
	let mut dest = dest.clone();
	let mut cost = max(from[i],from[j]);
	// i<jよりjを先に削除する
	dest.push(-from.remove(j));
	dest.push(-from.remove(i));
	// 返ってくるのは橋の向こう側にいるやつで一番早く返ってこれるやつでよいはず
	cost += -dest.peek().unwrap();
	from.push(-dest.pop().unwrap());
	min_val = min(min_val,cost + solve(from,dest));
	}
	min_val
	}
	fn main(){
	let xs = {
	let mut temp = read_ints();
	temp.sort();
	temp
	};
	println!("{}",solve(xs,BinaryHeap::new()));
	}

view raw algorithm_puzzle_7.rs hosted with ❤ by GitHub

3. 所感

難易度はまだ低いがまぁよい．
プログラミングの能力というのはぶっちゃけアルゴリズムを考える能力や数学力によって上限が決まってしまうので，それをどう上げるかが大事だと思ってるのだけれど，それが上がってないのはよく感じる．
そう考えるといちいち実装する必要はないので，頭で解けば良い問題は頭で解いて，実装が楽しそうな問題だけ実装することにした．
ただし今後も1日～2日に1回はブログを更新するつもり．