しりとり 無限ループ？

質問

【予約語から最長のしりとりを作ろう！】
https://codeiq.jp/ace/stakemura/q408

この問題やってるんですが
処理がtimeoutしちゃいます

最長の結果が１０個程度の時は期待通りに動作します
期待される結果が２０程度になると(?)timeoutします

単にウチのマシンじゃムリなのか、工夫が足りないのか
無限ループを起こしてるのか、重いだけなのか判断つきません

よろしくお願いします

（cpp11_keywords.csvはC++の予約語84個のcsvです）

<?php
$data=explode(chr(10),file_get_contents('cpp11_keywords.csv'));
foreach($data as $i=>$cpp){$data[$i]=trim($data[$i]);}
echo(implode('<br/>',createSiritori($data)));

function createSiritori($words){
$rtn=array();
$data=array();
for($i=0,$len=count($words);$i<$len;$i++){
$data[$i]=array();
for($j=0;$j<$len;$j++){
if($i==$j)continue;
if(is_connectable($words[$i],$words[$j]))$data[$i][]=$j;
}
}
$rcd=0;
for($i=0;$i<$len;$i++){
$crr=array($i);
for($j_arr=array(0),$j_ind=0,$len_arr=array(count($data[$i]));$j_arr[0]<$len_arr[0];$j_arr[$j_ind]++){
if($j_arr[$j_ind]>=$len_arr[$j_ind]){
array_pop($crr);
array_pop($j_arr);
array_pop($len_arr);
$j_ind--;
}else if(!in_array($data[end($crr)][$j_arr[$j_ind]],$crr)){
$crr[]=$data[end($crr)][$j_arr[$j_ind]];
$j_ind++;
$j_arr[$j_ind]=0;
$len_arr[$j_ind]=count($data[end($crr)]);
if($j_ind>$rcd){$rcd=$j_ind;$rtn=$crr;}
}
}
}
for($i=0,$len=count($rtn);$i<$len;$i++){
$rtn[$i]=$words[$rtn[$i]];
}
return $rtn;
}

function is_connectable($a,$b){
return (substr($a,-1)==substr($b,0,1));
}

回答No.8

めとろいと（@naktak） · ベストアンサー

このプログラムだと、
例えば
ab
bc
cd
というテキストだった時、最後のcdが出力されないし、

cd
bc
ab
だった時、bcから始まっちゃいます。(正解はabのはず)

どうやらこのロジックだと、1行目の単語に、次に紐付く単語が
あると、必ず1行目の単語から始めてしまいますね。
（1単語ずつしりとりを行って、最長しりとりが行われた
パターンについて出力しているのではない？）

ちなみにここまでは出るようですよ。enumの後で止まるので、
それ以降、条件に合致せず無限ループに陥っているのでは。
alignas
short
this
signed
default
throw
while
explicit
true
export
typedef
friend
delete
extern
noexcept
typeid
do
or
return
nullptr
reinterpret_cast
typename
enum

お礼

他のもの作ってて見直せてないですが
どうやらやり方以前にコード自体にも
問題があることを見つけてくれたのでBA

補足

コードに問題がありましたか…
自分でもちょっと混乱して処理を
追いきれなくなってました
あらためて見直してます

回答No.9

duke_kimura

なんか面白そうなサイトですね。

不正解答は駄目のようなのでアルゴリズムはさておき、
これをphpで組むならまずはデバッガ(トレーサ)を入れるところからやるべきかと思います。

XDEBUG

参考URL：

http://xdebug.org/

お礼

ありがとうございます

しかし、こういう遊びにしろDreamweaverとMAMPという環境下で出来る事の範囲を広げたり、あるいはこの環境の限界を知ったりその対応方法を考えるということが一つの目的なので環境を変えるということはないかと思います、スイマセン

回答No.7

Yune-Kichi

大元の問題で「timeoutする」とありましたが，これに関しては，CLI使えばタイムアウト「は」しなくなりますよ。
つまり，terminalなりコマンドプロンプトなりから，
php ファイル名
で実行すると，echoした内容はそのまま標準出力に書き出されます。
# 改行は定数PHP_EOLを出力して下さい。

PHPでアルゴリズム系の話をするなら，サーバー使うよりもCLIでやった方がわかりやすそうに思えます。

お礼

どうやら無限ループを起こしてるようなので
無謀なことはやめておきます（笑）

