Java Project: Tic Tac Toe

非常陽春的圈圈叉叉小遊戲，可以兩個人玩，但沒有電腦玩家。

練習和試驗一些基本的JAVA語法、事件，玩玩Swing的component。用JSmooth把檔案包成exe執行檔，可以直接在windows執行。

功能：
1. 兩個玩家玩井字遊戲。當獲勝者出現顯示獲勝者，若至遊戲結束皆無獲勝者則顯示"Draw"。
2. 隨時可按"New Game"或Alt+n開始新遊戲。

執行畫面：

檔案下載：
TicTacToe.rar (149 kb)

ACM: 134 - Loglan-A Logical Language

這題要用給定的文法規則，去檢查輸入的句子是否符合文法。我直接暴力的遞迴...

TIP

雖然題目寫"You can assume that all words will be correctly formed"，但實際上加了判斷不和語法的單字才拿到AC。

CODE

#include <iostream>
#include <vector>
using namespace std;

enum { A, MOD, BA, DA, LA, NAM, PREDA };

vector<int> loglan;
int n;

bool vowel(char c){
  return ( c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' );
}

int convert_loglan(string s, int n){
  if( !vowel( s[n-1] ) ) return NAM;
  if( n == 1 ) return A;
  if( n == 2 ){
    switch( s[0] ){
      case 'g': return MOD;
      case 'b': return BA;
      case 'd': return DA;
      case 'l': return LA;
    }
  }
  if( n==5 && (( !vowel(s[0]) && !vowel(s[1]) && vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) ) ||
   ( !vowel(s[0]) && vowel(s[1]) && !vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) )) )
    return PREDA;
  return NAM;
}

bool predstring(int st, int ed){
  if( st == ed )
    return (loglan[st] == PREDA); //"PREDA"
  return (loglan[ed] == PREDA && predstring(st, ed-1)); //"<predstring> PREDA"
}

bool verbpred(int st, int ed){
  return (loglan[st] == MOD && predstring(st+1, ed)); //"MOD <predstring>"
}

bool predname(int st, int ed){
  if( st == ed )
    return (loglan[st] == NAM); //"NAM"
  return (loglan[st] == LA && predstring(st+1, ed)); //"LA <predstring>"
}

bool preds(int st, int ed){
  for(int i=st+1; i<ed; ++i){
    if( loglan[i] == A ){
      return (preds(st, i-1) && preds(i+1, ed)); //"<preds> A <predstring> -> <preds> A <preds>"
    }
  }
  return predstring(st, ed); //"<predstring>"
}

bool statement(void){
  for(int i=1; i<n; ++i){
    if( loglan[i] == MOD ){
      bool pv = predname(0, i-1) && verbpred(i, n-1); //"<predname><verbpred>"
      bool pvp = 0;
      for(int j=i+1; j<n-1; ++j)
        pvp += (predname(0, i-1) && verbpred(i, j) && predname(j+1, n-1)); //"<predname><verbpred><predname>"
      return (pvp || pv);
    }
  }
  return 0;
}

bool predclaim(void){
  if( loglan[0] == DA ){
    return preds(1, n-1); //"DA <preds>"
  }
  for(int i=1; i<n; ++i){
    if( loglan[i] == BA )
      return (predname(0, i-1) && preds(i+1, n-1)); //"<predname> BA <preds>"
  }
  return 0;
}

bool sentence(void){
  return ( statement() || predclaim() );
}

int main(){
  string s;
  while( (cin >> s) && (s[0] != '#') ){
    int len = s.size();
    if( s[len-1] == '.' ){
      s.erase(len-1);
      loglan.push_back( convert_loglan(s, len-1) );
      n = loglan.size();
      cout << (sentence() ? "Good" : "Bad!") << endl;
      //initialize
      loglan.clear();
    }
    else
      loglan.push_back( convert_loglan(s, len) );
  }//while
  return 0;
}

ACM: 133 – The Dole Queue

simulation，類似Josephus problem，照著規則模擬。

CODE

#include <iostream>

#define MAX 20

int main(){
  int n, k, m;
  bool a[MAX];
  
  while( scanf("%d%d%d", &n, &k, &m) != EOF ){
    if( n==0 && k==0 && m==0 )
      break;
    
    for(int i=0; i<n; ++i)
      a[i] = 1;
    
    bool printed = 0;
    int i = -1, j = n, left = n;
    int cnt_k, cnt_m;
    while( left > 0 ){
      cnt_k = cnt_m = 0;
      while( cnt_k != k ){
        i = (i+1)%n;
        if( a[i] )
          ++cnt_k;
      }
      while( cnt_m != m ){
        j = (j+n-1)%n;
        if( a[j] )
          ++cnt_m;
      }
      
      if( printed )
        printf(",");
      else
        printed = 1;
        
      if( i == j ){
        a[i] = 0;
        --left;
        printf("%3d", i+1);
      }
      else{
        a[i] = a[j] = 0;
        left -= 2;
        printf("%3d%3d", i+1, j+1);
      }
    }//killing
    printf("\n");
  }//while
  return 0;
}

ACM: 137 - Polygons

寫完132，打鐵趁熱繼續寫geometry的題目。這題很複雜，但要解決的問題很清楚，就是求兩個凸多邊形的非交集的面積(xor, 異域)。

我的算法如下：
A: 第一個凸多邊形點集合
B: 第二個凸多邊形點集合
C: A,B交集部分的點集合(初始為空集合)

1. 檢查A的每一個點，若落在B內部或邊上即將該點加入C。
2. 檢查B的每一個點，若落在A內部或邊上即將該點加入C。
3. 檢查A的每一邊，對B的每一邊逐邊檢查是否可以相交，若可相交即求交點，將交點加入C。
4. A,B交集求畢，將C集合的點逆時針排序。
5. 輸出異域面積為 (A + B – C) – C = A + B - 2C

