アルゴリズムパズル 49-60 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の29-48番目の問題の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 49 宣教師と人食い人種

全幅探索だよなぁっておもって答え見て，状態空間グラフとか解答には書いてあるけど結局のところ禁止操作を除いた全幅探索では？と思ってる．

2.2. 50 最後の球

気づくのに時間がかかった．僕は(黒の球の数)x2+(白の球の数)がどちらの操作でも不変だということに気づいて回答したが，白の球の数のみに注目すれば良いことに答えを見てから気づいた．

2.3. 51 存在しない数字

まぁ100を法とした和が計算できれば行けるが……それはジルにできるのか？と半ば不安ながら答えを見た．できるらしい．
この手の問題は何言ってもヒントになってしまうので問題出題側に厳しいところがある．

2.4. 52 三角形の数え上げ

適当に数字を並べば法則性は見える，なんかややこしいだけな気がしたので証明は特にしなかった

2.5. 53 バネ秤を使った偽造硬貨の検出

にぶたん．$W(n)=W(\lceil n/2 \rceil)+1$の解が$W(n)=\lceil \log_2 n \rceil$になることはどうやって示されるんだろうか．
そのへんが気になりだしたら普通にアルゴリズム系の本を読んだ本がいい気もする．

2.6. 54 長方形の切断

No.30といたあとなら即答

2.7. 55 走行距離パズル

高校数学でみた気がする．

2.8. 56 新兵の整列

今の所暫定一番で問題文の意図が汲み取れなかった問題．
とりあえず昇順に並べれば良いのはわかるがヒントを見て何を言ってるんだ？となって答えを見て何を言ってるんだ？となった．
ここでいう差は二通りの読み方ができるよね？みたいなのは言葉の定義の話であってそこをどういう言うのは良い問題とは思えない．正直本質的でないところで悩むのは不毛すぎる．
答えを見たあとに問題文を見ると「なんで読み違えたんだろう」となってしまうので，レビューを頼まれたひとが指摘しないといけないのだと思う．
とりあえず僕の意見としては，この問題は「シュヴェイクは上司の命令を勘違いをしているが，どんな勘違いをしているだろうか」と一文入れたりするか，もしくは「～差の絶対値の平均が～の場合と，(ある兵士の身長)-(その兵士の前にいる兵士の身長)の平均が～の場合で解がことなる．どのように配置すればよいか」といういうふうに書き換えたほうが良いと思う．

2.9. 57 フィボナッチのウサギ問題

まぁ数列はすぐ出るでしょう．高校数学．

2.10. 58 ソートして、もう1回ソート

これは面白かった．トランプを実際に引っ張り出してきてあれこれやって「アレ？これひょっとして常に0なの？」と気づいたときは狐につままれたようだった．
証明は考えたがちゃんとまとまってないが納得できる状態まで持っていけた．

2.11. 59 2色の帽子

まぁよかった．少し考えたらわかると思う．
ただ「午後12:05から始めて午後12:55まで5分おきに囚人を整列させる」は12:05を含まないと思って「10回だからムリ！」と答えを見たら違ったので「合計11回整列させる」と書いてほしかった(中途半端な時間だから少し考えたらわかる気がするし若干ア.ス*ペ味がある)．

でも流石にこれは考えすぎかもしれないが，囚人の考え方しだいでうまくいかない場合があるのでは？と思った．というのも，解答では
・「自分の帽子の色がわからない，もしくは自分の帽子の色が白である」→「とどまる」
・「自分の帽子の色が黒である」→「前に出る」
という「黒だったときのみ前に出る」で行動をしていたが，
・「自分の帽子の色が白である」→「とどまる」
・「自分の帽子の色がわからない，もしくは自分の帽子の色が黒である」→「前に出る」
という「白だったときのみとどまる」で行動する可能性も否定出来ないなぁと思った．

2.12. 60 硬貨の三角形から正方形を作る

