忍者ブログ
[PR]
×

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



2017/03/27 21:35 |
PHP5.3.7 「第7回オフラインリアルタイムどう書くの参考問題」をPHPで解く
http://qiita.com/Nabetani/items/7b08b0eb9ef84d7cfe49
http://nabetani.sakura.ne.jp/hena/ord7xysort/

行列をソートするというもの。
PHPにはarray_multisort()という超絶便利関数があるので、こいつ呼ぶだけで一発だろーはっはっはー、とか思って作り始めたところ、実は全てのソート関数が値が同じときの順番を保証しないという事実が発覚して全滅。
仕方ないので自力でソートする羽目に。なんてこった。

で、キーを維持するユーザ定義ソート関数にはusort()uksort()があるのですが、usort()はコールバックに値しか渡さない、uksort()はキーしか渡さないという意味のわからない仕様。
use使えばいいのですが、デフォでキーと値両方とも渡してくださいマジで。

<?php
	class XYSORT{
		
		/**
		* 二次元でソート
		* @param  String 「AvEx」みたいな文字列
		* @return String 「305027」みたいな文字列
		*/
		public function get($input){
			
			// 初期状態
			$table = [
				[4, 1, 4, 2, 1, 3],
				[7, 3, 2, 0, 5, 0],
				[2, 3, 6, 0, 6, 7],
				[6, 4, 5, 7, 5, 1],
				[3, 1, 6, 6, 2, 4],
				[6, 0, 5, 5, 5, 1]
			];
			// 文字に対応する列
			$map = [
				'A'=>0, 'B'=>1, 'C'=>2, 'D'=>3, 'E'=>4, 'F'=>5,
				'u'=>0, 'v'=>1, 'w'=>2, 'x'=>3, 'y'=>4, 'z'=>5
			];
			
			// 現在のテーブルが縦か横かのフラグ
			$tableCol = true;
			
			// 入力値でくるくる
			for($i=0; $i<strlen($input); $i++){
				// 縦か横か
				$isTableCol = (strtoupper($input[$i]) === $input[$i]);
				
				// 縦横が合ってないときは転置
				if($tableCol !== $isTableCol){
					$tableCol = !$tableCol;
					$table = $this->getTransposed($table);
				}
				
				// ソート基準列
				$columnid = (int)$map[$input[$i]];
				$column = $table[$columnid];
				
				// ソート基準列を、昇順安定ソート
				uksort($column, function($a, $b) use($column){
					if($column[$a] < $column[$b]){
						return -1;
					}elseif($column[$a] > $column[$b]){
						return 1;
					}else{
						return $a > $b;
					}
				});
				
				// テーブルを基準列に合わせてソート
				$tmp = [];
				foreach($column as $key=>$val){
					foreach($table as $row=>$data){
						$tmp[$row][] = $table[$row][$key];
					}
				}
				$table = $tmp;
			}
			
			// 最後に転置されてたら戻す
			if($tableCol === false){
				$table = $this->getTransposed($table);
			}
			
			// 終了
			return implode('', $table[0]);
		}
		
		/**
		* 転置行列を得る
		* {@see http://blog.supermomonga.com/articles/php/array-to-transverse-matrix.html }
		* @param  array 二次元配列
		* @return array 縦横を入れ替え
		*/
		private function getTransposed($array){
			return call_user_func_array('array_map', array_merge(array(null), $array));
		}
	}
	
	// テスト
	$test = [
		['AvEx', '305027'],
		/* 省略 */
	];

	$xysort = new XYSORT();
	foreach($test as $key=>$data){
		$answer = $xysort->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}
いやー、想像以上に残念なコードになってしまった。
array_multisortにコールバックを渡せればねえ。

残念なのですが、いまいちこれよりよさげなアルゴリズムを考えつかないのでとりあえず保留。
またいずれリベンジしたいものですね。

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


2013/08/05 23:59 | Comments(0) | PHP

コメント

コメントを投稿する






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



<<PHP5.5.0 「第6回オフラインリアルタイムどう書くの問題」をPHPで解く | HOME | 買ったものリスト 2013/08/04>>
忍者ブログ[PR]