實作方法

檢查P點是否落在圖形內部或邊上
逆時針檢查圖形的每一點，若「每一點到下一點的向量」與「每一點至P點的向量」皆為逆時針旋轉(外積>0)，則P點在圖型內部。當外積=0時，P點在圖形邊上。

檢查線段P1P2與P3P4是否相交
單純用外積檢查兩線段是否互相跨立。
當 (P1P2 x P1P3)*(P1P2 x P1P4) < 0 時代表P3, P4分別在線段P1P2的兩端，故外積異號。
當 (P3P4 x P3P1)*(P3P4 x P3P2) < 0 時代表P1, P2分別在線段P3P4的兩端，故外積異號。
當兩者皆成立時，線段P1P2與線段P3P4相交。

相交線段求交點
參考「平面內兩條線段的位置關係判定及交點求解」，用向量法求解，只需用到一次除法，減少精確度的問題。

點逆時針排序
先找最左下方的點，其他的點對該點做逆時針的極角排序。

凸多邊形面積
 
起點與終點必須為同一個點，即X0Y0 = XnYn，而所有的點必須照順時針或逆時針排序，當點為順時針排序時，總和為負數，逆時針排序時，總和為正數，但兩者絕對值相同。

TIPS
1. 製造測資時可考慮相離、相鄰、相交的情況，而相交的圖形可考慮「其中一圖有點在另一圖中」和「兩個圖形完全沒有點在另一個圖中，但有相交部份」的兩種情況。
2. 輸出時雖然每筆輸出之間不需換行，但最後結尾仍需要換行符號，否則會給WA，不是PE。

REFERENCES
平面內兩條線段的位置關係判定及交點求解

CODE

#include <iostream>
#include <vector>
using namespace std;

struct vertex{
  float x, y;
};

//return outer product of pa->pb
float cross(vertex p, vertex a, vertex b){
  return ( (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y) );
}

float dist(vertex a, vertex b){
  return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}

//return true if p is inside or on boundary of g
bool inside(vertex p, vector<vertex> g, int n){
  int i = n - 1;
  for(; i>=0 && (cross(g[i], g[(i+n-1)%n], p) >= 0); --i);
  return (i == -1);
}

bool intersects(vertex p1, vertex p2, vertex p3, vertex p4){
  return ((cross(p1, p2, p3) * cross(p1, p2, p4) < 0) && (cross(p3, p4, p1) * cross(p3, p4, p2) < 0));
}

vertex intersection(vertex p1, vertex p2, vertex p3, vertex p4){
  float b1 = (p2.y - p1.y)*p1.x + (p1.x - p2.x)*p1.y;
  float b2 = (p4.y - p3.y)*p3.x + (p3.x - p4.x)*p3.y;
  float d = (p2.x - p1.x)*(p4.y - p3.y) - (p4.x - p3.x)*(p2.y - p1.y);
  float d1 = b2*(p2.x - p1.x) - b1*(p4.x - p3.x);
  float d2 = b2*(p2.y - p1.y) - b1*(p4.y - p3.y);
  vertex p0;
  p0.x = d1/d;
  p0.y = d2/d;
  return p0;
}

void check_intersect(vertex p1, vertex p2, vector<vertex> g, int n, vector<vertex> &gc){
  for(int i=0; i<n; ++i){
    if( intersects(p1, p2, g[i], g[(i+1)%n]) ){
      vertex inter = intersection(p1, p2, g[i], g[(i+1)%n]);
      gc.push_back(inter);
    }
  }
}

//check if ga vertices are inside gb
void check_vertices(vector<vertex> ga, int na, vector<vertex> gb, int nb, vector<vertex> &gc, bool calc_inter){
  for(int i=0; i<na; ++i){
    if( inside(ga[i], gb, nb) )
      gc.push_back(ga[i]);
    if( calc_inter )
      check_intersect(ga[i], ga[(i+1)%na], gb, nb, gc);
  }//i
}

void sort_vertices(vector<vertex> &g, int n){
  if( n > 0 ){
    int i, j, m = 0;
    for(i=1; i<n; ++i)
      if(g[i].y < g[m].y || (g[i].y == g[m].y && g[i].x < g[m].y))
        m = i;
    swap(g[m], g[0]);
    for(i=1; i<n; ++i){
      m = i;
      for(j=i+1; j<n; ++j){
        float t = cross(g[0], g[m], g[j]);
        if( t < 0 || (t == 0 && dist(g[0], g[j]) < dist(g[0], g[m])) )
          m = j;
      }//j
      swap(g[m], g[i]);
    }//i
  }
}

float area(vector<vertex> g, int n){
  float a = 0;
  for(int i=0; i<n; ++i)
    a += (g[(i+n-1)%n].x * g[i].y) - (g[i].x * g[(i+n-1)%n].y);
  return (a < 0) ? ( a / -2 ) : (a / 2);
}

int main(){
  int na, nb, nc; //number of vertices of graph a, b, c
  while( scanf("%d", &na) && (na != 0) ){
    vector<vertex> ga, gb, gc;
    vertex temp;
    
    for(int i=0; i<na; ++i){
      scanf("%f%f", &temp.x, &temp.y);
      ga.push_back(temp);
    }
    scanf("%d", &nb);
    for(int i=0; i<nb; ++i){
      scanf("%f%f", &temp.x, &temp.y);
      gb.push_back(temp);
    }
    
    check_vertices(ga, na, gb, nb, gc, 1);
    check_vertices(gb, nb, ga, na, gc, 0);
    nc = gc.size();
    sort_vertices(gc, nc);

    printf("%8.2f", area(ga, na) + area(gb, nb) - (2 * area(gc, nc)));
  }//while
  printf("\n");
  return 0;
}

ACM: 132 - Bumpy Objects

