忍者ブログ
[PR]
×

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



2017/07/23 19:50 |
PHP5.3.7 「第8回オフラインリアルタイムどう書くの参考問題」をPHPで解く
http://qiita.com/Nabetani/items/24b9be4ee3bae4c89a95
http://nabetani.sakura.ne.jp/hena/ord8entco/

エントロピー符号とは、Wikipediaの解説は相変わらず意味がわかりませんが、まあ文字を適当に01に割り当てたものです。
有名どころではハフマン符号です。
モールス信号では"11"が"EE"か"I"か区別できませんが、ハフマン符号では正しい値であれば必ず一意に復元可能です。
<?php
	
	class ENTROPY{
	
		/**
		* 符号を解読して返す
		* @param  String 「16d9d4fbd」みたいな文字列
		* @return String 「ethanol:30」みたいな文字列
		*/
		public function get($input){
			
			// マッチ文字列
			$search = ['/^000/', '/^0010/', '/^0011/', '/^0100/', '/^01010/', '/^0101101/', '/^010111/', '/^0110/', '/^0111/', '/^10/', '/^1100/', '/^1101/', '/^111/'];
			$replace = ['t', 's', 'n', 'i', 'd', 'c', 'l', 'o', 'a', 'e', 'r', 'h', 'z'];
			
			// 入力値を2進数に
			$str = '';
			for($i=0; $i<strlen($input); $i++){
				$str.= strrev(str_pad(base_convert($input[$i], 16, 2), 4, '0', STR_PAD_LEFT));
			}
			
			// 内部使用
			$entropy = ''; // できあがる文字列
			$lastmatch = ''; // 最後にマッチした文字
			$strlen = strlen($str); // ビット数カウント用
			
			// マッチする限り繰り返し
			$str = preg_replace($search, $replace, $str, 1, $count);
			while($count>0){
				$lastmatch = $str[0];
				$str = substr($str, 1);
				
				// 引っかかったのがEOFだったら終了
				if($lastmatch === 'z'){
					break;
				}
				
				// 次のループ用
				$entropy .= $lastmatch;
				$str = preg_replace($search, $replace, $str, 1, $count);
			};
			
			// マッチしなかった / EOFがなかった
			if($entropy === '' || $lastmatch !== 'z'){
				return '*invalid*';
			}
			
			// 返却
			return $entropy . ':' . ($strlen - strlen($str));
		}
		
	}
	
	// テスト
	$test = [
		['16d9d4fbd', 'ethanol:30'],
		/* 省略 */
	];

	$entropy = new ENTROPY();
	foreach($test as $key=>$data){
		$answer = $entropy->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}
2進数にするところで、通常"0x1"は"0001"になりますが、今回は"1000"にしないといけないので妙なことになってます。
検索ループはwhile(strpos()===0)とかwhile(preg_match())みたいにしたかったのですが、いまいちうまくいかなかったのでpreg_replaceを使って微妙なことに。
あとarray_shift()の文字列版ってないのだろうか。

かかった時間は2時間くらい。
どうマッチするかのところで相当時間をくってしまいました。
もうelseif繋げたほうが手っ取り早かったんじゃないかな。


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


2013/07/22 22:48 | Comments(1) | PHP

コメント

Services_Shitarabaはもうメンテされないのですか・・・
posted by 名無しじゃなきゃダメなのぉ! at 2013/07/26 01:14 [ コメントを修正する ]

コメントを投稿する






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



<<PHP5.3.7 TwitterOAuthの正しい使い方 | HOME | 買ったものリスト 2013/07/21>>
忍者ブログ[PR]