第22回 Ruby/Rails勉強会＠関西 でジャムプログラミングの課題が出ています。この課題の4番目の問題は、与えられた単語の集合から最長のしりとりを見つけるというものです。
単語の並びがしりとりとして成立しているかどうかを記述するだけで済むので、Prolog で解いてみました。以下のプログラムは swi-prolog で動作し、words.csv に含まれる単語の重複がないことを仮定しています。
:- module(shiritori, [shiritori_load_data/2, shiritori/4]).
shiritori_load_data(Path,Data) :-
open(Path,read,Stream,[encoding(utf8)]),
construct_array(Stream,[],Data),
close(Stream).
construct_array(Stream,Buffer,Data) :-
construct_word(Stream,[],Last,Word),
(Word == [] ->
Added = Buffer;
Added = [Word|Buffer]),
(Last == end_of_file ->
reverse(Added,Data);
construct_array(Stream,Added,Data)).
construct_word(Stream,Buffer,Last,Word) :-
get_char(Stream,Char),
((Char == end_of_file; Char == ','; Char == '\n') ->
Last = Char, reverse(Buffer,Word);
construct_word(Stream,[Char|Buffer],Last,Word)).
shiritori(W0,W1) :- W1 = [H|_], last(W0,H).
shiritori([],Data,Data,0).
shiritori([W],Data,Rest,1) :- select(W,Data,Rest).
shiritori([W0,W1|S],Data,Rest,N) :-
N>1, N1 is N-1,
select(W0,Data,R0),
shiritori(W0,W1),
shiritori([W1|S],R0,Rest,N1).
実行例:
$ ls
shiritori.pl words.csv
$ pl -s shiritori.pl -g "shiritori_load_data('words.csv',Data),shiritori(Seq,Data,_,23),write(Seq),nl,fail." -t halt
% shiritori.pl compiled into shiritori 0.00 sec, 4,632 bytes
[[た, ぬ, き], [き, つ, つ, き], [き, つ, ね], [ね, ず, み], [み, み, ず, く], [く, じ, ゃ, く], [く, じ, ら], [ら, っ, こ], [こ, う, も, り],
[り, ゅ, う], [う, し], [し, か], [か, も, し, か], [か, る, が, も], [も, も, ん, が], [が, ち, ょ, う], [う, ず, ら], [ら, く, だ], [だ, ち
, ょ, う], [う, ぐ, い, す], [す, ず, め], [め, じ, ろ], [ろ, ば]]
[[た, ぬ, き], [き, つ, つ, き], [き, つ, ね], [ね, ず, み], [み, み, ず, く], [く, じ, ゃ, く], [く, じ, ら], [ら, っ, こ], [こ, う, も, り],
[り, ゅ, う], [う, ず, ら], [ら, く, だ], [だ, ち, ょ, う], [う, し], [し, か], [か, も, し, か], [か, る, が, も], [も, も, ん, が], [が, ち
, ょ, う], [う, ぐ, い, す], [す, ず, め], [め, じ, ろ], [ろ, ば]]
[[た, ぬ, き], [き, つ, つ, き], [き, つ, ね], [ね, ず, み], [み, み, ず, く], [く, じ, ゃ, く], [く, じ, ら], [ら, く, だ], [だ, ち, ょ, う],
[う, し], [し, か], [か, も, し, か], [か, る, が, も], [も, も, ん, が], [が, ち, ょ, う], [う, ず, ら], [ら, っ, こ], [こ, う, も, り], [り
, ゅ, う], [う, ぐ, い, す], [す, ず, め], [め, じ, ろ], [ろ, ば]]
[[た, ぬ, き], [き, つ, つ, き], [き, つ, ね], [ね, ず, み], [み, み, ず, く], [く, じ, ゃ, く], [く, じ, ら], [ら, く, だ], [だ, ち, ょ, う],
[う, ず, ら], [ら, っ, こ], [こ, う, も, り], [り, ゅ, う], [う, し], [し, か], [か, も, し, か], [か, る, が, も], [も, も, ん, が], [が, ち
, ょ, う], [う, ぐ, い, す], [す, ず, め], [め, じ, ろ], [ろ, ば]]
$ pl -s shiritori.pl -g "shiritori_load_data('words.csv',Data),shiritori(Seq,Data,_,24),write(Seq),nl,fail." -t halt
% shiritori.pl compiled into shiritori 0.00 sec, 4,632 bytes
$この結果、最長の組み合わせは23個の単語からなり、4つのパターンがあると分かります。