Geometry的題目，給一個圖形的所有端點座標，和圖形的質心座標，要先找出可以讓圖形「站立」的邊，即當該邊水平時，質心在邊上方並在兩端點之間。一個圖形可能有大於一個可以站立的邊，邊的代號為該邊所經過最大編號(依輸入順序)的點，最後要輸出所有可以站立的邊中，最小的邊代號。

我的做法分為兩部分，第一部分是找convex hull，用graham scan，找出圖形的凸包。第二部分用內積檢查凸包的每個邊是否可以讓圖形站立，即質心到邊兩端點的夾角是否都小於90度(內積>0)。

TIPS

UVa討論區有大量本題測資

CODE

#include <iostream>
#include <vector>
using namespace std;

class vertex{
public:
  int x, y;
};

int n;
vertex mass;
vector<vertex> v; //original order
vector<int> p; //vertices id sorted by polar angle

//return outer product of pa->pb
int cross(vertex p, vertex a, vertex b){
  return ( (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y) );
}
//return true if pa dot pb > 0 (<90 degree)
bool dot(vertex p, vertex a, vertex b){
  return ( (a.x - p.x)*(b.x - p.x) + (a.y - p.y)*(b.y - p.y) ) > 0;
}

int dist(vertex a, vertex b){
  return ((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
}
//return true if a should be placed first than b to form counter-clockwise order
bool issmaller(vertex p, vertex a, vertex b){
  int f = cross(p, a, b);
  return ( f < 0 || ( f == 0  && dist(p, b) < dist(p, a) ) );
}

void quicksort(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    while(1){
      for(; (i<=right) && issmaller(v[p[0]], v[p[left]], v[p[i]]); ++i);
      for(; (j>left) && !issmaller(v[p[0]], v[p[left]], v[p[j]]); --j);
      if( i >= j )
        break;
      swap(p[i], p[j]);
    }
    swap(p[left], p[j]);
    quicksort(left, j-1);
    quicksort(j+1, right);
  }
}

int main(){
  string s;
  vertex temp;
  int i, j, tmp, minv, qn;
  
  while( (cin >> s) && (s[0] != '#') ){
    scanf("%d%d", &mass.x, &mass.y);
    v.clear();
    p.clear();
    i = 0;
    while( scanf("%d%d", &temp.x, &temp.y) ){
      if( temp.x == 0 && temp.y == 0 )
        break;
      v.push_back(temp);
      p.push_back(i++);
    }
    n = v.size();
    
    //find lowest-left
    for(minv=0, i=1; i<n; ++i)
      if( (v[i].y < v[minv].y) || (v[i].y == v[minv].y && v[i].x < v[minv].x) )
        minv = i;
    swap(p[minv], p[0]);
    //sort all vertices counter clockwisely by polar angle
    quicksort(1, n - 1);
    
    //graham scan
    vector<int> q; //stack of convex hull
    q.push_back(p[0]);
    q.push_back(p[1]);
    for(i=2; i<n; ++i){
      qn = q.size() - 1;
      if( (tmp = cross( v[ q[qn-1] ], v[ q[qn] ], v[ p[i] ] )) > 0 )
        q.push_back(p[i]);
      else if( tmp == 0 ){
        q.pop_back();
        q.push_back(p[i]);
      }
      else{
        q.pop_back();
        --i;
      }
    }//i:all vertices
    q.push_back(p[0]);
    
    //find stable sides
    qn = q.size();
    for(minv=n-1, i=1; i<qn; ++i){
      if( (cross(v[q[i-1]], mass, v[q[i]])!=0) && (dot(v[q[i-1]], mass, v[q[i]])>0) && (dot(v[q[i]], mass, v[q[i-1]])>0) )
        if( (tmp = (q[i] > q[i-1]) ? q[i] : (n - 1)) < minv )
          minv = tmp;
    }

    cout << s;
    for(i=s.size(); i<20; ++i)
      printf(" ");
    printf("%d\n", minv + 1);
  }//while
  return 0;
}

ACM: 131 - The Psychic Poker Player

給玩家五張撲克牌，桌上有另五張的撲克牌，玩家可選擇捨棄0~5張牌，並從桌上依序補充同數量的牌。輸出可以達到的最大牌型(poker hand)。

用了bool陣列去窮舉所有捨棄牌的方式，遞補相同數量的牌後，再一一檢查牌型。

CODE

#include <iostream>
#include <algorithm>
using namespace std;

enum { C, D, H, S };
enum { SF, FOAK, FH, FL, ST, TOAK, TP, OP, HC };
bool result[9]={0,0,0,0,0,0,0,0,0};
char line[9][16] = {"straight-flush", "four-of-a-kind", "full-house", 
"flush", "straight", "three-of-a-kind", "two-pairs", "one-pair", "highest-card"};

class poker{
public:
  int denom;
  int suit;
};

int next(bool *slot);
void check(poker *c);

int main(){
  int i, j, k;
  poker cards[2][5];
  char s[10][3];
  
  i = j = k = 0;
  while( scanf("%s", s[k]) != EOF ){
    if( s[k][0]>='2' && s[k][0]<='9' )
      cards[i][j].denom = s[k][0]-'0';
    else if( s[k][0] == 'A' )
      cards[i][j].denom = 1;
    else if( s[k][0] == 'T' )
      cards[i][j].denom = 10;
    else if( s[k][0] == 'J' )
      cards[i][j].denom = 11;
    else if( s[k][0] == 'Q' )
      cards[i][j].denom = 12;
    else if( s[k][0] == 'K' )
      cards[i][j].denom = 13;
    
    switch ( s[k][1] ){
      case 'C':
        cards[i][j].suit = C;
        break;
      case 'D':
        cards[i][j].suit = D;
        break;
      case 'H':
        cards[i][j].suit = H;
        break;
      case 'S':
        cards[i][j].suit = S;
        break;
    }//s[0]
    
    if( i==0 && j==4 ){
      i = 1;
      j = 0;
    }
    else if( i==1 && j==4 ){
      int count = 5;
      bool slot[5]={0, 0, 0, 0, 0};
      poker temp[5];
      while(1){
        j = 0;
        for(i=0; i<5; ++i){
          if( slot[i] )
            temp[i] = cards[1][j++];
          else
            temp[i] = cards[0][i];
        }
        check(temp);
        if( count == 0 )
          break;
        count = next(slot);
      }//search
      
      //output
      printf("Hand: ");
      for(i=0; i<5; ++i)
        printf("%s ", s[i]);
      printf("Deck: ");
      for(; i<10; ++i)
        printf("%s ", s[i]);
      printf("Best hand: ");
      for(i=0; i<9 && result[i]==0; ++i);
      printf("%s\n", line[i]);
      //initialize
      for(i=0; i<9; ++i)
        result[i] = 0;
      i = j = 0;
      k = -1;
    }
    else
      ++j;
    ++k;
  }//while get data
  
  return 0;
}

int next(bool *slot){
  if( slot[0] == 0 )
    slot[0] = 1;
  else{
    int i = 0;
    while( slot[i] == 1 )
      slot[i++] = 0;
    slot[i] = 1;
  }
  int count = 0;
  for(int i=0; i<5; ++i)
    if( slot[i] == 0 )
      ++count;
  return count;
}

void check(poker *c){
  int denoms[14]={0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  int suits[4]={0,0,0,0};
  
  //sort
  int i, j, min, maxsuit = 0;
  for(i=0; i<5; ++i){
    min = i;
    for(j=i+1; j<5; ++j)
      if( c[j].denom < c[min].denom )
        min = j;
    swap(c[i], c[min]);
    ++denoms[ c[i].denom ];
    if( ++suits[ c[i].suit ] > maxsuit )
      maxsuit = suits[ c[i].suit ];
  }
  
  //find if straight
  bool straight = 0;
  for(i=1; i<5 && (c[i].denom == c[i-1].denom + 1); ++i);
  if( i == 5 )
    straight = 1;
  if(!straight && (c[0].denom == 1)){
    for(i=2; i<5 && (c[i].denom == c[i-1].denom + 1); ++i);
    if( i == 5 )
      straight = 1;
  }
  if( straight ){
    if( maxsuit == 5 )
      result[SF] = 1; //straight flush
    else
      result[ST] = 1; //straight
  }
  if( maxsuit == 5 )
    result[FL] = 1; //flush
  
  int three = 0, two = 0;
  for(i=1; i<=13; ++i){
    switch ( denoms[i] ){
      case 4:
        result[FOAK] = 1; //four of a kind
        break;
      case 3:
        result[TOAK] = 1; //three of a kind
        ++three;
        break;
      case 2:
        ++two;
    }
  }//i
  
  if( three == 1 && two == 1 )
    result[FH] = 1; // full house
  else if( two == 2 )
    result[TP] = 1; //two pairs
  else if( two == 1 )
    result[OP] = 1; //one pair
  else
    result[HC] = 1; //highest card
}

Ubuntu!

裝了Wubi，直接從Windows像安裝應用程式一樣安裝了Ubuntu！不需要分割硬碟，也不需設定虛擬機器。裝的是Ubuntu 10.x，好漂亮，語言支援也很方便，雖然安裝的是英文版，但顯示中文完全沒問題，中文輸入也可以很方便的直接從System->Preference->iBus打開！

不過還要慢慢摸索linux，還是裝個Virtual Box同時用Windows跟Ubuntu吧。

Rails 3.0初體驗

終於成功嘗試Ruby on Rails了。安裝的是rails 3.0.0，一些以舊版rails為基礎的教學文件語法不同，後來找到了rails 3版本的教學文件"Getting Started with Rails"，終於step by step照著敲出了個最基礎的blog平台，有blog文章增刪修、comment增刪、tag，三項功能。

資料庫使用的是預設的SQLite，先照著查到的資料排除找不到"sqlite3.dll"的錯誤訊息。

ACM 30 題

不知不覺把121 - 130寫完了，這10題練習了C++的vector、string和其提供的函式。題目本身的話，印象最深的是DP的"125 – Numbering Paths"和學到運用餘數的"128 – Software CRC"。

ACM: 130 – Roman Roulette

simulation，但規則有點看不懂，看了中譯才搞清楚...

CODE

#include <iostream>
#include <vector>
using namespace std;

int n, k;
int kill(int i, vector<int> v);

int main(){
  int i, t;
  vector<int> r;
  
  while( (cin >> n >> k) && (n != 0) ){
    r.clear();
    for(i=1; i<=n; ++i)
      r.push_back(i);
    
    t = kill(0, r) - 1;
    t = (n - t) % n;
    cout << t + 1 << endl;
  }//while
  return 0;
}

int kill(int i, vector<int> v){
  int p;
  --i;
  while( v.size() > 1 ){
    i = p = (i+k) % v.size(); //p: killed
    v.erase(v.begin()+i);
    i = (i+k-1) % v.size(); //i: burier
    v.insert(v.begin()+p, v[i]);
    if( i >= p )
      ++i;
    v.erase(v.begin()+i);
    if( i >= p )
      i = p % v.size();
    else
      i = (p - 1) % v.size();
  }
  return v[0];
}

ACM: 129 – Krypton Factor

生成所有排序(permutations)，但要檢查生成的permutation是否有連續的重複組合，如有連續的重複組合即為無效的permutatoin，若否則為有效的permutation。如"ABAB"為無效，因連續出現"AB"組合，但"ABCAB"則為有效。輸出指定的第n個有效permutation。

CODE

#include <iostream>
using namespace std;

#define MAX 80
int n, let, seqn;
bool check(char *s, int len);
void gen(char *s, int len);
void output(char *s, int len);

int main(){
  char s[MAX];
  while( (cin >> n >> let) && (n != 0) ){
    seqn = 0;
    gen(s, 0);
  }//while
  return 0;
}

//return true if string is "hard", false when "easy"
bool check(char *s, int len){
  int i, j, k;
  for(i=0; i<len; ++i){
    for(j=0; j<i; ++j){
      for(k=j; k<i && s[k]==s[i+k-j]; ++k) ;//k
      if( k == i )
        return false;
    }//j
  }//i
  return true;
}

void gen(char *s, int len){
  for(int i=0; i<let && seqn<n; ++i){
    s[len] = 'A' + i;
    s[len+1] = '\0';
    if( check(s, len+1) ){
      if( ++seqn == n ){
        output(s, len+1);
        return;
      }
      if( seqn < n )
        gen(s, len+1);
    }
  }//i
}

void output(char *s, int len){
  for(int i=0; i<len; ++i){
    if( i == 64 )
      cout << endl;
    else if( i>0 && i%4==0 )
      cout << ' ';
    cout << s[i];
  }//i
  cout << endl << len << endl;
}

ACM: 127 - "Accordian" Patience

simulation。給52張撲克牌，向左一張或左三張合併同數字或同花色，輸出合併完成後剩下的堆數和每一堆的張數。每合併一次，要檢查是否可以繼續再向左合併。

CODE

#include <iostream>
using namespace std;

#define MAX 52

int main(){
  int i, j, k, moveto;
  char pile[MAX][MAX+MAX], remain[MAX];
  int len[MAX];
  
  while( (cin >> pile[0]) && (pile[0][0] != '#') ){
    len[0] = 2;
    for(i=1; i<MAX; i++){
      cin >> pile[i];
      len[i] = 2;
    }//i: read in all cards
    
    i=1;
    while( i < MAX ){
      moveto = i;
      for(j=i-1; j>=0 && len[j]==0; --j);//1 left
      if( (j >= 0) && (pile[j][ len[j]-2 ] == pile[i][ len[i]-2 ] || pile[j][ len[j]-1 ] == pile[i][ len[i]-1 ]) )
        moveto = j;
      for(--j; j>=0 && len[j]==0; --j);//2 left
      for(--j; j>=0 && len[j]==0; --j);//3 left
      if( (j >= 0) && (pile[j][ len[j]-2 ] == pile[i][ len[i]-2 ] || pile[j][ len[j]-1 ] == pile[i][ len[i]-1 ]) )
        moveto = j;
      if( i != moveto ){
        len[i] -= 2;
        pile[moveto][ len[moveto]++ ] = pile[i][ len[i] ];
        pile[moveto][ len[moveto]++ ] = pile[i][ len[i]+1 ];
        i = moveto;
      }
      else
        for(++i; i<MAX && len[i]==0; ++i);
    }
    
    k = 0;
    for(i=0; i<MAX; i++)
      if( len[i] > 0 )
        remain[k++] = i;
    cout << k << ( k == 1 ? " pile" : " piles" ) << " remaining:";
    for(i=0; i<k; i++)
      cout << ' ' << (len[ remain[i] ] / 2);
    cout << endl;
  }//while
  
  return 0;
}

ACM: 126 - The Errant Physicist

給多項式，輸出x降冪y升冪排序後的多項式相乘結果。重點在於字串處理，要找到方法把輸入字串拆解出可以運算的係數及次方數。

TIPS

記得移除(不要輸出)合併同類項後係數為0的項

CODE

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

class term{
public:
  int coef; //coefficient
  int pow_x;
  int pow_y;
};

vector<term> poly[2], result;

void get_terms(int no, string s);
void multiply(term a, term b);
void sort_terms(int left, int right);
void comb_terms(void);
bool isbigger(int a, int b);
string atostring(int num);

int main(){
  int i, j, n;
  string s, line1, line2;
  
  while( cin >> s ){
    if( s[0] == '#' )
      break;
    
    get_terms(0, s);
    cin >> s;
    get_terms(1, s);
    
    result.clear();
    for(i=0; i<poly[1].size(); i++)
      for(j=0; j<poly[0].size(); j++)
        multiply(poly[1][i], poly[0][j]);
    
    sort_terms(0, result.size()-1); //sort
    comb_terms(); //combine like terms
    
    line1.clear();
    line2.clear();
    for(i=0; i<result.size(); i++){
      //sign
      if( i > 0 ){
        line1.append("   ");
        if( result[i].coef > 0 )
          line2.append(" + ");
        else
          line2.append(" - ");
      }
      //coefficient
      if( result[i].coef < 0 ){
        result[i].coef *= -1;
        if( i==0 ){
          line1.push_back(' ');
          line2.push_back('-');
        }
      }
      if( result[i].coef > 1 ){
        s = atostring(result[i].coef);
        line2.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line1.push_back(' ');
      }
      else if( result[i].coef == 1 && result[i].pow_x == 0 && result[i].pow_y == 0 ){
        line1.push_back(' ');
        line2.push_back('1');
      }
      //power of x
      if( result[i].pow_x >= 1 ){
        line1.push_back(' ');
        line2.push_back('x');
      }
      if( result[i].pow_x > 1 ){
        s = atostring(result[i].pow_x);
        line1.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line2.push_back(' ');
      }
      //power of y
      if( result[i].pow_y >= 1 ){
        line1.push_back(' ');
        line2.push_back('y');
      }
      if( result[i].pow_y > 1 ){
        s = atostring(result[i].pow_y);
        line1.append(s);
        n = s.size();
        for(j=0; j<n; j++)
          line2.push_back(' ');
      }
    }//i
    cout << line1 << endl << line2 << endl;
  }//while
  
  return 0;
}

void get_terms(int no, string s){
  poly[no].clear(); //initialize polynomial vector
  
  term temp;
  string number;
  int sign = 1;
  int size = s.size();
  char flag = '+';
  
  for(int i=0; i<=size; i++){
    if( i==0 || i == size || s[i] == '+' || s[i] == '-' ){
      //if end of term
      if( i > 0 ){
        if( flag == '+' || flag == '-' )
          temp.coef = atoi(number.c_str()) * sign;
        else if( flag == 'x' ){
          if( s[i-1] == 'x' )
            temp.pow_x = 1;
          else
            temp.pow_x = atoi(number.c_str());
        }
        else if( flag == 'y' ){
          if( s[i-1] == 'y' )
            temp.pow_y = 1;
          else
            temp.pow_y = atoi(number.c_str());
        }
        poly[no].push_back(temp);
      }
      //initialize term
      temp.coef = temp.pow_x = temp.pow_y = 0;
      sign = 1;
      flag = '+';
      number.clear();
      //new term
      if( i < size && s[i] == '-' ){
        sign = -1;
        flag = '-';
      }
    }//term break point
    
    if( s[i] == 'x' || s[i] == 'y' ){
      if( i == 0 )
        temp.coef = sign;
      else if( flag == '+' || flag == '-' ){
        if( s[i-1] == flag )
          temp.coef = sign;
        else
          temp.coef = atoi(number.c_str()) * sign;
      }
      else if( flag == 'x' ){
        if( s[i-1] == 'x' )
          temp.pow_x = 1;
        else
          temp.pow_x = atoi(number.c_str());
      }
      else if( flag == 'y' ){
        if( s[i-1] == 'y' )
          temp.pow_y = 1;
        else
          temp.pow_y = atoi(number.c_str());
      }
      flag = s[i];
      number.clear();
    }
    else if( s[i] >= '0' && s[i] <= '9' )
      number.push_back(s[i]);
  }//i
}

void multiply(term a, term b){
  term temp;
  temp.coef = a.coef * b.coef;
  temp.pow_x = a.pow_x + b.pow_x;
  temp.pow_y = a.pow_y + b.pow_y;
  result.push_back(temp);
}

void sort_terms(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    while(1){
      for(; i<=right && !isbigger(i, left); i++);
      for(; j>left && isbigger(j, left); j--);
      if( i >= j )
        break;
      swap(result[i], result[j]);
    }//while
    swap(result[j], result[left]);
    sort_terms(left, j-1);
    sort_terms(j+1, right);
  }
}

//return true when a>b, false when a<=b
bool isbigger(int a, int b){
  if( result[a].pow_x < result[b].pow_x )
    return true;
  if( result[a].pow_x > result[b].pow_x )
    return false;
  if( result[a].pow_y > result[b].pow_y )
    return true;
  return false;
}

void comb_terms(void){
  int i = 0;
  while( i < result.size() ){
    if( result[i].coef == 0 )
      result.erase(result.begin()+i);
    else if( i < (result.size()-1) && (result[i].pow_x == result[i+1].pow_x) && (result[i].pow_y == result[i+1].pow_y) ){
      result[i].coef += result[i+1].coef;
      result.erase(result.begin()+i+1);
    }
    else
      i++;
  }
}

string atostring(int num){
  stringstream ss;
  ss << num;
  return ss.str();
}

ACM: 125 – Numbering Paths

這題頗有挑戰性，給有向圖(directed graph)，要找出圖上是否有環(cycle)，也要找出所有點之間存在的所有路徑數量，當路徑經過環(即代表路徑數量無窮大)，路徑數量要輸出-1。

我的作法是先以dp(Floyd-Warshall做變化)找出所有點之間存在的所有路徑數量，接著判斷是否有k->k (k = 1….n)路徑存在，若存在即為環存在，再跑一次迴圈將所有可與k相連的路徑的值設為-1。

在寫的時候原本Floyd-Warshall的觀念還是沒想清楚，在最外面多加了一層算「經過幾個點」的迴圈，寫出來超冗長且bug連連。後來改用recursive去產出所有組合，想當然Time Limit Exceed。苦思良久才領悟到不必多加那一層迴圈，也搞清楚找到環以後如何去刪掉所有受影響的節點了。柳暗花明，最後看到了清爽的程式碼 :))

