Created
May 15, 2014 10:24
-
-
Save ustreamer-01647/a3d7372566d1a7b2f194 to your computer and use it in GitHub Desktop.
codeiq860今週のお題：覆面算を満たす個数
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?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; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
truelog.txt
t: 1632497805
t: 1632 + 41976 + 7380 = 50988 === 50988
t: 2543706918
t: 2543 + 72065 + 6491 = 81099 === 81099
t: 4905268173
t: 4905 + 24689 + 8017 = 37611 === 37611
t: 5094731628
t: 5094 + 75310 + 1962 = 82366 === 82366
t: 5096371824
t: 5096 + 35710 + 1982 = 42788 === 42788
t: 5180692437
t: 5180 + 65921 + 2843 = 73944 === 73944
t: 5270813649
t: 5270 + 85132 + 3764 = 94166 === 94166
t: 7092351864
t: 7092 + 37510 + 1986 = 46588 === 46588
t: 7092431865
t: 7092 + 47310 + 1986 = 56388 === 56388
t: 9728146053
t: 9728 + 19467 + 6205 = 35400 === 35400