Beat Conway John

1 3
1 1 1 3
3 1 1 3
1 3 2 1 1 3
1 1 1 3 1 2 2 1 1 3
3 1 1 3 1 1 2 2 2 1 1 3
1 3 2 1 1 3 2 1 3 2 2 1 1 3
1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 3

next line?

A nice course on rubik's cube

This course discusses the inner relationship between Group Theory and Rubik' Cube, which seems very fascinating to me.

http://akbar.marlboro.edu/~mahoney/courses/Spr00/rubik.html

Shity Recursion

This is a program that could be used to calculate rook polynomial which is putting rooks in a irregular chess board( more specifically, it can partially solve sgu269). Almost killed by recursion.

#include <iostream>

#include <fstream>

#include <memory>

using namespace std;

fstream fin;

int n,k,num[5],rk[5],ans[5][8],ma,mi;

void ready()

{

    fin>>n>>k;

    for (int i=1;i<=n;i++)

     {

       fin>>num[i];

       if (num[i]>ma) ma=num[i];

       rk[i]=(1 << num[i])-1;

     }

     if (ma>n)

      mi=n;

      else

      mi=ma;

}

bool chk(int rook[])

{

    for (int i=1;i<=n;i++)

      if (rook[i]!=0)

        return false;

    return true;

}

void poly(int dep,int lev,int pow)

{  

   int tmp[5];

  if (chk(rk))  //如果检查是空棋盘

   {

ans[0][dep]=1;   

     return;

   }

           

             memcpy(tmp,rk,sizeof(tmp));

             while (rk[lev]==0) lev++;

while ((rk[lev] & (1 << pow))!=(1 << pow))

  pow++;

rk[lev]=rk[lev]- (1 << pow);

             if (rk[lev]==0)

poly(dep+1,lev+1,0);

else poly(dep+1,lev,pow+1);

            for (int l=0;l<=mi;l++)

{ans[l][dep]+=ans[l][dep+1];

ans[l][dep+1]=0;}

memcpy(rk,tmp,sizeof(rk));

                rk[lev]=0;

             for (int k=lev+1;k<=n;k++)

              if ((rk[k])>=(1 << pow))

rk[k]=rk[k]- (1 << pow);

              poly(dep+1,lev+1,0);

            for (int l=1;l<=mi;l++)

{ans[l][dep]+=ans[l-1][dep+1];

ans[l-1][dep+1]=0;}

memcpy(rk,tmp,sizeof(rk));

         

}

int main()

{   fin.open("c:\\test.txt");

    ready();

    poly(1,1,0);

cout<<ans[k][1];

    fin.close();

}

POJ 2449 A* search K shortest path

First real C++ program

#include<iostream>

#include<fstream>

using namespace std;

int n,m,s,t,k,size;

int l[1001],l2[1001],her[1001],time[1001];

bool used[1001];

fstream fin;

int a,b,r;

struct edge{

    int v,l,t;

};

struct key{

int v,value;

};

edge map[1001][1001],map2[1001][1001];

key data[1001],tmp;

void ready()

{

fin>>n>>m;

   for (int i=1;i<=m;i++)

   {  

  fin>>a>>b>>r;

  l[a]++;

      map[a][l[a]].v=b;

      map[a][l[a]].l=r;

      l2[b]++;

      map2[b][l2[b]].v=a;

      map2[b][l2[b]].l=r;

   }

   fin>>s>>t>>k;

   if (s==t) k++;

}

void dijkstra()

{ int z;

   for (int i=1;i<=n;i++)

her[i]=1000000;

   her[t]=0;

   for (int i=1;i<=n;i++)

   {

  int min=1000000;

  for (int j=1;j<=n;j++)

    if ((!used[j]) && (her[j]<min))

{

min=her[j];

z=j;

  }

used[z]=true;

for (int j=1;j<=l2[z];j++)

{

   if (her[z]+map2[z][j].l<her[map2[z][j].v])

            her[map2[z][j].v]=her[z]+map2[z][j].l;

}

   }

}

void push(int v,int i)

{    int tmp1;

     key temp;

    size++;

data[size].v=map[v][i].v;

data[size].value=tmp.value+map[v][i].l;

tmp1=size;

while (tmp1 > 1)

{

if (data[tmp1 >> 1].value+her[data[tmp1>>1].v]<data[tmp1].value+her[map[v][i].v]) break;

temp=data[tmp1];

data[tmp1]=data[tmp1 >> 1];

data[tmp1 >> 1]=temp;

        tmp1= tmp1 >> 1;

}

}

void del()

{   key temp;

temp=data[size];

data[size]=data[1];

data[1]=temp;

size--;

int i = 1;

while ((i << 1) <= size)

{

int j;

j = i << 1;

if ((j < size) && (data[j + 1].value+her[data[j+1].v]< data[j].value+her[data[j].v])) j++;

if (data[i].value+her[data[i].v]< data[j].value+her[data[j].v]) break;

temp=data[i];

data[i]=data[j];

data[j]=temp;

i = j;

}

}

int a_star()

{ 

if( her[s]==1000000 ) return -1;

data[1].v=s;

data[1].value=0;

  time[s]=0;

  size=1;

  

  while (size>0) {

    time[data[1].v]++;

 if (time[t]==k)

 return data[1].value;

 

      tmp=data[1];

 del();

 if (time[data[1].v]>k) continue;

 for (int e=1;e<=l[tmp.v];e++)

 {push(tmp.v,e);                           

  }

  }

return -1;

}

int main()

{

 fin.open("c:\\test.txt");

ready(); 

 dijkstra();

 int ans;

 ans=a_star();

 cout<<ans;  

 fin.close();

}

The Random Incoherent inside Physics

了解了一点广义相对论，于是知道在重力场里面的物体在进行自由落体的时候会Maximum its spacetime curve，于是无法理解阻力存在的作用，因为这一部分应该是热统的，所以想像纯数学描述的力还是跟现实有差距。

My opinion on the future of the universe

According to the third law of thermodynamic, the net entropy of our universe should monoticly increase, therefore the universe should have to expand to a infinitly dilute gas composition.

Unruh Thought Experiment

早在20世纪80年代早期，作为思想实验昂鲁就设想了一种类似的流体运动。他假想有一个瀑布，其中水流的速度超过了水中的声速。在这样的系统中，在水流达到声速的那个面就形成是了“视界”，水中的声波无法逃逸到“视界”之外。“如果你能恰到好处地调节水流”他说，“你确实可以模拟出一个黑洞。”