不過仍然是跑了兩次三層迴圈，應該算O(2 * n^3)吧，一定可以更省，就繼續研究吧。

CODE

#include <iostream>
using namespace std;

#define MAX 30

int main(){
  int i, j, k;
  int maxn, side, d1, d2, total;
  int matrix[MAX][MAX]; //total number of paths
  
  total = 0;
  while( cin >> side ){
    for(i=0; i<MAX; i++)
      for(j=0; j<MAX; j++)
        matrix[i][j] = 0;
        
    maxn = -1;
    for(i=0; i<side; i++){
      cin >> d1 >> d2;
      matrix[d1][d2] = 1;
      if( d1 > maxn ) maxn = d1;
      if( d2 > maxn ) maxn = d2;
    }
    maxn++;
  
    //findout all paths
    for(k=0; k<maxn; k++)
      for(i=0; i<maxn; i++)
        for(j=0; j<maxn; j++)
          if( matrix[i][k] * matrix[k][j] > 0 )
            matrix[i][j] += matrix[i][k];
    
    //eliminate paths involved cycles
    for(k=0; k<maxn; k++)
      if( matrix[k][k] != 0 ) //cycle
        for(i=0; i<maxn; i++)
          for(j=0; j<maxn; j++)
            if( matrix[i][k] * matrix[k][j] != 0 )
              matrix[i][j] = -1;
    
    //output
    cout << "matrix for city " << total << endl;
    for(i=0; i<maxn; i++){
      cout << matrix[i][0];
      for(j=1; j<maxn; j++)
        cout << ' ' << matrix[i][j];
      cout << endl;
    }
    
    total++;
  }//while
  return 0;
}

