小町算
Posted feedbacks - C#
「C# には eval が無いなぁ。動的コンパイルでもしようかな。あ待てよアレがあったな」 ということで C#2.0 + IronPython1.1 です。ところてんさんの #4728 を参考に、Python のコードを片っ端から生成して IronPython で Execute しています。komachi 関数は C# 側で作成。括弧なしで 101 個を、６分程度(orz)で調べ上げます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | using System;
using System.Collections.Generic;
using IronPython;
using IronPython.Hosting;
using IronPython.Runtime;
using IronPython.Runtime.Calls;
class Program {
static void Main() {
PythonEngine python = new PythonEngine();
EngineModule module = python.CreateModule();
Dictionary<string, object> locals = new Dictionary<string, object>();
int count = 0;
locals["komachi"] = new CallTarget2(delegate(object obj, object obj2) {
if (obj2.Equals(100.0)) {
count++;
Console.WriteLine(obj + " = " + obj2);
}
return null;
});
DateTime before = DateTime.Now;
foreach (string code in GenPythonCode()) {
python.Execute(code, module, locals);
}
Console.WriteLine("time: {0}", DateTime.Now - before);
Console.WriteLine("total: {0}", count);
}
static IEnumerable<string> GenPythonCode()
{
string[] ops = { "", ".0+", ".0-", ".0*", ".0/" };
for (int i = 0; i < Math.Pow(ops.Length, 8); i++) {
string code = "1";
int j = i;
foreach (char num in "23456789") {
code += ops[j % ops.Length] + num;
j /= ops.Length;
}
yield return string.Format("komachi(\"{0}\", {0})", code + ".0");
}
}
}
|
AMD Sempron 3400+ 1.99 GHz, 480 MB RAM で11秒。 書きあがるまでに6時間掛かりましたorz
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | using System;
using System.Text;
using System.Collections.Generic;
class Program {
static void Main(string[] args) {
StringBuilder ans = new StringBuilder();
long ticks = System.DateTime.Now.Ticks;
int count = 0;
List<string> Q = new List<string>(new string[] { "1", "□", "2", "□", "3", "□", "4", "□", "5", "□", "6", "□", "7", "□", "8", "□", "9" });
string[] MDPM = new string[] { "+", "-", "*", "/", " " };
foreach(string a in MDPM) {
foreach(string b in MDPM) {
foreach(string c in MDPM) {
foreach(string d in MDPM) {
foreach(string e in MDPM) {
foreach(string f in MDPM) {
foreach(string g in MDPM) {
foreach(string h in MDPM) {
try {
Q[1] = a; Q[3] = b; Q[5] = c; Q[7] = d; Q[9] = e; Q[11] = f; Q[13] = g; Q[15] = h;
} catch(ArgumentOutOfRangeException) { }
if(Eval(Q) == 100d) {
foreach(string str in Q) {
if(str != " ") {
ans.Append(str);
}
}
ans.AppendLine();
count++;
}
}
}
}
}
}
}
}
}
Console.Write(ans);
Console.WriteLine(count);
Console.WriteLine((System.DateTime.Now.Ticks - ticks) / 10000000L + "秒");
Console.ReadLine();
}
static double Eval(List<string> formula) {
List<string> fm = new List<string>(formula);
while(fm.Contains(" ")) {
int i = fm.IndexOf(" ");
string tmp = fm[i - 1] + fm[i + 1];
fm.RemoveAt(i - 1);
fm.RemoveAt(i - 1);
fm.RemoveAt(i - 1);
fm.Insert(i - 1, tmp);
}
AnyCalc[] ac = new AnyCalc[] { Multi, Div };
Calc("*", "/", "+", "-", fm, ac);
ac = new AnyCalc[] { Plus, Minus };
Calc("+", "-", "*", "/", fm, ac);
return double.Parse(fm[0]);
}
static void Calc(string xc, string yc, string ac, string bc, List<string> fm, AnyCalc[] anyCalc) {
while(fm.IndexOf(xc) != -1 || fm.IndexOf(yc) != -1) {
List<string> x = new List<string>();
List<string> y = new List<string>();
string f = " ";
int p = -1;
for(int i = 0; i < fm.Count; i++) {
double s;
if(double.TryParse(fm[i], out s)) {
if(x.Count == 0) {
x.Add(fm[i]);
} else {
y.Add(fm[i]);
}
} else if(fm[i] == xc || fm[i] == yc || fm[i] == ac || fm[i] == bc) {
p = i;
if(fm[i] == xc) {
f = xc;
} else if(fm[i] == yc) {
f = yc;
} else x.Clear();
}
if(y.Count >= 1) {
string tmp;
tmp = anyCalc[f == xc ? 0 : 1](fm[p - 1], fm[p + 1]);
for(int j = 1; j <= 3; j++) { fm.RemoveAt(p - 1); }
fm.Insert(p - 1, tmp);
break;
}
}
}
}
delegate string AnyCalc(string x, string y);
static string Plus(string x, string y) {
return (double.Parse(x) + double.Parse(y)).ToString();
}
static string Minus(string x, string y) {
return (double.Parse(x) - double.Parse(y)).ToString();
}
static string Multi(string x, string y) {
return (double.Parse(x) * double.Parse(y)).ToString();
}
static string Div(string x, string y) {
return (double.Parse(x) / double.Parse(y)).ToString();
}
}
|
Eval使いました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | using System;
using System.Collections.Generic;
using System.Windows.Forms;
using Microsoft.JScript.Vsa;
using Microsoft.JScript;
static class Program {
[STAThread]
static void Main() {
string[] s1 = new string[] { "2","3","4","5","6","7","8","9" };
string[] s2 = new string[] { "","+","-","*","/" };
int max = (int)Math.Pow(5,8);
for(int i = 0;i <= max;i++) {
string rslt = "1";
int iCopy = i;
foreach(string s in s1) {
rslt += s2[iCopy % 5] + s;
iCopy /= 5;
}
VsaEngine ve = VsaEngine.CreateEngine();
double r = System.Convert.ToDouble(Eval.JScriptEvaluate(rslt,ve));
if(r == 100.0) {
Console.WriteLine(rslt);
}
}
}
}
|
dpp
#4509()
Rating0/2=0.00
古典的なパズルである小町算を解くプログラムを作成してください。
小町算とは：
1□2□3□4□5□6□7□8□9＝100
四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。
解答例：
1－2－3＋4×56÷7＋8×9＝100
1＋234×5÷6－7－89＝100
参考： http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97
手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。
[ reply ]