「第17回オフラインリアルタイムどう書くの参考問題」をPHPで解く

http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
http://qiita.com/Nabetani/items/dabe8ec57e0313229552

10進数の数値を別の進数になおしたら、その数が回文数になることがある。
そうなる場合の基数を列挙せよ。
ちょっと考えただけで計算量が凄いことになりそうだが大丈夫だろうか。

<?php

	class SCHEHERAZADE{
	
		/**
		* 回文基数
		* @param String 「17301」みたいな文字列
		* @return String 「5,38,100,218,236,5766,17300」みたいな文字列
		*/
		public function get($input){
			$input = (int)$input;
			$ret = [];
			
			// 2からinput-1進数
			for($i=2;$i<$input;$i++){
				// 進数表現を取得
				$arr = $this->baseConvert($input, $i);
				// 逆順と等しければ回文
				if($arr === array_reverse($arr)){
					$ret[] = $i;
				}
			}
			// 答えがなければ-
			return $ret ? implode(',', $ret) : '-';
		}
		
		/**
		* $base進数を求める
		* @param int 元の数
		* @param int 基数
		* @return array ex:数字が1001、基数が25のとき、[1, 15 ,1]
		*/
		function baseConvert($num, $base){
			$result = [];
			while($num > 0){
				$result[] = $num % $base;
				$num = floor($num / $base);
			}
			return $result;
		}
	}
	
	// 以下はテスト
	$test = [
		['17301', '5,38,100,218,236,5766,17300'],
		['2', '-'],
		['1', '-'],
		['3', '2'],
		['4', '3'],
		['5', '2,4'],
		['6', '5'],
		['10', '3,4,9'],
		['101', '10,100'],
		['1001', '10,25,76,90,142,1000'],
		['10001', '10,24,30,42,80,100,136,10000'],
		['1212', '22,100,201,302,403,605,1211'],
		['123412', '62,100,205,215,30852,61705,123411'],
		['5179', '5178'],
		['4919', '4918'],
		['5791', '5790'],
		['5498', '2748,5497'],
		['453', '150,452'],
		['134', '66,133'],
		['8489', '27,652,8488'],
		['1234', '22,616,1233'],
		['5497', '41,238,5496'],
		['4763', '19,35,432,4762'],
		['3974', '17,27,1986,3973'],
		['3521', '44,55,502,3520'],
		['5513', '20,38,53,148,5512'],
		['8042', '23,29,60,4020,8041'],
		['7442', '37,60,121,3720,7441'],
		['4857', '25,1618,4856'],
		['22843', '49,69,91,141,430,22842'],
		['194823', '84,121,21646,64940,194822'],
		['435697', '160,169,235,626,1822,435696'],
		['142', '3,7,70,141'],
		['886', '5,14,442,885'],
		['3102', '7,65,93,140,281,516,1033,1550,3101'],
		['17326', '11,28,99,105,8662,17325'],
		['32982', '13,72,238,477,716,1433,5496,10993,16490,32981'],
		['36', '5,8,11,17,35'],
		['37', '6,36'],
		['251', '8,250'],
		['252', '5,10,17,20,27,35,41,62,83,125,251'],
		['253', '12,14,22,252'],
		['6643', '2,3,9,81,90,510,948,6642'],
		['5040', '71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039'],
		['9240', '23,38,62,104,109,119,131,139,153,164,167,209,219,230,263,279,307,329,384,419,439,461,615,659,769,839,923,1154,1319,1539,1847,2309,3079,4619,9239'],
	];

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

わりと大丈夫だった。
作成30分、実行0.2秒。
まあ高速化とかは何も考えてないけど充分でしょう。