ACM: 124 – Following Orders

真開心再用vector寫出了這題，嘗試用vector的push_back()及erase()產生所有的組合。在取出元素時檢查未被取出的元素是否有小於該元素的元素(小的元素應該先被取出)。

這題是給一些元素，再給其中部分元素的大小關係，依字典順序輸出在給定的大小關係下所有可能的元素組合。

CODE

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_LET 26

vector<char> vars; //variables
bool consts[MAX_LET][MAX_LET]; //constraints

void sort_vars(int left, int right);
void comb(vector<char> current, vector<char> pool);

int main(){
  int i, j;
  char c, d1, d2;
  bool flag = false;
  
  for(i=0; i<MAX_LET; i++)
    for(j=0; j<MAX_LET; j++)
      consts[i][j] = false;
  
  while( (c = getchar()) != EOF ){
    if( c >= 'a' && c <= 'z' ){
      vars.push_back(c);
    }//get variables
    else if( c == '\n' ){
      while( (d1 = getchar()) != '\n' ){
        if( d1 >= 'a' && d1 <= 'z' ){
          cin >> d2;
          consts[d2-'a'][d1-'a'] = true;
        }
      }//while get constraints
      
      if(flag == true)
        puts("");
      sort_vars(0, vars.size()-1); //sort variables
      vector<char> tmp;
      comb(tmp, vars); //produce combinations
      
      //initialize
      flag = true;
      vars.clear();
      for(i=0; i<MAX_LET; i++)
        for(j=0; j<MAX_LET; j++)
          consts[i][j] = false;
    }//get constraints
  }  
  
  return 0;
}

