弱小PHPerの憂鬱

http://qiita.com/Nabetani/items/9c514267214d3917edf2

縦5本横5本の通りを、同じ頂点を通らずに左上から右下まで進む方法が何パターンあるかを数えます。
ポイントは最短距離ではなく遠回りな道も有効というところでしょうか。

<?php

	class ROUTE{
		/*
			座標は↓のようになる
			abcde
			fghij
			klmno
			pqrst
			uvwxy
		*/
		
		// 次進める方向
		private $next = [
			'a'=>['b', 'f'], 'b'=>['c', 'g'], 'c'=>['d', 'h'], 'd'=>['e', 'i'], 'e'=>['j'],
			'f'=>['g', 'k'], 'g'=>['b', 'f', 'h', 'l'], 'h'=>['c', 'g', 'i', 'm'], 'i'=>['d', 'h', 'j', 'n'], 'j'=>['i', 'o'],
			'k'=>['l', 'p'], 'l'=>['g', 'k', 'm', 'q'], 'm'=>['h', 'l', 'n', 'r'], 'n'=>['i', 'm', 'o', 's'], 'o'=>['n', 't'],
			'p'=>['q', 'u'], 'q'=>['l', 'p', 'r', 'v'], 'r'=>['m', 'q', 's', 'w'], 's'=>['n', 'r', 't', 'x'], 't'=>['s', 'y'],
			'u'=>['v'], 'v'=>['q', 'w'], 'w'=>['r', 'x'], 'x'=>['s', 'y'],
		];
		
		// コンストラクタ
		public function __construct(){
			// 全ルートを作成
			$this->route = iterator_to_array(
				new RecursiveIteratorIterator(
					new RecursiveArrayIterator(
						$this->getRoute('', 'a')
					)
				)
			, false);
		}
		
		/**
		* 全ルートを作成する
		* @param String これまで進んできたルート
		* @param String 現在地
		* @return mixed 
		*		途中なら、これまでのルートを持った配列。
		*		yに辿り着いたらそのルートまでの文字列。
		*		行き止まったらfalse。
		*/
		private function getRoute($route, $point){
			// yならゴール
			if($point === 'y'){return $route . $point; }
			
			// 次に進める限り繰り返し
			$ret = [];
			if($nextPoints = $this->getNextPoints($route, $point)){
				foreach($nextPoints as $key=>$nextPoint){
					$tmp = $this->getRoute($route.$point, $nextPoint);
					if($tmp !== false){
						$ret[] = $tmp;
					}
				}
				return $ret;
			}
			
			// 進めなくなったら
			return false;
		}
		
		/**
		* 次進める場所を取得する
		* @param String これまで進んできたルート
		* @param String 現在地
		* @return array 次進める場所の配列
		*/
		private function getNextPoints($route, $point){
			// 既に通った道は不可
			$ret = [];
			foreach($this->next[$point] as $val){
				if(strpos($route, $val) === false){
					$ret[] = $val;
				}
			}
			return $ret;
		}
		
		/**
		* パターン数を取得
		* @param  String 「ab af」みたいな文字
		* @return int 「8192」みたいな数値
		*/
		public function get($input){
			$routes = $this->route;
			
			// パース
			if(!$input){ return count($routes); }
			$stopArray = explode(' ', $input);
			
			foreach($routes as $key=>$route){
				// 通行止めを通ってるルートは削除
				foreach($stopArray as $stop){
					if(strpos($route, $stop)!==false || strpos($route, strrev($stop))!==false){
						unset($routes[$key]);
					}
				}
			}
			return count($routes);
		}
	}
	
	// テスト
	$test = [
		['', 8512 ],
		['af', 4256 ],
		['xy', 4256 ],
		['pq qr rs st di in ns sx', 184 ],
		['af pq qr rs st di in ns sx', 92 ],
		['bg ch di ij no st', 185 ],
		['bc af ch di no kp mr ns ot pu rs', 16 ],
		['ab af', 0 ],
		['ty xy', 0 ],
		['bg ch ej gh lm lq mr ot rs sx', 11 ],
		['ty ch hi mn kp mr rs sx', 18 ],
		['xy ch hi mn kp mr rs sx', 32 ],
		['ch hi mn kp mr rs sx', 50 ],
		['ab cd uv wx', 621 ],
		['gh mn st lq qr', 685 ], 
		['fg gl lm mr rs', 171 ],
	];

	$route = new ROUTE();
	foreach($test as $key=>$data){
		$answer = $route->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}

とりあえず全経路を求めておいて、通行止めになった道を通っているものを削除するという、あまりに力業な求め方となりました。
今回は全経路が8512種類しかないので問題なく動作しますが、おそらく一辺があと2くらい増えたら動かなくなるでしょう。
二重ループとかもどうにかしたいところです。
かかった時間は制限をぶっちぎって3時間くらい。

作った後で思いついたが、先に「次進める方向」から通行止めの行き先を削除し、それから「ルートを作成」したほうが早そうだ。


「オフラインリアルタイムどう書く」の一覧