※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー問42」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問42 - (2014/02/15 (土) 19:10:01) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042

*problem 42 「符号化三角数」 †
三角数のn項は tn = 1/2*n*(n+1)で与えられる. 最初の10項は

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
である.

単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は 19 + 11 + 25 = 55 = t10である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ.

16Kのテキストファイル words.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか?
テキストファイルの詳細はリンク先を参照のこと。

解法
テキストファイルをPrologのリスト形式になるよう[].を先頭と末尾に着けて
後はリストとしてファイルを読み込んでスコアにしてスコアの小さい順に並べ替えて、
三角数の小さいほうと手前からマッチしていくだけです。


 to_score([],0):-!.
 to_score([N|Name],Result):-
  	to_score(Name,Re),
 	Result is Re+N-64.
 
 
 to_score_list([],[]):-!.
 to_score_list([Name|Names],[Score|Scores]):-
 	to_score(Name,Score),
 	to_score_list(Names,Scores).
 
 delta_list(30,_,[]):-!.
 delta_list(N,Sum,[Sum|Result]):-
 	N1 is N+1,
 	Sum1 is Sum+N,
 	delta_list(N1,Sum1,Result).
 
 deltaSum([],_,Sum,Sum):-!.
 deltaSum(_,[],Sum,Sum):-!.
 deltaSum([X|Xs],[X|Delta],Sum,Result):-
 	!,
 	Sum1 is Sum+1,
 	deltaSum(Xs,[X|Delta],Sum1,Result).
 deltaSum([X|Xs],[Y|Delta],Sum,Result):-
	X<Y,
  	!,
 	deltaSum(Xs,[Y|Delta],Sum,Result).
 deltaSum(Xs,[_|Delta],Sum,Result):-
 	!,
 	deltaSum(Xs,Delta,Sum,Result).
 
 
 myread(FN):-
  open(FN,read,IS),
  read_term(IS,Names,[]),
  to_score_list(Names,Scores),
  msort(Scores,Scores1),
  delta_list(2,1,Deltas),
  deltaSum(Scores1,Deltas,0,Ans),
  write(Ans),
   close(IS).
 
 main42:-
 	myread('pe42.txt').