void sort_vars(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (vars[i] <= vars[left]); i++);
      for(; (j>left) && (vars[j] > vars[left]); j--);
      if( i>=j )
        break;
      swap(vars[i], vars[j]);
    }
    swap(vars[j], vars[left]);
    sort_vars(left, j-1);
    sort_vars(j+1, right);
  }
}

void comb(vector<char> current, vector<char> pool){
  vector<char>::size_type i, j;
  if( pool.empty() ){
    for(i=0; i!=current.size(); i++)
      cout << current[i];
    cout << endl;
    return;
  }
  
  vector<char> tmp_cur, tmp_pool;
  vector<char>::size_type psize = pool.size();
  for(i=0; i<psize; i++){
    for(j=0; j<psize; j++){
      if( consts[ pool[i]-'a' ][ pool[j]-'a' ] )
        break;
    }
    if( j == psize ){
      tmp_pool = pool;
      tmp_cur = current;
      tmp_cur.push_back(pool[i]);
      tmp_pool.erase(tmp_pool.begin()+i);
    
      comb(tmp_cur, tmp_pool);
    }
  }//i
  return;
}

ACM: 123 – Searching Quickly

這題是要在所給的一連串字串中，排除特定一些關鍵字，再將排除後剩餘的所有單字連同原字串順序輸出。

