Prolog始めたよ

Prologというプログラミング言語があります．Prologは論理型言語の一つで，一階述語論理に基づいて命題を与え，その命題が正しいかを再帰的手続きによって探索する言語である，とのことです．

処理系にはSWI-Prologを用いました．ダウンロードは↓から．
SWI-Prolog's home

入門はこちら．
M.Hiroi's Home Page / Prolog Programming

事実，規則:

fly(X) :- airplane(X).
airplane(jet_plane).
airplane(helicopter).

質問:

?- fly(jet_plane).
YES
?- fly(taro).
NO

こんな感じ．
時間がある時に適当に記事を書く予定です．

セルオートマトン #24 ルール22

ルール22
クラス3

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	□	■	■	□

Fig.1 rule22

セルオートマトン #23 ルール21

ルール21
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	□	■	□	■

Fig.1 rule21

左にゆっくりと移動していますが，左程珍しくないです．

TopCoder 練習

RabbitNumbering(SRM463 DIV1 Easy)
AgeEncoding(SRM462 DIV1 Easy)

AgeEncodingは2分法で基本的には解けましたが，場合分けで若干苦戦しました．

プログラム・プロムナード 最大長方形の面積

下記の連載「プログラム・プロムナード」には，有益なアルゴリズムが色々と載っているので実装してみました．

プログラム・プロムナード
http://www.ipsj.or.jp/07editj/promenade/index.html

2002年4月号 最大長方形の面積(和田英一)

view plainprint?

1. import java.util.*;  
2. import java.awt.*;  
3.   
4. public class Main{  
5.   
6.  // 単純なループによる実装 O(n^6)  
7.  private int count1(int[][] a){  
8.   int res=0;  
9.   int m=a[0].length;  
10.   int n=a.length;  
11.   for(int y1=0;y1<n;y1++){  
12.    for(int x1=0;x1<m;x1++){  
13.     // 始点-(x1, y1)  
14.     for(int y2=y1;y2<n;y2++){  
15.      for(int x2=x1;x2<m;x2++){  
16.       // 終点-(x2, y2)  
17.       int c=0;  
18.       // (x1, y1)-(x2, y2)から構成される長方形内の1の個数を数える  
19.       for(int j=y1;j<=y2;j++)  
20.        for(int i=x1;i<=x2;i++)  
21.         if(a[j][i]==1)  
22.          c++;  
23.       // 長方形内のマスが全て1であり  
24.       // 長方形の大きさ(=c)が今までの最大値より大きい場合は更新  
25.       if(c==(x2-x1+1)*(y2-y1+1))  
26.        if(c>res)  
27.         res=c;  
28.      }  
29.     }  
30.    }  
31.   }  
32.   return res;  
33.  }  
34.    
35.  // 動的計画法による実装  
36.  private int count2(int[][] a){  
37.   int m=a[0].length;  
38.   int n=a.length;  
39.   int max=0;  
40.   LinkedList<Point>[][] lists=(LinkedList<Point>[][])new LinkedList[n][m];;  
41.   LinkedList<Point> temp=new LinkedList<Point>();  
42.   
43.   for(int j=0;j<n;j++)  
44.    for(int i=0;i<m;i++)  
45.     lists[j][i]=new LinkedList<Point>();  
46.   
47.   for(int j=0;j<n;j++){  
48.    for(int i=0;i<m;i++){  
49.     if(a[j][i]==0)  
50.      continue;  
51.     int up, left;  
52.     for(up=0;j-up>=0&&a[j-up][i]==1;up++)  
53.      ;  
54.     for(left=0;i-left>=0&&a[j][i-left]==1;left++)  
55.      ;  
56.     // 上隣=0，左隣=0  
57.     if((i==0||a[j][i-1]==0)&&(j==0||a[j-1][i]==0)){  
58.      // (1, 1)  
59.      lists[j][i].add(new Point(1, 1));  
60.     }  
61.     // 上隣=0，左隣=1  
62.     else if(j==0||a[j-1][i]==0){  
63.      // (左方に続く1の個数, 1)  
64.      lists[j][i].add(new Point(left, 1));  
65.     }  
66.     // 上隣=0，左隣=1  
67.     else if(i==0||a[j][i-1]==0){  
68.      // (1, 上方に続く1の個数)  
69.      lists[j][i].add(new Point(1, up));  
70.     }  
71.     // 上隣=1，左隣=1  
72.     else{  
73.      for(Point p:lists[j][i-1])  
74.       lists[j][i].add(new Point(p.x+1, Math.min(p.y, up)));  
75.      for(Point p:lists[j-1][i])  
76.       lists[j][i].add(new Point(Math.min(p.x, left), p.y+1));  
77.     }  
78.   
79.     // 重複要素の削除  
80.     for(Point p:lists[j][i])  
81.      if(!temp.contains(p))  
82.       temp.add(p);  
83.     lists[j][i].clear();  
84.     
85.     // qより大きい長方形が存在したらqをリストに追加しない  
86.     for(Point q:temp){  
87.      for(Point p:temp){  
88.       if(q!=p&&q.x<=p.x&&q.y<=p.y){  
89.        q=null;  
90.        break;  
91.       }  
92.      }  
93.      if(q!=null)  
94.       lists[j][i].add(q);  
95.     }  
96.     temp.clear();  
97.   
98.     for(Point p:lists[j][i])  
99.      max=Math.max(max, p.x*p.y);  
100.    }  
101.   }  
102.   return max;  
103.  }  
104.    
105.  public static void main(String[] args){  
106.   int[][] a;  
107.   a=new int[50][50];  
108.   for(int j=0;j<a.length;j++)  
109.    for(int i=0;i<a[0].length;i++)  
110.     a[j][i]=(int)(Math.random()*2);  
111.   System.out.println("1:"+new Main().count1(a));  
112.   System.out.println("2:"+new Main().count2(a));  
113.  }  
114. }  

