忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/03/27 21:31 |
「第27回オフラインリアルタイムどう書くの参考問題」をPHPで解く
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)) : '-';
		}
	}

最初からこうしたほうが手っ取り早かった。
PR


2015/01/16 23:31 | Comments(0) | PHP

コメント

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<ファイアーエムブレム 聖魔の光石をクリア | HOME | 柵を修理>>
忍者ブログ[PR]