とりあえず「正方形」って何？となった．
外枠だけで良くて複数の正方形を作らせたいのか，中身が詰まってる1つの正方形を作らせたいのか，中身を詰めるとしたら詰め方はどんなものを許容するのか．
あと「何種類の」とは「向き・場所が異なる正方形」を区別するの話なのか，あるいは「大きさの異なる正方形」を区別する話なのかわからないなぁとなってた．
いちゃもんみたいに聞こえるかもしれないけれど変に深読みしてしまって混乱したので，とりあえず目標となる正方形の図を入れてほしかったのはある．
正直何言ってもヒントになるタイプの問題なので辛いところではあるので致し方なし．

3. 感想とか

問題文がよくわからなくて本質的じゃないところで悩むのが本当に不毛である．
訳者は悪くなくて(むしろ訳注を入れてくれたりして助かっている)，多分これは著者というかレビューしたひとがちゃんとレビューしてくれなかったのがいけないのではと思ってる．

アルゴリズムパズル 29-48 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の29-48番目の問題「の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 29 魔法陣再び

足して15になる組み合わせは(1,5,9), (1,6,8), (2,4,9), (2,5,8), (2,6,7), (3,4,8), (3,5,7), (4,5,6)で，そうすると中央の数字は5以外ありえないことがわかる(中央は縦横斜めで4種類の和が15にならないといけないので)．そこから(1,5,9)をどう配置するかとか理詰めで考えていけば解は出て，回転対称とかやれば8通りある事がわかる．

2.2. 30 棒の切断

まぁなんかわかる．どんだけ頑張ってもn回の切断では2^n個の分割しかできないので100<2^7より最低でも7回だし7回でできるので7回でできる！！！！みたいな．
一般の場合は帰納的に証明できそうという感じだった(n=1明らか，n>1，n>=a_1をみたすもので最大のa_1=2^kとa_2=n-a_1にまず切断するとa_1>a_2より～みたいな)．

2.3. 31 3つの山のトリック

3分探索

2.4. 32 シングル・エリミネーション方式のトーナメント

シングル・エリミネーション方式？僕らの知ってるトーナメント戦であってるのか……？という不安があったので図を入れるか訳注入れるかしてほしかった．
有名な問題なので(a) (b)は明らかだけれど(c)は何が言いたいのかさっぱりわからなかったし，解答を見て問題文ちゃんと書けやとなった．

2.5. 33 魔法陣と擬似魔法陣

29を解いたあとなら割とすぐわかると思う．

2.6. 34 星の上の硬貨

ちょろい．

2.7. 35 3つの水入れ

初期状態の記述を読み漏らしてたけれどこれは試行錯誤してればいつか最適解みつかるでしょ感(本の解答も全幅探索紹介してるし)．

2.8. 36 限られた多様性

nが適当な数字のときについて考えたら普通にいけるやん！となって答え見たら不覚にも奇数のこと考えてなかった．

2.9. 37 2n枚の硬貨の問題

苦戦した．最初の僕の解は，重ねた状態でNクイーン問題解けば良いなとなったがNクイーン問題が任意のn>4で解を持つことが怪しかったし答えちら見したら貪欲っぽいことやってたのでもう少し考えて同じ構成法に至った．

2.10. 38 テトロミノによる敷き詰め

まぁ考えればわかる．ここまでちゃんと解いていれば不変条件とか市松模様の色とか散々やったのでそのタイプやろなぁとなる．

2.11. 39 盤面上の一筆書き

ルネジムだ！！！！！！！！！！！！ってなった．
エメラルドでいきなり出てきたルネジムのおっさん，ほんと影が薄いですよね．
とりあえずbは良いとして，aの理由付けがうまく行かなかった．
上下左右にある3x3の領域を埋める方法は，3x3の外から入ってきて全部埋めて出る方法は限られていること，最終的な位置が決まってることには気づいたので多分無理だよな……みたいな理由付けで答えを見たらなるほどーとなりましたね……

2.12. 40 交互に並ぶ4つのナイト

チュートリアルを見てればわかる．

2.13. 41 電灯の輪

とりあえず全部つければ全部つくことには幾つかのケースで試せばわかるし，3の倍数のときはうまくやれることにも気づくでしょう．

2.14. 42 もう1つの狼と山羊とキャベツのパズル

n>1ではできないと思って答えを見たら違った．
WCHGとGHCWはわかったが，n=2の場合はその2つをくっつけることしか考えてなくて，WCHGWCHGはダメじゃん！とおもいこんで完全に間違えた．
とりあえずn=2をちゃんと理詰めでやればよかった．

