http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
http://nabetani.sakura.ne.jp/hena/ord27raswi/
分岐と行き止まり
右に進む線路的な。
<?php
class RASWI{
// 進行可能ルート
private $nextOrigin = [
1=>['a','g'],
2=>['d','h'],
3=>['b','f'],
'a'=>['b'],
'b'=>['c',5],
'c'=>[4,6],
'd'=>['c','e'],
'e'=>[5],
'f'=>['g'],
'g'=>['c','e','h'],
'h'=>[4,'i'],
'i'=>[6],
];
private $next = [];
/**
* 分岐と行き止まり
* @param String 「befi」みたいな文字列
* @return String 「14,16,24,26」みたいな文字列
*/
public function get($input){
$this->next = $this->nextOrigin;
// 通れない道を削除
foreach(str_split($input) as $val){
unset($this->next[$val]);
}
// 全ルートを取得
$start = [ 1=>1, 2=>2, 3=>3 ];
$routes = $this->getRoute($start);
// 分岐/行き止まりを排除し、開始/終了地点だけ抽出
$route = [];
foreach($routes as $key=>$val){
$route[$key] = array_filter(array_unique(iterator_to_array(
new RecursiveIteratorIterator(new RecursiveArrayIterator($val)), false)),
function($val){ return is_int($val); }
);
sort($route[$key]);
}
// 文字列にして返す
$ret = '';
foreach($route as $key=>$val){
foreach($val as $key2=>$val2){
$ret .= $key . $val2 . ',';
}
}
if(!$ret){ return '-'; }
return substr($ret, 0, -1);
}
/**
* 辿れる全ルートを取得する
* @param [1,2,3]
* @return [1=>[[b],[[4,6],[e],...]
*/
private function getRoute($arr){
array_walk_recursive($arr, function(&$val, $key){
$val = isset($this->next[$val]) ? $this->next[$val] : $val;
if(is_array($val)){
$val = $this->getRoute($val);
}
});
return $arr;
}
}
// 以下はテスト
$test = [
['befi', '14,16,24,26'],
['abc', '14,15,16,24,25,26,34,35,36'],
['de', '14,15,16,24,26,34,35,36'],
['fghi', '14,15,16,24,25,26,34,35,36'],
['abcdefghi', '-'],
['ag', '24,25,26,34,35,36'],
['dh', '14,15,16,34,35,36'],
['bf', '14,15,16,24,25,26'],
['ch', '15,25,35'],
['be', '14,16,24,26,34,36'],
['ci', '14,15,24,25,34,35'],
['cgi', '15,24,25,35'],
['acgi', '24,25,35'],
['cdefghi', '15,35'],
['acdefghi', '35'],
['cdegi', '15,24,35'],
['bcdegi', '24'],
['afh', '14,15,16,24,25,26,34,35,36'],
['abfh', '14,15,16,24,25,26'],
['dfh', '14,15,16,34,35,36'],
['cdfh', '15,35'],
['deh', '14,15,16,34,35,36'],
['cdeh', '15,35'],
['abefgh', '24,26'],
['abdefgh', '-'],
['acfghi', '25,35'],
['acdfghi', '35'],
['cegi', '15,24,35'],
['abcfhi', '15,25'],
['abcefhi', '-'],
['abdi', '14,15,16,24,34,35,36'],
['abdfi', '14,15,16,24'],
['bdi', '14,15,16,24,34,35,36'],
['bdfi', '14,15,16,24'],
['adfh', '14,15,16,34,35,36'],
['adfgh', '34,35,36'],
['acdfhi', '15,35'],
['bcdfgi', '24'],
['bcdfghi', '-'],
['defi', '14,15,16,24,34,35,36'],
['defhi', '14,15,16,34,35,36'],
['cdefg', '15,24,26,35'],
['cdefgi', '15,24,35'],
['bdefg', '24,26'],
['bdefgi', '24'],
];
$raswi = new RASWI();
foreach($test as $key=>$data){
$answer = $raswi->get($data[0]);
if($answer !== $data[1]){
print('えらー');
}
}
文字列になおすあたりが野暮ったい。
かかった時間は2時間程度。
再帰は苦手なのです。
しかし昔やったような記憶があるなあ、と思ったら実際にやってました。
前の奴は全ルート求めてから行き止まりを排除していましたが、今回は行き止まりを排除してからルートを求めています。
もっとも今回は全部で21ルートしかないので、全部並べたほうがずっと楽だったりしますが。
<?php
class RASWI{
// 進行可能ルート
private $next = [
'1abc4' => '14',
'1gc4' => '14',
'1gh4' => '14',
'1ab5' => '15',
'1ge5' => '15',
'1abc6' => '16',
'1gc6' => '16',
'1ghi6' => '16',
'2dc4' => '24',
'2h4' => '24',
'2de5' => '25',
'2dc6' => '26',
'2hi6' => '26',
'3bc4' => '34',
'3fgc4' => '34',
'3fgh4' => '34',
'3b5' => '35',
'3fge5' => '35',
'3bc6' => '36',
'3fgc6' => '36',
'3fghi6' =>'36',
];
/**
* 分岐と行き止まり
* @param String 「befi」みたいな文字列
* @return String 「14,16,24,26」みたいな文字列
*/
public function get($input){
$input = str_split($input);
$route = array_filter($this->next, function($v, $k) use($input){
foreach($input as $val){
if(strpos($k, $val) !== false){
return false;
}
}
return true;
}, ARRAY_FILTER_USE_BOTH);
return $route ? implode(',', array_unique($route)) : '-';
}
}
最初からこうしたほうが手っ取り早かった。