今日は、登山の日、だったはずなのだが、現地の付近まで行って、雨が強いため断念ということになった。とはいえ、わざわざ車で遠くまで出かけてきて、そのままつくばに帰るというのもありえないということで、どこか遊べる場所を探すことに。話し合いの結果、巨大迷路パラディアムに行った後、龍王峡に行くことに。
しかし、巨大迷路を終えた段階で、雨で体がかなり濡れてしまったため、龍王峡を中止して、温泉に行くことに。温泉は、露天風呂と屋内の風呂両方があり、館内もきれいで、なかなか良い所だった。これで、雨がなければ最高だったのだが。
温泉に入った後は、帰ることに。昼ごはんを食べていなかったため、帰る途中に、宇都宮によって餃子を食べたが、なかなかうまかった。さすが、餃子の町だ。
餃子を食べた後は、何事も無く、19:00過ぎ頃にはつくばに帰って来た。その後、反省会と晩御飯を終えて、20:30頃、解散した。
ダウンロードしてみる。今回は、配列式{...}や、未定義変数をタグ関数にするnodeEdit()などが追加されている。
前回に引き続いてyaccの使い方の説明と、これから実習で作る言語処理系tinyCについての説明などがあった。今日は久しぶりにノートパソコンを持っていかなかったので、普通に授業を聞くことに。とはいえ、やはり退屈なので、途中からJava仮想マシン仕様を読んだりしていた。
IkejiWikiで、虫食い算の話が出ていたので、こちらも解いてみることにする。アルゴリズムとしては、基本的には総当りだが、無駄な計算をしないために、枝狩りをすることにした。また、言語は速度重視ということで、Javaを使った。コードは以下の通り。
import static java.lang.Math.*; import static java.lang.System.*;
public class Musikuisan{ public static void main(String[] args){ MusikuisanSolver solver = new SimpleSolver(); long start = currentTimeMillis(); solver.solve(); out.printf("time = %d\n", currentTimeMillis() - start); } }
abstract class MusikuisanSolver{ protected int figure_; void solve(){ int n = (int)pow(10, figure_); for(int i = 0; i < n; i ++){ if(pruned(i))continue; for(int j = 0; j < n; j++){ if(satisfied(i, j))correct(i, j); } } } abstract boolean pruned(int n); abstract boolean satisfied(int n, int s); abstract void correct(int n, int s); }
class SimpleSolver extends MusikuisanSolver{ private int[] south_; private int s0_, s1_, s2_, s3_, s4_, s5_; SimpleSolver(){ figure_ = 6; } boolean pruned1(int n){ for(int i = 0; i < 10; i++){ if(n * i / 1000 == 2002)return false; } return true; } boolean pruned2(int n){ for(int i = 0; i < 10; i++){ if((n * i - 2002) % 10000 == 0)return false; } return true; } boolean pruned(int n){ return pruned1(n) || pruned2(n); } private void split(int v, int n){ int rest = v; s0_ = rest / 100000 * n; rest = rest % 100000; s1_ = rest / 10000 * n; rest = rest % 10000; s2_ = rest / 1000 * n; rest = rest % 1000; s3_ = rest / 100 * n; rest = rest % 100; s4_ = rest / 10 * n; rest = rest % 10; s5_ = rest * n; } boolean satisfied(int n, int s){ split(s, n); long t; return (s5_ >= 2002000 && s5_ < 2003000) && (s4_ >= 1000000) && (s3_ >= 100000 && s3_ < 1000000) && (s2_ >= 1000000 && (s2_ - 2002) % 10000 == 0) && (s1_ >= 1000000) && (s0_ >= 1000000) && ((t = (((long)n) * s / 1000000 - 2002)) % 10000 == 0 && t / 10000 > 10); } void correct(int n, int s){ out.printf("n = %d, s = %d\n", n, s); } }
実行結果(実行環境:Pentium M 1GHz, Memory 768MB J2RE1.5.0 on Windows XP)は、
C:\java_example>java Musikuisan n = 250286, s = 647268 time = 2109
C:\java_example>java -server Musikuisan n = 250286, s = 647268 time = 625
一応、答えがあっているかどうか検算してみると、
C:\java_example>pnuts Pnuts version 1.1 (20040807001111), 1.5.0 (Sun Microsystems Inc.) Java HotSpot(TM) Client VM (mixed mode, sharing) > 250286 * 8 2002288 > 250286 * 6 1501716 > 250286 * 2 500572 > 250286 * 7 1752002 > 250286 * 4 1001144 > 250286 * 6 1501716 > 250286 * 647268 162002118648
となり、正しい答えであることがわかる。
追記:IKeJIWikiにあるRuby版をほぼそのままJavaに移植して、 正規表現でマッチングを行っていたところを、数値演算で 比較するように置き換えたものも作ってみた。
public class Calc{
public static void main(String[] args){
int t;
long start = System.currentTimeMillis();
for(int a = 100000; a < 1000000; a++){
for(int b1 = 1; b1 < 10; b1++){
t = a * b1;
if(2002000 < t && t < 2002999){
for(int b2 = 1; b2 < 10; b2++){
if(a * b2 > 999999){
for(int b3 = 1; b3 < 10; b3++){
if(1000000 > a * b3){
for(int b4 = 1; b4 < 10; b4++){
t = a * b4;
if(t > 999999 && (t - 2002) % 10000 == 0){
for(int b5 = 1; b5 < 10; b5++){
if(a * b5 > 999999){
for(int b6 = 1; b6 < 10; b6++){
int b = b6 * 100000 + b5 * 10000 + b4 * 1000 + b3 * 100 + b2 * 10 + b1;
long r = ((long)a) * b / 1000000 - 2002;
if(r / 10000 >= 10 &&
r % 10000 == 0){
System.out.printf("Hit!! :%d,%d\n",a,b);
}
}
}
}
}
}
}
}
}
}
}
}
}
System.out.printf("time = %d\n", System.currentTimeMillis() - start);
}
}
実行結果は、
C:\java_example>java Calc Hit!! :250286,647268 time = 141
C:\java_example>java -server Calc Hit!! :250286,647268 time = 203
この結果を見ると、どうやらIKeJIWiki版の方が、枝狩り刈りをより積極的に行っているためか、速いようだ。しかも、面白いことに、IKeJIWiki版では、Server VMにした方が遅いという結果が出ている。
このバージョンでは、instanceofによる型の判定をコンパイラが静的に検出して、ある型であることが確実である範囲内で、キャストなしで、その型として扱うことが可能になっている。例えば、以下のコードは、コンパイラによるチェックを通過して、正常に実行される。
package ex;
void main(String[] args){
Object obj = "hello,world";
assert obj instanceof String;
println(obj.substring(0, 5));
}
結果は、以下のようになる。
C:\nice_programs>nicec ex nice.lang: parsing ex: parsing
C:\nice_programs>java ex.fun hello
また、assert文だけでなく、if文を使ってチェックをすることも可能になっている。
package ex2;
void main(String[] args){
Object o = "hello,world";
if(o instanceof String){
o.substring(0, 5);
}
}
このようにコンパイラによる静的なチェックを、言語の柔軟性を増すために使っている例はあまり見たことが無いので、なかなか新鮮だ。
_ TELL [関係あるかどうかわかりませんが、 筑波朝比奈アンテナで、更新日時表示が??????なのにナゼか一番上です。]