2.15. 43 数の配置

上手いこと思いついたと思って喜々として証明を書いてたら違ってることに気づいた．
一応とりあえず1からnの数字を並べて，左から見てって不等号が成り立ってないところは入れ替えるというのを入れ替えがなくなるまで繰り返せば行けそうだけれどうまくいくという証明はできなくてうーん．答えみたいな方法正直思いつかんよ．

2.16. 44 より軽いか？より重いか？

解答とは少し違ってた．

n=3mのとき，|A|=ｍ, |B|=m, |C|=mとなるようにA,B,Cに分割する．
・AとBを比較して同じ重さ→Cに偽物があるのでAとCを比較
・AとBを比較して違う重さ→Cはすべて本物なのでAとCを比較
n=3m+x(x∈{1,2})のとき，|A|=ｍ, |B|=m, |C|=m+xとなるようにA,B,Cに分割する．
・AとBを比較して同じ重さ→Cに偽物があるので，AとBから|D|=m+xなるように硬貨を集めてCとDを比較
・AとBを比較して違う重さ→Cは本物なのでCからx枚を除いたものをDとしてAとDを比較

これでも行けるはず．

2.17. 45 ナイトの最短経路

チェスを上が来たとなるように東西南北に向けて考えると，ナイトが南南東に進むと(dx,dy)=(1,2)，東南東に進むと(dx,dy)=(2,1)なので南南東に進んだ回数をn，東南東に進んだ回数をmとして右下に到着できるn,mを求めた．

2.18. 46 3色配置

適当にやればいけるやろぐらいの解答しか思いつかなかった．答え見てすげーなーってなった．

2.19. 47 展示計画

(a)自明だったので適当にやったら1多く答えてしまった．(b)ルネジムの問題(No. 39)を見た後なのでまぁわかる．

2.20. 48 マックナゲット数

適当に足したりしてたら気づくでしょ．

3. 感想

競技プログラミングに似ている問題があるので競技プログラミングの向上が期待できそうだけれどほんと貪欲思いつかないのでアレ．
「それ貪欲で解けるよ」ってほんと何もヒントになってないからな～💢💢💢💢💢💢

アルゴリズムパズル 8-28 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の8-28番目の問題の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 8 ジグソーパズルの組み立て

1ピースの場合，2ピースの場合，3ピースの場合……と考えていけばあぁそういうことねみたいな感じになるので解けた．

2.2. 9 暗算

ガウスっぽい求め方もやったけれど，先に思いついたのは行列を分割する方法．

A = [ [1 2 3 ... 10] [1 2 3 ... 10] ... [1 2 3 ... 10] ]

B = [ [0 0 0 ...  0] [1 1 1 ... 1] ... [9 9 9 ... 9] ]

という行列を考えると問題の行列はA+BになるのでAの合計とBの合計を求めた．

こういう問題は僕は好きで，昔小学生のころの実験的な授業で，「九九の百ます計算の表の中から，性質をたくさん見つけましょう」というのがあって，あの授業は良かったなぁと今でも思い出す．

2.3. 10 8枚の硬貨に含まれる1枚の偽造硬貨

引っかかりました．8だから2^3やし3!!! と思って答えを見たら2と書いてあって，2手だよと書いてあるのをみてすぐに手法はわかったので先入観がネックだなぁと強く感じた問題．

2.4. 11 偽造硬貨の山

思いついたのですごく気分が良かった．やり方は本の解答と同じだった．

2.5. 12 注文付きのタイルの敷き詰め

本の解答同様に理詰めでやったところ，解答にある形とはちょっと違うけど条件を満たせない形に至った．

2.6. 13 通行止めの経路

大学受験でやった．

なにげにこういうテクニックって授業ではあまりやらなくて，どちらかといえば塾とかでしか教えてもらえないイメージ(友人から聞いた気がする)．

2.7. 14 チェス盤の再構成

同じ色が隣り合わせになってはダメなので，そうならないように切断する必要がある．

その場所を全部切れば答えに行き着く．

2.8. 15 トロミノによる敷き詰め