寫出來相當開心！第一次嘗試使用C++的class與string, vector等STL(Standard Template Library)，也使用了自訂class來做vector！string和vector乍看之下有點抽象，但實作起來還蠻方便有趣的，C++ Primer的作者在書中不斷警告使用者在C++要減少使用char*和array。

CODE

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class cls_kwords{
public:
  string keyword;
  int title_no;
  int position; //ending position of keyword in title
};

const int to_low = 'a' - 'A';
vector<string> words; //vector of words to ignore
vector<string> titles;
vector<cls_kwords> keywords;

void sort_words(int left, int right);
void sort_keywords(int left, int right);
bool isignore(string line);
bool isbigger(int a, int b);

int main(){
  string s;
  
  while( cin >> s ){
    if( s[0] == ':' ) break;
    words.push_back(s);
  }//words to ignore
  
  //sort words to ignore
  sort_words(0, words.size()-1);
  
  //get titles
  int total = 0;
  string key;
  string::size_type i, len;
  cls_kwords tmp;
  
  while( getline(cin, s) ){
    if( !s.empty() ){
      len = s.size();
      for(i=0; i<=len; i++){
        if( i == len || s[i] == ' ' ){
          if( !key.empty() ){
            if( !isignore(key) ){
              tmp.keyword = key;
              tmp.title_no = total;
              tmp.position = i;
              keywords.push_back(tmp);
            }
            key = "";
          }
        }
        else if( s[i] >= 'A' && s[i] <= 'Z' ){
          s[i] += to_low;
          key += s[i];
        }
        else if( s[i] >= 'a' && s[i] <= 'z' )
          key += s[i];
      }//i

      titles.push_back(s);
      total++;
    }
  }//while get titles
  
  int ksize, st, j;
  //sort keywords
  ksize = keywords.size();
  sort_keywords(0, ksize-1);
  
  //output
  for(int k=0; k!=ksize; k++){
    len = titles[ keywords[k].title_no ].size();
    st = keywords[k].position - keywords[k].keyword.size();
    for(j=0; j<st; j++)
      cout << titles[ keywords[k].title_no ][j];
    for(; j<keywords[k].position; j++)
      printf("%c", titles[ keywords[k].title_no ][j] - to_low);
    for(; j<len; j++)
      cout << titles[ keywords[k].title_no ][j];
    cout << endl;
  }
  
  return 0;
}

void sort_words(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (words[i]<=words[left]); i++);
      for(; (j>left) && (words[j]>words[left]); j--);
      if( i >= j )
        break;
      swap(words[i++], words[j--]);
    }//while
    swap(words[j], words[left]);
    sort_words(left, j-1);
    sort_words(j+1, right);
  }
}

bool isignore(string line){
  vector<string>::size_type i, max = words.size();

  for(i=0; i<max; i++){
    if( line < words[i] ) break;
    else if( line == words[i] ) return true;
  }

  return false;
}