回答No.6

めとろいと（@naktak）

これ何個でるのが答えなんですかねーー。
挑戦してみないと分からないのでしょうけど・・・。
C#で作ってみたら、正しいかどうかはさておき、最長29で、一瞬で返ってきました。
(一瞬すぎるから不正解なのかな？)

もともと処理しまくるものというのが拍車をかけて、めっちゃループしてる処理が
何をしようとしているのかすぐに読み解けない作りなので、ちょっと追えませんね。

色々書くと怒られそうだったので、簡単なヒントを出すと
　・しりとりとは先頭文字と末尾文字が必ず紐付いている。
　・先頭文字や末尾文字が同じものが複数ある。
　・もしかしたら逆引き(しりとりが終わる単語から遡る)のが楽かも？
　　後から気づいたので、私は試してません。

こんなものでしょうか。

お礼

基本的な処理の流れとしては
１、各単語に後続しうる単語の番号を配列に記録
２、先頭の単語の番号を前から順に一時配列にいれ
そこから後続しうる単語の番号をまた順にいれ
最大長であれば戻り値候補として記憶
後続しうる単語がなくなったら一時配列の末尾を除き
一つ前の単語の後続候補を次に進める
これを先頭の単語が８４個全部巡るまで続ける
３、戻り値の単語番号を単語に戻す
というような流れです
基本的にはしりとりが成立しうる組み合わせしか
試行しないので答えが短ければいくんですけどね…

回答No.5

bm_hiro

とりあえず、ソースは読んでいないのだけど・・・

84種類を 一個づつ 減らしながらかけていったらー

3.3142401345654E+126

うん。天文学的数字になりました。

まぁ、ヒントも出ちゃってるし、当たり前過ぎるだし、この程度なら言っても差し支えないかなと思うので言うと、最初の一文字で分類するのがいいんじゃない？

お礼

うん、ムリだ（笑）

回答No.4

noname#244856

ヒント
http://www.orsj.or.jp/~archive/pdf/bul/Vol.50_03_175.pdf

回答No.3

noname#244856

処理の遅いPHP言語で総当たりは非現実的すぎますね・・・
C言語でも結構厳しいと思います。

一応

for → foreach
欲しいものを値にとる配列 + in_array → 欲しいものをキーにとる配列 + isset

などまだまだソースコード実行を速められる余地があります。

お礼

ありがとうございます

まあでも多分チューニングしてどうにかなるレベルじゃないですよね（笑）

回答No.2

kmee

こういうのは、総当たりでやってたら、物凄い勢いで処理回数が増えていきます。
「組み合わせ爆発」と言われています。
確かに、遅いマシンでは遅いですが、このような問題では、多少マシンを速くしたところで焼け石に水です。

なので、アルゴリズムを工夫して、無駄をいかに省くか、というのがコツになります。
なんとか無駄な選択肢を減らせないか、を考えましょう。

ところで、そのサイトに
> 解答送信の有無を問わず、模範解答のネタばれにつながるような各種行為、別人による不正解答は、固くお断り申し上げます。
とあるのですが、大丈夫でしょうか?

お礼

多分、模範解答には全くならないので大丈夫です（笑）

回答としても、コード自体は間違っていないか
無限ループを起こすようなことにはなっていないか
この程度ならマシンスペックとかPHPの設定とかでどうにかなるレベルか
それともこのやり方ではスパコンつかってもムリなレベルなのか

その辺の回答をいただきたいと思っています

無駄な選択肢を減らす工夫、考えてみます
ありがとうございます

回答No.1

めとろいと（@naktak）

for($j_arr=array(0),$j_ind=0,$len_arr=array(count($data[$i]));$j_arr[0]<$len_arr[0];$j_arr[$j_ind]++){

このループをめっちゃ繰り返してますね。
ソースは追ってません。
各ループ直後でechoしたら上記ループが大量でした。

お礼

はい

単純にしりとりが成立する組み合わせを総当たりしているので
最悪全ての単語が互いにしりとり連結可能な場合
84!通りを総当たりする事になります

さすがにそれはないにしろ
多分、半分以上の単語を使用したしりとりが成立し
5^45ぐらいはループすることに
なるだろうと予想しています
（一度100万ループぐらいで止めてみましたが
予想される処理全体の0.01%も進んでませんでした）