人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

PHPのスクリプトを作っていただけないでしょうか。
いくつかの文字列をあるルールに従って並べて書き出すスクリプトです。
いるか賞には、少ないですが500ポイントを差し上げます。

具体的には、いくつかの文字の組み合わせで出来た文字列を与え、その中からスタートの文字列とゴールの文字列を決めると、それらの間を「下の文字列はすぐ上の文字列に1文字加えたものか、1文字減らしたものしか置けない」というルールにしたがって残りの文字列を並べて埋めてくれるというものです。(ルールを満たす並べ方が複数ある場合はすべて書き出し、不可能な場合はエラーを返す)
例えば、「い」「ろ」「は」3文字の組み合わせで出来た文字列、い,ろ,は,いろ,ろは,いは,いろは を与え、その中から「い」をスタート、「いろは」をゴールと決めると、


いろ

ろは

いは
いろは


いは

ろは

いろ
いろは

上記2種類の結果を書き出してくれるスクリプトです。この例では3つの文字で出来た7つの文字列でしたが、文字数や文字列数が増えても対応出来るスクリプトを希望します。
説明に解りにくい部分があれば質問してください。
よろしくお願いします。

●質問者: minapoo
●カテゴリ:コンピュータ ゲーム
✍キーワード:PHP いるか賞 いろは のし エラー
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● JULY
●0ポイント

ちゃんとデバッグした訳じゃないし、もっときれいで効率の良いコードがありそうだけど、とりあえず。

多分、文字は ASCII 限定になってると思います。

<?php
function get_str_sequence($start, $stop, $str_set, $charset, $max_len, $str_seq, &$result) {
 $str_seq[] = $start;

 if (strcmp($start, $stop) == 0) {
 $result[] = $str_seq;
 return;
 }

 if (strlen($start) < $max_len) {
 foreach ($charset as $char) {
 for ($i = 0; $i <= strlen($start); $i++) {
 $next_start = substr($start, 0, $i) . $char . substr($start, $i);
 if (array_search($next_start, $str_set) === false) continue;
 if (array_search($next_start, $str_seq) === false) {
 get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
 }
 }
 }
 }

 if (strlen($start) > 1) {
 for ($i = 0; $i < strlen($start); $i++) {
 $next_start = substr($start, 0, $i) . substr($start, $i + 1);
 if (array_search($next_start, $str_set) === false) continue;
 if (array_search($next_start, $str_seq) === false) {
 get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
 }
 }
 }
}

function print_str_sequence($start, $goal, $str_list) {
 $max_str_len = 0;
 $all_char = array();

 foreach ($str_list as $str) {
 for ($i = 0; $i < strlen($str); $i++) {
 $all_char[] = substr($str, $i, 1);
 }

 if (strlen($str) > $max_str_len) {
 $max_str_len = strlen($str);
 }
 }

 $charset = array_unique($all_char);

 $result = array();
 get_str_sequence($start, $goal, $str_list, $charset, $max_str_len, "", $result);

 if (count($result) > 0) {
 foreach ($result as $sequence) {
 foreach ($sequence as $str) {
 print "$str\n";
 }
 print "\n";
 }
 } else {
 print("No sequence\n");
 }
}

$str_list = array("abc", "ab", "a", "b", "bc");
print_str_sequence("a", "abc", $str_list);
?>
◎質問者からの返答

さっそくありがとうございます。

それで、まずお詫びしなければいけないのですが、上の質問文中に「すべての文字列を1回づつ使う」という条件が抜けておりました。

JULY様のお答えを確認させていただきましたら「a ab abc」というのも答えとして表示されましたので、そこを変えていただくと申し分ないと思うのです。