n=1について考えればチョロい．

2.9. 16 パンケーキの作り方

問題文読んで「よくわからない，普通に2枚ずつ焼いていって奇数だったら最後の1枚を2分かけて焼けばよいのでは？」みたいに思ったが当たり前に違っていて悲しい．

ヒントをちゃんと読んで考えるべきだった．

2.10. 17 キングの到達範囲

紙にかけばわかる．

2.11. 18 角から角への旅

小学生の頃「レイトン教授と悪魔の箱」をやっていて，ナイトツアーがめちゃくちゃ好きだったのだけれど問題見た瞬間「おっ！8x8のナイトツアーやな！久々だけれどできるかな～？」とやってたら問題を読み間違えていることに解答を見て気づいた．

2.12. 19 ページの番号付け

計算するだけ，高校数学感がすごい．

2.13. 20 山下りの最大和

本では上からだが僕は下から計算した(一番下に0があるものとして，下から順番にその数字の下のある数字で最も大きいものをその数字に加える，という処理を上までやると最大和が出て，その経路を見れば下り方もわかる)．

プロジェクトオイラーっぽい問題だなぁと思ってたらプロジェクトオイラーの問題だった．

なんとなく既視感があるしどこかで解いたのかもしれない．

2.14. 21 正方形の分割

答えはあってるし，構成法も解答と同様だったがn=5の場合にできない理由にあまり自信がなかった．

なお答えを見たらその理由が簡単に説明されていて少し考えたらなるほどとなった．

(n=5の場合に仮に分割できたとすると，分割されてできた小正方形の四隅は，大正方形の四隅にくっついていないといけないが，そうすると真ん中に「十」みたいな空間ができてしまい，その空有間を埋めるとn=4になるしどう頑張っても構成できない)

2.15. 22 チームの並べ方

結構苦戦した．問題文もすこし読み取りづらかった．でも面白い問題だった．

「推移律はないが大小比較ができる集合」って意識的に考えたことがなかったので普通におもしろいし，そういった集合でもソートみたいなことはできるのは面白いし，普通のソートのアルゴリズムが使えなさそうなのでどうやるんだろうとか妄想が捗る．

2.16. 23 ポーランド国旗の問題

問題文だけだとよくわからないので図と例が欲しいところではあった．

(正直一番左から～とか一番右から～というような情報を得ることはOKなのか？と若干不安になりながら答えを見た)

2.17. 24 チェス盤の塗り分け

問題文だけだとよくわからない問題だった．多分こういうことだろうと考えて答えを作った．