import java.util.*;
import java.awt.*;

public class Main{

 // 単純なループによる実装 O(n^6)
 private int count1(int[][] a){
  int res=0;
  int m=a[0].length;
  int n=a.length;
  for(int y1=0;y1<n;y1++){
   for(int x1=0;x1<m;x1++){
    // 始点-(x1, y1)
    for(int y2=y1;y2<n;y2++){
     for(int x2=x1;x2<m;x2++){
      // 終点-(x2, y2)
      int c=0;
      // (x1, y1)-(x2, y2)から構成される長方形内の1の個数を数える
      for(int j=y1;j<=y2;j++)
       for(int i=x1;i<=x2;i++)
        if(a[j][i]==1)
         c++;
      // 長方形内のマスが全て1であり
      // 長方形の大きさ(=c)が今までの最大値より大きい場合は更新
      if(c==(x2-x1+1)*(y2-y1+1))
       if(c>res)
        res=c;
     }
    }
   }
  }
  return res;
 }
 
 // 動的計画法による実装
 private int count2(int[][] a){
  int m=a[0].length;
  int n=a.length;
  int max=0;
  LinkedList<Point>[][] lists=(LinkedList<Point>[][])new LinkedList[n][m];;
  LinkedList<Point> temp=new LinkedList<Point>();

  for(int j=0;j<n;j++)
   for(int i=0;i<m;i++)
    lists[j][i]=new LinkedList<Point>();

  for(int j=0;j<n;j++){
   for(int i=0;i<m;i++){
    if(a[j][i]==0)
     continue;
    int up, left;
    for(up=0;j-up>=0&&a[j-up][i]==1;up++)
     ;
    for(left=0;i-left>=0&&a[j][i-left]==1;left++)
     ;
    // 上隣=0，左隣=0
    if((i==0||a[j][i-1]==0)&&(j==0||a[j-1][i]==0)){
     // (1, 1)
     lists[j][i].add(new Point(1, 1));
    }
    // 上隣=0，左隣=1
    else if(j==0||a[j-1][i]==0){
     // (左方に続く1の個数, 1)
     lists[j][i].add(new Point(left, 1));
    }
    // 上隣=0，左隣=1
    else if(i==0||a[j][i-1]==0){
     // (1, 上方に続く1の個数)
     lists[j][i].add(new Point(1, up));
    }
    // 上隣=1，左隣=1
    else{
     for(Point p:lists[j][i-1])
      lists[j][i].add(new Point(p.x+1, Math.min(p.y, up)));
     for(Point p:lists[j-1][i])
      lists[j][i].add(new Point(Math.min(p.x, left), p.y+1));
    }

    // 重複要素の削除
    for(Point p:lists[j][i])
     if(!temp.contains(p))
      temp.add(p);
    lists[j][i].clear();
  
    // qより大きい長方形が存在したらqをリストに追加しない
    for(Point q:temp){
     for(Point p:temp){
      if(q!=p&&q.x<=p.x&&q.y<=p.y){
       q=null;
       break;
      }
     }
     if(q!=null)
      lists[j][i].add(q);
    }
    temp.clear();

    for(Point p:lists[j][i])
     max=Math.max(max, p.x*p.y);
   }
  }
  return max;
 }
 
