codeiq860今週のお題：覆面算を満たす個数

正解した．フィードバックのRubyコード例に恐れおののいた．

array.permutation([n]) {|arr| block }

permutationメソッドは、配列から引数n個の要素を選んだときの順列（順序あり、重複を許さない組合せ）を数え上げます。組合せの数だけブロックを繰り返し実行し、ブロック引数arrに組合せを配列で入れます。戻り値はレシーバ自身です。引数を省略したときは、配列の要素数がnになります。

permutation (Array) - Rubyリファレンス

PHPにはこんな関数なかった．

問題文

今回は「覆面算」を考えます。
覆面算では、同じ文字には同じ数字が入り、違う文字には違う数字が入ります。
また、最上位の文字には0は入りません。

例えば、
We × love ＝ CodeIQ
という式が与えられたとき、以下のように当てはめることができます。

W = 7, e = 4, l = 3, o = 8, v = 0, C = 2, d = 1, I = 9, Q = 6

この変換により、「74 × 3804 ＝ 281496」という式ができます。
上記の式を満たすものはこの1通りしかありません。

では、以下の式を満たすような当てはめ方は何通りあるか求めてください。
READ + WRITE + TALK = SKILL

第26回「今週のアルゴリズム：覆面算を満たす個数」正解者発表｜CodeIQ MAGAZINE

提出コードindex.php

Gist codeiq860今週のお題：覆面算を満たす個数

<?php

/**
 * https://codeiq.jp/ace/thisweek_masuipeo/q860 今週のお題：覆面算を満たす個数
 */
// 総当たりログを扱うため，大容量メモリを使用させる
// php.ini初期値128M．256Mでも不足した
ini_set('memory_limit', '512M');

// ------------------------
// 設定
// 改行コード
define("KAIGYO", "\r\n");
// 数字パターン
define("INTCHARS", "0123456789");
// newleftパッド文字
define("NEWLEFTPAD", "X");
// 覆面算を満たすログ出力接頭辞
define("TRUEHEAD", "t: ");
// 覆面算を満たすログ出力接頭辞
define("FALSEHEAD", "f: ");
// 出力ファイル名．全部．91MBになる
define("OUTFILENAME_ALL", "alllog.txt");
// 出力ファイル名．覆面算を満たすケース．12件
define("OUTFILENAME_TRUE", "truelog.txt");

// ------------------------
// 実験エリア
//echo var_dump(hasNGzero(INTCHARS));
//echo var_dump(hasNGzero("1023456789"));
//calc("1023456789");
/* // データ整形動作確認用．結果はtestlogフォルダにぶっこんでおいた
  $log = <<< EOT
  f: 1632 + 41976 + 7305 = 50913 ===  85900
  f: 1632 + 41976 + 7308 = 50916 ===  58900
  f: 1632 + 41976 + 7350 = 50958 ===  80955
  t: 1632 + 41976 + 7380 = 50988 ===  50988
  f: 1632 + 41986 + 8305 = 51923 ===  75900
  f: 1632 + 41986 + 8307 = 51925 ===  57900
  f: 1632 + 41986 + 8350 = 51968 ===  70955
  f: 1632 + 41986 + 8370 = 51988 ===  50977
  f: 1632 + 51476 + 7308 = 60416 ===  98400
  f: 1632 + 51476 + 7309 = 60417 ===  89400
  f: 1632 + 51476 + 7380 = 60488 ===  90488
  f: 1632 + 51476 + 7390 = 60498 ===  80499
  f: 1632 + 51486 + 8307 = 61425 ===  97400
  f: 1632 + 51486 + 8309 = 61427 ===  79400
  f: 1632 + 51486 + 8370 = 61488 ===  90477
  f: 1632 + 51486 + 8390 = 61508 ===  70499
  f: 1632 + 51496 + 9307 = 62435 ===  87400
  f: 1632 + 51496 + 9308 = 62436 ===  78400
  EOT;
 */

// ------------------------
// 試行
// 総当たりする
permutation("", INTCHARS);

// ------------------------
// 結果出力．全ログは91MBになるから，毎回書き出すべきでない
// file_put_contents(OUTFILENAME_ALL, $log);
$lines = explode(KAIGYO, $log);
foreach ($lines as $key => $line) {
	if (substr($line, 0, strlen(FALSEHEAD)) === FALSEHEAD) {
		// false行を除去する
		unset($lines[$key]);
	}
}
// 連結して出力する
$truelog = implode(KAIGYO, $lines);
file_put_contents(OUTFILENAME_TRUE, $truelog);
//echo $truelog;

// ------------------------
// 以下，関数
/**
 * 計算してみる
 * 頭文字の非0確認は，パターン総当たり中に実行する
 * @param string $readwitlks [0-9]の割り当て
 * @global type $log 計算ログ
 */
function calc($readwitlks) {
	$r = $readwitlks[0]; //zero NG
	$e = $readwitlks[1];
	$a = $readwitlks[2];
	$d = $readwitlks[3];
	$w = $readwitlks[4]; //zero NG
	$i = $readwitlks[5];
	$t = $readwitlks[6]; //zero NG
	$l = $readwitlks[7];
	$k = $readwitlks[8];
	$s = $readwitlks[9]; //zero NG

	$read = (int) ($r . $e . $a . $d);
	$write = (int) ($w . $r . $i . $t . $e);
	$talk = (int) ($t . $a . $l . $k);
	$skill = (int) ($s . $k . $i . $l . $l);

	$left = $read + $write + $talk;
	if ($left === $skill) {
		$outdata = TRUEHEAD . $readwitlks . KAIGYO;
		$outdata .= TRUEHEAD;
	} else {
		$outdata = FALSEHEAD;
	}
	$outdata .= "$read + $write + $talk = $left ===  $skill" . KAIGYO;
	global $log;
	$log .= $outdata;
}

/**
 * 数字あてはめを総当たりする再帰関数
 * http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1231716637 javaで総当りアルゴリズムをしたい - Yahoo!知恵袋
 * phinloda 回答日時：2009/10/14 22:11:53 編集日時：2009/10/14 22:23:39
 * @param string $left 組み合わせ左側
 * @param string $right 組み合わせ右側
 */
function permutation($left, $right) {
	$newleft = $left . NEWLEFTPAD;
	for ($i = 0; $i < strlen($right); $i++) {
		$newleft[strlen($newleft) - 1] = $right[$i]; // 最後尾に右側の値を，順に入れる
		if (hasNGzero($newleft)) {
			// 頭文字が0になるパターンを刈り取る
			continue;
		}
		if (strlen($right) === 1) {
			// 組み合わせパターン確定
			calc($newleft);
		} else {
			// 左側に写した値を除く右側数列で再構成する
			$newright = substr($right, 0, $i) . substr($right, $i + 1);
			permutation($newleft, $newright);
		}
	}
}

/**
 * 頭文字の非0を確認する
 * $readwitlks R, W, T, Sは0足り得ない．このパターンならtrue
 * @param string $newleft [0-9]文字列
 * @return boolean 頭文字が0の場合，true
 */
function hasNGzero($newleft) {
	$len = strlen($newleft);
	switch ($len) {
		// fall throughでチェック
		// $ReadWiTlkS
		// _0123456789
		// _0___4_6__9 strlenが(0+1, 4+1, 6+1, 9+1)の場合，最後尾を確認する
		case 10: // Skill
		case 7: // Talk
		case 5: // Write
		case 1: // Read
			// $newleft構成時にチェックするため，文字列最後尾のみの確認で足りる
			if ($newleft[$len - 1] === "0") {
				return true;
			}
		default:
			return false;
	}
}