void sort_keywords(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (!isbigger(i, left)) ; i++);
      for(; (j>left) && (isbigger(j, left)) ; j--);
      if( i >= j )
        break;
      swap(keywords[i++], keywords[j--]);
    }
    swap(keywords[j], keywords[left]);
    sort_keywords(left, j-1);
    sort_keywords(j+1, right);
  }
}

//return true when a>b, false when a<=b
bool isbigger(int a, int b){
  if( a == b ) return false;
  
  if( keywords[a].keyword > keywords[b].keyword ) return true;
  else if( keywords[a].keyword < keywords[b].keyword ) return false;
  
  if( keywords[a].title_no > keywords[b].title_no ) return true;
  else if( keywords[a].title_no < keywords[b].title_no ) return false;
  
  if( keywords[a].position > keywords[b].position ) return true;
  else if( keywords[a].position < keywords[b].position ) return false;
  
  return false;
}

ACM: 122 – Trees on the level

這題是用文字給出二元樹，檢查是否是完整的樹，如果是完整的樹即輸出廣度優先搜尋(BFS, Bread First Search)的結果。

我用的方法是用quicksort先對字串排序(eg, L, R, LL, LR, RL, RR,…)，接著檢查是否是完整的樹，最後再照字串順序輸出該node的數字。Runtime 0.008，程式碼也相當龐大，在這題來說顯然有更快更精簡的方法，也許可以考慮使用struct, C++的STL函式庫，也許會有更好的表現。

CODE

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define MAX_LEN 300
#define MAX_NODE 256

int total, num[MAX_NODE], len[MAX_NODE];
char line[MAX_NODE][MAX_NODE];
bool rep;

void sort_tree(int left, int right);
bool isbigger(int a, int b);
void swapnode(int a, int b);
bool valid_tree(void);

int main(){
  char c, snum[MAX_LEN], sline[MAX_LEN];
  int p, pnum, pline;
  int i;
  
  rep = false;
  total = 0;
  for(i=0; i<MAX_NODE; i++)
    num[i] = -1;
    
  while( (c = getchar()) != EOF ){
    if( c == '(' ){
      p = pnum = pline = 0;
    }
    else if( c == ')' ){
      if( p == 0 ){        
        sort_tree(0, total-1);
        
        if( valid_tree() ){
          cout << num[0];
          for(i=1; i<total; i++)
            cout << ' ' << num[i];
          cout << endl;
        }
        else
          cout << "not complete" << endl;
        //initialize
        rep = false;
        total = 0;
        for(i=0; i<MAX_NODE; i++)
          num[i] = -1;
      }//end of tree
      else{
        if( pnum > 0 ){
          snum[pnum] = '\0';
          sscanf(snum, "%d", &num[total]);
          
          for(i=0; i<pline; i++)
            line[total][i] = sline[i];
          line[total][pline] = '\0';
          len[total] = pline;
        }//if pnum > 0
        total++;
      }//end of node
    }
    else if( c == ',' ){
      p++;
    }
    else if( c >= '0' && c <= '9' ){
      snum[pnum++] = c;
      p++;
    }
    else if( c == 'L' || c == 'R' ){
      sline[pline++] = c;
      p++;
    }
    else ;
  }//while
  
  return 0;
}

void sort_tree(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(i; (isbigger(i, left)==false) && (i<=right); i++);
      for(j; (isbigger(j, left)==true) && (j>left); j--);
      if( i >= j )
        break;
      swapnode(i, j);
      i++;
      j--;
    }//while
    
    swapnode(left, j);
    sort_tree(left, j-1);
    sort_tree(j+1, right);
  }
}

//return true if a > b, return false if a <= b
bool isbigger(int a, int b){
  if( a == b )
    return false;
  if( len[a] > len[b] )
    return true;
  if( len[a] < len[b] )
    return false;
  
  for(int i=0; i<len[a]; i++){
    if( line[a][i] > line[b][i] )
      return true;
    else if( line[a][i] < line[b][i] )
      return false;
  }
  
  rep = true;
  return false;
}

void swapnode(int a, int b){
  swap(num[a], num[b]);
  swap(len[a], len[b]);
  
  char tmps[MAX_LEN];
  strcpy(tmps, line[a]);
  strcpy(line[a], line[b]);
  strcpy(line[b], tmps);
}

bool valid_tree(void){  
  if( (num[0] == -1) || (len[0] != 0) )
    return false;
  if( rep )
    return false;
  
  int i, j;
  bool flag;
  char tmps[MAX_LEN];
  for(i=1; len[i]<=1 && i<total; i++)
    if( num[i] == -1 )
      return false;
  for(i; i<total; i++){
    if( num[i] == -1 )
      return false;
      
    flag = false;
    for(j=0; j<(len[i]-1); j++)
      tmps[j] = line[i][j];
    tmps[j] = '\0';
    for(j=(i-1); (j>=0) && (len[j]>=(len[i]-1)); j--)
      if( strcmp(line[j], tmps) == 0 ){
        flag = true;
        break;
      }

    if( !flag )
      return false;
  }//i
  
  return true;
}

《約耳談軟體》

把線上版的《約耳談軟體》(Joel On Software)照著實體書出版目錄至少看過了一遍，是融合技術、經驗、娛樂、還有勵志性的好看的書！書內談許多軟體專案開發的實務技巧，強調寫規格、定時程、Daily Build的重要性，也談及專案管理及軟體商業策略等等。

雖然有些內容還無法完全了解，但似乎對軟體業多了一分認識，也從〈軟體人員面試教戰守則〉中，思考怎樣是業界所需要的人。而勵志的〈邊開火邊移動〉更鼓勵讀者不要擔心每天只前進一點點，重點是每天都前進一點點。除此之外，由於作者曾經在微軟工作過，許多寫到關於微軟的管理風格、策略的部分都看得很過癮啊！