本当にすみません、私の説明不足でしたm(_"_)m


2 ● JULY
●500ポイント ベストアンサー

>>「すべての文字列を1回づつ使う」

対応してみました。

<?php

function get_str_sequence($start, $stop, $str_set, $charset, $max_len, $str_seq, &$result) {
 $str_seq[] = $start;

 if (strcmp($start, $stop) == 0) {
 if (count($str_seq) != count($str_set)) return;

 foreach ($str_set as $str) {
 if (array_search($str, $str_seq) === false) return;
 }

 $result[] = $str_seq;
 return;
 }

 if (strlen($start) < $max_len) {
 foreach ($charset as $char) {
 for ($i = 0; $i <= strlen($start); $i++) {
 $next_start = substr($start, 0, $i) . $char . substr($start, $i);
 if (array_search($next_start, $str_set) === false) continue;
 if (array_search($next_start, $str_seq) === false) {
 get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
 }
 }
 }
 }

 if (strlen($start) > 1) {
 for ($i = 0; $i < strlen($start); $i++) {
 $next_start = substr($start, 0, $i) . substr($start, $i + 1);
 if (array_search($next_start, $str_set) === false) continue;
 if (array_search($next_start, $str_seq) === false) {
 get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
 }
 }
 }
}

function print_str_sequence($start, $goal, $str_list) {
 $max_str_len = 0;
 $all_char = array();

 foreach ($str_list as $str) {
 for ($i = 0; $i < strlen($str); $i++) {
 $all_char[] = substr($str, $i, 1);
 }

 if (strlen($str) > $max_str_len) {
 $max_str_len = strlen($str);
 }
 }

 $charset = array_unique($all_char);

 $result = array();
 get_str_sequence($start, $goal, $str_list, $charset, $max_str_len, "", $result);

 if (count($result) > 0) {
 foreach ($result as $sequence) {
 foreach ($sequence as $str) {
 print "$str\n";
 }
 print "\n";
 }
 } else {
 print("No sequence\n");
 }
}

$str_list = array("abc", "ab", "a", "b", "bc");
print_str_sequence("a", "abc", $str_list);
?>
◎質問者からの返答

ありがとうございました!

こんなに早く回答していただけるとはうれしい限りです。

ワケの分からない要望に応えていただいてすみませんでした。

いるか賞500ポイントとさせていただきます!

ところで、ついうれしくて文字数&文字列数増やしてやってみたら

タイムアウトになってしまったんですが

php.iniいじったら良いんでしょうか

素人がいじらない方が良いでしょうか


3 ● KeyKey
●500ポイント

時間ないのでかなり汚いソースですがこんな感じでどうでしょう?

$now 現在の項目

$max ゴール

$map 全ての項目

$flg 使った項目

$ary 今まで辿った項目

$str_ary 文字列の配列

<?php
$str = "abc";
$str_ary = array();
$str_ary = str_split($str);

$len = count($str_ary);

$bin = '';
for ($i = 0; $i < $len; $i++) {
 $bin .= '1';
}

for ($i = 1; $i <= bindec($bin); $i++) {
 $map[] = str_split(sprintf("%0{$len}b", $i));
}

strSeek($map[0], $map[bindec($bin)-1], $map, array(0), array($map[0]), $str_ary);

exit;

function strSeek($now, $max, $map, $flg=array(), $ary, $str_ary)
{
 if (count($ary) === count($map) && $now === $max) {
 foreach ($ary as $key => $val) {
 foreach ($val as $key2 => $val2) {
 if ($val2 == 1) {
 echo $str_ary[$key2];
 }
 }
 echo "<br>";
 }
 echo "-------<br>";
 }
 
 for ($i = 0; $i < count($map); $i++) {
 $exit = 0;
 foreach ($flg as $val) {
 if ($i === $val) {
 $exit = 1;
 }
 }
 if ($exit !== 1) {
 $diff = 0;
 for ($j = 0; $j < count($map[$i]); $j++) {
 if ($now[$j] !== $map[$i][$j]) {
 $diff++;
 }
 }
 if ($diff === 1) {
 $ary2 = array();
 $ary2 = $ary;
 array_push($ary2, $map[$i]);
 $flg2 = array();
 $flg2 = $flg;
 array_push($flg2, $i);
 strSeek($map[$i], $max, $map, $flg2, $ary2, $str_ary);
 }
 }
 }
}
?>

出力

c
bc
b
ab
a
ac
abc
-------
c
ac
a
ab
b
bc
abc
-------
関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