(a) 2なのは明らか(チェス盤でナイトが行ける場所は今いる場所とは色が異なる場所なので9

(b) とりあえず角においてみて，効きのある場所の色をすべて異なるようにしてゴニョゴニョしたら[[1 2 3 ... n] ... [1 2 3 ... n]]とすれば条件を満たすことがわかったのでn.

(c) ビショップ同様とりあえず置いて……とやって本の答えと同じになった．

2.18. 25 最高の時代

競プロかな？？？みたいになった．

計算のオーダーが指定されてないし頭も良くはないので以下のようにやればいけそうだなぁと思って答えを見た．

1. 没年で昇順にソートして，i番目の科学者の生年と没年を(a_1 b_1) ... (a_n b_n)とする．

2. 各iについて，j番目(j<i)の科学者は死亡しているので，i番目～n番目の科学者でb_i-1年に生まれている科学者の集合をA_iとする(A_i = {a_k | a_k < b_i, k ∈ {i...n}})

3. A_iの要素の数をn_i，A_iの要素で最も大きい数字をc_iとする

4. iをn_iが最大となるiとすると，c_i年～b_i-1年が最高の時代

という方針でO(n^2)やなと思って見たらO(n log n)の方法が紹介されていてしょぼりーぬであった．

2.19. 26 何番目か求めよ

高校数学だった．

2.20. 27 世界周遊ゲーム

適当にやったら見つけられた．解はたくさんありそうではある．

2.21. 28. 一筆書き

ちょろい．

小学生の頃一筆書きをしよう！みたいな算数の授業があったのだけれどそれが全然できなくて軽く泣いた思い出がある．その時書けなかった図形は今でも覚えている．

まぁそういう経験があったので奇数のnodeがあったらそこから出発し，奇数のnodeで終わる必要があるのも熟知している．

3. 感想

今回得られた反省としては，

1: 問題文をよく読むこと

問題文をよく読んで，よくわからなかったらヒントを読むこと．

2: 先入観にとらわれるな

簡単すぎる場合はもう少し考えて本当にその解であってるか考えたほうが良い．

また最適だろうと思ってももう少し考えて改良できないか考えたほうが良い．

といったところだろうか．後加えるなら

3: オライリー本がプログラム書くための本だとは限らない

ですね．正直読むスタンスを間違えていた．

プログラムが書ける人向けのパズル集なので，数独の問題をとくのと同じように紙とペンで解いてるのが適切だった．とても楽しい．

アルゴリズムパズル 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回はブログを更新するつもり．

アルゴリズムパズル 5 行と列の入れ替え 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の5番目の問題「行と列の入れ替え」の実装例です．
この本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本なので，ブログにパズルの内容について書くのは引用に収まるのか？という疑問があるので問題文は書かないです．

2. 解説など

まぁ少し考えれば答えが「いいえ」であることはあきらかで，理由は解説に書いてあるとおりである(15と13といった同じ行にある数字を，相異なる行に移動させるという操作は行の入れ替え・列の入れ替えではできない)．
また一つの行を揃えれば全部の行の並びは揃うし，一つの列を揃えれば全部の列の並びは揃うという性質がある．
なお，パネルの並びを行列としてみたときに行の入れ替え・列の入れ替えは行列の積で表せる．
また行・列を入れ替えるような行列は行列式が-1であるから，初期状態と最終状態の行列式の絶対値が異なってるかどうかでもこの問題では判定できる(初期状態では行列式は0だが最終状態では行列式が0でない)．
ただし「行列式の絶対値が異なる→解はNo」は真だが「行列式の絶対値が等しい→解はYes」は必ずしも真ではない(行列によっては成り立たない).

3. ソースコード

一致させられるか判定するプログラムをCommon Lispで書こうとして詰まってしまって，ひょっとして単に僕のプログラミング力が低いからではと思いRustで実装した．
単に僕のプログラミング力が低いからだった．
判定方法は実際に揃えてみて一致するか確認してるだけ．

	// アルゴリズムパズル 5. 行と列の入れ替え
	use std::io;
	use std::process;
	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 read_int() -> i64{
	read_ints()[0]
	}
	///////////////////////////////////////////////////
	// xs = [3 1 2 4]というようなリストをtarget=[1 2 3 4]とおなじようにする置換のリストを返す
	fn generate_permutations(mut xs:Vec<i64>,target:Vec<i64>)->Vec<(usize,usize)>{
	// とりあえず1から順に揃えるだけ
	let mut result = vec![];
	let n = xs.len();
	for i in 0..n{
	if target[i] != xs[i]{
	let j = (0..n)
	.find(|&j| xs[j] == target[i])
	.unwrap();
	result.push((i,j));
	xs.swap(i,j);
	}
	}
	result
	}
	// 行列を表示する
	fn display_matrix(matrix:&Vec<Vec<i64>>){
	for i in 0..matrix.len(){
	println!("{:?}",matrix[i]);
	}
	}
	// matrixのperm.0列目とperm.1列目を入れかえる
	fn swap_col(matrix:&mut Vec<Vec<i64>>,perm:(usize,usize),show:bool){
	for i in 0..matrix.len(){
	matrix[i].swap(perm.0,perm.1);
	}
	if show{
	println!("swap {} th column and {} th column!",perm.0+1,perm.1+1);
	display_matrix(&matrix);
	}
	}
	// matrixのperm.0行目とperm.1行目を入れかえる
	fn swap_row(matrix:&mut Vec<Vec<i64>>,perm:(usize,usize),show:bool){
	for _ in 0..matrix.len(){
	matrix.swap(perm.0,perm.1);
	}
	if show{
	println!("swap {} th row and {} th row!",perm.0+1,perm.1+1);
	display_matrix(&matrix);
	}
	}
	// matrixの行からソートすると[1 2 3 4]となるような行を取り出す
	fn fetch_row_1(matrix:&Vec<Vec<i64>>)->Option<Vec<i64>>{
	let target = (1..matrix.len() as i64 + 1).collect::<Vec<_>>();
	for row in matrix.iter(){
	// ソートした行の取り出し
	let mut row_dash = row.clone();
	row_dash.sort_unstable();
	if row_dash == target{
	return Some(row.clone())
	}
	}
	None
	}
	// matrixの列からソートすると[1 5 9 13]となるような列を取り出す
	fn fetch_col_1(matrix:&Vec<Vec<i64>>)->Option<Vec<i64>>{
	let n = matrix.len();
	let target = (0..n).map(|i| (n * i + 1)as i64).collect::<Vec<_>>();
	for i in 0..n{
	let col = {
	let mut temp = vec![];
	for j in 0..n{
	temp.push(matrix[j][i])
	}
	temp
	};
	// ソートした列の取り出し
	let mut col_dash = col.clone();
	col_dash.sort_unstable();
	if col_dash == target{
	return Some(col)
	}
	}
	None
	}
	// matrixの列を入れ替えて揃える(左から右へ昇順になるようにする)置換のリストを返す
	fn arrange_col(matrix:&Vec<Vec<i64>>)->Vec<(usize,usize)>{
	// ソートすると[1 2 3 4]となる行を取り出す
	let row1 = fetch_row_1(&matrix).unwrap_or_else(|| {
	println!("Invalid matrix.");
	process::exit(0);
	});
	let n = row1.len();
	// row1を[1 2 3 4]とするような列に対する置換のリストを生成
	generate_permutations(
	row1,
	(1..1+n as i64).collect::<Vec<_>>())
	}
	// matrixの各列の順番を揃える(上から下へ昇順になるようにする)置換のリストを返す
	fn arrange_row(matrix:&Vec<Vec<i64>>)->Vec<(usize,usize)>{
	// ソートすると[1 5 9 13]となる列を取り出す
	let col1 = fetch_col_1(&matrix).unwrap_or_else(||{
	println!("Invalid matrix.");
	process::exit(0);
	});
	let n = col1.len();
	// col1を[1 2 3 4]とするような行に対する置換のリストを生成
	generate_permutations(
	col1,
	(0..n).map(|i| (n * i + 1)as i64).collect::<Vec<_>>())
	}
	// マトリックスが最終状態となっているか確認する関数
	fn check_matrix(matrix:&Vec<Vec<i64>>) -> bool{
	let n = matrix.len();
	for i in 0..n{
	for j in 0..n{
	if matrix[i][j] != (1+i*n+j) as i64{
	return false;
	}
	}
	}
	return true;
	}
	// 行列を規定の形に行と列だけを入れ替えて揃えられるかを調べる関数
	fn arrange_matrix(mut matrix:Vec<Vec<i64>>,show:bool){
	let perm_row = arrange_row(&matrix);
	let perm_col = arrange_col(&matrix);
	for perm in perm_col{
	swap_col(&mut matrix,perm,show);
	}
	for perm in perm_row{
	swap_row(&mut matrix,perm,show);
	}
	if check_matrix(&matrix){
	println!("Valid matrix.");
	}else{
	println!("Invalid matrix.");
	}
	}
	fn main(){
	// 入力の読み取り
	let n = read_int() as usize;
	let matrix = {
	let mut temp = vec![];
	for _ in 0..n{
	temp.push(read_ints());
	}
	temp
	};
	arrange_matrix(matrix,true);
	}
	// 入力を次のようにする
	// 1行目……n(行列の次数)
	// 2～n+1行目……行列
	// 3
	// 1 3 2
	// 4 6 5
	// 7 9 8
	/*
	3
	7 9 8
	1 3 2
	4 6 5
	-> Valid matrix.
	3
	7 9 8
	1 3 2
	4 5 6
	-> Invalid matrix.
	4
	12 10 11 9
	16 14 5 13
	8 6 7 15
	4 2 3 1
	*/

view raw algorithm_puzzle_5.rs hosted with ❤ by GitHub

4. 感想

線形代数の勉強をしているので少し面白かった．

アルゴリズムパズル 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. 所感

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

アルゴリズムパズル 1.狼と山羊とキャベツ 実装例[Rust]

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』という本を見つけたので，今勉強しているCommon Lispの練習として使ってみようと思ったが，思ったより苦戦してしまって癪だったのでRustで実装した．
有名な問題なのでググれば出てくるがこの本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本で，ブログにパズルの内容について書くのは引用に収まるのか？という疑問がある．
そのためパズルの名前と僕の解答(ソースコードとかんたんな解法)についてのみ書いておく．

2. 解答

Rustで幅優先探索で解いた．

	use std::collections::HashSet;
	#[derive(Hash, Eq, PartialEq, Debug, Clone)]
	enum Kind{
	None,
	Cabbage,
	Wolf,
	Goat,
	}
	// 解法の表示
	fn show_moves(moves:Vec<Kind>){
	println!("----- solved! -----");
	for m in moves {
	if m == Kind::None{
	println!("move nothing.");
	}else{
	println!("move {:?}",m);
	}
	}
	println!("-------------------");
	}
	// left_r,right_r,moves_rの状態で，mを動かした場合，
	// 不正な操作でなければ次状態を返す関数
	fn get_all_states(left_r:&HashSet<Kind>,right_r:&HashSet<Kind>,moves_r:&Vec<Kind>,m:Kind)
	->Result<(HashSet<Kind>,HashSet<Kind>,Vec<Kind>),()>{
	// left->rightとして考える
	let to_right = moves_r.len() % 2 == 0;
	let mut left = if !to_right {right_r.clone()}else{left_r.clone()};
	let mut right = if to_right {right_r.clone()}else{left_r.clone()};
	if m != Kind::None{
	if !left.contains(&m){
	return Err(())
	}
	left.remove(&m);
	right.insert(m.clone());
	}
	// 捕食関係が保たれていたら駄目
	if (left.contains(&Kind::Cabbage) && left.contains(&Kind::Goat))
	|| (left.contains(&Kind::Wolf) && left.contains(&Kind::Goat)){
	return Err(());
	}
	let mut moves = moves_r.clone();
	moves.push(m.clone());
	if to_right{
	Ok((left,right,moves))
	}else{
	Ok((right,left,moves))
	}
	}
	// 次状態を取得する
	// ゲームが終了していた場合，解法を表示しNoneを返す
	fn solve(left: HashSet<Kind>,right:HashSet<Kind>,moves:Vec<Kind>)
	->Option<Vec<(HashSet<Kind>,HashSet<Kind>,Vec<Kind>)>>{
	if left.len() == 0{
	// 左岸になにもない→成功
	show_moves(moves);
	None
	}else{
	let mut ret = vec![]; // 次状態
	for m in vec![Kind::Wolf,Kind::Cabbage,Kind::Goat,Kind::None]{
	if let Ok(v) = get_all_states(&left,&right,&moves,m){
	ret.push(v);
	}
	}
	Some(ret)
	}
	}
	// 幅優先探索で解く
	fn solves(mut xs:Vec<(HashSet<Kind>,HashSet<Kind>,Vec<Kind>)>){
	let mut min_hand = 9999999;
	loop{
	let (left,right,moves) = xs.remove(0);
	let n_hand = moves.len();
	if n_hand > min_hand{
	break;
	}
	if let Some(mut v) = solve(left,right,moves){
	xs.append(&mut v);
	}else{
	min_hand = n_hand;
	}
	}
	}
	fn main(){
	let left = {
	let mut h = HashSet::new();
	for v in vec![Kind::Wolf,Kind::Cabbage,Kind::Goat]{
	h.insert(v);
	}
	h
	};
	let right = HashSet::new();
	solves(vec![(left,right,vec![])]);
	}

view raw wolf_goat_cabbage.rs hosted with ❤ by GitHub

3.感想

思ったより書きにくかった．コードもあまりきれいじゃない．

気になったこととしてはRustについてで，get_all_statesの引数の変数名を，あとで使う変数名と違うものにしないとうまく動作しなかった．
同じ変数名は後で定義された変数で前に定義された変数が隠蔽されるようになっていたはずだけれど，思ったとおりの挙動をしなかった．

はじめてのLispインタプリタをRustで実装して失敗した話

# 概要

プログラミング言語を作りたいがいまいち何から初めていいのかわからない，という場合に有名？なものにmal - Make a Lispというプロジェクトがある．
これはmalというClojureライクなLispを実装してみよう！というもので，73種類のプログラミング言語による実装がリポジトリにある．
malによるmalの実装もあるため，セルフホスティングするのを目指したが，うまく行かなかった(実装はここ)．
今日は一ヶ月かかったその実装の過程を簡単にメモする．

# 失敗談

## 構文解析

GitHubのinitial commitは6月2日だった．
malは実装ガイドというものがあって，Step1-9，StepAという順番に実装するべきものが紹介されている．
最初の方は構文解析で割と辛いところではあるが，ネットに転がっていたものを参考にしつつ，お手製パーサーを実装した．
ただ適当に実装したため-1が読み込めないという悲しいバグを含んでいる(おととい気づいた)
あとよくわからないことに，字句解析器はidentifierと記号と数字という三種類に分解していて，なんで数字だけ独立してるんだ……という感じになっていた．

その後順調に進めるのだが，ちゃんと英語を読んでないために結構悲しいことが起きていた．
というのも，リポジトリの./process/下に擬似コードがあったり，./tests/下にテストケースがあるのを完全に見逃していた．

## 擬似コードを見なかったことによる失敗

特に擬似コードを見逃していたのが実はかなり痛くて，何が痛いかというと評価のタイミングを見誤るということが結構あった．
例えばapplyだと，(def! a 3)とすると，(apply func '(a 2))を実行すると(func a 2)というものに仕様では変換され，第一引数はシンボルのままとなる．
ところが僕の最初の実装では引数を2回評価してしまっていて，(func 3 2)となってしまうバグが有った．
あわてて評価をしないようにすると今度は(def! r '(1 2 3))として(apply func r)とすると，rを評価しないからapplyの第二引数がリストでなくシンボルのままとなるというバグが……．
多分こういった評価のバランス感覚？というものは何回もプログラミング言語を実装しないと生まれないものだと思うので，ちゃんと擬似コードを読みながらやるべきだったと反省．

## テストケースによる失敗

あとテストケースを見逃していたことは，細々としたところが違っているということがセルフホスティングの段階で顕著に現れた．
たとえば(first '())を僕の実装でやるとエラーを吐くのだが，Clojureとかはnilを返すんですよね……
そういった細かい違いが顕著化して残念な結果になってセルフホスティングを諦めるということとなった．

## Lisp力不足

なにげにLispをあまり本格的に使ったことがないという事実はわりと問題ではあった．
例えば上記のようなテストケースの問題は，そもそもLispに慣れていれば起きなかった問題かもしれない．
あと逐一Clojureを立ち上げて動作を比較するとかしていたので割と効率が悪かった．

## オリジナリティを求めたことによる失敗

きちんとしたエラーハンドリングのない言語とかやってられないというお気持ちはあったのでランタイムエラーをいい感じに表示させようといろいろコードを追加したが，一切使わなかった(しかも取り除くことなく未だにそのムダなコードは残っている)．

## Rust力，プログラミング力不足による失敗

Rustで1000行ぐらいのプログラムを書いた経験，なし．
プログラムで2000行以上のプログラムを書いた経験，心当たりなし．
こういう状態で挑んだがためにムダにプログラムが肥大化した上に，コードが僕のコントロール外に行ってしまった．

正直Rustのマクロを使えばこの辺1/10のコード量になるよね？みたいなところが無限にあったが，マクロを知らないので実装できてない．
もう一度Rustドキュメントを読み直すべきである．

# 成功談

もちろん失敗談だけではない．

遅いし仕様は違うが，大抵のプログラムなら実行できるので，プログラミング言語を作ったという実感はある．

あとRust力が上がったのは感じるし，Rustの良さを実感することもできた．
これだけ長いコードを曲がりなりにも書けたという実感は自信になった(多分)．

# 今後の予定

とりあえずLispをちゃんと知りたくなったので『Land of Lisp』を読むつもり．
あとRust力の向上は感じるので，パズルゲームをRustで実装したりしたいなぁと思っている．