「プロジェクトオイラー問８２」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問８２」(2014/03/04 (火) 11:53:35) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2082
*Problem 82 「経路の和:3方向」 †
数字の書かれたマス目を移動して左端から右端へ到達する。
経路上の数字の和が最小になる経路を通った時のその和を答えよ。
詳細はリンク先参照のこと。

解法
一列ごとの動的計画法で片が付きます。
一列ごとの処理が少しわかりづらいので機能ごとに分割してもよかったかもしれません。


 seed(0):-
 	between(0,79,_).
 
 min(a,B,B):-!.
 min(A,a,A):-!.
 min(A,B,A):-A<B,!.
 min(_,B,B):-!.
 
 dp_one_col([[R|Rest]],[Rest],[S],[D],U,D):-
 	!,
 	min(U,S,M),
 	D is R+M.
 dp_one_col([[R|Rest]|Rows],[Rest|Rows1],[S|Sum],[S2|Sum1],U,S2):-
 	!,
 	min(S,U,M1),
 	S1 is R+M1,
 	dp_one_col(Rows,Rows1,Sum,Sum1,S1,D),
 	min(M1,D,M2),
 	S2 is M2+R.
 dp(_,Sum,81):-!,
 	sort(Sum,[Min|_]),
 	write(Min).
 
 dp(Rows,Sum,ColP):-
 	dp_one_col(Rows,Rows1,Sum,Sum1,a,_),
 	ColP1 is ColP+1,
 	dp(Rows1,Sum1,ColP1).
 
 main82:-
 	open('pe82.txt',read,IS),
 	read_term(IS,Rows,[]),
 	close(IS),
 	findall(S,seed(S),Sum),
 	dp(Rows,Sum,1).

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2082
*Problem 82 「経路の和:3方向」 †
数字の書かれたマス目を移動して左端から右端へ到達する。
経路上の数字の和が最小になる経路を通った時のその和を答えよ。
詳細はリンク先参照のこと。

解法
一列ごとの動的計画法で片が付きます。
一列ごとの処理が少しわかりづらいので機能ごとに分割してもよかったかもしれません。
データファイルは一段を一つのリストとしてそのリストの集まりという形に手作業で変換してから読み込んでいる。


 seed(0):-
 	between(0,79,_).
 
 min(a,B,B):-!.
 min(A,a,A):-!.
 min(A,B,A):-A<B,!.
 min(_,B,B):-!.
 
 dp_one_col([[R|Rest]],[Rest],[S],[D],U,D):-
 	!,
 	min(U,S,M),
 	D is R+M.
 dp_one_col([[R|Rest]|Rows],[Rest|Rows1],[S|Sum],[S2|Sum1],U,S2):-
 	!,
 	min(S,U,M1),
 	S1 is R+M1,
 	dp_one_col(Rows,Rows1,Sum,Sum1,S1,D),
 	min(M1,D,M2),
 	S2 is M2+R.
 dp(_,Sum,81):-!,
 	sort(Sum,[Min|_]),
 	write(Min).
 
 dp(Rows,Sum,ColP):-
 	dp_one_col(Rows,Rows1,Sum,Sum1,a,_),
 	ColP1 is ColP+1,
 	dp(Rows1,Sum1,ColP1).
 
 main82:-
 	open('pe82.txt',read,IS),
 	read_term(IS,Rows,[]),
 	close(IS),
 	findall(S,seed(S),Sum),
 	dp(Rows,Sum,1).