 public static void main(String[] args){
  int[][] a;
  a=new int[50][50];
  for(int j=0;j<a.length;j++)
   for(int i=0;i<a[0].length;i++)
    a[j][i]=(int)(Math.random()*2);
  System.out.println("1:"+new Main().count1(a));
  System.out.println("2:"+new Main().count2(a));
 }
}

マージしないでも動作するかな?と思って，マージの実装を外して検証してみましたが，リストに保存する長方形が爆発的に増えた為，メモリが足りませんでした．

セルオートマトン #22 ルール20

ルール20
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	□	■	□	□

Fig.1 rule20

見たまんまです．■が右に連なっていきます．

数学 #16 ミルズの定理

ミルズの定理という過激な定理があったので御紹介．

Mills' Theorem -- from Wolfram MathWorld
httphttp://mathworld.wolfram.com/MillsTheorem.html

Mills' Constant -- from Wolfram MathWorld
http://mathworld.wolfram.com/MillsConstant.html

ミルズの定理(Mills' theorem)

すべての自然数nについて
[θ³ⁿ]
の値が素数になるようなθが存在する．

例えば，
θ=1.30637788386308069046861449260260571291678458515671364436805375996643405376682659882150140370119739570729+

実際には，θの精度を無限大にしなければ素数を得ることはできません．が，試しに上のθでどこまで素数が出るかやってみました．

θ³¹=2.229494772491595
θ³²=11.082031369896242
θ³³=1361.0000010797248
θ³⁴=2.5210088869999886E9
θ³⁵=1.6022236204009632E28
θ³⁶=4.113101149214954E84
θ³⁷=6.958380437695496E253
θ³⁸=Infinity
やはりバカでかい値になります，n=1~4までの値を切り下げると，

[θ³¹]=2
[θ³²]=11
[θ³³]=1361
[θ³⁴]=2521008886
n=4の場合が素数じゃないですが，実際の値は2521008887です．

色々と無理があったので，オンライン整数列大辞典(On-Line Encyclopedia of Integer Sequences)にて調べました．

On-Line Encyclopedia of Integer Sequences
http://www.research.att.com/~njas/sequences/

[θ³¹]=2
[θ³²]=11
[θ³³]=1361
[θ³⁴]=2521008887
[θ³⁵]=16022236204009818131831320183
[θ³⁶]=4113101149215104800030529537915953170486139623539759933135949994882770404074832568499

TopCoder 練習

ColorfulStrings(SRM465 DIV1 Easy)

TopCoder SRM 466

SRM466(4/4 1:00~3:00)

・LotteryCheating(DIV1 Easy)
約数が奇数個⇔平方数には気付いたのですが，ちょっと実装が粗かった為System Testで落ちました．後で見ましたが，Petr先生が提出したソースの美しいこと…．
Result:Failed System Test(0p)

・LotteryPyaterochka(DIV1 Normal)
組合せの問題ですが，組合せには鈍く，式が立てられませんでした．
Result:Opend(0p)

・DrawingBlackCrosses(DIV1 Hard)
＼(＾o＾)／
Result:Opened(0p)

・Challenges
0p

・Rating
1344->1292
1200台に落ちてしまいました．今後はDiv1の問題を出来るだけ多く解いて練習しておこうかと．
Yellow(1500以上)への道は遠い…．

Project Euler

problem 24

TopCoder 練習

TurretPlacement(Member SRM465 DIV1 Easy)
LotteryCheating(SRM466 DIV1 Easy)

セルオートマトン #21 ルール19

ルール19
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	□	□	■	■

Fig.1 rule19

白黒繰り返しの状態に落ち着いてしまいました．